PeterHarding at 14:40, 19 September 2011

2011-09-19T14:40:58Z

PeterHarding at 06:11, 19 July 2009

2009-07-19T06:11:50Z

← Older revision		Revision as of 16:11, 19 July 2009
Line 218:		Line 218:

	[[Category:Python]]		[[Category:Python]]
			[[Category:Examples]]

PeterHarding at 04:01, 25 February 2008

2008-02-25T04:01:07Z

← Older revision		Revision as of 14:01, 25 February 2008
Line 1:		Line 1:
	=~~maze.py~~=		=Overview=

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

PeterHarding at 04:00, 25 February 2008

2008-02-25T04:00:37Z

← Older revision		Revision as of 14:00, 25 February 2008
Line 1:		Line 1:
	=maze.py=		=maze.py=

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

	~~Shows~~ the use of classes ~~in Python~~

	==Script==		==Script==

PeterHarding: New page: =maze.py= A python implementation of a maze generator. Shows the use of classes in Python ==Script==

 #!/usr/bin/env python  # $Id: maze.py,v 1.2 2000/12/12 19:45:01 tlavoie Exp t...

2008-02-25T04:00:10Z

New page: =maze.py= A python implementation of a maze generator. Shows the use of classes in Python ==Script== <pre> #!/usr/bin/env python # $Id: maze.py,v 1.2 2000/12/12 19:45:01 tlavoie Exp t...

New page

=maze.py=

A python implementation of a maze generator.

Shows the use of classes in Python

==Script==

<pre>
#!/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()
</pre>

[[Category:Python]]

Maze.py - Revision history

PeterHarding at 14:40, 19 September 2011

PeterHarding at 06:11, 19 July 2009

PeterHarding at 04:01, 25 February 2008

PeterHarding at 04:00, 25 February 2008

PeterHarding: New page: =maze.py= A python implementation of a maze generator. Shows the use of classes in Python ==Script==
#!/usr/bin/env python # $Id: maze.py,v 1.2 2000/12/12 19:45:01 tlavoie Exp t...