# Board index » delphi » Automatic Maze/Labyrint genaration ?

## Automatic Maze/Labyrint genaration ?

Does Anyone know how to generate a solvable random maze with a
variable width and height into an array like

Var
Map : Array[0..74,0..74] of Byte;

Procedure MakeMaze(W, H : Byte);
Begin
............
............
............
............
End;

Where 0 is no wall and 1 is a wall

I have simple algorithim but there are too many straight long walls.

Thanks in advance.

## Re:Automatic Maze/Labyrint genaration ?

Yeah, me too please!

##### Quote
MandARK wrote:
> Does Anyone know how to generate a solvable random maze with a
> variable width and height into an array like

> Var
> ?? Map : Array[0..74,0..74] of Byte;

> Procedure MakeMaze(W, H : Byte);
> Begin
> ?? ............
> ?? ............
> ?? ............
> ?? ............
> End;

> Where 0 is no wall and 1 is a wall

> I have simple algorithim but there are too many straight long walls.

> Thanks in advance.

--
|? Algirdas 'Ze{*word*104}' Kepezinskas
|? E-Mail: cy...@vil.ktu.lt
|? ICQ 14187537
|? URL: http://www.botepidemic.com/fmods
+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*++*+*+*+*
|? If time is killing you
|?????????????????? kill some for time..
?

## Re:Automatic Maze/Labyrint genaration ?

##### Quote
MandARK wrote:

> Does Anyone know how to generate a solvable random maze with a
> variable width and height into an array like

> Var
>    Map : Array[0..74,0..74] of Byte;

> Where 0 is no wall and 1 is a wall

Hello MandARK.

Here's a maze-generator using your maze-definition.
It creates mazes, where every field of the maze is reachable
from every other field by exact one way.
Note, that Width and Height must be odd, but could else be
of any size between 3 and the array-size (75 in your
definition).

Var
Map : Array[0..74,0..74] of Byte;  // The maze as you defined it.
// 0 is no wall and 1 is a wall

Function SelectDirection(var DeltaX,DeltaY:integer;
const x,y,Width,Height:integer):boolean;
// Subroutine of MakeMaze.
// Selects an unvisited neighbour-field of (x/y).
// Result: FALSE: no unvisited neighbours, else TRUE.
// DeltaX,DeltaY: Direction of the selected neighbour.
begin
// Check for unvisited neighbours
result:=((y>1) and (Map[x,y-2]=1))
or ((y<Height-3) and (Map[x,y+2]=1))
or ((x>1) and (not Map[x-2,y]=1))
or ((x<Width-3) and (Map[x+2,y]=1));
// Select random neighbour
if result then begin
DeltaX:=0;
DeltaY:=0;
repeat
case random(4) of
0: if (y>1) and (Map[x,y-2]=1) then DeltaY:=-1;
1: if (y<Height-3) and (Map[x,y+2]=1) then DeltaY:=1;
2: if (x>1) and (Map[x-2,y]=1) then DeltaX:=-1;
3: if (x<Width-3) and (Map[x+2,y]=1) then DeltaX:=1;
end
until (DeltaX<>0) or (DeltaY<>0);
end;
end;

Procedure MakeMaze(Width, Height : Byte);
// Creates a random maze in the global array MAP
// where 0 is no wall and 1 is a wall.
// Width and Height must be an odd number!
label lStartField;
var x,y          : integer; // Actual position
DeltaX,DeltaY: integer; // Moving-direction
Begin
// Init
randomize;

// Set all the walls of the complete maze (so there is no way
// from any field to any other). Set all the Fields to 1 too as
// a Flag that it is not visited yet.
for x:=0 to Width do
for y:=0 to Height do
Map[x,y]:=1;

// Set starting-position.
x:=1;
y:=1;

repeat
while TRUE do begin
//  Mark the actual field as visited
Map[x,y]:=0;

// If there is any none visited neighbour-field then
// select one of them randomly. Else quit this loop.
if not SelectDirection(DeltaX,DeltaY,x,y,Width,Height) then
break;
// Remove the wall to the selected neighbour
Map[x+DeltaX,y+DeltaY]:=0;
// and make it your actual field.
inc(x,DeltaX*2);
inc(y,DeltaY*2);
end;

// Select a new starting-field with at least one visited
// neighbour.
x:=1;
y:=1;
while y<Height do begin
while x<Width do begin
if Map[x,y]=1 then goto lStartField;
inc(x,2);
end;
inc(y,2);
x:=1;
end;
lStartField:

if y<Height then begin  // unvisited field found?
// Remove the wall to a visited neigbour.
if y>1 then
Map[x,y-1]:=0
else
Map[x-1,y]:=0;
end;
// If there is no unvisited field left in your maze, you are
finished.
until y>=Height;
End;

Hope, I could help,
Klaus

## Re:Automatic Maze/Labyrint genaration ?

In article <36CAE220.7E549...@vil.ktu.lt>, someone calling themselves Algirdas Kepezinskas <cy...@vil.ktu.lt> wrote:

The simplest way to mark the path through the maze would be to fill
the path with a new number. That is, if you're using 0 for walls and 1
for the maze, then use 2 for the path.

Mab

##### Quote
>Well, it works, however its a porr algorythm.
>Anyway, I wrote a solver
>for this maze (atached). It works ok. But the
>problem is - how do i mark
>shortest path needed to access final location?
>Thanx.

>Klaus Diemer wrote:

>> MandARK wrote:

>> > Does Anyone know how to generate a solvable random maze with a
>> > variable width and height into an array like

>> > Var
>> >??? Map : Array[0..74,0..74] of Byte;

>> > Where 0 is no wall and 1 is a wall

>> Hello MandARK.

>> Here's a maze-generator using your maze-definition.
>> It creates mazes, where every field of the maze is reachable
>> from every other field by exact one way.
>> Note, that Width and Height must be odd, but could else be
>> of any size between 3 and the array-size (75 in your
>> definition).

>> Var
>> ?? Map : Array[0..74,0..74] of Byte;? // The maze as you defined it.
>> ????????????????????????????????????? // 0 is no wall and 1 is a wall

>> Function SelectDirection(var DeltaX,DeltaY:integer;
>> ???????????????????????? const x,y,Width,Height:integer):boolean;
>> // Subroutine of MakeMaze.
>> // Selects an unvisited neighbour-field of (x/y).
>> // Result: FALSE: no unvisited neighbours, else TRUE.
>> // DeltaX,DeltaY: Direction of the selected neighbour.
>> begin
>> ?? // Check for unvisited neighbours
>> ?? result:=((y>1) and (Map[x,y-2]=1))
>> ????????? or ((y<Height-3) and (Map[x,y+2]=1))
>> ????????? or ((x>1) and (not Map[x-2,y]=1))
>> ????????? or ((x<Width-3) and (Map[x+2,y]=1));
>> ?? // Select random neighbour
>> ?? if result then begin
>> ????? DeltaX:=0;
>> ????? DeltaY:=0;
>> ????? repeat
>> ???????? case random(4) of
>> ??????????? 0: if (y>1) and (Map[x,y-2]=1) then DeltaY:=-1;
>> ??????????? 1: if (y<Height-3) and (Map[x,y+2]=1) then DeltaY:=1;
>> ??????????? 2: if (x>1) and (Map[x-2,y]=1) then DeltaX:=-1;
>> ??????????? 3: if (x<Width-3) and (Map[x+2,y]=1) then DeltaX:=1;
>> ???????? end
>> ????? until (DeltaX<>0) or (DeltaY<>0);
>> ?? end;
>> end;

>> Procedure MakeMaze(Width, Height : Byte);
>> // Creates a random maze in the global array MAP
>> // where 0 is no wall and 1 is a wall.
>> // Width and Height must be an odd number!
>> label lStartField;
>> var x,y????????? : integer; // Actual position
>> ??? DeltaX,DeltaY: integer; // Moving-direction
>> Begin
>> ?? // Init
>> ?? randomize;

>> ?? // Set all the walls of the complete maze (so there is no way
>> ?? // from any field to any other). Set all the Fields to 1 too as
>> ?? // a Flag that it is not visited yet.
>> ?? for x:=0 to Width do
>> ????? for y:=0 to Height do
>> ???????? Map[x,y]:=1;

>> ?? // Set starting-position.
>> ?? x:=1;
>> ?? y:=1;

>> ?? repeat
>> ????? while TRUE do begin
>> ???????? //? Mark the actual field as visited
>> ???????? Map[x,y]:=0;

>> ???????? // If there is any none visited neighbour-field then
>> ???????? // select one of them randomly. Else quit this loop.
>> ???????? if not SelectDirection(DeltaX,DeltaY,x,y,Width,Height) then
>> ??????????? break;
>> ???????? // Remove the wall to the selected neighbour
>> ???????? Map[x+DeltaX,y+DeltaY]:=0;
>> ???????? // and make it your actual field.
>> ???????? inc(x,DeltaX*2);
>> ???????? inc(y,DeltaY*2);
>> ????? end;

>> ????? // Select a new starting-field with at least one visited
>> ????? // neighbour.
>> ????? x:=1;
>> ????? y:=1;
>> ????? while y<Height do begin
>> ???????? while x<Width do begin
>> ??????????? if Map[x,y]=1 then goto lStartField;
>> ??????????? inc(x,2);
>> ???????? end;
>> ???????? inc(y,2);
>> ???????? x:=1;
>> ????? end;
>> lStartField:

>> ????? if y<Height then begin? // unvisited field found?
>> ???????? // Remove the wall to a visited neigbour.
>> ???????? if y>1 then
>> ??????????? Map[x,y-1]:=0
>> ???????? else
>> ??????????? Map[x-1,y]:=0;
>> ????? end;
>> ?? // If there is no unvisited field left in your maze, you are
>> finished.
>> ?? until y>=Height;
>> End;

>> Hope, I could help,
>> ?? Klaus

## Re:Automatic Maze/Labyrint genaration ?

##### Quote
Algirdas Kepezinskas wrote:

> Well, it works, however its a porr algorythm.
> Anyway, I wrote a solver
> for this maze (atached).

Hello Algirdas.

You find the algorithm makes poor mazes? Yes, the algorithm is designed
to make mazes without loops, so they could easy solved by the
"right-hand"-algorithm you used. If you want a greater challenge, simply
break down some additional walls, so that you get loops. Your solver
would fail with such mazes.

Here's a procedure, that makes such loops for my maze-generater
published earlier:

Procedure AddLoops(const Width,Height,Count:integer);
// Breaks COUNT holes in the walls, creating loops in the maze.
var i,x,y: integer;
begin
for i:=1 to count do begin
repeat
if random(2)=0 then begin
x:=random((Width-3) div 2)*2+2;
y:=random((Height-1) div 2)*2+1;
end
else
begin
x:=random((Width-1) div 2)*2+1;
y:=random((Height-3) div 2)*2+2;
end;
until Map[x,y]=1;
Map[x,y]:=0;
end;
end;

I have written a maze-solver, which could solve mazes with loops. If you
want to see it, mail me.

Greetings,
Klaus

## Re:Automatic Maze/Labyrint genaration ?

Yeah, I did it. But it mark all the path, and not the shortest one. I tryied unmarking path if it steps over it once
more - doesnt help.

##### Quote
Mab wrote:
> In article <36CAE220.7E549...@vil.ktu.lt>, someone calling themselves Algirdas Kepezinskas <cy...@vil.ktu.lt> wrote:

> The simplest way to mark the path through the maze would be to fill
> the path with a new number. That is, if you're using 0 for walls and 1
> for the maze, then use 2 for the path.

> Mab

> >Well, it works, however its a porr algorythm.
> >Anyway, I wrote a solver
> >for this maze (atached). It works ok. But the
> >problem is - how do i mark
> >shortest path needed to access final location?
> >Thanx.

> >Klaus Diemer wrote:

> >> MandARK wrote:

> >> > Does Anyone know how to generate a solvable random maze with a
> >> > variable width and height into an array like

> >> > Var
> >> >??? Map : Array[0..74,0..74] of Byte;

> >> > Where 0 is no wall and 1 is a wall

> >> Hello MandARK.

> >> Here's a maze-generator using your maze-definition.
> >> It creates mazes, where every field of the maze is reachable
> >> from every other field by exact one way.
> >> Note, that Width and Height must be odd, but could else be
> >> of any size between 3 and the array-size (75 in your
> >> definition).

> >> Var
> >>??? Map : Array[0..74,0..74] of Byte;? // The maze as you defined it.
> >>?????????????????????????????????????? // 0 is no wall and 1 is a wall

> >> Function SelectDirection(var DeltaX,DeltaY:integer;
> >>????????????????????????? const x,y,Width,Height:integer):boolean;
> >> // Subroutine of MakeMaze.
> >> // Selects an unvisited neighbour-field of (x/y).
> >> // Result: FALSE: no unvisited neighbours, else TRUE.
> >> // DeltaX,DeltaY: Direction of the selected neighbour.
> >> begin
> >>??? // Check for unvisited neighbours
> >>??? result:=((y>1) and (Map[x,y-2]=1))
> >>?????????? or ((y<Height-3) and (Map[x,y+2]=1))
> >>?????????? or ((x>1) and (not Map[x-2,y]=1))
> >>?????????? or ((x<Width-3) and (Map[x+2,y]=1));
> >>??? // Select random neighbour
> >>??? if result then begin
> >>?????? DeltaX:=0;
> >>?????? DeltaY:=0;
> >>?????? repeat
> >>????????? case random(4) of
> >>???????????? 0: if (y>1) and (Map[x,y-2]=1) then DeltaY:=-1;
> >>???????????? 1: if (y<Height-3) and (Map[x,y+2]=1) then DeltaY:=1;
> >>???????????? 2: if (x>1) and (Map[x-2,y]=1) then DeltaX:=-1;
> >>???????????? 3: if (x<Width-3) and (Map[x+2,y]=1) then DeltaX:=1;
> >>????????? end
> >>?????? until (DeltaX<>0) or (DeltaY<>0);
> >>??? end;
> >> end;

> >> Procedure MakeMaze(Width, Height : Byte);
> >> // Creates a random maze in the global array MAP
> >> // where 0 is no wall and 1 is a wall.
> >> // Width and Height must be an odd number!
> >> label lStartField;
> >> var x,y????????? : integer; // Actual position
> >>???? DeltaX,DeltaY: integer; // Moving-direction
> >> Begin
> >>??? // Init
> >>??? randomize;

> >>??? // Set all the walls of the complete maze (so there is no way
> >>??? // from any field to any other). Set all the Fields to 1 too as
> >>??? // a Flag that it is not visited yet.
> >>??? for x:=0 to Width do
> >>?????? for y:=0 to Height do
> >>????????? Map[x,y]:=1;

> >>??? // Set starting-position.
> >>??? x:=1;
> >>??? y:=1;

> >>??? repeat
> >>?????? while TRUE do begin
> >>????????? //? Mark the actual field as visited
> >>????????? Map[x,y]:=0;

> >>????????? // If there is any none visited neighbour-field then
> >>????????? // select one of them randomly. Else quit this loop.
> >>????????? if not SelectDirection(DeltaX,DeltaY,x,y,Width,Height) then
> >>???????????? break;
> >>????????? // Remove the wall to the selected neighbour
> >>????????? Map[x+DeltaX,y+DeltaY]:=0;
> >>????????? // and make it your actual field.
> >>????????? inc(x,DeltaX*2);
> >>????????? inc(y,DeltaY*2);
> >>?????? end;

> >>?????? // Select a new starting-field with at least one visited
> >>?????? // neighbour.
> >>?????? x:=1;
> >>?????? y:=1;
> >>?????? while y<Height do begin
> >>????????? while x<Width do begin
> >>???????????? if Map[x,y]=1 then goto lStartField;
> >>???????????? inc(x,2);
> >>????????? end;
> >>????????? inc(y,2);
> >>????????? x:=1;
> >>?????? end;
> >> lStartField:

> >>?????? if y<Height then begin? // unvisited field found?
> >>????????? // Remove the wall to a visited neigbour.
> >>????????? if y>1 then
> >>???????????? Map[x,y-1]:=0
> >>????????? else
> >>???????????? Map[x-1,y]:=0;
> >>?????? end;
> >>??? // If there is no unvisited field left in your maze, you are
> >> finished.
> >>??? until y>=Height;
> >> End;

> >> Hope, I could help,
> >>??? Klaus

--
|? Algirdas 'Ze{*word*104}' Kepezinskas
|? E-Mail: cy...@vil.ktu.lt
|? ICQ 14187537
|? URL: http://www.botepidemic.com/fmods
+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*++*+*+*+*
|? If time is killing you
|?????????????????? kill some for time..
?