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