My implemenation of A* pathfinding in Python
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
boards
.gitattributes
.gitignore
README.md
board.py
search.py
square.py

README.md

astarpython

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.

Example

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**

Setup

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.

Running

python search.py <board txt path> <board width> <board height>

ie:

python search.py boards/board50obs2.txt 50 50

Pseudocode

This was taken from http://en.wikipedia.org/wiki/A*_search_algorithm

More Info

http://www.davidcraddock.net/2014/06/12/a-algorithm-implementation-in-python/