AI Pathfinding Visual Test
Built from scratch | Personal custom C++ engine
- A visual test that demonstrates how pathfinding algorithms work in a tile based map
- Created this project to help me visually see how different AI pathfinding algorithm work
- Gave me a bedrock on which new pathfinding algo can be plugged in and this project can be used for understanding new algorithms
Algorithms Demonstrated
- A*
- Dijkstra's
- Influence Maps
- Flow fields
- BFS
- DFS
1. A*
The green cube on the map represents an expensive tile. The higher the stack of green cubes, the more expensive it is to step on that tile.
In my observations of A* expansion, I noticed that it sometimes did not shy away from stepping on a high-cost tile if it meant getting closer to the goal.
When I tweaked the heuristic to prioritize the goal above everything else, A* behaved like a greedy BFS. Conversely, if the heuristic for finding the goal was loosened, A* behaved more like Dijkstra's algorithm.
In my observations of A* expansion, I noticed that it sometimes did not shy away from stepping on a high-cost tile if it meant getting closer to the goal.
When I tweaked the heuristic to prioritize the goal above everything else, A* behaved like a greedy BFS. Conversely, if the heuristic for finding the goal was loosened, A* behaved more like Dijkstra's algorithm.
2. Dijkstra's
In Dijkstra's expansion, I observed that it almost scans the entire map and tries to avoid expensive tiles as much as possible. Compared to A*, Dijkstra's algorithm seems almost blind because it doesn't keep track of how far it is from the goal.
The green cube on the map represents an expensive tile; the higher the stack of green cubes, the more expensive it is to step on that tile.
The green cube on the map represents an expensive tile; the higher the stack of green cubes, the more expensive it is to step on that tile.
3. Influence Maps
When dealing with multiple goals, influence maps can be used to find a way to the closest goal.
By using BFS expansion from both goals, multiple actors can follow the same influence map to reach their goal. This is unlike A* and Dijkstra's algorithms, where a different path has to be created for each actor/player.
By using BFS expansion from both goals, multiple actors can follow the same influence map to reach their goal. This is unlike A* and Dijkstra's algorithms, where a different path has to be created for each actor/player.
4. Flow fields
Instead of storing the distance to the nearest goal position, a flow field stores the direction towards the goal position.
I create the flow fields on top of the influence maps. Once the flow field is generated, it allows for very fast pathfinding decisions, as each actor/player simply follows the precomputed direction.
I create the flow fields on top of the influence maps. Once the flow field is generated, it allows for very fast pathfinding decisions, as each actor/player simply follows the precomputed direction.
5. BFS
The breadth-first search (BFS) algorithm expands by first exhausting the neighbors of a tile before moving further.
Here, I have shown the debug visualization of BFS expanding first over an empty map and then over a maze.
Here, I have shown the debug visualization of BFS expanding first over an empty map and then over a maze.
6. DFS
(Don't try this at home)
There is a reason DFS expansion is not considered for pathfinding. When I debugged the expansion, it became evident why.
Instead of finding the closest path to the goal, it creates a path that resembles a drunkard's walk towards the goal. It's pretty funny but not very useful for pathfinding.
There is a reason DFS expansion is not considered for pathfinding. When I debugged the expansion, it became evident why.
Instead of finding the closest path to the goal, it creates a path that resembles a drunkard's walk towards the goal. It's pretty funny but not very useful for pathfinding.
