Maze Generator

mazy.py

"""
Maze Generator.

Based on discussion here:
http://www.mazeworks.com/mazegen/mazetut/index.htm
"""

from random import randrange, choice


class Maze(object):
    """
    The maze object.

    Generates a random maze
    """

    def __init__(self, rows=10, cols=10, autoGen=True):
        """
        @param rows: The number of rows in the maze
        @param cols: The number of columns in the maze
        @param autoGen: If True, runs L{self.genPath} on init
        """
        self.rows, self.cols = rows, cols
        self.initCells()

        if autoGen:
            self.genPath()

    def initCells(self):
        """
        Initializes all cells in the maze with borders around edges and all
        inter cells walls up.
        """
        self.maze = []
        for r in range(self.rows):
            row = []
            rowBorder = 'N' if r==0 else 'S' if r==self.rows-1 else ''
            for c in range(self.cols):
                borders = rowBorder + ('W' if c==0 else 'E' if c==self.cols-1 \
                                       else '')
                cell = {'walls': 'NESW', 'borders': borders}
                row.append(cell)
            self.maze.append(row)

    def cell(self, x, y):
        """
        Returns the cell at position x, y
        """

        return self.maze[y][x]

    def neighbors(self, cell):
        """
        Returns a list of neighbors to cell.

        A neighbor is defined as an (x,y) tuple.
        """
        n = []
        x,y = cell
        # The neighbor to the north if any
        if y>0:
            n.append((x, y-1))
        # The neighbor to the east if any
        if x<self.cols-1:
            n.append((x+1, y))
        # The neighbor to the south if any
        if y<self.rows-1:
            n.append((x, y+1))
        # The neighbor to the west if any
        if x>0:
            n.append((x-1, y))

        return n
    
    def neighborsWithAllWalls(self, cell):
        """
        Returns a list (possibly empty) of all neighbors of cell that have all
        four walls in tact.
        """
        neighbors = []
        # Check all wals for the neighbors of this cell
        for n in self.neighbors(cell):
            c,r = n
            if self.maze[r][c]['walls'] == 'NESW':
                neighbors.append(n)
        return neighbors

    def knockDownWall(self, cell1, cell2):
        """
        Knocks down the walls between two adjacent cells.

        The relative position between the cells are not known, so this needs to
        be determined.
        """
        x1,y1 = cell1
        x2,y2 = cell2

        w = ''
        # Is cell2 north of cell1?
        if y2==(y1-1):
            w = 'NS'    # Knock down cell1 N wall and cell2 S wall
        # cell2 east of cell1?
        elif x1==(x2-1):
            w = 'EW'
        # cell2 south of cell1
        elif y1==(y2-1):
            w = 'SN'
        # cell2 west or cell1?
        elif x2==(x1-1):
            w = 'WE'
        assert w != '', "Cells are not adjacent: %s, %s" % (cell1, cell2)

        # Remove the cell1 wall
        cell = self.cell(*cell1)
        cell['walls'] = cell['walls'].replace(w[0], '')
        # Remove the cell2 wall
        cell = self.cell(*cell2)
        cell['walls'] = cell['walls'].replace(w[1], '')

    def genPath(self, start=(0,0)):
        """
        Generates the path through the maze, starting at position start.

        @param start: an (x,y) tuple for the cell to start at. Pass None to
               select a random, or leave the default to start at (0,0)
               (top-left)
        """
        # If start is none, we need to select a random start point
        if start is None:
            start = (randrange(0, self.cols), randrange(0, self.rows))
        
        # Set up the callstack and other counters
        callStack = []
        totalCells = self.rows * self.cols
        currCell = start
        visited = 1

        # Visit each cell
        while visited < totalCells:
            # Find all neighbors will all walls in tact
            neighbors = self.neighborsWithAllWalls(currCell)
            # Found any?
            if len(neighbors):
                # Choose a random one
                neighbor = choice(neighbors)
                # Knock down the walls between currCell and neighbor
                self.knockDownWall(currCell, neighbor)
                # Push current cell onto the stack
                callStack.append(currCell)
                # Neighbor now become current cell
                currCell = neighbor
                # Update visited
                visited += 1
            else:
                # Get the last cell back from the stack and make it current cell
                currCell = callStack.pop()
            
    def __str__(self):
        res = ''
        for r in self.maze:
            l1 = l2 = ''
            for c in r:
                v = '#' if 'W' in c['walls'] else ' '
                h1 = "#" if v=='#' else '#'
                h2 = '#' if 'N' in c['walls'] else ' '
                l1 += '%s%s' % (h1, h2)
                l2 += '%s ' % (v)
            l1 += '%s' % ("#" if 'E' in c['walls'] else ' ')
            l2 += '%s' % ('#' if 'E' in c['walls'] else ' ')
            res += '%s\n%s\n' % (l1, l2)

        return res