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)


Do it like this instead:

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.