Scalar's GP-TRICKS Homepage
| Site Map | Tricks Section | How To Randomly Generate a Maze |
|---|
|
|
How To Randomly Generate a Maze
Sometimes in game development, you want to create a maze on the fly, either because you do not want do design
one yourself, or to present a new challange every time the game is played. This maze generator might help you.
It uses a simple but very flexible algorithm to create mazes. In fact, the algorithm is so easy that everybody
should be able to understand it immediately; you should, however, keep in mind that the results of the algorithm are
random. Neither I nor you can make sure that all mazes generated fulfill your requirements. This is why I
would not include this generator in a game, but rather generate a few hundred maps during development, check them and then
ship them with the game. If the player has an opportunity to preview the level to play, that is a whole different
story again, though.
So, what are the requirements for a maze? Obviously, obstacles should block the direct path from start to finish,
whatever locations these might be. Another goal for this generator is to make sure that any point in the maze could be
reached from any other.
These prerequisites are easy to achieve: You begin with an empty map and select a location for the first wall. Then you
randomly chose a direction (up, down, left, or right) and check the adjacent fields in that direction. It is important
not to check the row you come from. If there is no wall set in the surrounding fields so far, a wall will be set here and the
algorithm continues with this position. The old position will be stored on a stack. If there is a wall set, you try a
different direction, or if you have already tried all directions, you pop the last position from the stack, move back
and try again there. If you end up with an empty stack, the maximum number of walls has been set.
To clarify this a bit, please consider this diagram:
| Checking right |
| | | | |
| | check | check | |
| old > | > new | check | |
| | check | check | |
| | | | |
old marks the old position. We want to move to the right.
new is to the right of the old position.
We check all fields marked with check as well as the new field
itself for walls already existing.
If there are walls found, the new position is rejected.
As already said, do not check the old field and the fields above and below of it. Otherwise, obviously all positions
will be rejected.
The program in Listing 1 also adds other interesting features. It is, for example, possible to choose the "wiggliness",
which I define as the probability that the direction is changed. This is done by generating another random number
before choosing a new direction.
Listing 1 also lets you decide on the width of the paths between the walls. In the example above, this would be 1.
In order to allow for wider spaces between the walls, the area checked for walls has to be extended, as shown below.
| Checking right, width 2 |
| | check | check | check |
| | check | check | check |
| old > | > new | check | check |
| | check | check | check |
| | check | check | check |
Again, all fields marked check as well as the new field have to
be checked for walls.
As you can see, the area has been extended into all directions but the one you come from. The maze generated with
this method will have two free spaces between all walls.
The mazes generated with this algorithm are random, so I had no way to check that it works in all cases. Be
careful where you utilize it, and - don't get lost.
| Listing 1 |
|---|
| Borland Pascal 7.0 |
program MazeGen;
uses Crt;
const x1=1; y1=1; x2=80; y2=24;
var map:array[1..80,1..24] of byte;
procedure DField(x,y:byte);
begin
GotoXY(x,y); if map[x,y]=0 then Write(' ') else Write('X');
if keypressed then if readkey=#27 then halt;
end;
procedure DMap;
var x,y:byte;
begin
for y:=y1 to y2 do
for x:=x1 to x2 do DField(x,y);
end;
procedure CMap;
var x,y:byte;
begin
for y:=y1 to y2 do
for x:=x1 to x2 do map[x,y]:=0;
end;
procedure FMap;
var z:byte;
begin
for z:=x1 to x2 do begin map[z,y1]:=1; map[z,y2]:=1; end;
for z:=y1 to y2 do begin map[x1,z]:=1; map[x2,z]:=1; end;
end;
{ x/y starting position; w width of path;
wiggle_pc percentage of wiggliness }
procedure Generate(x,y,w:byte; wiggle_pc:byte);
type TStack=record x,y:byte; end;
var st:array[1..2000] of TStack;
sp:word; r:byte; d:array[1..4] of boolean;
{ return number of occupied fields ahead }
function Get(xc,yc:byte; xn,yn,xp,yp:shortint) : byte;
var x,y:shortint; a:byte;
begin
a:=0;
for y:=yc+yn to yc+yp do
for x:=xc+xn to xc+xp do
if (x>=x1) and (x<=x2) and
(y>=y1) and (y<=y2) then
begin
if map[x,y]<>0 then inc(a);
end else inc(a);
Get:=a;
end;
begin
{ push first position on stack and draw it }
map[x,y]:=1; sp:=1; st[1].x:=x; st[1].y:=y; DField(x,y);
repeat
FillChar(d,4,false); { no direction checked so far }
repeat
{ if wiggly enough get random direction }
if random(100)>wiggle_pc then r:=random(4)+1;
{ if direction impossible retry }
if d[r] then r:=0 else
case r of
1:begin { up }
if Get(x,y-1,-w,-w,+w,0)>0 then
begin { if obstacles ahead }
{ retry and remember direction impossible}
r:=0; d[1]:=true;
end;
end;
2:begin { down }
if Get(x,y+1,-w,0,+w,+w)>0 then
begin
r:=0; d[2]:=true;
end;
end;
3:begin { left }
if Get(x-1,y,-w,-w,0,+w)>0 then
begin
r:=0; d[3]:=true;
end;
end;
4:begin { right }
if Get(x+1,y,0,-w,+w,+w)>0 then
begin
r:=0; d[4]:=true;
end;
end;
end;
until (r<>0) or (d[1] and d[2] and d[3] and d[4]);
{ until direction found or all tried }
if r=0 then { if all tried }
begin { pop position from stack }
x:=st[sp].x; y:=st[sp].y; dec(sp);
end else
begin
case r of { else change position }
1:dec(y);
2:inc(y);
3:dec(x);
4:inc(x);
end;
map[x,y]:=1; { write and push on stack }
inc(sp); st[sp].x:=x; st[sp].y:=y;
DField(x,y);
end;
until sp=0;
end;
begin
ClrScr; randomize;
repeat
CMap; DMap;
Generate(x2 div 2,y2 div 2,2,80);
FMap; DMap;
until readkey=#27;
end.
|
Back to Top of Page
|