Building a Custom NavMesh and A* Pathfinding in Babylon.js

Background

In a 3D sandbox game a character moves on a flat plane while buildings can be placed and edited. A naïve straight‑line movement works only on an empty plane; when buildings are present the character clips through them.

Attempted Built‑in Obstacle Avoidance (Babylon.js + RecastJS)

Babylon.js provides an extension that uses RecastJS to generate a navigation mesh (NavMesh) and a crowd‑agents module for automatic pathfinding. The NavMesh consists of convex polygons (Polys). In practice the generated NavMesh was incomplete for larger obstacles, so the avoidance only succeeded for very small objects and the character still passed through bigger buildings.

Custom Navigation Mesh and Pathfinding

Because the built‑in solution was unusable, a custom NavMesh and search algorithm were implemented.

Overall workflow:

Generate a suitable NavMesh from the map data.

Obtain the character’s start and end positions.

Run a search algorithm on the NavMesh to find the shortest path.

Move the character along the computed path.

Search Algorithm Choice

Two classic algorithms were evaluated: Breadth‑First Search (BFS) and the heuristic A* algorithm.

Breadth‑First Search

BFS expands from the start cell to the four orthogonal neighbours (up, down, left, right), marking visited cells and storing back‑pointers to reconstruct the path. It guarantees a shortest path on a uniform grid but may need to explore the entire map, which is inefficient for large scenes.

A* Algorithm

A* improves performance by adding a heuristic cost. Each node has a current cost (f‑cost) – the number of steps taken so far – and an estimated cost (g‑cost) – a heuristic estimate of the remaining distance to the goal. The total cost is f‑cost + g‑cost. The node with the lowest total cost is expanded next.

Common heuristics:

Euclidean distance : Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) Manhattan distance : Math.abs(x1-x2)+Math.abs(y1-y2) (faster to compute)

Custom NavMesh Construction

RecastJS builds a NavMesh in six steps. For the simple 64×64 sandbox map (axis‑aligned cube buildings) the process was simplified:

Voxelization : Convert triangle meshes to a voxel grid.

Walkable Surface Extraction : Identify voxels that represent walkable ground.

Region Generation : Group walkable voxels into large, hole‑free regions.

Simplified Contours : Approximate region boundaries with simplified polygons.

Poly Mesh Creation : Subdivide contours into convex Polys.

Detailed Mesh Generation : Triangulate each Poly to produce the final NavMesh.

Because the map is a regular grid, the implementation treats the grid vertices as raw NavMesh data, then discards any vertex whose projection intersects a building footprint. The remaining vertices form a non‑overlapping mesh suitable for pathfinding.

Integrating A* with the Custom NavMesh

In 3D the NavMesh consists of triangles rather than squares. The algorithm proceeds as follows:

Filter out vertices that intersect building footprints.

For each remaining triangle compute its centroid, list of neighbouring triangles (neighbours), and shared edges (portals).

Locate the triangles that contain the start and end positions.

Run A* on the triangle graph using f‑cost + Euclidean(centroidA, centroidB) as the total cost to find the shortest sequence of triangles.

Move the character along the resulting sequence of centroids.

Path Smoothing

The raw path often contains many intermediate waypoints, producing a jagged movement. A string‑pulling (funnel) algorithm was applied to remove points that lie on a straight line, yielding a smoother trajectory.

Further Optimizations

Convert the dense grid into a set of waypoints to reduce node count.

Use an octree to partition 3D space, accelerating neighbour searches.

Future Work

Current implementation still generates many nodes for large maps. Planned improvements include simplifying the NavMesh into waypoints and integrating octree‑based queries to improve performance.

References

Rope (string‑pulling) algorithm: https://zhuanlan.zhihu.com/p/359393767

NavMesh principles: https://zhuanlan.zhihu.com/p/359376662

Game navigation basics: https://www.jianshu.com/p/490a9128b248

A* algorithm details: https://developer.huaweicloud.com/hero/thread-86168-1-1.html