Комбинаторные алгоритмы для программистов



             

Автоматическое построение лабиринтов - часть 2


program Maze; uses Graph, Crt;

var m,n: Integer; Matrix: array [1..100,1..100] of Boolean; Start,Finish: Integer;

procedure PrepareGraph; var Driver,Mode: Integer; begin Driver:=VGA; Mode:=VGAHi; InitGraph(Driver,Mode,'c:\borland\tp\bgi'); end;

procedure DisplayMaze(x1,y1,x2,y2: Integer); var i,j: Integer; dx,dy: Real; begin SetFillStyle(1,8); SetColor(15); dx:=(x2-x1)/m; dy:=(y2-y1)/n; for i:=1 to n do for j:=1 to m do if not Matrix[i,j] then Rectangle(Round(x1+(i-1)*dx),Round(y1+(j-1)*dy), Round(x1+i*dx),Round(y1+j*dy)); end;

function CreatesPath(i,j: Integer): Boolean; var Result: Boolean; Count: Integer; ii,jj: Integer; begin Count:=0; if (i>1) and Matrix[i-1,j] then Inc(Count); if (i<m) and Matrix[i+1,j] then Inc(Count); if (j>1) and Matrix[i,j-1] then Inc(Count); if (j<m) and Matrix[i,j+1] then Inc(Count); if Count>1 then Result:=true else Result:=false; CreatesPath:=Result; end;

function DeadEnd(i,j: Integer): Boolean; var Result: Boolean; Count: Integer; begin Count:=0; if (i=2) or CreatesPath(i-1,j) then Inc(Count); if (i=m-1) or CreatesPath(i+1,j) then Inc(Count); if (j=2) or CreatesPath(i,j-1) then Inc(Count); if (j=n-1) or CreatesPath(i,j+1) then Inc(Count); if Count=4 then Result:=true else Result:=false; DeadEnd:=Result; end;

function CreateMaze: Boolean; var i,j: Integer; di,dj: Integer; Result: Boolean; begin Randomize; for i:=1 to n do for j:=1 to m do Matrix[i,j]:=false; Start:=Random(m-2)+2; i:=Start; j:=2; Matrix[Start,1]:=true; repeat Matrix[i,j]:=true; di:=0; dj:=0; while (di=0) and (dj=0) do begin di:=1-Random(3); if (i+di=1) or (i+di=m) then di:=0; if di=0 then dj:=1-Random(3); if j+dj=1 then dj:=0; if CreatesPath(i+di,j+dj) then begin di:=0; dj:=0; end; end; i:=i+di; j:=j+dj; until DeadEnd(i,j) or (j=n); Finish:=i; Matrix[Finish,n]:=true; if j<n then Result:=false else Result:=true; CreateMaze:=Result; end;

begin m:=6; n:=6;

PrepareGraph; repeat ClearDevice; repeat until CreateMaze; DisplayMaze(120,40,520,440); repeat until KeyPressed; until ReadKey=#27; CloseGraph; end.




Содержание  Назад  Вперед