# Generating a random maze using disjoint sets

I've had a go at writing something that generates a random maze using disjoint sets using the grouping class I found here.

The way I'm generating the maze is by generating all the cells, with each cell having a wall to the right of it and beneath it. Each wall can either be active or not.

I pick wall at random and look at the pair of cells on either side of it to see if they are in the same group (connected), if they are, I leave the wall, if they aren't, I destroy the wall, and join the groups the neighbouring cells belonged to.

This will continue until all the cells are connected. I'm then trying to print the maze, probably in a really horrible way.

I'd really like to get some feedback on anything I could be doing better. Is it possible to make the code more efficient? If I do a 1000*1000 maze, it takes a very long time to calculate.

import random
from grouper import Grouper
import sys

X = 20
Y = 20

class Cell():
"""Represents a cell in the maze, with an x and y coordinate and its
right hand wall and downwards wall.

"""
def __init__(self, x, y):
self.x, self.y = x, y
self.right_wall = self.down_wall = None

class Wall():
"""Represents a wall in the maze with its two neighbouring cells.
"""
def __init__(self):
self.neighbours = None
self.active = True

def popchoice(seq):
"""Takes an iterable and pops a random item from it.
"""
return seq.pop(random.randrange(len(seq)))

# A mapping of coord tuple to Cell object
cells = {}
# A list of all the non-edge walls
walls = []

# Generate cells
for y in range(Y):
for x in range(X):
cells[(x, y)] = Cell(x, y)

# Generate walls and add to the neighbouring cells
for y in range(Y):
for x in range(X):
current_cell = cells[(x,y)]
down_wall = Wall()
current_cell.down_wall = down_wall
right_wall = Wall()
current_cell.right_wall = right_wall
if y != Y-1:
down_wall.neighbours = (current_cell, cells[(x,y+1)])
walls.append(down_wall)

if x != X-1:
right_wall.neighbours = (current_cell, cells[(x+1,y)])
walls.append(right_wall)

# Get a list of all the cell objects to give to the Grouper
cell_list = [cells[key] for key in cells]

maze = Grouper(cell_list)

for _ in range(len(walls)):
# Pop a random wall from the list and get its neighbours
wall = popchoice(walls)
cell_1, cell_2 = wall.neighbours
# If the cells on either side of the wall aren't already connected,
# destroy the wall
if not maze.joined(cell_1, cell_2):
wall.active = False
maze.join(cell_1, cell_2)

# Draw the maze

maze_map = []

x_max = (X*2)+1
y_max = (Y*2)+1

# Make an empty maze map with True for wall and False for space
# Make top wall
maze_map.append([True for _ in range(x_max)])
for y in range(1, y_max):
# Make rows with left side wall
maze_map.append([True]+[False for _ in range(1, x_max)])

# Add the down and right walls from each cell to the map
for coords, cell in cells.items():
x, y = coords
# Add the intersection wall for each cell (down 1 right 1)
maze_map[(y*2)+2][(x*2)+2] = True
if cell.right_wall.active:
maze_map[(y*2)+1][(x*2)+2] = True
if cell.down_wall.active:
maze_map[(y*2)+2][(x*2)+1] = True

def output(string):
sys.stdout.write(string)

# Print the map
for row in maze_map:
for tick in row:
if tick: output('X'),
else: output('.'),
output('\n')


It gives a maze like this:

XXXXXXXXXXXXXXXXXXXXX
X.......X...X.X.X...X
XXX.XXXXXXX.X.X.X.XXX
X.X...............X.X
X.XXXXXXXXX.XXXXX.X.X
X...X...X.X.X.......X
X.XXXXX.X.X.XXXXXXXXX
X.X.X.....X...X...X.X
X.X.XXX.XXX.XXXXX.X.X
X.X...X.........X...X
X.XXX.XXX.X.XXX.X.XXX
X...X.X.X.X.X.X.X.X.X
XXX.X.X.XXX.X.XXX.X.X
X.................X.X
XXXXX.XXX.XXXXX.X.X.X
X...X.X.X.X...X.X.X.X
XXX.XXX.X.XXX.X.XXX.X
X.X...X...X.....X...X
X.X.X.XXX.X.X.XXX.X.X
X...X.....X.X.....X.X
XXXXXXXXXXXXXXXXXXXXX


import random
from grouper import Grouper
import sys

X = 20
Y = 20

class Cell():


Either put object as the base class, or don't include the (). It doesn't really matter, but I think this is ugly.

    """Represents a cell in the maze, with an x and y coordinate and its
right hand wall and downwards wall.

"""
def __init__(self, x, y):
self.x, self.y = x, y
self.right_wall = self.down_wall = None

class Wall():
"""Represents a wall in the maze with its two neighbouring cells.
"""
def __init__(self):
self.neighbours = None
self.active = True

def popchoice(seq):
"""Takes an iterable and pops a random item from it.
"""
return seq.pop(random.randrange(len(seq)))


Call it pop_choice so that you don't have guess where one word begins and the other exists. Also it takes a sequence not an iterable

# A mapping of coord tuple to Cell object
cells = {}


I recommend looking at numpy. It has an array type. Basically, you can create an array like: cells = numpy.array( (Y,X), object) which will provide an efficent 2d array structure. That would be nicer to work with and faster then the dictionary you are using.

# A list of all the non-edge walls
walls = []

# Generate cells
for y in range(Y):
for x in range(X):
cells[(x, y)] = Cell(x, y)


You shouldn't do logic and loops in module scope. They are slower there then in functions.

# Generate walls and add to the neighbouring cells
for y in range(Y):
for x in range(X):
current_cell = cells[(x,y)]
down_wall = Wall()
current_cell.down_wall = down_wall
right_wall = Wall()
current_cell.right_wall = right_wall
if y != Y-1:
down_wall.neighbours = (current_cell, cells[(x,y+1)])
walls.append(down_wall)

if x != X-1:
right_wall.neighbours = (current_cell, cells[(x+1,y)])
walls.append(right_wall)


You create Walls in every case, but only sometimes add them to walls. This suggests either a bug or a misnamed walls variable.

# Get a list of all the cell objects to give to the Grouper
cell_list = [cells[key] for key in cells]


If using dict, this is the same as cell_list = cells.values() If you use numpy arrays like I suggest its cell_list = cells.flatten()

maze = Grouper(cell_list)


This variable really isn't holding the maze. Calling it maze is misleading

for _ in range(len(walls)):
# Pop a random wall from the list and get its neighbours
wall = popchoice(walls)
cell_1, cell_2 = wall.neighbours
# If the cells on either side of the wall aren't already connected,
# destroy the wall
if not maze.joined(cell_1, cell_2):
wall.active = False
maze.join(cell_1, cell_2)


random.shuffle(walls)
for wall in walls:
cell_1, cell_2 = wall.neighbours
...


That'll be more efficient and is clearer.

# Draw the maze

maze_map = []

x_max = (X*2)+1
y_max = (Y*2)+1


Its not clear why you need x_max, a comment would be helpful explaining that

# Make an empty maze map with True for wall and False for space
# Make top wall
maze_map.append([True for _ in range(x_max)])
for y in range(1, y_max):
# Make rows with left side wall
maze_map.append([True]+[False for _ in range(1, x_max)])


Here is another case that can really use numpy's ndarrays:

maze_map = numpy.zeros( (x_max, y_max), bool)
maze_map[0,:] = True
maze_map[:,0] = True


That does the same as all your maze_map code so far. Also, calling maze_map, blocked or something would make it clearer why you are putting True/False in it.

# Add the down and right walls from each cell to the map
for coords, cell in cells.items():
x, y = coords
# Add the intersection wall for each cell (down 1 right 1)
maze_map[(y*2)+2][(x*2)+2] = True
if cell.right_wall.active:
maze_map[(y*2)+1][(x*2)+2] = True
if cell.down_wall.active:
maze_map[(y*2)+2][(x*2)+1] = True


The formula being used to figure out which cells are being reference is kinda hard to figure out.

def output(string):
sys.stdout.write(string)

# Print the map
for row in maze_map:
for tick in row:
if tick: output('X'),
else: output('.'),
output('\n')


The following might be a clearer version for drawing:

def output(blocked):
sys.stdout.write(".*"[blocked])

for x in range(2*X+1):
output(True)
sys.stdout.write('\n')

for y in range(Y):
output(True)
for x in range(X):
cell = cells[(x,y)]
output(False)
output(cell.right_wall.active)
sys.stdout.write('\n')
output(True)
for x in range(X):
cell = cells[(x,y)]
output(cell.down_wall.active)
output(True)
sys.stdout.write('\n')


I think its a bit clearer because it doesn't have formulas like 2*x+1. It needs more comment but I trust you can handle that.

EDIT

For numpy, use it like this:

cells = numpy.empty( (X,Y), object)
# object is the python object type, not the object you want to put into it
# python's default is to use a number types which are more efficient
# but we aren't storing numbers
for x, y in numpy.ndindex(X, Y):
cell[index] = Cell(x,y)


Speed:

The biggest time-consumer in the code is the grouper code. That code has opted to implemented the simpler rather then more efficient algorithm for the task. You should really implememt the union-find algorithm. That algorithm is crazy efficient, running in for what is all intents and purposes constant time.

Memory:

If memory is a concern, add slots to your classes. Look up the documentation for how to do it. However, I wouldn't bother unless you are really running out of memory.

• Thank you so much for the amazing review! I've implemented all of your suggestions: here. I didn't quite understand how to use numpy arrays. I wanted to make an empty array to append my cells to, but it wouldn't let me make an array without giving it an object. I've also been trying to make the script more efficient. Here's the result of cProfile with the version linked above: benchmark. I then tried a different way of making the walls: script + benchmark. A bit faster. – Acorn Apr 3 '11 at 12:40
• @Acrorn, I've responded to your additional questions in the edit – Winston Ewert Apr 3 '11 at 13:52
• @Acorn, as an aside you should checkout code.google.com/p/jrfonseca/wiki/Gprof2Dot, it draws a graph showing what your code is doing and make it much easier to see where performance problems lie. – Winston Ewert Apr 3 '11 at 13:53
• imagebin.org/146412 for an example – Winston Ewert Apr 3 '11 at 13:55
• @Acorn, I've reworked your code into a version as optimized as I can do: pastebin.com/J5Ny83vU The union-find code is taking up the bulk of the running time. The only thing left would be to implement the union-find algorithm in C and use it as an extension module. – Winston Ewert Apr 3 '11 at 19:16