Date Created: 25 July 2021
No. of people involved: Only me
Length of project: 1 week
Tools: SDL2, C++
At the time, we were halfway through the Artificial Intelligence subject at AIE (Academy of Interactive Entertainment), and we had a week break. I wasn't entirely happy with the knowledge I already had, so I took it upon myself to further my knowledge of how pathfinding works in video games, along with creating a cool app that shows off how each algorithm works.
I wanted to have a deeper understanding of why some algorithm's are better than others, and in what kinds of area's or maps each one would be useful in. The app uses Breadth First Search, Depth First Search, Dijkstra's Algorithm and A star.
Dijkstra's Algorithm being used in a simple maze. The brown circles represent sand, which have a G-score of 5, while the boxes with no sand have a G-score of 1.
The same maze as above, though using the A-Star algorithm.
An example of Breadth First Search being used with diagonals allowed.
Using the same map as above, but instead using the A-Star algorithm, with diagonals allowed. It's interesting comparing this with the one above, as it's at least 2-3 times faster.