# Maze.py # Last update 20031115-214011 """ implements class Maze Three public methods are implemented: __init__(rows,cols) __str__() as_html_table() Usage: maze = Maze( 20, 30 ) # create a maze 20 rows x 30 cols print maze # print out the maze print "%s" % maze.as_html_table() # publish it To do: 1. Method find_path() :) 2. Different algorithms for big mazes (>50x50) or iteration instead of recursion """ # Translation to Python (C) 2003 Georgy Pruss # From http://www.siteexperts.com/tips/functions/ts20/mm.asp # // Copyright 1999 Rajeev Hariharan. All Rights Reserved. import random, sys # Constants -- cell marks BOTTOMWALL = 0 RIGHTWALL = 1 VISITED = 2 NORTH = 0 SOUTH = 1 WEST = 2 EAST = 3 class Maze: """Creates a maze and formattes it as text or HTML""" #***************************************** def __init__( self, n_rows, n_cols ): """Create a maze with given number of rows and cols. The path connects upper left and lower right cells. Actually, all cells are connected. Can raise 'MemoryError: Stack overflow' for big arguments, e.g. 100,100 """ self.n_rows = n_rows self.n_cols = n_cols self.maze = [None]*n_rows # Set up the hedge array - initially all walls intact for i in range(n_rows): self.maze[i] = [None]*n_cols for j in range(n_cols): self.maze[i][j] = [True,True,False] # BOTTOMWALL,RIGHTWALL,VISITED # Choose a random starting point currCol = random.randrange(n_cols) currRow = random.randrange(n_rows) # The searh can be quite deep if n_rows*n_cols > sys.getrecursionlimit(): sys.setrecursionlimit( n_rows*n_cols+5 ) # Recursively Remove Walls - Depth First Algorithm self._make_path( currRow, currCol ) #***************************************** def _make_path( self, R, C, D=None ): maze = self.maze # speed up a bit # Knock out wall between this and previous cell maze[R][C][VISITED] = True; if D==NORTH: maze[R] [C] [BOTTOMWALL] = False elif D==SOUTH: maze[R-1][C] [BOTTOMWALL] = False elif D==WEST: maze[R] [C] [RIGHTWALL] = False elif D==EAST: maze[R] [C-1][RIGHTWALL] = False # Build legal directions array directions = [] if R>0 : directions.append(NORTH) if R0 : directions.append(WEST) if C>sys.stderr, syntax % (name,name,name) sys.exit(1) elif argc == 2: n_rows = n_cols = int(sys.argv) elif argc == 3: n_rows = int(sys.argv) n_cols = int(sys.argv) # create and print maze try: if n_rows > 0: print Maze( n_rows, n_cols ) else: maze = Maze( abs(n_rows), abs(n_cols) ) print maze.as_html_table() except MemoryError: print "Sorry, n_rows, n_cols were too big" # EOF