Board index » delphi » Maze/Labyrint generation

Maze/Labyrint generation

Can anybody please, give me some source, url,
algorythm of Maze/Labyrint generation (solveable),
and also inteligent solving?

--
|? 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:Maze/Labyrint generation


Quote
Algirdas Kepezinskas <cy...@vil.ktu.lt> writes:
> Can anybody please, give me some source, url, algorythm of
> Maze/Labyrint generation (solveable), and also inteligent
> solving?

-----------------------------------------------------------------
A common way to generate a solvable maze is to construct what's
known in graph theory as a spanning tree.  By definition, a maze
whose configuration of cells and pathways meet the requirements
of a spanning tree will have one and only one path from any cell
to any other cell.

Of course there are many ways to construct a spanning tree.
Someone has already posted an example using the random walk
method and as a short example of an alternative method, I'm
submitting the following:

  program maze;
  const width=25; leng=12;
  var  i,j,k,t,b:integer;
       row:array[1..1000] of integer;

  function isolated (i,s:integer):boolean;
  var j:integer;
  begin
    isolated:=true;
    for j:=s to width do if (row[j]=row[i]) and (i<>j) then isolated:=false
  end;

  begin
    randomize; b:=width;
    for i:=1 to width do begin write('+--'); row[i]:=i end; writeln('+');
    for i:=1 to leng-1 do begin
      write('|');
      for j:=1 to width-1 do begin
        if (random(100)<=80) and (row[j]<>row[j+1]) then begin
             write('   '); t:=row[j+1];
             for k:=1 to width do if row[k]=t then row[k]:=row[j]
           end
           else write('  |')
      end;
      writeln('  |');
      for j:=1 to width do begin
        if isolated(j,1) or (random(100)<=50) then write('+  ')
           else begin write('+--'); b:=b+1; row[j]:=b end
      end;
      writeln('+');
    end;
    write('|');
    for j:=1 to width-1 do begin
      if isolated(j,j+1) then begin
           write('   ');t:=row[j+1];
           for k:=1 to width do if row[k]=t then row[k]:=row[j]
         end
         else write('  |')
    end;
    writeln('  |');
    for j:=1 to width do write('+--'); write('+')
  end.

-----------------------------------------------------------------
Derek Asari
eq...@cleveland.freenet.edu

Re:Maze/Labyrint generation


Thanx, it just could be little more commented;)

Quote
Derek T. Asari wrote:
> Algirdas Kepezinskas <cy...@vil.ktu.lt> writes:

> > Can anybody please, give me some source, url, algorythm of
> > Maze/Labyrint generation (solveable), and also inteligent
> > solving?
> -----------------------------------------------------------------
> A common way to generate a solvable maze is to construct what's
> known in graph theory as a spanning tree.? By definition, a maze
> whose configuration of cells and pathways meet the requirements
> of a spanning tree will have one and only one path from any cell
> to any other cell.

> Of course there are many ways to construct a spanning tree.
> Someone has already posted an example using the random walk
> method and as a short example of an alternative method, I'm
> submitting the following:

> ? program maze;
> ? const width=25; leng=12;
> ? var? i,j,k,t,b:integer;
> ?????? row:array[1..1000] of integer;

> ? function isolated (i,s:integer):boolean;
> ? var j:integer;
> ? begin
> ??? isolated:=true;
> ??? for j:=s to width do if (row[j]=row[i]) and (i<>j) then isolated:=false
> ? end;

> ? begin
> ??? randomize; b:=width;
> ??? for i:=1 to width do begin write('+--'); row[i]:=i end; writeln('+');
> ??? for i:=1 to leng-1 do begin
> ????? write('|');
> ????? for j:=1 to width-1 do begin
> ??????? if (random(100)<=80) and (row[j]<>row[j+1]) then begin
> ???????????? write('?? '); t:=row[j+1];
> ???????????? for k:=1 to width do if row[k]=t then row[k]:=row[j]
> ?????????? end
> ?????????? else write('? |')
> ????? end;
> ????? writeln('? |');
> ????? for j:=1 to width do begin
> ??????? if isolated(j,1) or (random(100)<=50) then write('+? ')
> ?????????? else begin write('+--'); b:=b+1; row[j]:=b end
> ????? end;
> ????? writeln('+');
> ??? end;
> ??? write('|');
> ??? for j:=1 to width-1 do begin
> ????? if isolated(j,j+1) then begin
> ?????????? write('?? ');t:=row[j+1];
> ?????????? for k:=1 to width do if row[k]=t then row[k]:=row[j]
> ???????? end
> ???????? else write('? |')
> ??? end;
> ??? writeln('? |');
> ??? for j:=1 to width do write('+--'); write('+')
> ? end.

> -----------------------------------------------------------------
> Derek Asari
> eq...@cleveland.freenet.edu
> ?

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