# How can I improve my A* algorithm in Python?

I'm trying to implement my own A* pathfinder, but the voices in my head scream of better ways to do this. Probably because I'm exceeding Python's default maximum recursion depth of 1000.

class PathFinder():

## grid is a list of 8 sub-lists, each containing 8 nodes.
## start and goal are tuples representing the grid indexes of my start and goal.

def __init__(self, start, goal, grid):
## I don't do anything with these yet,
## just thought they would be good to have.
self.goal = goal
self.start = start
self.grid = grid

def find_path(self, start, goal, path=[]):

## My seemingly hackish method of looping through
## the 8 cells surrounding the one I'm on.
for row in (-1,0,1):
for col in (-1,0,1):
if row == 0 and col == 0:
continue
cell = [start[0]+row,start[1]+col]

## Catching the inevitable exception when I try to examine
## the surroundings of cells that are already on the edge.
try:
## Skip if the cell is blocked ("X").
if self.grid[cell[0]][cell[1]] == "X":
continue
except IndexError:
continue

path.append(cell)
if cell == goal:
return path
self.find_path(cell, goal, path)

def main():
import Gridder2
grid = Gridder2.board()
start = (0,0)
goal = (0,3)
pt = PathFinder(start, goal, grid)
print(pt.find_path(start, goal))

return 0

if __name__ == '__main__':
main()


My find_path function particularly seems like it needs work. Seems like I should be able to calculate a path through an 8x8 grid with a recursion depth of less than 1000.

How can I improve this?

class PathFinder():


Either but object in the () or drop them. Having them there empty makes me feel hollow inside.

    ## grid is a list of 8 sub-lists, each containing 8 nodes.
## start and goal are tuples representing the grid indexes of my start and goal.

def __init__(self, start, goal, grid):
## I don't do anything with these yet,
## just thought they would be good to have.
self.goal = goal
self.start = start
self.grid = grid

def find_path(self, start, goal, path=[]):


Don't put mutable values like list as your default parameters. Python will not create a new list everytime this function is called, rather it will keep reusing the same list which is probably not what you want

        ## My seemingly hackish method of looping through
## the 8 cells surrounding the one I'm on.
for row in (-1,0,1):
for col in (-1,0,1):
if row == 0 and col == 0:
continue


I suggest creating a global constant with the 8 directions and doing: for row, col in DIRECTIONS:

                cell = [start[0]+row,start[1]+col]


Don't use lists unless they are actually lists. This should be a tuple.

                ## Catching the inevitable exception when I try to examine
## the surroundings of cells that are already on the edge.
try:
## Skip if the cell is blocked ("X").
if self.grid[cell[0]][cell[1]] == "X":
continue
except IndexError:
continue


I suggest a function get_blocked that you pass cell to which check for 'X' and also returns True if the cell is off the side of the map. Also catching IndexError may not be quite what you want because negative numbers are valid indexes, but probably not want you want. I suggest checking in the get_blocked function for inboundedness.

                path.append(cell)
if cell == goal:
return path
self.find_path(cell, goal, path)

def main():
import Gridder2


Usually not a good idea to import anywhere but at the start of a file

    grid = Gridder2.board()
start = (0,0)
goal = (0,3)
pt = PathFinder(start, goal, grid)


pt?

    print(pt.find_path(start, goal))


Decide whether the start/goal get passed to the constructor or the find method. Don't do both.

    return 0

if __name__ == '__main__':
main()


If you are going to return a value from your main function, you should pass it to sys.exit() so that it actually functions as a return code.

And everything Thomas said.

• All good points, but especially important catch on the negative indices not raising an IndexError, just wrapping around. I won't so confidently assert what the code is doing without executing it next time. – Thomas Oct 7 '11 at 4:29
• @Thomas, yah, I've hit that enough times to be wary. – Winston Ewert Oct 7 '11 at 5:01
• It works so much better now and it's more readable too! Thank you very much! – John Oct 7 '11 at 18:40

Note: this is a fair distance from being an A* algorithm - perhaps correctly implementing a recursive depth-first search (what your algorithm is currently closest too) would be a good start.

You're right, you should be able to calculate a path through an 8x8 without exceeding the recursion limit. Try tracing your code through as you expect it to execute, or add a print statement to show what cell is being checked each time. (and a raw_input() or something so you can easily read it - I would suggest a debugger but that's a crutch you can do without at this level)

(spoiler) Due to negative indices not raising IndexError's in Python (edited this answer after Winston pointed this out), the path you're trying isn't the one you think it is. And the path that exceeds the recursion limit is probably one that repeatedly tries to stay in the current square, checking over and over what happens if the next node visited is the current square.

If only there were a way to close off some of these execution paths; a way to know that a certain path isn't worth checking out any further, so another branch of execution which probably holds a better solution should be tried instead. A good start is that staying in the same place is never really helpful for a static maze, since that's the position you were just in the middle of checking the solutions for! But there are other instances in which you're about to check a square you should have already figured out isn't worth investigating. Check out any literature on depth-first search for the solution.

• Not marking them as visited! I had a feeling I was missing something fundamental... I will try this. – John Oct 7 '11 at 3:54
• Decided I shouldn't have given it away so easily - it's a fun realization to come to on your own. But in your case, you probably don't quite understand depth-first search yet or are forgetting something. – Thomas Oct 7 '11 at 4:03
• @John feel free to open another question if you get stuck again - I didn't actually answer the question in your title with this post, marking nodes as visited won't actually make this a A* search. – Thomas Oct 7 '11 at 4:12
• Well, I was going for A*, but I'm very new to pathfinding. I didn't even know this was called a depth-first search. Now that I know what to Google for, I should be a lot better off. :P You answered the question I meant to ask, that's the important part. – John Oct 7 '11 at 4:16