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 randomfrom grouper import Grouperimport sysX = 20Y = 20class 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 = Noneclass Wall():    Represents a wall in the maze with its two neighbouring cells.        def __init__(self):        self.neighbours = None        self.active = Truedef 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 wallswalls = []# Generate cellsfor y in range(Y):    for x in range(X):        cells[(x, y)] = Cell(x, y)# Generate walls and add to the neighbouring cellsfor 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 mazemaze_map = []x_max = (X*2)+1y_max = (Y*2)+1# Make an empty maze map with True for wall and False for space# Make top wallmaze_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 mapfor 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] = Truedef output(string):    sys.stdout.write(string)# Print the mapfor row in maze_map:    for tick in row:        if tick: output('X'),        else: output('.'),    output('\n')It gives a maze like this:XXXXXXXXXXXXXXXXXXXXXX.......X...X.X.X...XXXX.XXXXXXX.X.X.X.XXXX.X...............X.XX.XXXXXXXXX.XXXXX.X.XX...X...X.X.X.......XX.XXXXX.X.X.XXXXXXXXXX.X.X.....X...X...X.XX.X.XXX.XXX.XXXXX.X.XX.X...X.........X...XX.XXX.XXX.X.XXX.X.XXXX...X.X.X.X.X.X.X.X.XXXX.X.X.XXX.X.XXX.X.XX.................X.XXXXXX.XXX.XXXXX.X.X.XX...X.X.X.X...X.X.X.XXXX.XXX.X.XXX.X.XXX.XX.X...X...X.....X...XX.X.X.XXX.X.X.XXX.X.XX...X.....X.X.....X.XXXXXXXXXXXXXXXXXXXXXX
Generating a random maze using disjoint sets
python
import randomfrom grouper import Grouperimport sysX = 20Y = 20class 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 = Noneclass Wall():    Represents a wall in the maze with its two neighbouring cells.        def __init__(self):        self.neighbours = None        self.active = Truedef 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 wallswalls = []# Generate cellsfor 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 cellsfor 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 misleadingfor _ 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 mazemaze_map = []x_max = (X*2)+1y_max = (Y*2)+1Its 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 wallmaze_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,:] = Truemaze_map[:,0] = TrueThat 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 mapfor 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] = TrueThe 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 mapfor 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.EDITFor 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 numbersfor 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.