Introduction
There are a few maze solving algorithms out there. Some are more efficient then others, but many have been around for a while. Like any other subject Wikipedia has a nice summary of the subject. What we are going to do in this post is solving a maze using Python3. The maze is represented by a 2 dimensional array like this:
m = [[1, 1, 1, 1, 1, 1, 1],
[0, 0, 1, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 1, 1],
[1, 0, 1, 1, 0, 1, 1],
[1, 0, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1]]
Thinking about the problem
If we put a side code and algorithms, and just try to think about how to solve a maze we can come up with a few strategies. The most basic one would be to not really have a strategy, so it would be:
- walk straight until we reach an intersection.
- on that intersection randomly pick a path.
- if we get to a dead end go back to the last intersection and repeat.
This is called the “random mouse” strategy, which is not very efficient.
A more well known efficient strategy is the “Wall follower”. This basically means that the player (whoever solves the maze), picks a “wall” and stick to it. So, for example if we decide we are always taking the left side wall, we simply walk along that wall until we reach the exit.
For any algorithm the concept is the same, continue and if you get to a dead end, get back to the last intersection.
Using an algorithm
When we think about the last sentence, we understand that a route along a maze could be represented as a tree. Every intersection would be a node and every path going from this intersection would be a branch. Of course, that branch can later have more intersections branching out the tree even further.
For that reason we are going to use the “Depth first algorithm”. The algorithm uses a stack (if you don’t know what a stack is go and read this). So, first every option is inserted into the stack. Then, the latest option is popped out and walked. This mimics what we talked about earlier, walk until a dead end and go back to the latest intersection. Let’s imagine our stack looks like this:
[ Left (1, 3) ]
[ Right (1, 3) ]
[ Up (0, 3) ]
[ Up (1, 3) ]
[ Left (4, 1) ]
Each value represents an option in an intersection.
Let’s say we pop the first option and take a left at 1, 3.
Great. Now let’s say we hit a dead end. The next option on the stack would be [ Right (1, 3) ], which exactly means going back to the latest intersection and take the path non taken.
Now, let’s look how this works in code.
Coding it
Alright, first of all, because we are not a person (or a mouse) we need to mark where we have already been.
def solve_maze(maze, startX, startY, endX, endY):
visited = []
for x, line in enumerate(maze):
visited.append([])
for cell in line:
visited[x].append(cell)
visited[startX][startY] = 2
currX = startX
currY = startY
This is copying the 2d array. Then mark the visited point (the starting point) with a 2.
We are also initializing currX and currY to represent where the solver currently is.
Every list in python can be used as a stack, so nothing fancy, but yet our stack:
....
visited[startX][startY] = 2
currX = startX
currY = startY
options = []
For ease of use I also defined a Point class
class Point:
def __init__(self, x, y):
self.x = x
self.y =y
Now we have to put all the options into the stack for every step. For each point we have to check the points next to it so x+1, x-1, y+1, y-1. Of course we also have to check that:
- we are not out of bounds
- that we are not hitting a wall
- that the point have not been already visited (we mark visited with 2).
Here’s how it looks like:
....
options = []
while currX != endX or currY != endY:
if currX+1 < len(maze[currX]) and maze[currX+1][currY] == 0 and visited[currX+1][currY] !=2:
options.append(Point(currX+1, currY))
if currX-1 >= 0 and maze[currX-1][currY] == 0 and visited[currX-1][currY] !=2:
options.append(Point(currX-1, currY))
if currY+1 < len(maze[currX]) and maze[currX][currY+1] == 0 and visited[currX][currY+1] !=2:
options.append(Point(currX, currY+1))
if currY-1 >= 0 and maze[currX][currY-1] == 0 and visited[currX][currY-1] !=2:
options.append(Point(currX, currY-1))
if len(options) == 0: # no options means nowhere to go
return None
Alright! Now for the walking part:
go_to_point = options.pop()
currX = go_to_point.x
currY = go_to_point.y
visited[currX][currY] = 2
return visited
As you can see we are returning the visited array, that will show the maze and the walked part.
Here’s the whole function:
def solve_maze(maze, startX, startY, endX, endY):
visited = []
for x, line in enumerate(maze):
visited.append([])
for cell in line:
visited[x].append(cell)
visited[startX][startY] = 2
currX = startX
currY = startY
options = []
while currX != endX or currY != endY:
if currX+1 < len(maze[currX]) and maze[currX+1][currY] == 0 and visited[currX+1][currY] !=2:
options.append(Point(currX+1, currY))
if currX-1 >= 0 and maze[currX-1][currY] == 0 and visited[currX-1][currY] !=2:
options.append(Point(currX-1, currY))
if currY+1 < len(maze[currX]) and maze[currX][currY+1] == 0 and visited[currX][currY+1] !=2:
options.append(Point(currX, currY+1))
if currY-1 >= 0 and maze[currX][currY-1] == 0 and visited[currX][currY-1] !=2:
options.append(Point(currX, currY-1))
if len(options) == 0: # no options means nowhere to go
return None
go_to_point = options.pop()
currX = go_to_point.x
currY = go_to_point.y
visited[currX][currY] = 2
return visited
Ok, great!
I wrote a little function to print the maze to the terminal, so we can look at the path the algorithm took.
I’m using the colored library that you can easily pip install.
def print_maze(maze):
for line in maze:
print(' ', end='')
for cell in line:
if cell == 1:
print(colored('##', 'red'), end='')
elif cell == 0:
print(' ', end='')
else:
print(colored('**', 'green'), end='')
print('\n', end='')
Now we can run our function
def main():
visited = solve_maze(m, 1, 0, 4, 6)
print_maze(visited)
if __name__ == '__main__':
main()
And here’s the result!
Conclusion
We solved our maze using the Depth first algorithm then we printed it to the terminal. Cool right?
On the next post, we’ll try to generate mazes and also take on a different approach for solving the maze.
Until next time!
