[comp.sources.wanted] wanted: maze algorithm

sdh@thumper.UUCP (06/03/87)

wanted:
source to generate a maze.  Simple, right?  not quite.  You must be
able to get from any point in the maze to any other point, and ideally,
I would like it to work by starting off with a grid of segments and
selectively removing them.

Anybody have something that will do this (or something close)?

Steve Hawley
{decvax, ucbvax}!bellcore!sdh

peter@sugar.UUCP (06/10/87)

This is how I make mazes when I feel the urge. It's pretty much the most
obvious technique... or at least seemed that way to me. I first implemented
it in basic using a string for the stack (couldn't hold an array large enough)
and the screen for the grid, so the recursion in maze() shouldn't cause you
any problems. It does recurse rather deeply: potentially up to (MAXX*MAXY-1).
You could use breadth-first searching instead of depth-first if you want to
cut it down... it's much more complicated though.

north:	0
east:	1
south:	2
west:	3

dx:	0, 1, 0, -1
dy:	1, 0, -1, 0
grid:	[1..MAXX, 1..MAXY]

main:
	grid = FALSE

	maze(randomx, randomy)

maze(x, y):

	visit (x,y)
	for dir = some random purmutation of (north, south, east, west):
		if not visited(x+dx[dir], y+dy[dir]):
			draw line from (x, y) to (x+dx(dir), y+dy(dir))
			maze(x+dx(dir), y+dy(dir))
		endif
	endfor

visit(x, y):

	grid(x, y) = TRUE

visited(x, y):

	if x in range and y in range
		return grid(x, y)
	else
		return true