9
\$\begingroup\$

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

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

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.

\$\endgroup\$
  • \$\begingroup\$ 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 ? \$\endgroup\$ – Rockybilly Jan 22 '16 at 1:15
  • \$\begingroup\$ And shouldn't I use .next() with the print function to return the answer ? \$\endgroup\$ – Rockybilly Jan 22 '16 at 1:33
  • \$\begingroup\$ @Rockybilly Generators are very useful everywhere, it's not specific to this problem. I don't understand your second question. \$\endgroup\$ – Barry Jan 22 '16 at 2:39
  • \$\begingroup\$ 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. \$\endgroup\$ – Rockybilly Jan 22 '16 at 2:41
  • \$\begingroup\$ 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 ? \$\endgroup\$ – Rockybilly Jan 22 '16 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.