Constructing a Navigation Mesh in Node.js

A Navigation Mesh or “navmesh” is a data structure used for route planning within virtual environments, and is particularly useful in game development. It consists of a collection of convex polygons representing areas of the map; the edges of the polygons are annotated with additional connectivity information, showing which areas are traversable by game characters.

As you can see in the following illustration, the navigation mesh provides a simplified representation of the obstacles in the world, allowing a route planning algorithm to quickly and efficiently compute an optimal path.

I’m not going to talk too much about the theory behind navigation meshes in this essay, there are a number of good resources on the web; the Wikipedia entry is a good starting point. Instead, I am going to focus on techniques for constructing the navigation mesh.

I’m also not going to talk about updating the mesh at runtime to accommodate dynamic obstacles, although that may be the subject of another article in the future.

The mesh I will be working with is a “2+1/2 D” mesh, meaning that it’s a collection of flat two-dimensional meshes connected by ramps:

This also supports navigation meshes that follow the contours of a terrain height field:

For this project, I elected to use classic polygonal navigation meshes instead of the more advanced Explicit Corridor Maps. Although ECMs have a number of advantages, I wanted to embed additional landscape attributes, such as travel cost (roads and trails have a lower travel cost than grass or snow, and thus are preferred by characters when planning routes) into the mesh. Unfortunately, the ECM approach divides the world strictly into “obstacles” and “non-obstacles”, with no provision for “semi-obstacles”. Doing this with polygonal regions, on the other hand, is relatively straightforward.

The process of constructing the mesh mainly consists of boolean operations on polygons. Fortunately there are a number of excellent open-source libraries for doing these kinds of operations.

Libraries Used

The builder uses a number of open-source libraries from npm, but there are three packages in particular that are critical to making this work:

• polygon-clipping is a library for doing efficient boolean operations on polygons — union, intersection, difference, and so on.
• rbush is an implementation of R-Trees, making it possible to quickly search for objects within a 2D space.
• poly-partition is an algorithm for breaking up a complex polygon into smaller polygons which are convex. Note that I had to fork this library to make a slight tweak to the algorithm (there was an edge case that the original library did not handle, see this GitHub issue for details).

Next we need to talk about how the data structures are organized.

Data Structures

The navigation mesh is represented by a TypeScript class named, obviously enough, NavigationMesh. This holds the representation of the navigation mesh at runtime and is used by the route planner.

The code for constructing the mesh is in another class named NavigationMeshBuilder. This class walks through all of the objects in the game world — terrain, walkable surfaces, obstacles, and so on — and updates the mesh geometry. Note that NavigationMeshBuilder can run in Node.js as well as in the browser, which is important for offline computation of navigation meshes.

A NavigationMesh is essentially a collection of NavRegions, organized in an R-Tree. Each NavRegion represents a polygonal area within the mesh.

The region itself consists of a linked-list of edges, representing the edges of the polygon. Following the standard terminology used in computational geometry, these are called HalfEdges, because they store a single vertex, along with a pointer to the next HalfEdge.

export interface HalfEdge {
  next: HalfEdge;
  region: NavRegion;
  origin: NavVertex;
  connections: HalfEdge[];
}
export interface NavRegion extends BBox {
  surface?: SurfaceType;
  edges: HalfEdge; // Pointer to first edge in the list
  plane: Plane;
}

The reason for using a linked list is that this allows us to easily iterate around the edges of the polygon starting at any edge. This is important during route planning since a region can be entered from any direction.

The half edge contains a list of “connections” which is a list of edges belonging to adjacent regions that are touching this edge.

The HalfEdge contains a pointer to a NavVertex, which is a three.js Vector3 with some additional fields, including a list of all HalfEdges that use that vertex. Note that vertices are shared objects— that is, two different regions that have a vertex at the same location will point to the same NavVertex.

The NavRegion itself has pointer to the linked list of edges, along with a surface type (which is used by the route planner) and a three.js Plane object. The Plane object represents the planar surface of the polygon, and is used to quickly test whether a point is above or below the NavRegion surface.

You may notice that the NavRegion type extends BBox, which is a 2D bounding box. The BBox type comes from the RBush package, and is required for objects being inserted into the R-Tree.

The NavigationMeshBuilder also uses regions during construction, but the data layout is slightly different. The main reason for this is that the open-source libraries for operating on polygons are designed to work with 2D coordinates, not 3D, and it’s a pain to constantly have to convert back and forth between the two formats. For this reason, the BuilderRegion consists of a 2D polygon along with a Plane object. Converting the 2D coordinates into 3D is done by simply projecting the points vertically onto the plane.

interface BuilderRegion extends BBox {
  surface?: SurfaceType;
  vertices: Pair[];
  holes?: Pair[][];
  minHeight: number;
  maxHeight: number;
  plane: Plane;
}

Pair is defined by the polygon-clipping library and consists of a 2-tuple of the form [number, number]. You may notice that this structure also has a holes field. The reason for this is that, during construction, the polygons being generated will be complex shapes that may be concave or convex, and may contain holes. It is only during the later stages of construction that the regions are split into concave polygons with no holes.

Construction Steps

The steps for constructing the mesh are as follows:

1. Add all walkable surfaces from the game world to the mesh as polygons.
2. Subtract all obstacles from the mesh.
3. Merge together adjacent regions that are in the same plane and have the same surface type.
4. Split regions into convex polygons.
5. Compute connections between regions.
6. Clean up any unused vertices.
7. Serialize and write to output.

Step 1: Adding Walkable Surfaces

What exactly constitutes a walkable surface will depend on your game. In my case, this is based on the physics collider objects — any solid top surface that has an angle less than 45 degrees.

During construction, regions are stored in the builder’s RBush. The process of updating the mesh consists of doing the following step for each polygonal surface:

1. Compute the 2D vertices of the polygon to be added.
2. Calculate the 2D bounding box of those vertices.
3. Compute the plane of the new region, which can be done given any three vertices of the walkable surface that are not co-linear.
4. Call rbush.search(box) to find any regions that overlap with the new polygon.
5. For each overlapping region found:
   - If the existing region is in a different plane, then don’t modify it, just skip over it.
   - If the existing region has the same surface type, then remove it from the RBush and make the new region the union of the two regions.
   - If the existing region has a different surface type, then subtract the new region from the old, clipping it away. If this causes a change in the bounding box, then remove the old region from the RBush and re-add it with the new bounds.
6. Now, add the new polygon to the RBush as a region.

Step 2: Subtract all obstacles from the mesh.

This step is similar to the previous one, however there are several important differences:

• We are subtracting (cutting holes) in the mesh rather than adding new regions.
• The obstacles are “inflated” by a margin to account for the fact that the character has a non-zero radius. This is also known as a “Minskowski sum”.
• The height of the obstacle needs to be taken into account, as well as the height of the character. The obstacle will be subtracted from any region where movement along that region would be blocked by the obstacle.

Note that for this type of navigation mesh, the radius and height of the character are “baked” into the mesh geometry. This means that the mesh only works for characters that are roughly the same size.

Step 3: Merge Similar Regions

During the previous two steps, a lot of small regions will have been created. We can merge many of these regions together as long as they are adjacent, have the same surface type, and in the same plane. The method is very similar to what was done in Step 1: query the RBush for regions in a rectangular search area, and then union together the ones that match.

However, you may want to set a limit on how large a region can grow. In my implementation, I keep the regions relatively small (fit within a 4 meter x 4 meter area). The main reason for doing this is that it makes it easier to add dynamic obstacles to the navigation mesh at runtime — each obstacle added or removed only requires updating a small section of the mesh, instead of having to update gigantic polygons that could stretch for long distances.

Step 4: Split regions into convex polygons.

Many of the regions created in the previous steps will have complex shapes. We can use the poly-partition package to split these into smaller regions that are convex. For each region:

1. First, remove all the holes by calling removeHoles(). This doesn’t affect the shape, it just connects the hole with the outer edge.
2. Now call convexPartition() to generate a list of convex polygons.

At this stage, I also convert the BuilderRegion into a NavRegion by transforming all of the 2D coordinates into 3D coordinates.

Step 5: Compute connections between regions.

This step might seem simple at first glance — for each edge of a region, look for a region that has an edge between the same vertices, but going in the opposite direction. And in fact, that would be the normal way to do this if you were going by the standard computational geometry textbook.

However, there’s a catch: the polygon-clipping library likes to optimize polygons by removing redundant, co-linear vertices.

Imagine you have a region that has a “T” shape:

A “t”-shape

Depending on the order in which the polygons are generated and then merged, you may end up with two separate rectangles that have no shared vertices — because the extra vertices in the top rectangle will get optimized away.

This is the reason why the HalfEdge object has a list of connections rather than a single edge reference. This list is constructed by searching for edges from nearby regions that are both co-linear and overlapping. To make this efficient, we can create a second RBush that stores HalfEdges during this phase.

Note that this representation will make our route planner a bit more complex, but not much — it just means we have to be a bit smarter about what we consider a “connection”.

Depending on your preference, you may also want to remove small “island” regions — that is, regions that are not connected to any other region. Since there are no connections, there is no way for the character to ever get to those regions. However, there is no real harm in leaving them in either.

Step 7: Clean up unused vertices

Once all of the regions have been processed, you may find yourself with extra vertices that are no longer used by any region. A simple mark & sweep garbage collection algorithm can be used to get rid of these.

This is also a good place to assign a unique numeric index to each vertex, which will be needed when we want to serialize the navigation mesh and write it to a file in the next step.

Step 8: Write to file

You’ll need to invent some sort of serialization format for your navigation mesh. The vertices are the easiest part: you can take all of the { x, y, z } coordinates and merge them into a single flat array. Vertices are then referenced by an index into that array.

There’s no need to serialize the RBush, since it’s pretty fast to just build it again when you load the mesh in to your game engine. Instead, you can just write out the list of regions as an array of objects. Each object contains the list of vertices (as integers) and the list of connections — although you can also omit that latter part and recompute the connections at load time as well.

At this point you’ll have a JSON object that contains your nav mesh. You can either write this out as a string, or use a binary encoding like msgpack.

Visualization

Of course, the navigation mesh builder is a complex piece of code and you’re going to have bugs along the way. I recommend using test-driven development — write some simple unit tests, using Jest or your favorite test runner, and then get the builder to pass those tests.

In addition, it can be very helpful to see the mesh rendered in 3D. For this, you can create an overlay helper — a class that renders the mesh as a translucent overlay on top of your world. The screenshots displayed at the beginning of this article were created using that helper.

See Also

Creating portals in three.js

Talin’s Index of Essays