My implementation of the A* pathfinding algorithm, with 'Roguelike' text visulisations of the pathfinding in plain ASCII.
Passable squares are denoted by a '0' character, and impassable squares by a '7'. For the sake of simplicity, currently the start square is always the top left square (0,0) and the goal square is always the bottom right square.
This is the board before running:
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**
You will need a board to find a path across. Some sample boards are in /boards. Passable squares are denoted by a '0' character, and impassable squares by a '7'. For the sake of simplicity, currently the start square is always the top left square (0,0) and the goal square is always the bottom right square.
python search.py <board txt path> <board width> <board height>
ie:
python search.py boards/board50obs2.txt 50 50
This was taken from http://en.wikipedia.org/wiki/A*_search_algorithm
http://www.davidcraddock.net/2014/06/12/a-algorithm-implementation-in-python/