Maze algorithms

[Michael Turner]

I'm working on a maze cgi-bin (and if there is one out there, well soon there
will be two).

The idea for the front end being you are in a mze, and can see ahead
and to either side of you. Clicking infront of you will move forward, each
side will rotate you in that direction. The tricky part is the maze
generation.

So far, I know of two ways to generate mazes: remove walls, and add walls.
The addition of walls, I think I have down rather well, however, it dosn't
map to 3D mazes at all (which I plan to eventualy do).

The other option is removal of walls in the maze. First you generate
a random walk, then you remove walls untill all rooms have a path to
them. Anyone care to elaborate on this algorithm?

--Michael Turner

[Nicolaas D]

m_tu...@picard.cs.wisc.edu (Michael Turner) writes:

>I'm working on a maze cgi-bin (and if there is one out there, well soon there
>will be two).

>The idea for the front end being you are in a mze, and can see ahead
>and to either side of you. Clicking infront of you will move forward, each
>side will rotate you in that direction. The tricky part is the maze
>generation.

>So far, I know of two ways to generate mazes: remove walls, and add walls.

I know one more: Find a spanning tree of a grid. (Get a book on graph
theory.) A spanning tree is a subgraph of a graph, you get it by removing
all edges wich cause there are two paths from one node to another. Take
the positions you can stand on as nodes, and the doorways between them
as edges, and generate a spanning tree by removing random edges. If
you want to know the details, mail me.
This algorithm works for 3d, 4d, or any other d mazes you may have in
mind.

Good luck,

--
---. /) |
/ \ / _ _ | _ _ _ Dion Nicolaas
-/ )\ | (_(_ (_) \_ ()\ ()\ \ dni...@cs.vu.nl
_/___/ \| -------------------' <URL: http://www.cs.vu.nl/~dnicola/>

[John McNulty]

One idea is to start with a straight hallway or a square room then
stretch and fold it randomly and/or duplicate and adjoin. The neat
part is that you are always guaranteed to have a complete path from
start to finish because stretching and folding won't change that.
For example,

Start with: +--------------------------------+
Enter Exit
+--------------------------------+

Stretch (x3) and fold twice:

+-------------------------+
Enter |
+----------------------- |
| |
+ -----------------------+
| Exit
+-------------------------+

Stretch southern 1/3 of maze

+-------------------------+
Enter |
+----------------------- |
| |
+ ---------+-------------+
| | Exit
+--------+ | +----------+
| | |
| | |
| | |
| |
+-----+
+-----+
| |
| | |
Duplicate, flip and append: | | |
| | |
+-------------------------+--------+ | +----------+
Enter | | Exit
+----------------------- | ---------+-------------+
| | |
+ ---------+-------------+----------------------- |
| | |
+--------+ | +----------+-------------------------+
| | |
| | |
| | |
| |
+-----+

You get the idea. It's gleaned from ideas in iterative maps
and fractal geometry and graph homomorphisms. The relation
to a graph homomorphism is that when you really get right down
to it, a maze is just one very folded, pinched and distorted
tube.

I've never known this to be tried but I don't know much about
this area. If anyone does know of efforts along this line,
please post. I'd like to know if it's been tried and how it
fared.

John McNulty

[Stefan Dachwitz]

I don't know if this one is widely known:

1. take a rectangular map
2. take two starting points
3. generate some kind of branching tree from either starting point one step at a time
4. stop when the two branches have contact
(5.) Optional : Proceed in generating the branching tree WITHOUT allowing any contact between the branches

You get a fine random maze (which look depends on the not so trivial branch generating algorithm) with exactly one (or any chosen number) ways through the maze.

I don't know where I read about it, but it was some years ago in some magazine.

So have fun you maze-builders !

PS .-) if sbd. writes a program (pascal, c, C++), please post it!

--
Stefan Dachwitz

[Nicolaas D]

dach...@mathematik.uni-Bremen.de (Stefan Dachwitz) writes:

(Please, keep your line length down to 72 characters or thereabouts)

>I don't know if this one is widely known:

>1. take a rectangular map
>2. take two starting points
>3. generate some kind of branching tree from either starting point one
>step at a time
>4. stop when the two branches have contact
>(5.) Optional : Proceed in generating the branching tree WITHOUT allowing
>any contact between the branches

The algorithm I suggested to Frank Bignone looks like it, but is even
simpler: Generate a spanning tree of a grid. Ready.
(A tree guarantees there is exactly one path from every point to every
other point; edges in the graph are doorways, non-edges between
adjacent points are walls. Points are possible positions.)
By the way, the maze will have two solutions if you remove one wall,
it will have a room in the middle if you add one wall. Trees are
wonderful inventions!

Here's a program, written in turbo pascal (about any version will do)
to draw a maze on the screen. I wrote it a while ago, it has some
peculiarities regarding the writing of the maze on the screen because
I wanted it to happen while you looked at it.

--------8<--------8<--------8<--------8<--------8<--------8<--------8<

PROGRAM MazeMaker;
(* Draws a maze on the screen. The maze is a spanning tree of a grid.
Author:
Dion Nicolaas
Willem de Zwijgerlaan 357-II
1055 RB Amsterdam
The Netherlands
e-mail: dni...@cs.vu.nl (until 1-9-95)
!sp 1989
Hereby released to the public domain. The author would be
very happy if anyone who did something useful with it let
him know. Thanks in advance.
Written for Turbo Pascal 4.0 (?), should work with almost
everything else.
*)

USES
Crt;

CONST
ScreenWidth = 79;
ScreenHeight = 23;
Space = ' ';
Block = #219;

TYPE
RowType = 1 .. ScreenHeight;
ColType = 1 .. ScreenWidth;
MazeType = ARRAY [RowType, ColType] OF BOOLEAN;

CoordType = RECORD
x: ColType;
y: RowType;
END;
QueueCountType = 0 .. 8000;
QueueIndexType = 1 .. 8000;
CoordArrayType = ARRAY [QueueIndexType] OF CoordType;
QueueType = RECORD
Nr: QueueCountType;
Element: CoordArrayType;
END;

VAR
Maze: MazeType;
Queue: QueueType;

PROCEDURE DrawPanel;

(* Draws the panel for the maze on the screen *)

VAR
y: RowType;
x: ColType;

BEGIN
ClrScr;
FOR x := 1 TO ScreenWidth DO
FOR y := 1 TO ScreenHeight DO
BEGIN
GotoXY(x,y);
Write(Block);
END;
GotoXY(2,1); Write(Space);
GotoXY(ScreenWidth-1, ScreenHeight); Write(Space);
END; (* DrawPanel *)

PROCEDURE InitQueue(VAR Queue: QueueType);
(* An empty queue is created *)
BEGIN
Queue.Nr := 0;
END;

PROCEDURE AddElement(VAR Queue: QueueType; Coord: CoordType);
(* Element appended to Queue *)
BEGIN
IF Queue.Nr = 8000 THEN
BEGIN
WriteLn('Out of queuespace!');
HALT(1);
END
ELSE
BEGIN
INC(Queue.Nr);
Queue.Element[Queue.Nr] := Coord;
END;
END; (* AddElement *)

FUNCTION GetElement(VAR Queue: QueueType; VAR Coord: CoordType): BOOLEAN;
(* Random element returned in Coord if Queue isn't empty, else FALSE *)
VAR
i: QueueIndexType;
BEGIN
IF Queue.Nr = 0 THEN
GetElement := FALSE
ELSE
BEGIN
i := Random(Queue.Nr)+1;
Coord := Queue.Element[i];
Queue.Element[i] := Queue.Element[Queue.Nr];
DEC(Queue.Nr);
GetElement := TRUE;
END;
END; (* GetElement *)

PROCEDURE InitMaze(VAR Maze: MazeType);

(* Initialisation: the grid is generated. *)

VAR
y: RowType;
x: ColType;

BEGIN
Randomize;
FOR x := 1 TO ScreenWidth DO
FOR y := 1 TO ScreenHeight DO
Maze[y,x] := TRUE;
END; (* InitMaze *)

PROCEDURE AddNeighbours(VAR Queue: QueueType; NodeX: ColType; NodeY: RowType);
(* Puts neighbours of node on queue *)

FUNCTION Ok(Coord: CoordType): BOOLEAN;
BEGIN
WITH Coord DO
IF (x=1) OR (y=1) OR (x=ScreenWidth) OR (y=ScreenHeight) THEN
Ok := FALSE
ELSE
Ok := TRUE;
END; (* Ok *)

VAR
Coord: CoordType;
BEGIN
Coord.x := NodeX+1; Coord.y := NodeY;
IF Ok(Coord) THEN
AddElement(Queue, Coord);
Coord.x := NodeX-1; Coord.y := NodeY;
IF Ok(Coord) THEN
AddElement(Queue, Coord);
Coord.x := NodeX; Coord.y := NodeY+1;
IF Ok(Coord) THEN
AddElement(Queue, Coord);
Coord.x := NodeX; Coord.y := NodeY-1;
IF Ok(Coord) THEN
AddElement(Queue, Coord);
END; (* AddNeighbours *)

PROCEDURE PrintSpace(x: ColType; y: RowType);
(* Draws a space at (x,y) *)
BEGIN
GotoXY(x,y);
Write(Space);
END; (* PrintSpace *)

PROCEDURE MakeMaze(VAR Maze: MazeType);

(* Generates a maze by constructing a spanning tree from the grid *)

VAR
x: ColType;
y: RowType;
Edge: CoordType;

BEGIN
InitQueue(Queue);
Maze[2,2] := FALSE;
PrintSpace(2,2);
Edge.x := 3; Edge.y := 2;
AddElement(Queue, Edge);
Edge.x := 2; Edge.y := 3;
AddElement(Queue, Edge);
WHILE GetElement(Queue, Edge) DO
BEGIN
IF ODD(Edge.x) THEN
BEGIN
IF (Maze[Edge.y, Edge.x-1] = FALSE) AND
(Maze[Edge.y, Edge.x+1] = TRUE) THEN
BEGIN
Maze[Edge.y, Edge.x+1] := FALSE;
(* Add Node *)
PrintSpace(Edge.x+1, Edge.y);
AddNeighbours(Queue, Edge.x+1, Edge.y);
Maze[Edge.y, Edge.x] := FALSE;
(* Add Edge *)
PrintSpace(Edge.x, Edge.y);
END
ELSE IF (Maze[Edge.y, Edge.x+1] = FALSE) AND
(Maze[Edge.y, Edge.x-1] = TRUE) THEN
BEGIN
Maze[Edge.y, Edge.x-1] := FALSE;
(* Add Node *)
PrintSpace(Edge.x-1, Edge.y);
AddNeighbours(Queue, Edge.x-1, Edge.y);
Maze[Edge.y, Edge.x] := FALSE;
(* Add Edge *)
PrintSpace(Edge.x, Edge.y);
END;

END
ELSE (* y is ODD *)
BEGIN
IF (Maze[Edge.y-1, Edge.x] = FALSE) AND
(Maze[Edge.y+1, Edge.x] = TRUE) THEN
BEGIN
Maze[Edge.y+1, Edge.x] := FALSE;
(* Add Node *)
PrintSpace(Edge.x, Edge.y+1);
AddNeighbours(Queue, Edge.x, Edge.y+1);
Maze[Edge.y, Edge.x] := FALSE;
(* Add Edge *)
PrintSpace(Edge.x, Edge.y);
END
ELSE IF (Maze[Edge.y+1, Edge.x] = FALSE) AND
(Maze[Edge.y-1, Edge.x] = TRUE) THEN
BEGIN
Maze[Edge.y-1, Edge.x] := FALSE;
(* Add Node *)
PrintSpace(Edge.x, Edge.y-1);
AddNeighbours(Queue, Edge.x, Edge.y-1);
Maze[Edge.y, Edge.x] := FALSE;
(* Add Edge *)
PrintSpace(Edge.x, Edge.y);
END;

END;
END; (* WHILE *)
END; (* MakeMaze *)

(* MAIN *)

BEGIN
DrawPanel;
InitMaze(Maze);
MakeMaze(Maze);
GotoXY(1,ScreenHeight+1);
END.

[Greg Phillips]

I have written a very nice random maze generating in Turbo Pascal 7.0. If
anyone wants it, I will post the source code here. It is very heavily
commented and even includes a recursive solution finder.

Later,
Greg

[Tom HANKS]

mcn...@cs.umass.edu (John McNulty) writes:

>One idea is to start with a straight hallway or a square room then
>stretch and fold it randomly and/or duplicate and adjoin. The neat
>part is that you are always guaranteed to have a complete path from
>start to finish because stretching and folding won't change that.
>For example,

> Start with: +--------------------------------+
> Enter Exit
> +--------------------------------+

[snip, ends up with...]

> +-----+
> | |
> | | |
> Duplicate, flip and append: | | |
> | | |
> +-------------------------+--------+ | +----------+
> Enter | | Exit
> +----------------------- | ---------+-------------+
> | | |
> + ---------+-------------+----------------------- |
> | | |
> +--------+ | +----------+-------------------------+
> | | |
> | | |
> | | |
> | |
> +-----+

>You get the idea. It's gleaned from ideas in iterative maps
>and fractal geometry and graph homomorphisms. The relation
>to a graph homomorphism is that when you really get right down
>to it, a maze is just one very folded, pinched and distorted
>tube.

>I've never known this to be tried but I don't know much about
>this area. If anyone does know of efforts along this line,
>please post. I'd like to know if it's been tried and how it
>fared.

>John McNulty

A maze with no intersections... kind of defeats the purpose of a maze
(at least in a game) doesn't it? I mean the only problem is remembering
to keep going forward and not backtracking. Or have I missed something?

TTFN Tom.

[Cisco Lopez-Fresquet]

Yes, you missed something. ;)

To use the methodology of the previous poster, if we start with our simple
tube:

+--------------------------------------------+
start end
+--------------------------------------------+

And add a small bulge:

+--+
| |
+----------------------+ +------------------+
start end
+--------------------------------------------+

We still have an (irregular) tube. But now the tube has an "intersection".
If this bulge is extended, and subsidiary bulges are attached, then we have
all the tools necessary to produce the standard 2-D maze.

Proof of the "tube" theory of 2-D mazes is the fact that by following
either the left hand or right hand wall from the start is guranteed
to eventually lead you to the end.

- cisco

--
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
ci...@src.honeywell.com lope...@maroon.tc.umn.edu
-------------------------------------------------------------
An employer? Oh yeah - I do have one of those. I guess that
means I have to use this space for a disclaimer. *sigh*
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

[Jonas Andersson]

In article <41giuc$3...@news.orst.edu>, phil...@ucs.orst.edu says...
>
>In article <952301...@mulga.cs.mu.OZ.AU>,
>Tom HANKS <t...@munta.cs.mu.OZ.AU> wrote:

>>mcn...@cs.umass.edu (John McNulty) writes:
>>
>>>One idea is to start with a straight hallway or a square room then
>>>stretch and fold it randomly and/or duplicate and adjoin. The neat
>>>part is that you are always guaranteed to have a complete path from
>>>start to finish because stretching and folding won't change that.
>>>For example,
>>

[Cut..]

Without knowing the original question on this thread.
A simpler algorithm for making a maze N*N-squres is as follows:

[Algorithm]
You have a NxM matrix.
Pick a random position in the matrix, mark this position(room) as processed.
Mark all adjecent position as border "rooms". (N,W,S,E - or any other definition of adjecent)

Repeat the following
Now pick a random border position. Make a connection from
the border position to one(randomly connected room) "processed" room(position).
Mark up the new border positions.
Until there are no border positions.

This yields a maze that has one way to any given point.