Reap What You Saw - AI Pathfinding

Below is a video demo of the AI pathfinding algorithm that we are going to implement into the 'Reap What you Saw' game.

It's not very exciting to look at and you may be thinking that path-finding is nothing special and that you could probably do the same in five minutes with a simple A* algorithm. It is not A* because it does not calculate the path each time you click a new destination. This would be too computer intensive if you were setting the destination for a large number of agents at once. It would be terrible if every time you moved your character the game would slow down or freeze while it calculates all the agents paths. Instead, before the program loads, it compiles a path table for each grid cell in the map. It then 'smooths' this path so that it can skip grids in the path table. Ie instead of going A->B->C it just gets directed from A -> C. This allows for shorter and more straight paths to the destination, without having to go through the center of each grid cell. This means that the user will also be less likely to notice the map is actually divided into a grid. Obviously the 'smoothing' also takes into account obstacles, otherwise the agent would just go directly towards the final destination and get stuck. A path-table is used in the following way:

1. If the agent is in cell 1 and it wants to get to cell 53, it accesses the pathTable array in cell 1 at index 53.



2. The path table then returns a link (c++ pointer) to the next cell to go towards.



3. The agent can then use this cells path table and access element 53 again in order to get to the next cell.



4. Finally the agent stops when it reaches cell 53.

This is far less cpu intensive than performing an a* search to get from A to B and avoid obstacles.