Welcome, guest | Sign In | My Account | Store | Cart

The Maze class can create 2D mazes and return their ASCII or HTML representation.

Python, 226 lines
  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 += "&nbsp;"
        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).

5 comments

Georgy Pruss (author) 18 years ago  # | flag

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

Georgy Pruss (author) 18 years ago  # | flag

Updates. Sorry for the mess. Please visit http://zxw.nm.ru/maze.htm for the latest version. G-:

penny wenny 17 years, 10 months ago  # | flag

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!

greg p 14 years, 4 months ago  # | flag

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.

Danx 8 years, 8 months ago  # | flag

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.