Making a maze....

[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....

[Cameron Laird]

Re: Making a maze....

In article <1PSsb.44675$jy .34613@clgrps13 >,
Bernard Fields <TalksLikeGargo yle@hotmail.com > wrote:[color=blue]
>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....
>
>[/color]

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

Cameron Laird <claird@phaseit .net>
Business: http://www.Phaseit.net

[Lee Harr]

Re: Making a maze....

On 2003-11-13, Bernard Fields <TalksLikeGargo yle@hotmail.com > wrote:[color=blue]
> 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....
>
>[/color]

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.

[Walter Moreira]

Re: Making a maze....

On Thu, Nov 13, 2003 at 09:35:57PM +0000, Bernard Fields wrote:[color=blue]
> 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....[/color]

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

--
--------------
Walter Moreira <> Centro de Matematica <> Universidad de la Republica
email: walterm@cmat.ed u.uy <> Home Page: http://www.cmat.edu.uy/~walterm
PGP: 0x1DB0E000 45DC 8212 9680 4507 5E5A 7490 0134 8144 1DB0 E000
PGP key: www.keyserver.net

[Jegenye 2001 Bt]

Re: Making a maze....

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

Miklós

Bernard Fields <TalksLikeGargo yle@hotmail.com > wrote in message
news:1PSsb.4467 5$jy.34613@clgr ps13...[color=blue]
> 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....
>
>[/color]

[Christopher Koppler]

Re: Making a maze....

On Thu, 13 Nov 2003 21:35:57 GMT, "Bernard Fields"
<TalksLikeGargo yle@hotmail.com > wrote:
[color=blue]
>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....
>[/color]

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

--
Christopher

[Georgy Pruss]

Re: Making a maze....

http://zxw.nm.ru/maze.htm

It was fun! :)
G-:
--
Georgy Pruss
E^mail: 'ZDAwMTEyMHQwMz MwQGhvdG1haWwuY 29t\n'.decode(' base64')


"Bernard Fields" <TalksLikeGargo yle@hotmail.com > wrote in message news:1PSsb.4467 5$jy.34613@clgr ps13...
| 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....
|
|

[Wilk]

Re: Making a maze....

"Georgy Pruss" <SEE_AT_THE_END @hotmail.com> writes:
[color=blue]
> http://zxw.nm.ru/maze.htm[/color]

Great !

Could you put it in the pygame code repository ?

http://www.pygame.org/pcr/

--
Wilk - http://flibuste.net

[Phil Schmidt]

Re: Making a maze....

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... :)

[Bengt Richter]

Re: Making a maze....

On Thu, 13 Nov 2003 21:35:57 GMT, "Bernard Fields" <TalksLikeGargo yle@hotmail.com > wrote:
[color=blue]
>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.
>[/color]
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?
[color=blue]
>I've done many, many web-searches, but nothing that I've found so far has
>provided any clues....
>[/color]
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

[Georgy Pruss]

Re: Making a maze....

I've put it in ASPN Python Cookbook, Algorithms.

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/252127

--
Georgy Pruss
E^mail: 'ZDAwMTEyMHQwMz MwQGhvdG1haWwuY 29t\n'.decode(' base64')


"Wilk" <wilkSPAM@OUTfl ibuste.net> wrote in message news:87y8ujyuk5 .fsf@blakie.rio l%23flibuste.ne t...
| "Georgy Pruss" <SEE_AT_THE_END @hotmail.com> writes:
|
| > http://zxw.nm.ru/maze.htm
|
| Great !
|
| Could you put it in the pygame code repository ?
| http://www.pygame.org/pcr/
|
| --
| Wilk - http://flibuste.net

[Phil Schmidt]

Re: Making a maze....

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':'gree n',
'frontier':'bro wn',
'explored':'yel low'}
self.walls = {}
# display the cell
x0, x1, y0, y1 = self.coords
self.cell = self.canvas.cre ate_rectangle(x 0, y0, x1, y1,
fill=self.color s[self.state],
outline='')
self.canvas.low er(self.cell) # ensures the walls are all on top
# make the walls
self.walls['north'] = self.canvas.cre ate_rectangle(x 0-grid.borderwidt h/2,
y0-grid.borderwidt h/2,
x1+grid.borderw idth/2,
y0+grid.borderw idth/2,
fill='black')
self.walls['south'] = self.canvas.cre ate_rectangle(x 0-grid.borderwidt h/2,
y1-grid.borderwidt h/2,
x1+grid.borderw idth/2,
y1+grid.borderw idth/2,
fill='black')
self.walls['west'] = self.canvas.cre ate_rectangle(x 0-grid.borderwidt h/2,
y0-grid.borderwidt h/2,
x0+grid.borderw idth/2,
y1+grid.borderw idth/2,
fill='black')
self.walls['east'] = self.canvas.cre ate_rectangle(x 1-grid.borderwidt h/2,
y0-grid.borderwidt h/2,
x1+grid.borderw idth/2,
y1+grid.borderw idth/2,
fill='black')
def removeWall(self , wall):
self.canvas.del ete(self.walls[wall])
del self.walls[wall]
def changeState(sel f, state):
self.canvas.ite mconfigure(self .cell, fill=self.color s[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.borderwidt h = borderwidth
if not canvas:
# create the canvas and display it
self.c = Canvas()
self.c.pack()
else:
self.c = canvas
self.c.configur e(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.appe nd(row)
# start with an empty frontier
self.frontier = []
def openExploration (self):
# pick an initial cell to open the frontier
start = rand.choice(ran d.choice(self.c ells))
start.changeSta te('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(se lf, x, y):
if self.isVirgin(x , y):
self.cells[y][x].changeState('f rontier')
self.frontier.a ppend(self.cell s[y][x])
def extendFrontier( self, x, y):
self.markFronti er(x+1, y)
self.markFronti er(x-1, y)
self.markFronti er(x, y+1)
self.markFronti er(x, y-1)

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

# this is the main iteration loop
while 1:
# mark all the frontier cells
grid.extendFron tier(x, y)
# pick a random frontier cell, and open a random wall to an explored cell
pick = rand.choice(gri d.frontier)
x, y = pick.location
walls = ['north','south' ,'east','west']
rand.shuffle(wa lls)
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(oth erwall)
# mark the cell as explored
pick.changeStat e('explored')
# take the cell off the frontier list
grid.frontier.r emove(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(gri d)

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

c.mainloop()

[Bengt Richter]

Re: Making a maze....

On 17 Nov 2003 09:46:28 -0800, phil_nospam_sch midt@yahoo.com (Phil Schmidt) wrote:
[color=blue]
>I couldn't resist...
>--------------------------------------------------[/color]
very pretty ;-)

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

from Tkinter import Canvas?

[...]

Regards,
Bengt Richter

[Paul Moore]

Re: Making a maze....

phil_nospam_sch midt@yahoo.com (Phil Schmidt) writes:
[color=blue]
> I couldn't resist...
> --------------------------------------------------[/color]

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.
--
This signature intentionally left blank

[Phil Schmidt]

Re: Making a maze....

bokr@oz.net (Bengt Richter) wrote in message news:<bpb8dk$dh q$0@216.39.172. 122>...[color=blue]
> On 17 Nov 2003 09:46:28 -0800, phil_nospam_sch midt@yahoo.com (Phil Schmidt) wrote:
>[color=green]
> >I couldn't resist...
> >--------------------------------------------------[/color]
> very pretty ;-)
>
> BTW, did you mean to prefix your code with something like
>
> from Tkinter import Canvas?
>
> [...]
>
> Regards,
> Bengt Richter[/color]



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