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()

#--------------------------------------------------------------------------