🗺️ NavMesh AI Pathfinding - Intelligent Navigation System for FiveM

Automatic NavMesh generation and optimized A pathfinding for NPCs*

📋 Table of Contents

Description
Architecture
Features
Installation
Usage
Commands
Project Structure
Technologies
Configuration

📝 Description

NavMesh AI Pathfinding is an advanced 3D navigation system for FiveM/GTA V written in C#. It automatically generates a navigation mesh (NavMesh) to enable NPCs to move intelligently through the game world using the A* pathfinding algorithm.

The system uses a client-server architecture where:

The client generates the NavMesh via physics raycasts and handles visualization
The server performs all pathfinding calculations to ensure consistency and optimize performance

🏗️ Architecture

Overview

The project is divided into two main parts:

┌─────────────────────────────────────────────────────────────┐
│                         CLIENT                               │
│  (SetupZone.csproj - NavMesh Generation & Visualization)    │
│                                                              │
│  • NavMesh generation via physics raycasts                   │
│  • Manual node and connection editing                        │
│  • Real-time 3D visualization                                │
│  • QuadTree spatial indexing (O(log n) search)              │
│  • Batch saving system                                       │
└──────────────────────────────────┬───────────────────────────┘
                                   │
                    Events: navmesh:requestPath
                            navmesh:requestLoadZone
                            navmesh:saveZoneChunk
                                   │
┌──────────────────────────────────▼───────────────────────────┐
│                         SERVER                               │
│    (NavMeshServer.csproj - Pathfinding Calculations)        │
│                                                              │
│  • Lazy loading of NavMesh data                             │
│  • Optimized A* algorithm with heuristics                   │
│  • Wall avoidance via cost penalties                        │
│  • Smoothed waypoint generation                             │
│  • Spatial indexing for fast queries                        │
│  • Optimized priority queue management                      │
└─────────────────────────────────────────────────────────────┘

Modular Architecture

The system follows SOLID principles with dependency injection:

Client (SetupZone.csproj)

NavMeshManager: Main entry point, handles commands and events
Services:
- NavMeshGenerationService: Automatic NavMesh generation
- PhysicsService: Raycasts for ground detection
- VisualizationService: 3D rendering of nodes and connections
- ManualNodeEditingService: Manual node editing
- AsyncDataService: Thread-safe data management
Spatial:
- QuadTree<T>: Spatial index for O(log n) queries

Server (NavMeshServer.csproj)

ServerScript: Main server entry point
Services:
- AStarPathfindingService: A* implementation with lazy loading
- PathfindingRequestHandler: Client request management
- NavmeshDataService: Data loading/saving
- WaypointGenerationService: Smoothed waypoint generation
- WallProximityService: Wall proximity penalty calculation
- SpatialIndexService: Fast spatial search
Algorithms:
- AStarAlgorithm: A* algorithm with optimizations

✨ Features

🗺️ NavMesh Generation

Automatic Generation

Physics scanning: Uses raycasts to detect ground
Configurable grid: Spacing, dimensions and height configurable
Intelligent detection:
- Ignores inaccessible areas
- Automatically detects obstacles
- Handles height variations
Automatic connection:
- Connects to 8 direct neighbors (N, S, E, W, NE, NW, SE, SW)
- Line-of-sight validation to avoid connections through walls
- Automatic cleanup of isolated nodes

Manual Editing

Add nodes: Manual placement of individual nodes
Delete nodes: Remove specific nodes
Connection management:
- Manually add connections between nodes
- Delete connections
- Visual mode to select nodes

🎯 Server-Side Pathfinding

Optimized A* Algorithm

Advanced heuristic: Euclidean distance with directional bias
Wall avoidance:
- Cost penalties based on wall proximity
- Favors paths in center of navigable areas
- Uses connections to detect areas close to walls
Performance optimizations:
- Optimized priority queue (OptimizedPriorityQueue)
- Spatial indexing for O(log n) search
- Configurable iteration limit (default: 100,000)
- Configurable timeout (default: 5000ms)
- Periodic yield to avoid server blocking

Waypoint Generation

Path smoothing: Generates interpolated waypoints every 0.5 units
Trajectory optimization: Reduces point count while maintaining accuracy
Total distance calculation: Provides path length

🎨 3D Visualization

Real-Time Rendering

Nodes: Colored markers (green by default)
- Size: 0.2 units
- Configurable render distance
- Visibility cache for performance optimization
Connections: White lines between connected nodes
- Height: 0.8 units above node
- Alpha: 220 (semi-transparent)
Highlighting:
- Targeted node in red/yellow
- Intensity increased by 1.5x
Target marker: Displays pathfinding destination
Crosshair: Crosshair mode for precise editing

Rendering Optimizations

Distance culling: Only renders nearby nodes
Visibility cache: Avoids unnecessary recalculations
Batch updates: Thread-safe with AsyncDataService
Spatial QuadTree: O(log n) proximity queries

💾 Save System

Batch Saving

Intelligent chunking: Automatic division into 500-node packets

JSON format:

{
  "Id": 0,
  "Position": {"X": 100.0, "Y": 200.0, "Z": 30.0},
  "Connections": [1, 2, 3],
  "GridPosition": {"Item1": 0, "Item2": 0}
}

Timestamp: Files named navmesh_data_YYYYMMDDHHMMSS.json
Lazy loading: Server loads data only when needed
Custom converters:
- Vector3Converter: Vector3 serialization/deserialization
- TupleConverter: Grid position handling

🔧 Event Management

Client → Server Events

navmesh:requestPath: Request path calculation
- Parameters: startX, startY, startZ, endX, endY, endZ
- Returns: navmesh:pathResult with waypoints or error message
navmesh:requestLoadZone: Request NavMesh loading
navmesh:startBatchSave: Start batch save
navmesh:saveZoneChunk: Send data chunk
navmesh:endBatchSave: End save

Server → Client Events

navmesh:pathResult: Pathfinding result
- Success: Waypoint array [{x, y, z}, ...]
- Error: Error message
navmesh:loadZone: NavMesh data loaded
navmesh:loadError: Loading error

🚀 Installation

Prerequisites

FiveM Server: Recent version compatible with .NET Framework 4.5.2
.NET SDK: For compilation (or use pre-compiled DLLs)
Visual Studio Code or Visual Studio (optional, for development)

Installation Steps

1. Download

# Clone or download the project
git clone <repository_url> navmesh_scanner
cd navmesh_scanner

2. Compilation

Option A: Automatic compilation

# Compile both projects
dotnet build NavMeshServer.csproj
dotnet build SetupZone.csproj

DLLs will be generated in bin/Debug/net452/

Option B: Use pre-compiled DLLs

If you already have compiled DLLs, skip to step 3.

3. FiveM Server Configuration

Copy folder to your server:

resources/
└── navmesh_scanner/
    ├── fxmanifest.lua
    ├── bin/Debug/net452/
    │   ├── SetupZone.net.dll
    │   ├── NavMeshServer.net.dll
    │   └── *.dll (dependencies)
    └── save/ (will be created automatically)

Add to server.cfg:
```
ensure navmesh_scanner
```
Create save folder (optional, created automatically):
```
mkdir save
```

4. Start Server

# Start your FiveM server
./FXServer.exe +exec server.cfg

5. Verification

Connect to server and check console:

NavMesh Server Script loaded with modular architecture...

📖 Usage

Typical Workflow

1. Generate a NavMesh

Position yourself in the area to scan
Execute command:
```
/setupzone [width] [length] [height] [spacing]
```
Example:
```
/setupzone 50 50 1.0 1.0
```
- Width: 50 units
- Length: 50 units
- Height: 1.0 unit above player
- Spacing: 1.0 unit between nodes
Wait for generation: System scans area and creates nodes automatically
Visualize: Nodes appear in green with white connections

2. Manual Editing (optional)

Add/Remove Nodes

/editnodes

Aim at location with crosshair
E: Add node at aimed position
Delete: Remove nearest node
Escape: Exit edit mode

Modify Connections

/editconnections

Aim at first node and press E
Aim at second node and press E
Enter: Create connection
Delete: Remove connection
Escape: Cancel/Exit

3. Save

/savezone

Creates file in save/navmesh_data_YYYYMMDDHHMMSS.json
Uses batch saving for large NavMeshes

4. Load

/loadzone

Loads most recent NavMesh file
Data automatically loaded server-side on pathfinding request

5. Test Pathfinding

/testpath

Creates marker at your current position as destination
Server calculates path and returns waypoints
Path is visualized with debug markers

Usage in Your Scripts

Client-Side: Request a Path

// Request path from server
Vector3 start = Game.PlayerPed.Position;
Vector3 end = new Vector3(100f, 200f, 30f);

TriggerServerEvent("navmesh:requestPath", 
    start.X, start.Y, start.Z,
    end.X, end.Y, end.Z);

// Receive result
EventHandlers["navmesh:pathResult"] += new Action<object, string>((pathData, error) =>
{
    if (error != null)
    {
        Debug.WriteLine($"Pathfinding error: {error}");
        return;
    }
    
    // Convert waypoints
    var waypoints = ((IEnumerable<object>)pathData)
        .Cast<IDictionary<string, object>>()
        .Select(p => new Vector3(
            Convert.ToSingle(p["x"]),
            Convert.ToSingle(p["y"]),
            Convert.ToSingle(p["z"])
        ))
        .ToList();
    
    Debug.WriteLine($"Path received with {waypoints.Count} waypoints");
    
    // Use waypoints to move NPC
    // ...
});

🎮 Commands

Command	Parameters	Description
`/setupzone`	`[width] [length] [height] [spacing]`	Generates NavMesh around your position
`/clearzone`	-	Completely clears NavMesh from memory
`/editnodes`	-	Activates node editing mode
`/editconnections`	-	Activates connection editing mode
`/savezone`	-	Saves NavMesh to JSON file
`/loadzone`	-	Loads most recent NavMesh
`/clearmarkers`	-	Clears all debug markers
`/testpath`	-	Tests pathfinding to your position

Edit Mode Controls

Node Edit Mode (`/editnodes`)

E: Add node
Delete: Remove nearest node
Escape: Exit edit mode

Connection Edit Mode (`/editconnections`)

E: Select node
Enter: Create/Remove connection (after selecting 2 nodes)
Delete: Remove existing connection
Escape: Cancel selection/Exit

📁 Project Structure

navmesh_scanner/
│
├── fxmanifest.lua              # FiveM manifest
├── NavMeshServer.csproj        # Server project (pathfinding)
├── SetupZone.csproj            # Client project (generation/editing)
├── CLAUDE.md                   # Documentation for Claude AI
├── README.md                   # French documentation
├── README_EN.md                # This file (English)
│
├── Client/                     # Client code (.NET Framework 4.5.2)
│   ├── NavMeshManager.cs       # Main entry point
│   │
│   ├── Core/
│   │   ├── Interfaces/         # Service contracts
│   │   │   ├── IAsyncDataService.cs
│   │   │   ├── IManualNodeEditingService.cs
│   │   │   ├── INavMeshGenerationService.cs
│   │   │   ├── IPhysicsService.cs
│   │   │   ├── ISpatialIndex.cs
│   │   │   └── IVisualizationService.cs
│   │   │
│   │   └── Models/
│   │       └── RaycastResult.cs    # Raycast results
│   │
│   ├── Services/
│   │   ├── Data/
│   │   │   └── AsyncDataService.cs         # Thread-safe management
│   │   ├── Editing/
│   │   │   └── ManualNodeEditingService.cs # Manual editing
│   │   ├── Generation/
│   │   │   └── NavMeshGenerationService.cs # NavMesh generation
│   │   ├── Physics/
│   │   │   └── PhysicsService.cs           # Physics raycasts
│   │   └── Visualization/
│   │       └── VisualizationService.cs     # 3D rendering
│   │
│   └── Spatial/
│       └── QuadTree.cs         # O(log n) spatial index
│
├── Server/                     # Server code (.NET Framework 4.5.2)
│   ├── ServerScript.cs         # Main entry point
│   │
│   ├── Algorithms/
│   │   └── AStarAlgorithm.cs   # A* implementation
│   │
│   ├── Converters/             # Custom JSON converters
│   │   ├── TupleConverter.cs
│   │   └── Vector3Converter.cs
│   │
│   ├── Models/
│   │   ├── OptimizedPathfindingState.cs    # Optimized A* state
│   │   ├── OptimizedPriorityQueue.cs       # Priority queue
│   │   ├── PathfindingConfig.cs            # A* configuration
│   │   └── PathfindingState.cs             # Base state
│   │
│   └── Services/
│       ├── AStarPathfindingService.cs      # Main A* service
│       ├── IPathfindingService.cs          # Pathfinding interface
│       ├── NavmeshDataService.cs           # Loading/saving
│       ├── PathfindingRequestHandler.cs    # Request management
│       ├── SpatialIndexService.cs          # Server spatial index
│       ├── WallProximityService.cs         # Wall avoidance
│       └── WaypointGenerationService.cs    # Path smoothing
│
├── Share/                      # Shared client/server code
│   └── Models/
│       └── Node.cs             # NavMesh node model
│
├── save/                       # Saved NavMesh files
│   └── navmesh_data_*.json     # Format: navmesh_data_YYYYMMDDHHMMSS.json
│
└── bin/Debug/net452/           # Compiled DLLs (not tracked in git)
    ├── SetupZone.net.dll       # Compiled client
    ├── NavMeshServer.net.dll   # Compiled server
    └── *.dll                   # Dependencies (CitizenFX, Newtonsoft.Json)

🛠️ Technologies Used

Frameworks and Libraries

.NET Framework 4.5.2: Target for FiveM compatibility
CitizenFX.Core.Client 1.0.*: FiveM client API
CitizenFX.Core.Server 1.0.*: FiveM server API
Newtonsoft.Json 11.0.2: JSON serialization

Algorithms and Data Structures

Pathfinding

A (A-Star)*: Optimal pathfinding algorithm
- Heuristic: Euclidean distance with directional bias
- Cost penalties for wall avoidance
- Optimizations: early exit, spatial indexing, priority queue

Data Structures

QuadTree: 2D spatial index for O(log n) searches
- MAX_ITEMS_PER_NODE: 16
- MAX_DEPTH: 10
- Dynamic subdivision
OptimizedPriorityQueue: Priority queue for A*
- Binary heap based
- O(log n) operations
Dictionary<int, Node>: Fast O(1) node lookup by ID

NavMesh Generation

Physics raycasting: Ground and obstacle detection
Uniform grid: Node generation on regular grid
8-directional connection: Connection to 8 neighbors (cardinals + diagonals)
Line-of-sight validation: Visibility check between nodes

Design Patterns

Dependency Injection: Constructor-based dependency injection
Service Layer Pattern: Specialized services with interfaces
Repository Pattern: NavmeshDataService for persistence
Command Pattern: FiveM commands with handlers
Observer Pattern: FiveM events for client-server communication
Lazy Loading: On-demand NavMesh loading server-side

⚙️ Configuration

Pathfinding Configuration

Parameters defined in Server/Models/PathfindingConfig.cs:

public static class PathfindingConfig
{
    // Maximum A* iterations before abort
    public const int MAX_ITERATIONS = 100000;
    
    // Maximum processing time in milliseconds
    public const int MAX_PROCESSING_TIME_MS = 5000;
    
    // Yield every N iterations to avoid blocking
    public const int YIELD_EVERY_N_ITERATIONS = 1000;
    
    // Penalty factor for wall proximity (1.0 - 5.0)
    public const float WALL_AVOIDANCE_PENALTY_FACTOR = 2.0f;
    
    // Proximity threshold to consider a wall close
    public const float WALL_PROXIMITY_THRESHOLD = 2.0f;
}

Generation Configuration

Parameters in Client/Services/Generation/NavMeshGenerationService.cs:

// World size for QuadTree (10km)
private const float WORLD_SIZE = 10000f;

// Chunk size for batch saving
private const int CHUNK_SIZE = 500; // nodes per chunk

Visualization Configuration

Parameters in Client/Services/Visualization/VisualizationService.cs:

// Node render distance
private float displayDistance = 5.0f;

// Node marker size
private const float NODE_MARKER_SIZE = 0.2f;

// Connection height above ground
private const float CONNECTION_HEIGHT_OFFSET = 0.8f;

// Colors (RGBA)
private int nodeColorR = 0;      // Red
private int nodeColorG = 255;    // Green
private int nodeColorB = 0;      // Blue
private int nodeColorA = 200;    // Alpha

Performance Optimization

Client

QuadTree spatial indexing: Reduces complexity from O(n) to O(log n)
Visibility cache: Avoids render recalculations
Batch updates: AsyncDataService for thread safety
Distance culling: Renders only nearby nodes

Server

Lazy loading: NavMesh loaded on first request
Single lock: Only one pathfinding request at a time
Spatial index: Fast nearest node search
Early exit A*: Stops early if path found
Periodic yield: Avoids server blocking

🐛 Debugging

Client-Side Logs

Debug.WriteLine("Debug message");

Visible in FiveM F8 console

Server-Side Logs

CitizenFX.Core.Debug.WriteLine($"[PATHFINDING] Message");

Visible in FiveM server console

Debug Markers

Use navmesh:drawDebugMarker event to display temporary markers:

TriggerEvent("navmesh:drawDebugMarker", 
    x, y, z,           // Position
    255, 0, 0,         // RGB (red)
    5000,              // Duration in ms
    0.5f               // Size
);

Debug Commands

/clearmarkers    # Clear all debug markers
/testpath        # Test pathfinding to your position

📊 Performance

Typical Metrics

Generation:
- 50x50 grid (2500 nodes): ~30-60 seconds
- 1.0 unit spacing
Pathfinding:
- Short distance (<50 units): <50ms
- Medium distance (50-200 units): 50-200ms
- Long distance (>200 units): 200-1000ms
NavMesh Loading:
- 5000 nodes: ~100-300ms
- 10000 nodes: ~200-600ms

Recommended Optimizations

Optimal spacing: 1.0 - 2.0 units
- Smaller = more precise but slower
- Larger = faster but less precise
Reasonable zones:
- Small zone: 25x25 (625 nodes)
- Medium zone: 50x50 (2500 nodes)
- Large zone: 100x100 (10000 nodes)
Divide large zones:
- Create multiple small NavMeshes instead of one huge one
- Load only necessary zones

🤝 Contributing

Development

# Clone project
git clone <repository_url>

# Compile
dotnet build NavMeshServer.csproj
dotnet build SetupZone.csproj

# Test
# Copy to your FiveM server and launch

Recommended Branch Structure

main: Stable version
develop: Active development
feature/*: New features
bugfix/*: Bug fixes

📄 License

This project is provided "as is" without warranty. Use freely for your FiveM projects.

🙏 Acknowledgments

CitizenFX: FiveM framework
Newtonsoft.Json: JSON serialization
FiveM community for resources and support

📞 Support

For questions or issues:

Check server and client logs
Consult the Debugging section
Verify DLL files are present in bin/Debug/net452/
Ensure save/ folder exists and is writable

Last Updated: October 2025
Version: 1.0.0
Compatibility: FiveM (.NET Framework 4.5.2)

Name		Name	Last commit message	Last commit date
Latest commit History 1 Commit
Client		Client
Server		Server
Share/Models		Share/Models
NavMeshServer.csproj		NavMeshServer.csproj
README.md		README.md
README_FR.md		README_FR.md
SetupZone.csproj		SetupZone.csproj
fxmanifest.lua		fxmanifest.lua

skyline624/NavMesh-AI-Pathfinding

Folders and files

Latest commit

History

Repository files navigation