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..
?

Other Threads