Maze.py

Overview

A Python implementation of a maze generator which demonstrates the use of classes.

Script

#!/usr/bin/env python

# $Id: maze.py,v 1.2 2000/12/12 19:45:01 tlavoie Exp tlavoie $
# $Log: maze.py,v $
# Revision 1.2  2000/12/12 19:45:01  tlavoie
# Last save before changing self.cells from a list to a dictionary.
#

import sys, random

def debug(x):
       pass
    #print 'DEBUG: ' + `x`
    #sys.stdout.flush()


class MazeCell:
    "Class which defines a single cell in an n-dimensional maze"

    def __init__ (self, size=4):
        self.numNeighbours = size  # will be changed when initialized by maze routine
        self.currState = 0        # 0 is out, 1 is frontier, 2 is in.  This is used for Prim's algorithm.
        self.myNeighbours = []
        self.myWalls = {}

    def stateFrontier(self):
        if(self.currState == 0):
            self.currState = 1
            return(1)   # used to decide whether or not maze code should increment  frontier counter.
        else:
            return(None)


    def stateIn(self):
        self.currState = 2
        #  Incrementing "out" neighbours to "frontier" state will be handled by maze code, not here.

class PrimMaze:
    "Creates a maze using Prim's algorithm"
    def __init__(self):
        self.frontiers = {}   # keep a dict of current frontier cells.
        self.cells = {}          # Store cell data here...
        self.opposites = {}        # create a list of "return" paths since cell walls map both ways.
        self.height = 0
        self.width = 0

    def genPrim(self):
        currCell = random.randint(0,len(self.cells))
        self.cells[currCell].stateIn()
        debug('cell ' + `currCell` + ' now IN')
        for i in range(self.cells[0].numNeighbours):
            thisNeigh = self.cells[currCell].myNeighbours[i]
            if(thisNeigh != -1):
                if(self.cells[thisNeigh].stateFrontier() == 1):
                    self.frontiers[thisNeigh] = 1
                    debug('cell ' + `thisNeigh` + ' now FRONTIER')

        # Now, if there are any frontier cells, pick one, give it a path to an 'IN' cell,  and make it IN also.
        while(len(self.frontiers) > 0):
            debug('frontier cells: ' + `self.frontiers`)
            nextCell = self.frontiers.keys()[random.randint(0,len(self.frontiers.keys()) -1)]
            debug('cell ' + `nextCell` + ' is NEXT')
            foundIn = 0
            # Now, pick a neighbour who's IN, at random
            while(foundIn == 0):
                myPalRef = random.randint(0, len(self.cells[nextCell].myNeighbours) - 1)
                myPal = self.cells[nextCell].myNeighbours[myPalRef]
                if (myPal != -1):
                    debug('cell ' + `myPal` + ' is my pal')
                    if(self.cells[myPal].currState == 2):
                        foundIn = 1

           # OK, we've got a route out to the existing maze. Move own state to IN
            self.cells[nextCell].stateIn()
            # break down walls
            # debug('BAD WALL: ' + `self.cells[nextCell].myWalls[myPal]`)
            debug('BAD WALL1: ' + `myPalRef`)
            debug('BAD WALL2: ' + `self.opposites[myPalRef]`)
            debug('nextCell walls: ' + `self.cells[nextCell].myWalls`)
            del self.cells[nextCell].myWalls[myPalRef]
            del self.cells[myPal].myWalls[self.opposites[myPalRef]]

            # update OUT neighbours to FRONTIER
            currCell = nextCell
            for i in range(self.cells[0].numNeighbours):
                thisNeigh = self.cells[currCell].myNeighbours[i]
                if(thisNeigh != -1):
                    if(self.cells[thisNeigh].stateFrontier() == 1):
                        self.frontiers[thisNeigh] = 1
                        debug('cell ' + `thisNeigh` + ' now FRONTIER')

            # remove currCell from frontiers{}
            del self.frontiers[currCell]

    def ortho(self, x=10, y=10):
        self.width = x
        self.height = y

        # Define wall-mapping for this maze geometry.
        self.opposites[0] = 2
        self.opposites[1] = 3
        self.opposites[2] = 0
        self.opposites[3] = 1

        # Create basic stuff prior to maze generation
        counter = 0
        for i in range(y):
            sys.stdout.flush()
            for j in range(x):
                self.cells[counter] = MazeCell(4)

                # fill for neighbour to "north"
                if(i == 0):
                    self.cells[counter].myNeighbours.append(-1)
                else:
                    self.cells[counter].myNeighbours.append(counter - x)

                # fill for neighbour to "east"
                if(j == (x - 1)):
                    self.cells[counter].myNeighbours.append(-1)
                else:
                    self.cells[counter].myNeighbours.append(counter + 1)

                # fill for neighbour to "south"
                if(i == (y - 1)):
                    self.cells[counter].myNeighbours.append(-1)
                else:
                    self.cells[counter].myNeighbours.append(counter + x)

                # fill for neighbour to "west"
                if(j == 0):
                    self.cells[counter].myNeighbours.append(-1)
                else:
                    self.cells[counter].myNeighbours.append(counter - 1)

                self.cells[counter].myWalls[0] = 1
                self.cells[counter].myWalls[1] = 1
                self.cells[counter].myWalls[2] = 1
                self.cells[counter].myWalls[3] = 1

                # If we're done in this loop, increment counter
                counter = counter + 1

        ## Basic init done, now actually traverse this crap to build maze structure.
        self.genPrim()

        # DEBUG: print out stuff for maze
##        print "Test: "+ `x` + ' ' + `y`
##        counter = 0
##        for i in range(y):
##            for j in range(x):
##                print 'Neighbours: ' +`len(self.cells[counter].myNeighbours)`
##                for z in range(len(self.cells[counter].myNeighbours)):
##                    sys.stdout.write(`self.cells[counter].myNeighbours[z]` + ' ')
##                sys.stdout.write('\n')

##                counter = counter + 1

    def printOrthoAscii(self):
        debug('***PRINTING***   height: ' + `self.height` + '   width: ' + `self.width`)
        # print very top bit
        y = 0

        sys.stdout.write('+')
        for j in range(self.width):
            if(self.cells[j].myWalls.has_key(0)):
                sys.stdout.write('--+')
            else:
                sys.stdout.write('  +')
        sys.stdout.write('\n')

        # Now, for each row, print sides, then bottoms

        for i in range(self.height):

            # sides
            sys.stdout.write('|')
            for j in range(self.width):
                if(self.cells[(i * self.width) + j].myWalls.has_key(1)):
                    sys.stdout.write('  |')
                else:
                    sys.stdout.write('   ')
            sys.stdout.write('\n')

            # bottom
            sys.stdout.write('+')
            for j in range(self.width):
                if(self.cells[(i * self.width) + j].myWalls.has_key(2)):
                    sys.stdout.write('--+')
                else:
                    sys.stdout.write('  +')
            sys.stdout.write('\n')

def mazeBench():
       import profile,pstats

       profile.run('foo = PrimMaze()')
       profile.run('foo.ortho(25,25)', 'maze_prof')
       foo.printOrthoAscii()
       sys.stdout.flush()
       p = pstats.Stats('maze_prof')
       p.sort_stats('time')
       p.print_stats()

if __name__ == '__main__':
    foo = PrimMaze()
    foo.ortho(25,25)
    foo.printOrthoAscii()
    # mazeBench()