text: # 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(syntax % (name,name,name), file=sys.stderr)
      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
  