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

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 comm

StackExchange Code Review Q#1626, answer score: 4