2D Navmesh generation and pathfinding in Javascript
This post covers generation of two-dimensional navmeshes and path finding in it in Javascript with minimal dependencies.
1. Navmesh generation
What is a Navmesh?
Navmesh is a data structure primarily used for pathfinding purposes. Whereas traditional grid-based graph works perfectly well for path finding in tiled games, navmeshes make path finding efficient for arbitrary map layouts as well. This is achieved by using the underlying map geometry as the building block.
Generating a navmesh
Setup
Our starting point is a rectangular map with two objects blocking movement.
const mapBounds = { left: 10, top: 10, right: 450, bottom: 450,};const objectBounds = [ { left: 50, top: 50, right: 220, bottom: 120, }, { left: 300, top: 90, right: 380, bottom: 390, },];
Walkable area into a mesh
Next up is the actual mesh generation. There are two options for the vertices we will have in the navmesh: triangles and polygons. Both options have pros and cons, but here we will go with triangles since using triangles results in simpler math operations for our purposes.
This is where we benefit from libraries. I’ve chosen to use earcut.
![Map with a triangulated navmesh](/_app/immutable/assets/navmesh_triangulated.B6D74fTM.png)
// Convert map and object bounds into polygons and concatenate into the same arrayconst boundariesVerts = rectPoly(mapBounds);const objectVerts = objectBounds.flatMap((b) => rectPoly(b));const mapVerts = [...boundariesVerts, ...objectVerts];// Generate indices for object vertices (ie. the polygons that will be cut as holes)const holeIndices = new Array(objectBounds.length) .fill() .map((_, i) => (i + 1) * 4);// Triangulate the polygonconst indices = earcut(mapVerts, holeIndices);// End result is triangle indices pointing to our vertex data array// Convert the indices (ie. [i]) back to vertices (ie. [x, y])const vertices = indices.flatMap((index) => [ mapVerts[index * 2], mapVerts[index * 2 + 1],]);
Improve mesh quality
There’s still more to do. While the generated navmesh is already usable, traversing the mesh vertices would cause the actor to travel too close to the object boundaries when walking past them.
Easy way to make the meshes more natural is to add artificial margin to all our boundaries.
![Navmesh with margin added](/_app/immutable/assets/navmesh_withmargin.DO_yi-lx.png)
const boundariesVerts = rectPoly( withMargin(mapBounds, -20));const objectVerts = objectBounds.flatMap((b) => rectPoly(withMargin(b, 10)));
While margin seems like it has shrunk our walkable area in this example, it will result in more natural looking paths in the end.
2. Navmesh path-finding
We’re starting from a previously generated navmesh. Also on the map are marked our path’s starting and goal positions.
![Navmesh and start/goal positions](/_app/immutable/assets/navmesh_startgoal.BRsiAHeg.png)
Our goal is to find the smoothest path to travel from the orange dot to the blue one.
Edgefinding
We’re dealing with a set of triangles, so the first step of path finding can be summed up as finding the triangles to traverse. The “triangle-path-finding” consists of these steps:
- Find the triangle containing the start point and the triangle containing the end point
- Build a graph with individual triangles as nodes and triangles sharing sides as edges
- Use a standard path finding algorithm, such as Dijkstra’s, to find the sequence of triangles to traverse from the start point’s triangle to the end point’s triangle
- Since an edge in the graph represents a navmesh triangle’s edge, we can compose a path of navmesh edges from a sequence of graph edges
Step 1: find the triangles that contain start point and end point
function findTriangleContaining( indices: number[], vertices: number[], point: Point) { let i = 0; for (const triangle of triangles(indices, vertices)) { if (triangleContainsPoint(triangle, point)) { return i; } i++; }}const startTriangle = findTriangleContaining( indices, mapVerts, startPos);const endTriangle = findTriangleContaining( indices, mapVerts, endPos);
Step 2: graph building
The core of turning our navmesh into a graph is finding neighbours for each navmesh triangle. Since our triangulation method provided us with a list of indices, finding neighbours is as easy as finding the other triangles that share at least two vertices with the current triangle.
type Node = { id: number; neighbours: Node[] };const graph: Node[] = [];const tIndices = [...triangleIndices(indices)];// First step: add all trianglesfor (let i = 0; i < tIndices.length; ++i) { graph.push({ id: i, neighbours: [] });}// Second step: find neighboursfor (const [triangle, indices0] of tIndices.entries()) { const neighbours = [...tIndices.entries()] .filter(([nTriangle, indices1]) => { return ( nTriangle !== triangle && doTrianglesShareEdge(indices0, indices1) ); }) .map(([nTriangle]) => graph[nTriangle]); graph[triangle].neighbours = neighbours;}
We can test it out by drawing the neighbours for both the start and the end point’s triangles.
![Navmesh with start and end neighbours highlighted](/_app/immutable/assets/navmesh_startgoal_neighbours.DZxNCkyp.png)
const startAndEndNeighbourIndices = [ ...graph[startTriangle].neighbours, ...graph[endTriangle].neighbours,].flatMap(({ id }) => { return [ indices[id * 3 + 0], indices[id * 3 + 1], indices[id * 3 + 2], ];});drawTriangles(startAndEndNeighbourIndices, mapVerts);
Step 3: finding the path of edges
Only thing that remains is finding the path. For sake of simplicity we’ll just use a package for A-star. If you’re interested in learning more about path finding in-depth, Amit’s A* Pages is an excellent resource.
function triangleMidPoint(triangleIndex) { const tIndices = [ indices[triangleIndex * 3 + 0], indices[triangleIndex * 3 + 1], indices[triangleIndex * 3 + 2], ]; const x = tIndices.reduce( (prev, cur) => prev + mapVerts[cur * 2 + 0], 0 ) / 3; const y = tIndices.reduce( (prev, cur) => prev + mapVerts[cur * 2 + 1], 0 ) / 3; return [x, y];}const { path } = astar({ start: startTriangle, isEnd: (n) => n === endTriangle, neighbor: (n) => graph[n].neighbours.map((n) => n.id), distance: (a, b) => { const [ax, ay] = triangleMidPoint(graph[a].id); const [bx, by] = triangleMidPoint(graph[b].id); const [dx, dy] = [ax - bx, ay - by]; return Math.sqrt(dx * dx + dy * dy); }, heuristic: (n) => { // Euclidean distance const [nx, ny] = triangleMidPoint(graph[n].id); const dx = nx - endPos[0]; const dy = ny - endPos[1]; return Math.sqrt(dx * dx + dy * dy); },});
The end result we get is the triangles forming the shortest path from the start to the end triangle, here highlighted in green.
![Navmesh with triangle path highlighted](/_app/immutable/assets/navmesh_startgoal_triangles.BJBwh_rh.png)
We’re already getting somewhere, but our “path” is still too coarse. Rather than knowing the triangles we need to walk through, we should find the triangle edges we should pass through. We already almost have this information stored in our path
array; we just need to map a pair of triangles [fromTriangle, toTriangle]
into the edge in between.
function* pathToEdges(path, graph) { for (let i = 1; i < path.length; ++i) { const fromTriangle = graph[path[i - 1]].id; const toTriangle = graph[path[i]].id; const tri0 = [ indices[fromTriangle * 3 + 0], indices[fromTriangle * 3 + 1], indices[fromTriangle * 3 + 2], ]; const tri1 = [ indices[toTriangle * 3 + 0], indices[toTriangle * 3 + 1], indices[toTriangle * 3 + 2], ]; // Find vertices in both triangles. MUST have length of 2 const sharedVertices = tri0.filter((i) => tri1.includes(i) ); const vert0 = [ mapVerts[sharedVertices[0] * 2 + 0], mapVerts[sharedVertices[0] * 2 + 1], ]; const vert1 = [ mapVerts[sharedVertices[1] * 2 + 0], mapVerts[sharedVertices[1] * 2 + 1], ]; yield [vert0, vert1]; }}const pathVertices = [...pathToEdges(path, graph)];
![Navmesh with path edges marked](/_app/immutable/assets/navmesh_startgoal_edges.CDX2pz9I.png)
Edges into path
We know the edges, but we want a path. Let’s start experimenting with a simple idea. Now we know what edges the actor will have to pass through to traverse our chosen path, so what if we just link the middlepoints of each edge together?
![Naive middle point based path](/_app/immutable/assets/navmesh_startgoal_naivepath.BZpv58Z-.png)
The path does not look clean or fast, but importantly it is still a correct path. We just found our first walkable path!
This also leads us to another realization: since we chose to use triangles for our polygon tessellation and triangles are by definition convex, we can freely move our path nodes to any part of their respective edge while still having a valid path.
![Navmesh path with different weights](/_app/immutable/assets/navmesh_weights.C98vboas.gif)
Let’s use this to our advantage with some heuristical shifting around.
Path optimization
Let’s simplify the problem:
We have an array W
, containing weights for each edge. Weight here essentially means how far is the vertex from the first vertex of the edge.
We have a function length(W)
, which gives us the length of the whole path for given weights.
Our goal is to find the W
for which the return value of length(W)
is the lowest, or in mathy terms argmin length(W)
.
Our options are
- Brute force
- Gradient descent
Brute forcing it
For simplicity, we will go with the “screw math, CPU power is cheap” option here. We’ll brute force 1000 random weights and choose the one giving us the shortest path.
let [shortestWeights, shortestDist] = [null, Infinity];for (let i = 0;i < 1000; ++i) { const weights = pathVertices.map(() => Math.random()); const length = lengthWithWeights(pathVertices, weights); if (length < shortestDist) { [shortestWeights, shortestDist] = [weights, length]; }}const pathPoints = pathWithWeights( pathVertices, shortestWeights);
This is a reasonable option for many cases since it’s quite obvious what’s happening and relatively inexpensive operation. For more complex path finding cases, more thought might be applicable.
The results can be reasonably good as well:
![Navmesh path bruteforced](/_app/immutable/assets/navmesh_startgoal_bruteforce.CNTlZWW0.png)
Appendix: utility functions used for navmesh generation
// Generate an array of [x, y] vertices forming a polygon from the given rectanglefunction rectPoly({ left, top, right, bottom }) { return [ left, top, right, top, right, bottom, left, bottom, ];}// Return rectangle with added marginfunction withMargin({ left, top, right, bottom }, amount) { return { left: left - amount, top: top - amount, right: right + amount, bottom: bottom + amount, };}// Draw given list of triangle vertices to a canvasfunction drawTriangles(tris: number[]) { ctx.beginPath(); for (let i = 0; i < tris.length; i += 2) { const [x, y] = [tris[i], tris[i + 1]]; if (i % 3 == 0) { if (i !== 0) { ctx.closePath(); ctx.stroke(); } ctx.moveTo(x, y); } else { ctx.lineTo(x, y); } } ctx.closePath(); ctx.stroke();}
Appendix: utility functions used for pathfinding
Functions here have TypeScript types for understandability.
type Point = [number, number];type Triangle = [Point, Point, Point];function* triangleIndices(indices: number[]) { for (let i = 0; i < indices.length; i += 3) { yield [indices[i], indices[i + 1], indices[i + 2]] as [ number, number, number ]; }}function doTrianglesShareEdge( indices0: [number, number, number], indices1: [number, number, number]) { // If triangles A and B share two indices, they share an edge let shared = 0; for (const i of indices0) { if (indices1.includes(i) && ++shared === 2) { return true; } } return false;}function* triangles(indices: number[], vertices: number[]) { for (const [i0, i1, i2] of triangleIndices(indices)) { const p0: Point = [ vertices[i0 * 2], vertices[i0 * 2 + 1], ]; const p1: Point = [ vertices[i1 * 2], vertices[i1 * 2 + 1], ]; const p2: Point = [ vertices[i2 * 2], vertices[i2 * 2 + 1], ]; yield [p0, p1, p2] as Triangle; }}// https://blackpawn.com/texts/pointinpoly/default.html// https://github.com/mattdesl/point-in-trianglefunction triangleContainsPoint( triangle: Triangle, testing: Point) { //compute vectors & dot products const cx = testing[0], cy = testing[1], t0 = triangle[0], t1 = triangle[1], t2 = triangle[2], v0x = t2[0] - t0[0], v0y = t2[1] - t0[1], v1x = t1[0] - t0[0], v1y = t1[1] - t0[1], v2x = cx - t0[0], v2y = cy - t0[1], dot00 = v0x * v0x + v0y * v0y, dot01 = v0x * v1x + v0y * v1y, dot02 = v0x * v2x + v0y * v2y, dot11 = v1x * v1x + v1y * v1y, dot12 = v1x * v2x + v1y * v2y; // Compute barycentric coordinates const b = dot00 * dot11 - dot01 * dot01, inv = b === 0 ? 0 : 1 / b, u = (dot11 * dot02 - dot01 * dot12) * inv, v = (dot00 * dot12 - dot01 * dot02) * inv; return u >= 0 && v >= 0 && u + v < 1;}function pathWithWeights(pathVertices, weights) { return pathVertices.map(([v0, v1], i) => { const w = weights[i]; return [v0[0] + (v1[0] - v0[0]) * w, v0[1] + (v1[1] - v0[1]) * w]; });}function dist(a, b) { const [dx, dy] = [a[0] - b[0], a[1] - b[1]]; return Math.sqrt(dx * dx + dy * dy);}function lengthWithWeights(pathVertices, weights) { const withWeights = pathWithWeights(pathVertices, weights); const startToFirstDistance = dist(startPos, withWeights[0]); const lastToEndDistance = dist(withWeights[withWeights.length - 1], endPos); return withWeights.reduce( ([prev, pathDist], cur) => { if (prev) { pathDist += dist(cur, prev); } return [cur, pathDist]; }, [null, startToFirstDistance + lastToEndDistance] )[1];}