Making a maze....

[Phil Schmidt]

I couldn't resist...
--------------------------------------------------

import random as rand

rand.seed()

opposite = {'north':'south', 'south':'north', 'east':'west', 'west':'east'}
adjacentcell = {'north': lambda x,y: (x,y-1),
                'south': lambda x,y: (x,y+1),
                'east' : lambda x,y: (x+1,y),
                'west' : lambda x,y: (x-1,y)}

class Cell:
    def __init__(self, canvas, x, y, grid, state='virgin'):
        self.canvas = canvas
        self.location = (x, y)
        x0 = 3 + x * grid.cellsize_x
        x1 = x0 + grid.cellsize_x
        y0 = 3 + y * grid.cellsize_y
        y1 = y0 + grid.cellsize_y
        self.coords = (x0, x1, y0, y1)
        self.state = state
        self.colors = {'virgin':'green',
                       'frontier':'brown',
                       'explored':'yellow'}
        self.walls = {}
        # display the cell
        x0, x1, y0, y1 = self.coords
        self.cell = self.canvas.create_rectangle(x0, y0, x1, y1,
                                                 fill=self.colors[self.state],
                                                 outline='')
        self.canvas.lower(self.cell)    # ensures the walls are all on top
        # make the walls
        self.walls['north'] = self.canvas.create_rectangle(x0-grid.borderwidth/2,
                                                           y0-grid.borderwidth/2,
                                                           x1+grid.borderwidth/2,
                                                           y0+grid.borderwidth/2,
                                                           fill='black')
        self.walls['south'] = self.canvas.create_rectangle(x0-grid.borderwidth/2,
                                                           y1-grid.borderwidth/2,
                                                           x1+grid.borderwidth/2,
                                                           y1+grid.borderwidth/2,
                                                           fill='black')
        self.walls['west'] = self.canvas.create_rectangle(x0-grid.borderwidth/2,
                                                          y0-grid.borderwidth/2,
                                                          x0+grid.borderwidth/2,
                                                          y1+grid.borderwidth/2,
                                                          fill='black')
        self.walls['east'] = self.canvas.create_rectangle(x1-grid.borderwidth/2,
                                                          y0-grid.borderwidth/2,
                                                          x1+grid.borderwidth/2,
                                                          y1+grid.borderwidth/2,
                                                          fill='black')
    def removeWall(self, wall):
        self.canvas.delete(self.walls[wall])
        del self.walls[wall]
    def changeState(self, state):
        self.canvas.itemconfigure(self.cell, fill=self.colors[state])
        self.state = state

class Grid:
    def __init__(self, canvas=None,
                 cellsize_x=10, cellsize_y=10,
                 gridsize_x=10, gridsize_y=10,
                 borderwidth=2):
        self.cellsize_x = cellsize_x
        self.cellsize_y = cellsize_y
        self.gridsize_x = gridsize_x
        self.gridsize_y = gridsize_y
        self.borderwidth = borderwidth
        if not canvas:
            # create the canvas and display it
            self.c = Canvas()
            self.c.pack()
        else:
            self.c = canvas
        self.c.configure(height = 3 + gridsize_y * cellsize_y + borderwidth,
                         width = 3 + gridsize_x * cellsize_x + borderwidth)
        self.c.update()
        # create cells
        self.cells = []
        for y in range(gridsize_y):
            row = []
            for x in range(gridsize_x):
                row.append(Cell(self.c, x, y, self))
            self.cells.append(row)
        # start with an empty frontier
        self.frontier = []
    def openExploration(self):
        # pick an initial cell to open the frontier
        start = rand.choice(rand.choice(self.cells))
        start.changeState('explored')
        return start.location
    def update(self):
        self.c.update()
    def isInArray(self, x, y):
        return x >= 0 and x < self.gridsize_x \
               and y >= 0 and y < self.gridsize_y
    def isExplored(self, x, y):
        if self.isInArray(x, y):
            return self.cells[y][x].state is 'explored'
        else:
            return False
    def isVirgin(self, x, y):
        if self.isInArray(x, y):
            return self.cells[y][x].state is 'virgin'
        else:
            return False
    def markFrontier(self, x, y):
        if self.isVirgin(x, y):
            self.cells[y][x].changeState('frontier')
            self.frontier.append(self.cells[y][x])
    def extendFrontier(self, x, y):
        self.markFrontier(x+1, y)
        self.markFrontier(x-1, y)
        self.markFrontier(x, y+1)
        self.markFrontier(x, y-1)

def MazeBuilder(grid):
    # pick an initial cell to open the frontier
    x, y = grid.openExploration()
    yield x, y

    # this is the main iteration loop
    while 1:
        # mark all the frontier cells
        grid.extendFrontier(x, y)
        # pick a random frontier cell, and open a random wall to an explored cell
        pick = rand.choice(grid.frontier)
        x, y = pick.location
        walls = ['north','south','east','west']
        rand.shuffle(walls)
        for wall in walls:
            x1, y1 = adjacentcell[wall](x, y)
            if grid.isExplored(x1, y1):
                # open the wall in the target cell
                pick.removeWall(wall)
                # and then the wall in the adjacent cell
                otherwall = opposite[wall]
                grid.cells[y1][x1].removeWall(otherwall)
                # mark the cell as explored
                pick.changeState('explored')
                # take the cell off the frontier list
                grid.frontier.remove(pick)
                break
        if grid.frontier:
            yield x,y
        else:
            return

for y in range(8):
    for x in range(8):
        c = Canvas()
        c.grid(column=x, row=y)
        
        # make a grid
        grid = Grid(c,
                    cellsize_x=8, cellsize_y=8,
                    gridsize_x=10, gridsize_y=10)

        # get the maze generator
        explorer = MazeBuilder(grid)

        while 1:
            grid.update()
            try:
                explorer.next()
            except StopIteration:
                break

c.mainloop()