Skip to content

How A* Sees the World; An Introduction to Navigation Meshes

Published: at 12:30 PM

Preface

The idea for this article came to my mind after finishing the last entry, where I asked myself, “How exactly does A* get information about a scene?” This simple but important question bothered me so much that I decided to explore it.

Although I’ve used or interacted with a NavMesh thousands of times, I had never asked myself how it works. I think that in complex systems, we stop paying attention to parts that just work.

Navigation Mesh is a mature concept that solves problems most people had forgotten even existed. It was exciting for me to step into the shoes of people who had to solve these problems in the first place.

Prerequisites

You should be familiar with A*. I recommend reading my previous post where I explain A* within a wide context.

Introduction

Let’s step back a little and take a different perspective: imagine there’s no NavMesh implementation. How would we make pathfinding work? This question requires us to solve three main problems. First, we need to pass the information to the pathfinding algorithm. Secondly, we must do it efficiently so we don’t destroy our game’s performance. Finally, we have to consider the validity of the path. Let’s go through them one by one.

Table of contents

Open Table of contents

Feeding the algorithm

At the center of any scene is a Cartesian coordinate system. We use it to express positions, measure distances, and have a center we can relate to.

Figure 1: Y-up right handed coordinate system

A coordinate system uses real numbers. If you remember from your math lessons, the set of real numbers has infinitely many elements. On one hand, this is great because it gives us infinite precision for expressing positions. On the other hand, it’s a problem because a pathfinding graph cannot have an infinite number of nodes. Even if we were to limit the coordinate space to the furthest position in a scene in each dimension, we still would be working with an infinitely sized set.

You might say that this is not technically correct, since computers are physical machines with finite precision, and they cannot express all real numbers. You’d be right. However, with 32 bits (typical size of float) we have 2324 294 967 2962^{32} \approx 4\space294\space967\space296 distinct bit values just in one dimension. We might as well treat it as a set with an “approximately” infinite number of elements.

This points out an old but fundamental problem: how do we express a continuous or an extremely large set with a finite set? Fortunately, people who deal with signal processing have figured it out a long time ago; the answer is quantization.

Quantization

Quantization expresses continuous values using a finite set of approximated values. Although approximation helps us immensely with expressing these values, it introduces errors. Figure 2 shows an example of quantizing a sine wave.

Figure 2: Sine wave quantization. The height represents the signal value, while the width w is constant

I won’t detail the math of this process, but you can see that the rectangles have a constant width and a height which represents the signal value. We can fit a fixed amount of these fixed-width rectangles, meaning they don’t follow the curve perfectly. This is important, and we are going to come back to this later.

The same approach can be applied to a scene. We can subdivide it into square shaped cells of length Δl\Delta l, essentially repeating the same process as with the sine wave but in two dimensions.

Figure 3.A: A simple flat 3D scene. Figure 3.B: The same piece of geometry subdivided into squares of length Δl

In this subdivided form, by placing a node in the middle of each cell, we are essentially getting a square graph, which we can feed into a pathfinding algorithm. This approach is called Grid Graph; it’s a simple way of doing pathfinding.

Since each node connects to its closest neighbors, they can have two, three, or four edges. The cost of traveling between any adjacent nodes can be calculated as a function of distance between their positions or the traveling time between them.

Figure 4.A: Cell graph with nodes. Figure 4.B: Cell graph with connections

Searching the path

What happens if we want to do a search from point AA to BB where none of the points are in the center of the cell? We are going to approximate their positions to the closest nodes (see Figure 5.A). As I said before, quantization introduces errors. We can influence the error by decreasing the size of Δl\Delta l, but this increases the number of nodes.

Figure 5.A: Points $A$ and $B$ approximated to the closest cells. Figure 5.B: Solved path from $A'$ to $B'$

With positions corresponding to nodes, we finally have a form that matches A*’s or any other pathfinding algorithm’s expectations. We perform the search and get back path pp (see Figure 5.B).

The path is unfortunately very angular; it changes heading at every node. An agent taking this path would look very unnatural. This situation could be fixed if we allowed for 8-directional connections instead of four. It would make a straighter path, but it would nearly double the number of edges (by 77% according to my calculations). Another option is to smooth out the path, which we will cover later. Now, let’s look at a different case.

Validity

The previous example is incredibly optimistic in terms of elements in a scene. In order to truly evaluate this technique, we have to see how it would behave, at least, in an average scenario: a scene with one building. Figure 6.A shows a plane with a rectangular building on it and three distinct points n1n_1, n2n_2, and n3n_3.

Although point n3n_3​ is on walkable ground, its cell’s center is blocked, making the node invalid. We cannot perform a search to it because that would result in an invalid path.

Figure 6.A: An example scene with a building on it

There’s another difficult case here: points n1n_1 and n2n_2. Let’s say we want to move from one to another. Since they are both in the center of the node, the algorithm can solve a path between them. The shortest path between those two points is a straight line. An NPC following this path would collide with the wall, this is not good. The issue can be mitigated if we increase the resolution of the graph and use smaller cells. While fixing this, I increased the number of cells twenty five times for Figure 6.B.

Figure 6.B: Scene with a building with an increased resolution

Grid graphs are simple and straightforward implement; however they require high resolution to accurately represent objects that don’t lie on a grid.

Division schemes are ways of abstracting a scene into a format that’s useful for processing, it can be pathfinding or other spatial reasoning. So far we’ve talked about grid graphs, but they are other ways of doing this: Dirichlet Domains, Points of Visibility, or finally, Navigation Meshes. They are the de facto standard of the industry.[3]

Image 1: Navigation mesh example from Unreal Engine (source: https://dev.epicgames.com/documentation/en-us/unreal-engine/basic-navigation-in-unreal-engine)

Navigation mesh , or NavMesh, is a search space optimization built from a scene. Like a grid graph, NavMesh is used as an abstraction of a scene; it can be used for feeding the pathfinding algorithm. It takes the form of a static mesh, built in the editor after the level geometry has been laid out. Just this fact is a major improvement over Grid Graphs. Since there’s no information about the areas that weren’t marked as walkable, the game doesn’t have to check if a cell is blocked by a static geometry or not, which makes it mostly valid. In other words, if you can’t walk on it, it has no NavMesh.

Image 2: Navigation mesh example from Unity Engine (source https://learn.unity.com/tutorial/navmesh-baking-1#5ce58ae8edbc2a0ff933255a)

The process of generating a Navigation Mesh is called baking. Either the rendering or the physics geometry can be used for baking, but the latter option is chosen more often. Why? Nowadays physics geometry, aka. colliders, is much simpler in comparison to rendering geometry. Additionally, they are the source of truth for the physics engine which controls most of the object in a scene. Despite what’s used, the resulting mesh is constructed from polygons, usually triangles, but quads are also a valid option.

How a NavMesh is baked and what influences its generation are interesting topics themselves. Things like agent size, the NavMesh’s maximum and minimum allowed slope, or even the minimum size of a created region are all configurable in most engines. However, I’ll focus only on the basic ideas behind NavMesh for now, so I’ll ignore those low-level details.

Characteristics

Figure 7.A: simple 3D scene with an obstacle in the middle. Figure 7.B The same scene with Navigation Mesh drawn over

Figure 7.A shows a simple scene with a walkable floor and a box that’s unavailable for the navigation system. The drawing to the left shows how a Navigation Mesh would look after being baked (the process of generating the NavMesh is called baking) from the scene. You can see immediately see there are fewer triangles than there were squares in a grid graph.

A pathfinding graph is created by placing a node in the center of each polygon. Any two nodes are connected if the corresponding polygons share an edge. Notice the difference between NavMesh and the grid graph.

Figure 7.C: The same scene with nodes marked. Figure 7.D The same scen with pathfinding graph visualized

Just like with Grid Graphs, when searching, positions are first quantized to a node in the graph. This process of matching positions and nodes is simple in theory for Navigation Meshes. We just have to check which triangle contains the requested position, whether it’s the start or finish position.

Figure 8.A: Point quantization shown. Figure 8.B: Solved path between A' and B'

A*, or any other pathfinding algorithm, operates in something that I would call the graph space. It has no information about the game world; it only has information about the graph. The graph itself is made out of nodes, edges and cost functions, but they are only an abstraction of the real world. For us this means three things:

String-pulling based smoothing

Introduction

The last two things we have to do are smooth out the path, and make it relative to the game world. As always there are multiple ways of doing things, String-Pulling Approach is the industry standard. [https://idm-lab.org/bib/abstracts/papers/socs20c.pdf]

Introduced by Han et al. [2], String Pulling is an algorithm for smoothing out paths. You can imagine it working as if we were to pull a piece of string between the start and end points. The shape that the string would have would be the shortest path between two points.

The authors of the paper added a benchmark for the algorithm against different versions of A* and a more sophisticated pathfinding algorithm, Theta*. The string-pulling approach introduced a minor runtime overhead, increasing the average time by 2%. The path length deviated by around 0.47% from the calculated reference. In comparison, raw A* extended the path by 4.73%. Last, but not least, string-pulling on average removed all unnecessary heading changes, it even beat Theta*.

![[Pasted image 20250701153840.png|1000]] **

Image 3. Example of how a string-pulling algorithm works (taken from: [2]).

How does it fit together?

Figure 8.C: A string-pulled path

The sequence of nodes that’s returned from A* is transformed to a sequence of positions. Start and finish positions are added to that sequence with an assumption that there is a direct line of sight, from the node centre to that position. Then the path is smoothed out, which means, that it’s shorter, has fewer unnecessary turns and just looks better.

Summary

In this post, we talked about how A* gets information about a scene, and what the basic concepts behind quantization are. We followed the simplest approach (Grid Graphs) for abstracting the scene and found issues with that. We moved from Grid Graphs to current techniques called Navigation Meshes, and, we discussed the entire pathfinding process with these meshes.

Conclusions

For me, grasping the core problem allows me to understand the tool or method that I’m using. And I hope with this entry I have achieved the same for you. This blog post is by no means a complete description of what can be achieved with NavMeshes. There are other topics like: generation, multiple agents, dynamic obstacles, moving NavMeshes, etc. I encourage you to try reading and playing with those concepts on your own.

Bibliography

  1. https://en.wikipedia.org/wiki/Quantization_(signal_processing)
  2. https://idm-lab.org/bib/abstracts/papers/socs20c.pdf
  3. Millington, I. (2019). AI for Games, Third Edition (3rd ed.). CRC Press. https://doi.org/10.1201/9781351053303
  4. https://www.wikiwand.com/en/articles/Navigation_mesh
  5. https://www.wikiwand.com/en/articles/A%2A_search_algorithm
  6. https://dev.epicgames.com/documentation/en-us/unreal-engine/basic-navigation-in-unreal-engine