How can I improve my A* algorithm in Python?

Question

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?

Answer 1

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.

Answer 2

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.