Lately I’ve had the idea of creating a text-based Roguelike in C++. This lead me on to think about the game AI experiments that I worked during my degree in Computer Science and A.I.. Essential to game AI is the notion of pathfinding, or finding a path from ‘A’ to ‘B’, past any obstacles that get in the way. One way to do this is to use the A* algorithm. I decided to implement an A* pathfinding algorithm for possible use in a Roguelike later, and chose the pseudocode from the Wikipedia example to implement.
The program finds a path from the top right hand corner to the top left, avoiding impassable ‘7’ obstacles. The ‘*’ are the steps along the path. The algorithm is guaranteed to find the shortest path between the goal and the start, which means it can optimally solve any solvable maze, given time.
This is a sample board with obstacles setup:
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000777000000000000000 00000000000000000000000000000000777000000000000000 00000000000000000000000000000000777000000000000000 00000000000000000000000000000000777000000000000000 00000000000000000000000000000000777000000000000000 00000000000000000000000000000000777000000000000000 00000000000000000000000000000000777000000000000000 00000000000000000000000000000000777000000000000000 00000000000000000000000000000000777000000000000000 00000000000000000000000000000000777000000000000000 00000000000000000000000000000007777000000000000000 00000000000000077777777777777777700000000000000000 00000000077777777777777777777777700000000000000000 00000077777777777700000000000000000000000000000000 77777777777000000000000000000000000000000000000000 77777777000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 77777777777777777707777777777777777777777777777777 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 70777777777777777777777777777777777777777777777777 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 77777777777777777777700000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000777777777777777777777707777777 00000000000000000000700000000000000000000000000000 00000000000000000000700000000000000000000000000000 00000000000000000000700000000000000000000000000000 00000000000000000000700000000000000000000000000000 00000000000000000000700000000000000000000000000000 00000000000000000000700000000000000000000000000000 00000000000000000000700000000000000000000000000000 00000000000000000000700000000000000000000000000000
This is the path found (the ‘*’s):
**000000000000000000000000000000000000000000000000 0***********************************00000000000000 00000000000000000000000000000000777*00000000000000 00000000000000000000000000000000777*00000000000000 00000000000000000000000000000000777*00000000000000 00000000000000000000000000000000777*00000000000000 00000000000000000000000000000000777*00000000000000 00000000000000000000000000000000777*00000000000000 00000000000000000000000000000000777*00000000000000 00000000000000000000000000000000777*00000000000000 00000000000000000000000000000000777*00000000000000 00000000000000000000000000000000777*00000000000000 00000000000000000000000000000007777*00000000000000 00000000000000077777777777777777700*00000000000000 00000000077777777777777777777777700*00000000000000 00000077777777777700000000000000000*00000000000000 77777777777000000000000000000000000*00000000000000 77777777000000000000000000000000000*00000000000000 00000000000000000000000000000000000*00000000000000 00000000000000000000000000000000000*00000000000000 00000000000000000000000000000000000*00000000000000 00000000000000000000000000000000000*00000000000000 00000000000000000000000000000000000*00000000000000 000000000000000000******************00000000000000 777777777777777777*7777777777777777777777777777777 000000000000000000*0000000000000000000000000000000 0******************0000000000000000000000000000000 7*777777777777777777777777777777777777777777777777 0*****************************00000000000000000000 00000000000000000000000000000**0000000000000000000 000000000000000000000000000000**000000000000000000 0000000000000000000000000000000*000000000000000000 0000000000000000000000000000000***0000000000000000 000000000000000000000000000000000*0000000000000000 000000000000000000000000000000000**000000000000000 0000000000000000000000000000000000**00000000000000 77777777777777777777700000000000000***000000000000 0000000000000000000000000000000000000**00000000000 00000000000000000000000000000000000000*00000000000 00000000000000000000000000000000000000**0000000000 000000000000000000000000000000000000000****0000000 000000000000000000007777777777777777777777*7777777 000000000000000000007000000000000000000000**000000 0000000000000000000070000000000000000000000*000000 0000000000000000000070000000000000000000000***0000 000000000000000000007000000000000000000000000**000 0000000000000000000070000000000000000000000000*000 0000000000000000000070000000000000000000000000***0 000000000000000000007000000000000000000000000000*0 000000000000000000007000000000000000000000000000**
Here is source code
Amit’s A* pages were incredibly useful in developing this.
(Perhaps one day I will do a flashy JavaScript version!)
DavidCraddock.net 