Making a maze....

Georgy Pruss see_signature__ at hotmail.com
Tue Nov 18 06:25:55 CET 2003


Couldn't resist either :-)


================= tk_test.py
# tk_test.py
# Based on Phil Schmidt's script
# "http://groups.google.com/groups?dq=&hl=en&lr=&ie=UTF-8&c2coff=1&threadm="
# "221e7b06.0311171422.ceb82c5%40posting.google.com&prev=/groups%3Fhl%3Den%26l"
# "r%3D%26ie%3DUTF-8%26c2coff%3D1%26group%3Dcomp.lang.python"
# I just removed some unused functions -- Georgy Pruss 20031118-002204

from Tkinter import Canvas
import random as rand

rand.seed()

opposite = {'north':'south', 'south':'north', 'east':'west', 'west':'east'}
adjacentcell = {'north': lambda x,y: (x,y-1),
                'south': lambda x,y: (x,y+1),
                'east' : lambda x,y: (x+1,y),
                'west' : lambda x,y: (x-1,y)}

class Cell:
    def __init__(self, canvas, x, y, grid, state='virgin'):
        self.canvas = canvas
        self.location = (x, y)
        x0 = 3 + x * grid.cellsize_x
        x1 = x0 + grid.cellsize_x
        y0 = 3 + y * grid.cellsize_y
        y1 = y0 + grid.cellsize_y
        self.coords = (x0, x1, y0, y1)
        self.state = state
        self.colors = {'virgin':'green',
                       'frontier':'brown',
                       'explored':'yellow'}
        self.walls = {}
        # display the cell
        x0, x1, y0, y1 = self.coords
        self.cell = self.canvas.create_rectangle(x0, y0, x1, y1,
                                                 fill=self.colors[self.state],
                                                 outline='')
        self.canvas.lower(self.cell)    # ensures the walls are all on top
        # make the walls
        self.walls['north'] = self.canvas.create_rectangle(x0-grid.borderwidth/2,
                                                           y0-grid.borderwidth/2,
                                                           x1+grid.borderwidth/2,
                                                           y0+grid.borderwidth/2,
                                                           fill='black')
        self.walls['south'] = self.canvas.create_rectangle(x0-grid.borderwidth/2,
                                                           y1-grid.borderwidth/2,
                                                           x1+grid.borderwidth/2,
                                                           y1+grid.borderwidth/2,
                                                           fill='black')
        self.walls['west'] = self.canvas.create_rectangle(x0-grid.borderwidth/2,
                                                          y0-grid.borderwidth/2,
                                                          x0+grid.borderwidth/2,
                                                          y1+grid.borderwidth/2,
                                                          fill='black')
        self.walls['east'] = self.canvas.create_rectangle(x1-grid.borderwidth/2,
                                                          y0-grid.borderwidth/2,
                                                          x1+grid.borderwidth/2,
                                                          y1+grid.borderwidth/2,
                                                          fill='black')
    def removeWall(self, wall):
        self.canvas.delete(self.walls[wall])
        del self.walls[wall]
    def changeState(self, state):
        self.canvas.itemconfigure(self.cell, fill=self.colors[state])
        self.state = state

class Grid:
    def __init__(self, canvas=None,
                 cellsize_x=10, cellsize_y=10,
                 gridsize_x=10, gridsize_y=10,
                 borderwidth=2):
        self.cellsize_x = cellsize_x
        self.cellsize_y = cellsize_y
        self.gridsize_x = gridsize_x
        self.gridsize_y = gridsize_y
        self.borderwidth = borderwidth
        if not canvas:
            # create the canvas and display it
            self.c = Canvas()
            self.c.pack()
        else:
            self.c = canvas
        self.c.configure(height = 3 + gridsize_y * cellsize_y + borderwidth,
                         width = 3 + gridsize_x * cellsize_x + borderwidth)
        self.c.update()
        # create cells
        self.cells = []
        for y in range(gridsize_y):
            row = []
            for x in range(gridsize_x):
                row.append(Cell(self.c, x, y, self))
            self.cells.append(row)
        # start with an empty frontier
        self.frontier = []

    def update(self):
        self.c.update()


import Maze


# Tk grid
N_ROWS = 3     # was 8
N_COLS = 3     # was 8
# Maze grid
MAZE_ROWS = 30 # was 10
MAZE_COLS = 30 # was 10

for y in range(N_ROWS):
    for x in range(N_COLS):
        c = Canvas()
        c.grid(column=x, row=y)

        # make a grid
        grid = Grid(c,
                    cellsize_x=8, cellsize_y=8,
                    gridsize_x=MAZE_COLS, gridsize_y=MAZE_ROWS)

        path = []
        maze = Maze.Maze( MAZE_ROWS, MAZE_COLS, path ) # OUT path

        # get the maze generator
        explorer = iter(path)

        while 1:
            grid.update()
            try:
                row,col,wall = explorer.next()
                cell = grid.cells[row][col]
                cell.changeState('explored')

                if wall != Maze.ORIGIN:
                  # remove walls, both of them!
                  wall = ('','north','south','west','east')[wall]
                  cell.removeWall(wall)
                  c1, r1 = adjacentcell[wall](col, row)
                  otherwall = opposite[wall]
                  grid.cells[r1][c1].removeWall(otherwall)

            except StopIteration:
                break

c.mainloop()

================= Maze.py
# Maze.py
# Last update 20031118-001428
# Improved version - no recursion, no dimension limitation.

"""
implements class Maze

Three public methods are implemented:
  __init__(rows,cols[,path]) -- constructor
  __str__()                  -- text representation (for print and str())
  as_html_table()            -- html formatting

If path is specified, the building path will be returned there. It's
suitable for showing the maze creation process.

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:
  Method find_path() -- It must be very easy. Later.
"""

# Copyright (C) 2003 Georgy Pruss
# email = 'ZDAwMTEyMHQwMzMwQGhvdG1haWwuY29t\n'.decode('base64')
#
# Some ideas from:
#
# 1. http://www.siteexperts.com/tips/functions/ts20/mm.asp
#    Copyright 1999 Rajeev Hariharan. All Rights Reserved.
#
# 2. This program (possible from from IOCCC? rcarter~at~wpi.wpi.edu?
#    jhallen~at~world.std.com--Joseph H. Allen? Last Update 05-Jul-1997)
#
# int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
# +r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
# ]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}


import random


# Constants. (I wish Python had true constants that allowed optimization... :-( )

# A maze cell is a vector of three items:
# -- a direction from where we got here (ORIGIN=0 if not visited)
# -- two flags, showing if bottom and right walls are present
#    (for top and left walls refer to upper and left cells resp.)
# These are indexes in the cell array
BACKTRACK  = 0 # direction where we came from
BOTTOMWALL = 1 # if the bottom wall is present
RIGHTWALL  = 2 # if the right wall is present1

# These are value for direction or "not visited" flag
ORIGIN = 0 # must be zero, shows "not visited"
NORTH  = 1
SOUTH  = 2
WEST   = 3
EAST   = 4

# A mapping for finding reverse direction
BACK_DIR = [ORIGIN,SOUTH,NORTH,EAST,WEST]

# The initial state of all cells
INITIAL_STATE = [ORIGIN,True,True] # not visited, both walls are intact


class Maze:

  """Creates a maze and ouputs it as text or html"""


  #*****************************************

  def __init__( self, n_rows, n_cols, path = None ):
    """Create a maze with given number of rows and cols.
    The class of mazes that the program generates are referred to as
    Perfect mazes, because any two cells of the maze are connected by
    a single unique path. The program uses the top left cell as the
    start and the bottom right cell as the finish, but any two randomly
    selected cells could be chosen as start and finish. Perfect mazes
    do not contain any dead zones, areas which are inaccessible by any path.
    They also differ from Cyclic mazes, in which more than one solution to
    the maze is possible. A depth-first search algorithm is used to
    generate the maze.
    [http://www.siteexperts.com/tips/functions/ts20/backtrack.zip:mazes.htm]
    """

    if n_rows < 2 or n_cols < 2: # this also requires them to be numbers
     raise ValueError, "Invalid maze dimentions %d x %d" % (n_rows, n_cols)

    self.n_rows = n_rows
    self.n_cols = n_cols

    # Set up the maze - initially all walls intact
    self.maze = [None]*self.n_rows
    for r in range(self.n_rows):
      self.maze[r] = [None]*n_cols
      for c in range(n_cols):
        self.maze[r][c] = INITIAL_STATE[:]

    # Choose a random starting point R0,C0
    R0 = random.randrange(self.n_rows)
    C0 = random.randrange(self.n_cols)

    r = R0
    c = C0
    self.maze[r][c][BACKTRACK] = NORTH # No matter what, just must be 'visited'

    if path is not None:
      path.append( (r,c,ORIGIN) )

    while 1: # loop forever (ain't it stupid, while 1? :-)
             # we'll *return* when we return back to R0,C0

      # find out where we can theoretically go
      dirs = self._find_legal_dirs( r,c )

      # and then find a cell not visited yet
      while dirs:
        dir = dirs.pop() # pop the directions one by one
        if not self._visited( r,c,dir ): # found, do a move
          break # see below, marked (HERE) on the right

      else: # all the cells around were visited

        # go back one step and repeat for the directions left available

        dir = self.maze[r][c][BACKTRACK]
        # do a move back
        if   dir==NORTH: r-=1
        elif dir==SOUTH: r+=1
        elif dir==EAST : c+=1
        elif dir==WEST : c-=1

        # check if be moved back to the origin
        if r==R0 and c==C0:
          return # found the very initial cell, all done!

        continue # remeber while 1? now it's time to check if 1 changed :-)

      # not visited ==> move  AND Knock out the wall                     (HERE)
      if   dir==NORTH:  r-=1; self.maze[r]  [c]  [BOTTOMWALL] = False
      elif dir==SOUTH:  r+=1; self.maze[r-1][c]  [BOTTOMWALL] = False
      elif dir==WEST :  c-=1; self.maze[r]  [c]  [RIGHTWALL]  = False
      elif dir==EAST :  c+=1; self.maze[r]  [c-1][RIGHTWALL]  = False

      # remember the way back
      self.maze[r][c][BACKTRACK] = BACK_DIR[dir]

      if path is not None:
        path.append( (r,c,BACK_DIR[dir]) )


  def _visited( self,r,c,dir ):
    """Check if the cell in given direction is already visited"""
    if dir==NORTH: return self.maze[r-1][c][BACKTRACK]
    if dir==SOUTH: return self.maze[r+1][c][BACKTRACK]
    if dir==EAST : return self.maze[r][c+1][BACKTRACK]
    if dir==WEST : return self.maze[r][c-1][BACKTRACK]

  def _find_legal_dirs( self,r,c ):             # to be optimized
    # Build legal directions array for cell r,c
    dirs = []
    if r>0            : dirs.append(NORTH)
    if r<self.n_rows-1: dirs.append(SOUTH)
    if c>0            : dirs.append(WEST)
    if c<self.n_cols-1: dirs.append(EAST)
    # Shuffle the directions array randomly
    dir_len = len(dirs)
    for i in range(dir_len):
      j = random.randrange(dir_len)
      dirs[i],dirs[j] = dirs[j],dirs[i]
    #assert 2 <= len(dirs) <= 4 # 2 for corners, 3 for borders, 4 otherwise
    return dirs


  #*****************************************

  def __str__(self):
    """Return maze table in ASCII"""

    result = '.' + self.n_cols*'_.' + '\n'

    for r in range(self.n_rows):
      result += '|'

      for c in range(self.n_cols):
        if r==self.n_rows-1 or self.maze[r][c][BOTTOMWALL]:
          result += '_'
        else:
          result += ' '
        if c==self.n_cols-1 or self.maze[r][c][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=12>"

      for j in range(self.n_cols):
        result += "<TD WIDTH=12 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"
           )

  import sys, os.path

  # parse arguments if any

  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 the maze

  try:
    if n_rows > 0: # ascii
      print Maze( n_rows, n_cols )
    else: # html
      nr,nc = abs(n_rows), abs(n_cols)
      import time
      start = time.clock()
      maze = Maze( abs(n_rows), abs(n_cols) )
      generated = time.clock()
      html_code = maze.as_html_table()
      printed = time.clock()
      print "<!-- %d x %d, generation time: %.3f sec -->" \
          % (nr,nc,generated-start)
      print "<!-- %d chars, formatting time: %.3f sec -->" \
          % (len(html_code),printed-generated)
      print html_code
  except Exception, e:
    print e


# EOF

================= END
-- 
Georgy Pruss
E^mail: 'ZDAwMTEyMHQwMzMwQGhvdG1haWwuY29t\n'.decode('base64')

"Phil Schmidt" <phil_nospam_schmidt at yahoo.com> wrote in message news:221e7b06.0311170946.3baaa2ca at posting.google.com...
| I couldn't resist...
| --------------------------------------------------
| <...>
| c.mainloop()






More information about the Python-list mailing list