A-Star NavMesh Pathfinding and Funneling
Summary
NavMesh, short for navigation mesh, is a non-rendered object in a game world composed entirely of convex polygons (closed 2D shapes with three or more outward-pointing sides). These polygons are connected by shared edges, forming a mesh that enables the calculation of viable paths between two points. This system is primarily used to help AI-controlled (or indirectly player-controlled) characters navigate the environment. NavMesh pathfinding is a core component in many modern games, with the A-Star algorithm being one of the most popular and efficient methods for determining these paths. Once a viable path has been found, regardless which algorithm was used to find it, a smoothing algorithm (in this case funneling) is needed to make the path both more efficient and better looking. This is because pathfinding algorithms usually only find the shortest path via centerpoints of polygons, not the actual shortest path between the start and end points. An actor wandering centerpoint to centerpoint would not only look strange doing so, but also take far longer to get to its goal than it needed to.
From Curiosity to Requirement
During the spring of my first year at TGA we had a course called "Datastructures and Algorithms", where one of the assignments was to implement a pathfinding algorithm usable on both NavMeshes and 2D grids. Even though the initial version I made as part of that assignment was very unoptimized and had no smoothing algorithm to speak of, the assignment sparked a curiosity in me regarding game AI as a broader field and especially the algorithms that drive intelligent behavior. That curiosity stayed with me, pushing me to explore pathfinding more deeply and refine my skills outside the classroom.
During the summer, with some extra free time on my hands, I revisited the project and challenged myself to implement a basic smoothing algorithm. My first attempt was rudimentary, relying on midpoints between triangle centerpoints to create smoother paths, but it served its purpose as a proof of concept. However, once I started using that version in a larger project, I quickly realized it couldn't be used for more than a few actors at a time without bogging down performance. It was full of inefficient memory allocations and unnecessary loops over large collections. Around the same time, I also found out that an efficient smoothing algorithm would be a requirement in a later group project. With a new sense of urgency, I committed myself to reworking the entire system. Over the course of a week, I iterated repeatedly on the pathfinding logic and rewrote the smoothing algorithm from the ground up. The result, as seen on this page, was a far more efficient and scalable solution, one that could meet the performance needs of more demanding projects.
In my opinion, the biggest flaw of my implementation is that it isn't thread safe, but I know exactly which modifications I would need to make for it to be thread safe if I were to encounter a situation where I need it to be. My focus when optimizing my implementation has instead been to make better use of the cache, reduce memory overhead and eliminate redundant iterations.
A-Star pathfinding
My implementation defines polygons as "nodes" and currently only works on NavMeshes made up entirely of triangles. I could adapt it to handle polygons with more sides without too much effort, but using triangle meshes was enough to satisfy my own curiosity and to fulfill the requirements of the projects I needed to use the algorithms in, so I settled for that.
The pathfinding algorithm works by traversing a priority queue, sorted by the cost of reaching each node from the starting node, and marking visited nodes along with updating their cost as the algorithm goes along. As the algorithm progresses it tracks which nodes it had to walk through to get to each other node by the shortest path there.
Go to the function on GitHub
If the algorithm traverses all nodes by shared edges originating from the start node without reaching its goal, the algorithm fails. This can only happen if a NavMesh was fed to the algorithm where not all triangles share an edge. It could also happen if I were to implement a way to make nodes untraversable (driven by gameplay), signifying a blocked or otherwise obstructed path.
If the algorithm succeeds in traversing its way to the end node however, it constructs a collection consisting of the shortest path of nodes used to reach the end node from the start node. Using this collection it then constructs a collection of "portals". Portals are synonymous with edges, consisting of two of the triangle's three vertices. The only difference is that a portal has to be an edge the actor would need to walk through to traverse along the path to reach the end. These portals are then fed to the funneling algorithm to produce the final smooth path. The resulting path before any funneling is applied is displayed as the pink line in the visualization shown when hovering over this sentence. (🔍)
Go to the snippet on GitHub
Funneling the Found Path
The funneling algorithm essentially functions like plastic cling wrap visually. It tries to wrap the path along corners on the way to the goal without overshooting the corner and "ripping" the cling wrap. Though funneling is a more apt name for the algorithm, since it essentially works by defining cones that it keeps narrowing more and more, which end up looking like funnels.
The start of the algorithm works by defining either vertex from the first portal as the apex of the funnel (they are assumed to be the same and that is always the case in my implementation) and the left and right points of the second portal as the left and right points of the funnel, essentially defining two edges, one spanning from the left to the apex and one spanning from the right to the apex, forming a cone.
Go to the function on GitHub
Then the traversing of the path of portals begins. Stepping along the sorted path of portals, the algorithm checks if the portal's left point is a better left point for the funnel to use without overshooting the right point, and vice versa for the right portal point to the right funnel point. If the left or right points of the portal were to make the funnel overshoot (meaning the right point of the funnel would be to the left of the left point or vice versa), that means a corner for the final smooth path has been found and the algorithm should define a new funnel apex and new left and right points using the next portal following the one where the corner point was found on. Once the iteration reaches the final portal, the best smooth path has always been found and we can allow the actor to traverse along it. The resulting smoothed path is displayed as the pink line in the visualization shown when hovering over this sentence. (🔍)
Go to the snippet on GitHub
Used in Projects
The First Version Used on a 2D Grid
I used my initial unoptimized version (which lacked path smoothing) for the enemies in our 4th group project (Carl Off Duty).
The Optimized and Funneled Version Converted to Work in 3D and used on a NavMesh
In our 6th group project (Order of the Roses), I used the new and improved version for the enemies as well as for the player's point-and-click movement. It was also used for the enemies in our 7th group project (Blacksite: Deep Horizon).
