Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!ames!ptsfa!hoptoad!academ!uhnix1!sugar!peter
From: peter@sugar.UUCP
Newsgroups: comp.sources.wanted
Subject: Re: wanted: maze algorithm
Message-ID: <155@sugar.UUCP>
Date: Wed, 10-Jun-87 09:52:19 EDT
Article-I.D.: sugar.155
Posted: Wed Jun 10 09:52:19 1987
Date-Received: Mon, 15-Jun-87 05:41:43 EDT
References: <763@thumper.UUCP>
Organization: Sugar Land UNIX - Houston, TX
Lines: 42
Summary: Here's how

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