Navigation Mesh System

Git Repository

Debug Build

Release Build

Getting AI moving in 2D

This project was one I made while learning C++. Utilising raylib it was was a lesson in AI. Making use of Finite State Machines as the decision making system, and for the path finding it utilised an A* algorithm to path through the Navigation mesh that I generated for this project.

Due to the diving into generation with this project started my interest with procedural generation as a whole.

How to get triangles?

Start off with a square. The way that I approached the nav mesh was to see the program window as a sheet of paper. Any obstacle to be added was a hole that got cut out of the paper. The AI Agents could only traverse the remaining paper. So to start I needed to cut out/define the obstacles. I went about this in a very blunt force way, and manually set each vertex per obstacle (something I later regretted) in anti-clockwise winding order. Once I had my list of obstacles and the list of vertices per obstacles they were my walls that you can see in the picture above. I kept these lists for drawing the visuals, but for the nav mesh I needed to pad them out to allow for agent radii so that the agents didn't overlap the wall with their interactions and movement. Generating a new array I added some padding to the values of the obstacles. I made use of a library called poly2tri, which is a 2D constrained Delaunay triangulation library. It calculated the triangles of what is left after cutting the holes of the nav mesh obstacles using the array of padded obstacles.

Nodes and A* pathfinding

After receiving the triangles back from poly2tri, I converted them to be a node that could be traversed with the A* algorithm. When you use A* on a navmesh, the resulting path by default goes between the centre points of the nav cells. This gives a very jagged path and various techniques exist to smooth it. Pictured to the right is a close up of the jagged path. Below we have the jagged path that you can seee is connecting to all the nodes along its path.

Smoothing the path

Smoothing out the pathfinding was the next step. The method I implemented was the string pull method. To achieve this I check each adjacent edge of the nodes that the agents need to cross. From the position that the path starts at I tracked two points of line of sight. These started as the vertices of the first adjacent edge the agent needed to cross. Once that first angle was formed, I processed each adjacent edge that is needed to cross. As each edge was processed, I checked each vertex and see if it formed a new angle within the first angle. If so, track the smaller angle and keep track of the new line of sight corners. If the vertex of the edge was outside the angle I did nothing and processed the next edge. If the new corner goes past the other, I add the other corner as a the next position to move to in the smooth path and restarted the process.

Pictured to the left is the A* path in blue, which you can see is traversing all the nodes (green triangles) to their center. The orange line is the smoothed path. I used the start and end vector positions as additional nodes in the process of calculating the smoothed path so that the agent could start and end in any position rather than be limited to node centre points.

What's next?

Utilization of these techniques outside of raylib
Implementing steering behaviours to influence the path smoothing so as to not directly wrap around the corners of the path

Page updated

Google Sites

Report abuse