Making a maze....
Georgy Pruss
see_signature__ at hotmail.com
Tue Nov 18 00:25:55 EST 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 += " "
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