Making a maze....

B

Bernard Fields

Greets, all.


As the title suggests, I'm trying to make a maze. Specifically, it's a
top-down, 2-d maze, preferably randomly generated, though I'm willing to
forego that particular aspect as this point.

I've done many, many web-searches, but nothing that I've found so far has
provided any clues....
 
C

Cameron Laird

Greets, all.


As the title suggests, I'm trying to make a maze. Specifically, it's a
top-down, 2-d maze, preferably randomly generated, though I'm willing to
forego that particular aspect as this point.

I've done many, many web-searches, but nothing that I've found so far has
provided any clues....

<URL: http://wiki.tcl.tk/maze >. While these are all
Tk-based, I claim it's easy to recode 'em in Tkinter.
 
W

Walter Moreira

Greets, all.


As the title suggests, I'm trying to make a maze. Specifically, it's a
top-down, 2-d maze, preferably randomly generated, though I'm willing to
forego that particular aspect as this point.

I've done many, many web-searches, but nothing that I've found so far has
provided any clues....

The following url was useful for me:

http://www.ai.mit.edu/people/shivers/mazes.html

Algorithms are written in Scheme but they are translated almost verbatim
to Python.

Walter

--
 
L

Lee Harr

Greets, all.


As the title suggests, I'm trying to make a maze. Specifically, it's a
top-down, 2-d maze, preferably randomly generated, though I'm willing to
forego that particular aspect as this point.

I've done many, many web-searches, but nothing that I've found so far has
provided any clues....

How about xscreensaver?
http://www.jwz.org/xscreensaver/

The code is all C, but you could probably translate the algorithm
to python without too much trouble.

Looks like maze.c has at least 3 different methods.
 
J

Jegenye 2001 Bt

I saw an annotated and explained piece of C++ code in Crystal Space.
Actually the algorithm was described, too, I think

Miklós
 
C

Christopher Koppler

Greets, all.


As the title suggests, I'm trying to make a maze. Specifically, it's a
top-down, 2-d maze, preferably randomly generated, though I'm willing to
forego that particular aspect as this point.

I've done many, many web-searches, but nothing that I've found so far has
provided any clues....

If you can stand to translate it to Python, there's a PHP random maze
generator at
http://www.moo3.at/flo/labyrinth/labyrinth.html
with the source code (with comments in German, I'm afraid) at
http://www.moo3.at/flo/labyrinth/code.html
 
G

Georgy Pruss

http://zxw.nm.ru/maze.htm
It was fun! :)
G-:
--
Georgy Pruss
E^mail: 'ZDAwMTEyMHQwMzMwQGhvdG1haWwuY29t\n'.decode('base64')


| Greets, all.
|
|
| As the title suggests, I'm trying to make a maze. Specifically, it's a
| top-down, 2-d maze, preferably randomly generated, though I'm willing to
| forego that particular aspect as this point.
|
| I've done many, many web-searches, but nothing that I've found so far has
| provided any clues....
|
|
 
P

Phil Schmidt

I did this 20+ years ago, in Z80 assembly on a TRS-80. It drove an
Epson MX-80 lineprinter to produce the output. I later converted it to
C when I was learning that language around '88, and had the maze
generate and display on the screen, using different colored cells for
different cell states. The resulting display resembles a grass fire on
a calm day (hmm, what if the algorithm considered "wind"? But I
digress), in that it starts as a point at a random location, and grows
out from that point in a random fashion, spreading out until all cells
are part of the maze (they are "burned out").

Anyway, here is the algorithm. Hopefully I haven't forgotten any
steps:

1) Start with a grid of cells, with each cell being marked as "virgin
territory".
2) Pick any cell at random, and mark it as "explored". From that cell,
identify all the adjacent "virgin territory" cells, and mark them as
"frontier".
3) Pick any random "frontier" cell X from the maze, and choose from X
at random any wall that adjoins an "explored" cell. Remove that wall,
and mark cell X as "explored". Also from cell X, identify all the
adjacent "virgin territory" cells, and mark them as "frontier".
4) Repeat (3) until there are no more "frontier" cells.

You will need to deal with the boundaries. The "virtual" cells just
outside the boundaries have the property that they can't become
"frontier" cells, and therefore can't become part of the maze.

This will produce a maze with the property that there will be one and
only one path from any cell to any other cell in the maze. So, to have
an entry and exit to the maze, just open the walls of two cells at the
boundaries of the maze.

I never tried this with anything but a rectangular grid. It would be
fun to use a hexagonal grid. It would also be interesting to do it in
3-D.

Sometimes I wish I were still a kid, and had time to play with this
kind of stuff... :)
 
B

Bengt Richter

Greets, all.


As the title suggests, I'm trying to make a maze. Specifically, it's a
top-down, 2-d maze, preferably randomly generated, though I'm willing to
forego that particular aspect as this point.
I'm not sure what you mean by 'top-down.' Also, do you just want to show
(print and/or display) a maze, or do you want a representation that you
can "walk" through with a program?
I've done many, many web-searches, but nothing that I've found so far has
provided any clues....
It should not be that hard, but do you have any constraints on loops, islands,
where entry and exit are supposed to be, dimensions, connectivity (e.g. square cells
vs rooms and corridors of arbitrary shape, etc.)?

Regards,
Bengt Richter
 
P

Phil Schmidt

I couldn't resist...
--------------------------------------------------

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 openExploration(self):
# pick an initial cell to open the frontier
start = rand.choice(rand.choice(self.cells))
start.changeState('explored')
return start.location
def update(self):
self.c.update()
def isInArray(self, x, y):
return x >= 0 and x < self.gridsize_x \
and y >= 0 and y < self.gridsize_y
def isExplored(self, x, y):
if self.isInArray(x, y):
return self.cells[y][x].state is 'explored'
else:
return False
def isVirgin(self, x, y):
if self.isInArray(x, y):
return self.cells[y][x].state is 'virgin'
else:
return False
def markFrontier(self, x, y):
if self.isVirgin(x, y):
self.cells[y][x].changeState('frontier')
self.frontier.append(self.cells[y][x])
def extendFrontier(self, x, y):
self.markFrontier(x+1, y)
self.markFrontier(x-1, y)
self.markFrontier(x, y+1)
self.markFrontier(x, y-1)

def MazeBuilder(grid):
# pick an initial cell to open the frontier
x, y = grid.openExploration()
yield x, y

# this is the main iteration loop
while 1:
# mark all the frontier cells
grid.extendFrontier(x, y)
# pick a random frontier cell, and open a random wall to an explored cell
pick = rand.choice(grid.frontier)
x, y = pick.location
walls = ['north','south','east','west']
rand.shuffle(walls)
for wall in walls:
x1, y1 = adjacentcell[wall](x, y)
if grid.isExplored(x1, y1):
# open the wall in the target cell
pick.removeWall(wall)
# and then the wall in the adjacent cell
otherwall = opposite[wall]
grid.cells[y1][x1].removeWall(otherwall)
# mark the cell as explored
pick.changeState('explored')
# take the cell off the frontier list
grid.frontier.remove(pick)
break
if grid.frontier:
yield x,y
else:
return

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

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

# get the maze generator
explorer = MazeBuilder(grid)

while 1:
grid.update()
try:
explorer.next()
except StopIteration:
break

c.mainloop()
 
B

Bengt Richter

I couldn't resist...
--------------------------------------------------
very pretty ;-)

BTW, did you mean to prefix your code with something like

from Tkinter import Canvas?

[...]

Regards,
Bengt Richter
 
P

Paul Moore

I couldn't resist...
--------------------------------------------------

Interesting! One thing I'd like (I don't know if the OP had this in
mind) is to have a marked "start" point, and a marked "end" point. A
guarantee that there is a route from "start" to "end" would be good,
too :)

I'm not sure, at a brief glance, how easy the algorithm would adapt to
this.

Paul.
 
P

Phil Schmidt

I couldn't resist...
--------------------------------------------------
very pretty ;-)

BTW, did you mean to prefix your code with something like

from Tkinter import Canvas?

[...]

Regards,
Bengt Richter



I actually used "from Tkinter import *", but yes, you are correct. A
copy-paste error on my part. :)
 
G

Georgy Pruss

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,dirs[j] = dirs[j],dirs
#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[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[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')

| I couldn't resist...
| --------------------------------------------------
| <...>
| c.mainloop()
 
P

Phil Schmidt

Georgy Pruss said:
Couldn't resist either :)
< -snip code- >


Hey, that's very pretty too! Very cool!

Would you care to explain the algorithm? Sure, I can read your
references, or reverse-engineer it, but I'll have to save that
exercise for later, when I have some more time. I want immediate
gratification! ;)

I like the ASCII and HTML generation too.

Thanks for the entertainment!

(So, who's gonna tackle the hexagonal maze?)
 
G

Georgy Pruss

| > Couldn't resist either :)
| >
| >
| < -snip code- >
|
|
| Hey, that's very pretty too! Very cool!
|
| Would you care to explain the algorithm? Sure, I can read your
| references, or reverse-engineer it, but I'll have to save that
| exercise for later, when I have some more time. I want immediate
| gratification! ;)

Hehe, you want me to have an exercise in English? :) OK.

Every cell of the maze remembers if the right and the bottom walls
are present. This information is already enough to draw the maze.
Then, for the recursive algorithm, it was enough that each cell could
tell if it was visited or not. If we want an iterative algorithm, then we
require more. We want each cell to save some useful information,
namely, the direction where we came from to this cell. Then we can
do backtracking just reading the maze itself. Thus, each cell should
contain the direction from where it was visited first, or if there's no
such data, the cell hasn't been visited yet (and will look green :)).

The algorithm starts at an arbitrary point. Then we determine where
it's possible to move physically, i.e. we consider only physical limits:
the outer walls of the maze. Then we go through all the potential
directions in random order and look for any adjacent cell that hasn't
been visited yet. If there's such a cell, we ruin the wall between the
cells, and save the direction *back* to the current cell in that new cell.
We move there and repeat from the beginning. If there's no free cell
around, we step one move back and try to repeat the algorithm.
This is when we need the direction where to return, and we take it
from the current cell. When we step back again and again and finally
reach to the first cell, it means that all the variants were tried and we
did all we could. Fortunatelly. it also means that all the cells were
visited and the full perfect path through the maze is built.

# We could save the original directions of the moves instead of the
# 'back' directions and inverse them while backtracking. It would just
# change the place of finding the inverse direction.

But probably the code is more precise and clear than my explanations. :)

G-:

p='p=;print p[:2]+chr(39)+p+chr(39)+p[2:]';print p[:2]+chr(39)+p+chr(39)+p[2:]

|
| I like the ASCII and HTML generation too.
|
| Thanks for the entertainment!
|
| (So, who's gonna tackle the hexagonal maze?)
 
M

mensanator

Paul Moore said:
Interesting! One thing I'd like (I don't know if the OP had this in
mind) is to have a marked "start" point, and a marked "end" point. A
guarantee that there is a route from "start" to "end" would be good,
too :)

It appears that all the yellow squares are contiguous. I did a screen
capture and then used a paint bucket to dump onto a yellow square. The
paint flowed to every cell, so you could probably punch start and end
points anywhere in the outer wall, although some may end up trivially
easy.

I changed the program to do a single 100x100 maze instead of 64 10x10.
Really slows it down, but you can watch how the algorithm explores the
virgin territory.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top