The Maze class can create 2D mazes and return their ASCII or HTML representation.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 | # 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 "<html><body>%s</body></html>" % 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 R<self.n_rows-1: directions.append(SOUTH)
if C>0 : directions.append(WEST)
if C<self.n_cols-1: directions.append(EAST)
# Shuffle the directions array randomly
dir_len = len(directions)
for i in range(dir_len):
j = random.randrange(dir_len)
directions[i],directions[j] = directions[j],directions[i]
# Call the function recursively
for dir in directions:
if dir==NORTH:
if not maze[R-1][C][VISITED]:
self._make_path( R-1,C,NORTH )
elif dir==SOUTH:
if not maze[R+1][C][VISITED]:
self._make_path( R+1,C,SOUTH )
elif dir==EAST:
if not maze[R][C+1][VISITED]:
self._make_path( R,C+1,EAST )
elif dir==WEST:
if not maze[R][C-1][VISITED]:
self._make_path( R,C-1,WEST )
#else: raise 'bug:you should never reach here'
#*****************************************
def __str__(self):
"""Return maze table in ASCII"""
result = '.' + self.n_cols*'_.'
result += '\n'
for i in range(self.n_rows):
result += '|'
for j in range(self.n_cols):
if i==self.n_rows-1 or self.maze[i][j][BOTTOMWALL]:
result += '_'
else:
result += ' '
if j==self.n_cols-1 or self.maze[i][j][RIGHTWALL]:
result += '|'
else:
result += '.'
result += '\n'
return result
#*****************************************
def as_html_table(self):
"""Return table"""
result = "<TABLE ID='TMaze' CELLSPACING=0 CELLPADDING=0>\n"
for i in range(self.n_rows):
result += "<TR HEIGHT=25>"
for j in range(self.n_cols):
result += "<TD WIDTH=24 style='"
if i==0:
result += "BORDER-TOP: 2px black solid;"
if i==self.n_rows-1 or self.maze[i][j][BOTTOMWALL]:
result += "BORDER-BOTTOM: 2px black solid;"
if j==0:
result += "BORDER-LEFT: 2px black solid;"
if j==self.n_cols-1 or self.maze[i][j][RIGHTWALL]:
result += "BORDER-RIGHT: 2px black solid;"
result += "'>"
if i==0 and j==0:
result += 'S' # start
elif i==self.n_rows-1 and j==self.n_cols-1:
result += 'E' # end
else:
result += " "
result += "</TD>\n"
result += "</TR>\n"
result += "</TABLE>\n"
return result
#*****************************************
if __name__ == "__main__":
syntax = ( "Syntax: %s [[-]n_rows [n_cols]]\n\n"
"If n_cols is missing, it will be the same as n_rows\n"
"If n_rows is negative, html representation will be generated\n\n"
"Examples:\n%s 50 39 -- text maze 50 rows by 39 columns\n"
"%s -40 -- html code of 40 x 40 cell maze"
)
# parse arguments if any
import os.path
argc = len(sys.argv)
name = os.path.basename( sys.argv[0] )
if argc not in (2,3):
print >>sys.stderr, syntax % (name,name,name)
sys.exit(1)
elif argc == 2:
n_rows = n_cols = int(sys.argv[1])
elif argc == 3:
n_rows = int(sys.argv[1])
n_cols = int(sys.argv[2])
# 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
|
This class can be used in games for making mazes.
It can raise MemoryError for big mazes (> 50 x 50).
Tags: algorithms
Improved version. I've rewritten the maze generator. It's not recursive any more, so no dimension limitations, no MemoryError. Also some documentation added.
Just to mention some figures, a maze 100 x 100 is generated in I've rewritten the maze generator. It's not recursive any more, so no dimension limitations, no MemoryError. Also some documentation added.
Just to mention some figures, a maze 100 x 100 is generated in
Updates. Sorry for the mess. Please visit http://zxw.nm.ru/maze.htm for the latest version. G-:
Very Nice. I like it alot. I happened upon it while looking for ideas for maze traversal algorithms and now I can't stop playing with it. Way to go!
I Put it Online. I put this code online, into a little web application:
http://www.utilitymill.com/utility/Maze_Generator
I hope that's alright. Let me know if you have the newer code and I'll upgrade it to that. This thing is really cool. Great work.
I also did an online version. Mine has a different output. keep up the good work. http://danrugeles.appspot.com/#!/Projects Click on Maze Generator.