2D Navmesh Pathfinding

Pathfinding is complex. Most game engine already provide a generic solution that handle all the messy parts. However, if you are building your own, this is something you will have to code (mostly) from scratch.

Good news, there are plenty of high quality articles online. Understanding the basics of pathfinding is just a few google search away.

Bad news, theory is different than practice, the more you move away from the simple stuff (like grid based pathfinding) the more fragmented the information becomes and the harder is becomes to piece everything together.

This is a interactive article explaining all the steps I've done to build my own 2D pathfinding utility, from building the navmesh, computing the optimal path using A-star, to generating the final path. Using Rust of course.

It is MUCH better to run the demo on a desktop. If your screen width is smaller than 1600 pixels, the demo will be hidden by default.

The code for this demo is available on github HERE and all of the pathfinding logic is in THIS file

Controls

Primary mouse click / single tap to select sprites, interact with the gui
Secondary mouse click / double tap to move selected pawn
Single finger drag to simulate a mouse move
Middle mouse / double finger drag to pan the world
[D] or [Toggle Demo] header label to toggle the demo visibility
[R] or [Reset Demo] header label to reset the demo

Special thanks to:

Red Blob Games: For the best A* Algorithm guide available online
PixelFrog: For the amazing assets used in this article
Delaunator: The great library that handles the Delaunay triangulation
Delaunator-rs: The rust port of delaunator
Simple stupid funnel algorithm: For the path smoothing algorithm

Using Delaunay triangulation to generate the base navmesh

On its own, a navmesh is really just a 2D mesh. In the "Generation" demo you can toggle the navmesh using the "Show navmesh" check box.

In most game engines, building a navmesh is not done manually. Usually there is a "baking" feature that takes 2D or 3D objects as inputs, and then generates the navmesh. The overall process in this article should be almost identical to this.

The best way to generate a navmesh is called Delaunay triangulation. With a dynamic demo, this must be done in real-time; however, Delaunay triangulation is cheap to compute and can easily process thousands of vertices in only a few ms, even on less powerful hardware. Moreover, you don't need to implement Delaunay triangulation from scratch; there are many libraries, in every language, ready to be used. Also, most of them are small, self contained, and REALLY optimized.

The Rust Delaunay triangulation crates are: delaunator, cdt, and spade. Spade has a document comparing the features between each of them. Of those three, spade is the most feature-rich.

In this demo, I'm using delaunator because it is the most simple. The source code consists of a single file with approximately 600 lines of code. However, this simplicity comes with limitations, as detailed in the Limitations & Steps Forward section.

Using delaunator, the generation is done by building a list of points (also called vertices), and the calling the triangulate function:

pub fn triangulate(points: &[Point]) -> Triangulation

When working with sprites, first add all the corners of the world and then, for each sprite with collisions, add the bounding box coordinates. We're also saving the bounding boxes of each one of those sprites, we will need them to remove the unreachable nodes in the following steps.

Understanding the triangulation output

The output of the triangulation is a doubly connected edge list (also known as DCEL). It is defined as:

pub struct Triangulation {
    /// A vector of point indices where each triple represents a Delaunay triangle.
    /// All triangles are directed counter-clockwise.
    pub triangles: Vec<usize>,

    /// A vector of adjacent halfedge indices that allows traversing the triangulation graph.
    ///
    /// `i`-th half-edge in the array corresponds to vertex `triangles[i]`
    /// the half-edge is coming from. `halfedges[i]` is the index of a twin half-edge
    /// in an adjacent triangle (or `EMPTY` for outer half-edges on the convex hull).
    pub halfedges: Vec<usize>,

    /// A vector of indices that reference points on the convex hull of the triangulation,
    /// counter-clockwise.
    pub hull: Vec<usize>,
}

The structure might seem unintuitive at first, but once you understand 3 simple things. It becomes much easier to wrap your head around it.

#1. The edges. Edges are the building blocks of a DCEL. They are stored in the triangles Vec. Each value in the vector is the starting point of an edge. As such:

triangulation.triangles.len() returns the number of edges in the triangulation
triangulation.triangles[0] returns, for edge #0, the index of the point in the original vertex vector
points[triangulation.triangles[0]] returns, for edge #0, the coordinates of the starting point (points being the original vector passed to the triangulate function)

#2. The triangles. Triangles are also stored in the triangles. Each triple of edges forms a triangle. As such:

triangulation.triangles.len() / 3 returns the number of triangles in the triangulation
triangulation.triangles[0..3] defines the first triangle
index [0, 1] defines the start and end points of the first edge
index [1, 2] defines the start and end points of the second edge
index [2, 0] defines the start and end points of the third edge

#3 Moving from one triangle to one of its neighbor. A triangle can have up to three neighbors, so iterating over the triangles in a linear fashion is not really helpful. That's where the halfedges comes to save the day. For an edge "X", indexing into the halfedges returns the edge of the opposite triangle (or usize::Max if the edge points outside of the triangulation). As such:

triangulation.halfedges[0] returns the index of the neighbouring triangle edge
triangulation.triangles[triangulation.halfedges[0]] returns the index of the point of the neighbouring edge
points[triangulation.triangles[triangulation.halfedges[0]]] returns the coordinates of the starting point of the neighbouring edge

For more details, delaunator has a more in depth guide on how the data structure works.

Lets put this knowledge into practice, and do one of the most simple operation you can do on a navmesh...

Mapping a point inside the navmesh

One of the most basic thing to query in a navmesh is in which triangle an object is located. Sure it is possible to brute force it by looping over every triangle and check if the point is inside. However, thanks to how the navmesh is built, it is possible to query the information with much fewer instructions.

To debug this feature. On the navigation tab, check "Debug Triangle lookup". The triangle_at function code is also available HERE.

Generate a graph

The A* algorithm works on a graph, however a navmesh is not a graph. Building a pathfinding graph can be done using many different techniques, and you may not even need a navmesh! For this demo, I'm using the simplest method available: the navmesh triangles are the cells, and the cost to move between the cells is the distance between each triangle incenter. There is also a very good article by Red Blob games called map representation that goes deeper into the subject.

To debug the graph, go to the "pathfinding" tab and check the "show pathfinding graph" option.

Because working directly with the navmesh, with the multiple levels of indirection, is not very good for code readability or data locality, We can store more than just the distance between the nodes. Each field will be explained later, but for now, here's the data type of a node:

pub struct Triangle(u32);

struct NavNodeNeighbor {
    pub center: PositionF32,
    pub segment: [PositionF32; 2],
    pub triangle: Triangle,
    pub distance: f32,
}

struct NavNode {
    pub triangle: Triangle,
    pub center: PositionF32,
    pub n0: NavNodeNeighbor,
    pub n1: NavNodeNeighbor,
    pub n2: NavNodeNeighbor,
    pub disconnected: u32
}

The nodes are stored in a Vec<NavNode> that maps to the navmesh triangles.

The code is HERE.

Removing blocked nodes from the graph

Next step is removing the blocked nodes from the graph. Toggle blocked cell debugging in the navigation tab by checking "show blocked cells"

To detect which cell is blocked, check if the center of a cell is in the bounding box saved in step #1. The algorithm brute force it by checking each bounding box for each node in the graph. The scaling is a problem for future me.

Removing the nodes from the Vec is not a good idea because we lose the triangle->node mapping and because we may need to compute the path from inside a blocked node. Instead we add a disconnected flag. For every blocked node, set this flag to true and next, lookup the neighbouring nodes and set the distance from that neighbouring node and the blocked node to infinity.

The code is HERE

Using A* to compute the optimal path between two cells

Rust has an implementation of the A* algorithm in the pathfinding crate. However, because the algorithm is simple enough to code, we have our own implementation. Toggle pathfinding debugging in the pathfinding tab by checking "debug pathfinding".

Also, while coding the algorithm is simple, explaining the logic behind the code should be a topic for a separate article. Several such articles already exist online. The best one I found is Implementation of A* by Red Blob Games.

Because of the graph generated in the previous step, all the information needed to run the A* algorithm is already in the node. Each neighbor (n0, n1, n2) in the cell as the distance to quickly add the new_cost to move to the node. And the center of the neighbor node can be used to compute the heuristic (neighbor.center.distance(end_point)).

The output of the algorithm is a Vec of segments (or "gates") the moving unit will have to go through. This will be needed to optimize the path in the following step.

Check this project implementation HERE