Path finding algorithm using recursion in Python

Question

Here is a code I developed some time ago. I wonder if there is anything I can do to improve it. It works for non-loopy mazes which was already my goal.

In the maze defined, True are the open ways and False are the walls.

The main subjects that I gladly accept suggestions can be listed like this:

• Is the solution pythonic, if not what can be done to improve?
• Because of the recursion, after I reach the ending point, I cannot directly return the true_path because the dead ends encountered by the player makes the function return None. So I have to save it in another variable and let the recursion end after that. It is not directly an issue but I am eager to hear suggestions about it.(That is the reason i didn't return the recursions done in the function. They are just called.)
• Is a while loop a better solution to this kind of problem?
• Even if the solution is pythonic, are there any better ways to implement this path finding algorithm.

def possible_paths(maze, coor):
    # This function checks the 4 available routes around the current point.

    paths = [
    (coor[0]- 1, coor[1]),
    (coor[0],coor[1]-1),
    (coor[0], coor[1] + 1),
    (coor[0] + 1, coor[1])
        ]
    possible_paths = []

    for path in paths:
        if path[0] >= 0 and path[1] >= 0 and path[0] < len(maze[0]) \
        and path[1] < len(maze):
            if maze[path[1]][path[0]]:             
                possible_paths.append(path)
    return possible_paths

answer = []
def solve(maze, pos, exit, true_path = []):
    global answer
    paths = [path for path in possible_paths(maze, pos) if path not in true_path]

    if pos == exit:
        answer = true_path
    elif len(paths) == 1:

        pos = paths[0]
        true_path.append(pos)
        solve(maze, pos, exit, true_path)

    else:
        for path in paths:
            temp_path = true_path[:] + [path]
            solve(maze, path, exit, temp_path)

maze = [[True, False, True,  False],
        [True, False, True,  False],
        [True, True , True,  False],
        [True, False, False, False],
        [True, True,  True, True],
        [True, False, False, False]]

solve(maze, (0,0), (2,0), [(0,0)])
print answer
# Gives [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 1), (2, 0)]

Note: Please notice that (2,0) is a coordinate, so it is actually equivalent to maze[0][2].

Answer 1

What's in a name?

This code is pretty easy to follow, and I could mostly understand it on the first read through. However, we could do better. Let's take a look at possible_paths(). This function doesn't return paths - it returns neighbors. It returns all the adjacent squares. Moreover, what is path[0] and what is path[1]? Let's name these things too.

Point = collections.namedtuple('Point', 'x y')

def neighbors(maze, coor):
    adjacent = (Point(coor.x - 1, coor.y),
        Point(coor.x, coor.y-1),
        Point(coor.x, coor.y+1),
        Point(coor.x+1, coor.y)
    )

    for p in adjacent:
        if 0 <= p.x < len(maze[0]) and 0 <= p.y < len(maze):
            if maze[p.y][p.x]: # I don't understand this flipping
                yield p

Having x and y is easier to grok than path[0], which looks like a point in a path, rather than an individual coordinate of a point. You could split this up even more by putting the adjacent points in their own function:

def adjacent(coor):
    yield Point(coor.x - 1, coor.y)
    yield Point(coor.x, coor.y - 1)
    yield Point(coor.x, coor.y + 1)
    yield Point(coor.x + 1, coor.y)

def neighbors(maze, coor):
    for p in adjacent(coor):
        ...

That's nice and bite-size. This idea should get propagated through to solve() so instead of starting with paths = ... we call it next_nodes = ... (or next_neighbors or something equivalent suggesting that we're talking about single points, not paths).

Global Variables

Right now, your solver is a little hard to use. You have to call it, then separately, check some global variable to see the result. Global variables are bad for a lot of reasons that I won't get into here, but the important one here is: you want your solver to return the answer. So let's do that:

if pos == exit:
    # we made it!
    return current_path

Okay that part is easy. What do we do in the other cases? First, there's not really a special case for len(paths) == 1 if you think about it. There is a special case for 0 though. Did we hit a dead end? Let's quit.

elif not next_nodes:
    # no path found
    return []

And for the rest, we just have to check the return of solve() every time. Note that there's no reason to copy the full list of current_path every time! That's expensive. You can just append to the end before the call to solve and pop afterwards:

else:
    for node in next_nodes:
        current_path.append(node)
        res = solve(maze, node, current_path)
        if res:
            return res
        current_path.pop()

Since current_path is what gets returned anyway, this can be simplified into just:

    for node in next_nodes:
        current_path.append(node)
        if solve(maze, node, current_path):
            return current_path:
        current_path.pop()

Now your usage is just:

>>> print solve(maze, Point(0,0), Point(2,0), [Point(0,0)])
[Point(0,0), ...]

Default values

Be very wary of having default values that are mutable. The canonical counterexample is something like:

def foo(x = []):
    x.append(1)
    return x

>>> foo()
[1]
>>> foo()
[1,1]
>>> foo()
[1,1,1]

Prefer to default to None. Then you can check it and assign it as appropriate:

def solve(maze, pos, exit, current_path = None):
    if current_path is None:
        current_path = [pos]

    next_nodes = [...]

What about other paths?

There may be more than one path. Let's return all of them. Or, rather than returning all of them, let's make this a generator. If the caller only wants one path, he can just take the first one!

def solve(maze, pos, exit, current_path = None):
    if current_path is None:
        current_path = [pos]
    if pos == exit:
        yield current_path # instead of return
    else:
        for node in neighbors(maze, pos):
            if node not in current_path:
                for result in solve(maze, node, exit, current_path + [node]):
                    yield result

A Path != Best Path

Depth-first search (what you're doing) will definitely find a path if it exists. But it won't necessary find the shortest one. Try out a few of the other path-finding algorithms. The direct corollary to DFS is Breadth-first search (which does exactly what it sounds like). And then there is a lot of room for optimization.