Since we covered navmeshes briefly, I also thought it would be good to provide a quick overview of the pathfinding algorithms that underpin them.
This knowledge will serve as a good jumping off point if you want to delve deeper, but can also be very useful in recognising what might be happening with an AI when they are not behaving as expected.
Djikstra’s Algorithm
This is the most basic search algorithm that we would reasonably use in a 3D video game, and it is very closely related to A* search which is the industry standard algorithm, so it’s a good place to start.
The concept is very simple.
- From your starting point you search every adjacent space and place them into a list representing the frontier of the search.
- After all of the adjacents have been explored, you search the adjacents of the frontier nodes
- You repeat this on and on and on, until you find the goal node
- You then recurse back though the adjacencies until you have a path back to the start
A* Algorithm
This is simply an optimisation of Djikstra. It uses a concept called a Heuristic - this is simply an estimation of how close each node is to the goal node. For this example we will use linear distance to the goal node (the most common heursitic).
- From the starting point you look for the adjacent with the smallest heuristic value and place them into a list representing the frontier of the search
- You then move onto the next node with the lowest heuristic cost
- You continue to do this until you reach the goal node
- You then recurse back though the nodes until you have a path back to the start
The difference here is that instead of searching all adjacencies before you expand the frontier, you are trying to guess which direction the search should go in to be successful faster.
Of course this isn’t always optimal, as shown in this example. however it’s an edge case and it still slightly more optimal that Djikstra seaching the same space.
