Path finding algorithm using recursion in Python

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- 1, coor),
(coor,coor-1),
(coor, coor + 1),
(coor + 1, coor)
]
possible_paths = []

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

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

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

pos = paths
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)])
# 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.

• Hi! Welcome to Code Review. Good Job on your first post! – TheCoffeeCup Jan 21 '16 at 20:23

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 and what is path? 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)
)

if 0 <= p.x < len(maze) 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, 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):
...


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:
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()


>>> 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()

>>> 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 = [...]


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.

• Thanks for this nice answer. I am very new to algorithms, even this is my first implementation of search. Now for the answer, you say using generators is a better approach to Depth-first search algorithms ? – Rockybilly Jan 22 '16 at 1:15
• And shouldn't I use .next() with the print function to return the answer ? – Rockybilly Jan 22 '16 at 1:33
• @Rockybilly Generators are very useful everywhere, it's not specific to this problem. I don't understand your second question. – Barry Jan 22 '16 at 2:39
• When I call the function with print, it returns a generator object. But if I use solve (arguments).next () it gives the answer. That is what I tried to ask. – Rockybilly Jan 22 '16 at 2:41
• I got one more question. In the implementation of this algorithm, is this how you would do it, or you just derived this from just correcting mine ? If not, how would you implement this in python ? – Rockybilly Jan 22 '16 at 15:46