Maze.py
Revision as of 01:40, 20 September 2011 by PeterHarding (talk | contribs)
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()
#--------------------------------------------------------------------------