Welcome, guest | Sign In | My Account | Store | Cart
# 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

History