Welcome back!
This is part 2 of “Be a-maze-d”! You can read all about part 1 right here.
To sum up what we did in part 1:
- We talked about some maze solving algorithms
- We talked about depth first search
- We implemented a depth first search for solving a maze
- We created a nice colorful printing function
Automating maze generation
Ok, great, we solved our hand crafted maze.. But I’m sure no one really wants to create mazes using 0 and 1. Also, in order to test our beautiful implementation we will need many mazes. In the end, like any thing more or less, we want to automate the maze generation.
We can use more or less the same logic we used for solving the maze, but the conditions would be a bit different. Instead of just seeing where we can go and where we were, we need to check that we are not making the walls disappear. Of course we also need to check if we are out of bounds.
Jumping into the code
Our function would get a size for the maze, and initialize a 2d array all with ones.
def generate_maze(size):
maze = []
# initialize our matrix
for i in range(0, size):
maze.append([])
for j in range(0, size):
maze[i].append(1)
Let’s randomize the starting and ending point.
startX = 1
startY = 1
endX = 1
endY = 1
# create a random starting point and ending point
while startX == endX or startY == endY or abs(startX - endX) < (size/2) or abs(startY - endY) < (size/2):
random.seed()
startX = random.randint(1, size-2)
startY = random.randint(1, size-2)
endX = random.randint(1, size-2)
endY = random.randint(1, size-2)
Note that we are using the abs function to determine whether our starting and ending points are too close.
Cool, now let’s use the same approach we used for solving the maze and see what’s missing.
# Wrong code, do not use!
....
options = []
maze[currX][currY] = 0
# start creating the maze halls
while (currY != endY or currX != endX):
if currX > 1 and maze[currX-1][currY] != 0: # left
options.append(Point(currX-1, currY))
if currX + 2 < size and maze[currX+1][currY] != 0: # right
options.append(Point(currX+1, currY))
if currY +2 < size and maze[currX][currY+1] != 0: # up
options.append(Point(currX, currY+1))
if currY > 1 and maze[currX][currY-1] != 0: # down
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
maze[currX][currY] = 0
return maze
I incremented the boundary check, so we don’t go over the outer walls.
Instead of currX > 0 there’s currX > 1. Great, so that’s one problem solved.
Other than that the code looks pretty much the same.
Let’s print the maze and see what we get.
def main():
maze = generate_maze(20)
print_maze(maze)
This is what I got:
Of course, that’s no good.. We want walls. Let’s add validation that we don’t destroy walls. Note that if we add the wall checking where we now check for the options, that’s not good enough. Let’s do that and see what happens.
# Wrong code, do not use!
...
while (currY != endY or currX != endX):
if currX > 1 and maze[currX-1][currY] != 0 and maze[currX-2][currY] != 0: # left
options.append(Point(currX-1, currY))
if currX + 2 < size and maze[currX+1][currY] != 0 and maze[currX+2][currY] != 0: # right
options.append(Point(currX+1, currY))
if currY +2 < size and maze[currX][currY+1] != 0 and maze[currX][currY+2] != 0: # up
options.append(Point(currX, currY+1))
if currY > 1 and maze[currX][currY-1] != 0 and maze[currX][currY-2] != 0: # down
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
maze[currX][currY] = 0
return maze
So we added a check that the next next cell is also not 0.
That didn’t change a lot:
This is for two reasons:
- We actually need to check all neighboring cells and not just the next.
- We check for the cell when we analyze the options, that means that - we actually write the 0 the maze could already look different.
Let’s fix that.
# Still wrong code, do not use!
...
# start creating the maze halls
while (currY != endY or currX != endX):
if currX > 1 and maze[currX-1][currY] != 0: # left
options.append(Point(currX-1, currY))
if currX + 2 < size and maze[currX+1][currY] != 0: # right
options.append(Point(currX+1, currY))
if currY +2 < size and maze[currX][currY+1] != 0: # up
options.append(Point(currX, currY+1))
if currY > 1 and maze[currX][currY-1] != 0: # down
options.append(Point(currX, currY-1))
if len(options) == 0: # no options means nowhere to go
return maze
go_to_point = options.pop()
zeros = 0
while True:
if maze[go_to_point.x-1][go_to_point.y] == 0:
zeros+=1
if maze[go_to_point.x+1][go_to_point.y] == 0:
zeros+=1
if maze[go_to_point.x][go_to_point.y+1] == 0:
zeros+=1
if maze[go_to_point.x][go_to_point.y-1] == 0:
zeros+=1
if zeros == 1:
break
if len(options) == 0:
break
go_to_point = options.pop()
currX = go_to_point.x
currY = go_to_point.y
maze[currX][currY] = 0
return maze
Alrighty, what we are doing here is checking how many zeros we have in the surroundings of the next point. Having just 1 zero makes sense, because we are just coming from a neighboring cell. Other than that neighboring cell we want all others to have a 1, creating the wall effect.
Let’s see how this looks when we print it to the terminal:
Looks much better, but still not a maze.
Why does it look like this?
Well, since our option analyzing always works in the same order, we’ll always get this “snaking trail” sort of shape.
The code would always try first to go left, then right, up, down. This worked great when we tried to solve the maze, but now in order to create the maze we have to do something else.
We need our code to create some dead ends. This can be done by adding a little randomization to the path we choose.
Instead of popping from the options like a stack we’ll try a random option.
...
random.seed()
rand_opt = random.randint(0, len(options)-1)
go_to_point = options.pop(rand_opt)
while True:
zeros = 0
if maze[go_to_point.x-1][go_to_point.y] == 0:
zeros+=1
if maze[go_to_point.x+1][go_to_point.y] == 0:
zeros+=1
if maze[go_to_point.x][go_to_point.y+1] == 0:
zeros+=1
if maze[go_to_point.x][go_to_point.y-1] == 0:
zeros+=1
if zeros == 1:
break
if len(options) == 0:
break
rand_opt = random.randint(0, len(options)-1)
go_to_point = options.pop(rand_opt)
currX = go_to_point.x
currY = go_to_point.y
maze[currX][currY] = 0
As you can see, instead of just popping the last option the code now pops a random option from the options array. This code has a bit of a problem though, sometimes the finishing point is surrounded by zeros and the code can’t generate the maze to get to it. Since this doesn’t happen a lot we can do something like a retry. Anyway, we get something that looks more like a maze (I added @@ as the starting point and && as the end):
Doesn’t look too bad, doesn’t it?
It’s definitely something we can try and give our maze solver code.
Right now the function just returns the 2d array, but we need it to return the maze. Let’s remember how the solve maze function signature looks like:
def solve_maze(maze, startX, startY, endX, endY):
And create a Maze class that we can return from generate_maze function.
class Maze:
def __init__(self, matrix, startX, startY, endX, endY):
self.matrix = matrix
self.startX = startX
self.startY = startY
self.endX = endX
self.endY = endY
Use the class in our generate_maze function.
....
currX = go_to_point.x
currY = go_to_point.y
maze[currX][currY] = 0
return Maze(maze, startX, startY, endX, endY)
The entire function now looks like this:
def generate_maze(size):
maze = []
# initialize our matrix
for i in range(0, size):
maze.append([])
for j in range(0, size):
maze[i].append(1)
startX = 1
startY = 1
endX = 1
endY = 1
# create a random starting point and ending point
while startX == endX or startY == endY or abs(startX - endX) < (size/2) or abs(startY - endY) < (size/2):
random.seed()
startX = random.randint(1, size-2)
startY = random.randint(1, size-2)
endX = random.randint(1, size-2)
endY = random.randint(1, size-2)
currX = startX
currY = startY
options = []
maze[currX][currY] = 0
# start creating the maze halls
while (currY != endY or currX != endX):
if currX > 1 and maze[currX-1][currY] != 0: # left
options.append(Point(currX-1, currY))
if currX + 2 < size and maze[currX+1][currY] != 0: # right
options.append(Point(currX+1, currY))
if currY +2 < size and maze[currX][currY+1] != 0: # up
options.append(Point(currX, currY+1))
if currY > 1 and maze[currX][currY-1] != 0: # down
options.append(Point(currX, currY-1))
if len(options) == 0: # no options means nowhere to go
return None
random.seed()
rand_opt = random.randint(0, len(options)-1)
go_to_point = options.pop(rand_opt)
while True:
zeros = 0
if maze[go_to_point.x-1][go_to_point.y] == 0:
zeros+=1
if maze[go_to_point.x+1][go_to_point.y] == 0:
zeros+=1
if maze[go_to_point.x][go_to_point.y+1] == 0:
zeros+=1
if maze[go_to_point.x][go_to_point.y-1] == 0:
zeros+=1
if zeros == 1:
break
if len(options) == 0:
break
rand_opt = random.randint(0, len(options)-1)
go_to_point = options.pop(rand_opt)
currX = go_to_point.x
currY = go_to_point.y
maze[currX][currY] = 0
return Maze(maze, startX, startY, endX, endY)
Quite a large function! Actually, it has more complexity than the solving code.
I made some minor changes to the solving code, so we could the start and the end of the maze:
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] = 3
currX = startX
currY = startY
options = []
while currX != endX or currY != endY:
if currX+1 < len(maze[currX]) and maze[currX+1][currY] != 1 and visited[currX+1][currY] < 2:
options.append(Point(currX+1, currY))
if currX-1 >= 0 and maze[currX-1][currY] != 1 and visited[currX-1][currY] < 2:
options.append(Point(currX-1, currY))
if currY+1 < len(maze[currX]) and maze[currX][currY+1] != 1 and visited[currX][currY+1] < 2:
options.append(Point(currX, currY+1))
if currY-1 >= 0 and maze[currX][currY-1] != 1 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
visited[endX][endY] = 4
return visited
Let’s paste everything together in the main function:
def main():
size = 20
maze = generate_maze(size)
while maze == None:
maze = generate_maze(size)
solved = solve_maze(maze.matrix, maze.startX, maze.startY, maze.endX, maze.endY)
if solved == None:
print("Can't solve maze")
print_maze(maze.matrix)
return
print_maze(solved)
And see what we got:
Great! We managed to generate a maze and solve it!
You can run the code a few times see a few different solved mazes.
Concluding part 2
If you want the entire code it’s in this gist.
I mentioned in part 1 that in this part I’m going to show another approach to solving the maze. However… This post got pretty long and it kind of makes sense to pause right here. So…..
Please, stay tuned for Be-a-maze-d part 3 !!!
