Thuật toán xây dựng mê cung

ChuyÖn thÇn tho¹i th× lµ như vËy, cßn mª cung th× ®· hÊp dÉn nhiÒu nhµ kiÕn tróc, ho¹ sÜ, thi sÜ trong hµng chôc thÕ kØ quạ C¸c nhµ to¸n häc còng chó ý ®Õn mª cung v× nã mang nhiÒu ý ngh

VIETBOOK

ThuËt to¸n x©y dùng mª cung

Trong thÇn tho¹i Hi L¹p, cã con quû Min«to rÊt hung d÷, ë trong mét hang s©ụ §ưêng ®i vµo hang lµ mét

mª cung, ai cã can ®¶m vµo diÖt quû th× còng kh«ng dÔ g× lÇn ®ưîc vµo hang quû mµ cßn cã thÓ bÞ l¹c, kh«ng t×m ®ưîc lèi rạ Ngưêi anh hïng Tªzª ®· liÒu m×nh vµo hang quû §Ó gióp anh, nµng Arian ®· ®ưa cho Tªzª mét cuén chØ vµ nµng cÇm ®Çu mèị Khi vµo mª lé th× Tªzª kÐo dÇn cuén chØ, ®Õn lóc quay vÒ th× chØ cÇn cuèn chØ l¹i ®Ó lÇn theo ®ã mµ ra khái mª cung

ChuyÖn thÇn tho¹i th× lµ như vËy, cßn mª cung th× ®· hÊp dÉn nhiÒu nhµ kiÕn tróc, ho¹ sÜ, thi sÜ trong hµng chôc thÕ kØ quạ C¸c nhµ to¸n häc còng chó ý ®Õn mª cung v× nã mang nhiÒu ý nghÜa s©u s¾c liªn quan ®Õn nhiÒu ngµnh cña to¸n häc hiÖn ®¹ị Ngay trong cuéc sèng thưêng ngµy, chóng ta còng thưêng gÆp mª cung trong c¸c bµi to¸n ®è vui "T×m ®ưêng trong mª cung" Trong bµi b¸o nµy t«i xin giíi thiÖu víi c¸c b¹n mét thuËt to¸n x©y dùng mª cung kÝch thưíc tuú ý

Ta xem tÊt c¶ c¸c ®ưêng ®i trong mª cung lµ mét tËp hîp c¸c « ®ưîc nèi víi nhaụ Ban ®Çu tÊt c¶ c¸c «

®Òu kh«ng ®ưîc nèi vµ xung quanh tÊt c¶ c¸c « ®Òu cã tưêng LÊy mét bøc tưêng bÊt k× vµ kiÓm tra xem « ë bªn kia bøc tưêng cã ®ưîc nèi b»ng mét ®ưêng ®i nµo ®ã hay kh«ng NÕu ®óng như vËy, thö mét bøc tưêng kh¸c NÕu kh«ng th× ph¸ bøc tưêng vµ kÕt hîp hai tËp hîp ®ưêng ®i víi nhaụ

H×nh: Mét mª cung kÝch thưíc 20x20

Ta dïng mét m¶ng hai chiÒu ®Ó lưu l¹i mª cung x©y dùng ®ưîc Mçi thµnh phÇn cña m¶ng chøa gi¸ trÞ 1,

2 hoÆc b»ng 1 or 2, trong ®ã 1 biÓu thÞ lµ « cã tưêng däc, cßn 2 biÓu thÞ « cã tưêng ngang Ta sö dông hai cÊu tróc sau ®Ó thÓ hiÖn tËp hîp ®ưêng ®i vµ tËp hîp tưêng

PMazeCell = ^MazeCell;

MazeCell = record

(* Trá tíi ®Çu danh s¸ch tÊt c¶ c¸c « cã thÓ tíi ®ưîc tõ « nµỵ

DÔ dµng nhËn biÕt ®Ó cã thÓ so s¸nh *)

mset:PMazeCell;

(* Trá tíi « tiÕp theo cña tËp hîp c¸c « nèi víi nhau nµy *)

next:PMazeCell;

end;

PMazeWall=^MazeWall;

MazeWall = record

(* Cã tưêng hay kh«ng, tưêng ngang hay däc *)

wall:byte;

(* To¹ ®é cña bøc tưêng *)

x,y:integer;

end;

ThuËt to¸n x©y dùng mª cung:

1 Khëi t¹o:

Gäi walls vµ cells lµ hai biÕn trá ®Õn m¶ng tưêng vµ « DÔ thÊy sè « b»ng width*height, cßn sè bøc tưêng tèi

®a lµ (width-1)*height+(height-1)*width (kh«ng kÓ c¸c bøc tưêng n»m ë c¸c c¹nh cña mª cung) Ta gäi hµm GetMem ®Ó cÊp ph¸t bé nhí cho hai con trá trªn X©y tÊt c¶ c¸c bøc tưêng bëi vËy lóc nµy hai « bÊt k× kh«ng thÓ ®i ®Õn nhaụ Víi tÊt c¶ c¸c «, khëi t¹o trưêng mset trá tíi chÝnh nã, cßn trưêng next ®Æt b»ng nil (tËp hîp ®ưêng ®i chØ gåm mét «)

2 §æi chç ngÉu nhiªn m¶ng tưêng:

Ban ®Çu m¶ng tưêng ®ưîc s¾p xÕp theo thø tù: ®Çu tiªn lµ c¸c tưêng däc, sau ®Õn lµ c¸c tưêng ngang theo thø tù t¨ng dÇn cña to¹ ®é x vµ ỵ Ta lÇn lưît chän c¸c cÆp tưêng bÊt k× vµ ®æi chç chóng cho nhau ®Ó ®ưîc mét m¶ng tưêng ngÉu nhiªn

3 Xo¸ c¸c bøc tưêng ®Ó nhËp c¸c « vµo víi nhau:

B©y giê ta ®· cã mét danh s¸ch ngÉu nhiªn c¸c bøc tưêng Ta duyÖt l¹i danh s¸ch c¸c bøc tưêng Víi mçi bøc tưêng, ta chän « cã to¹ ®é lµ to¹ ®é cña bøc tưêng Xem xÐt « ë phÝa bªn kia bøc tưêng liÖu hai « cã

®ưîc nèi víi nhau b»ng mét ®ưêng nµo ®ã hay kh«ng §iÒu nµy cã thÓ kiÓm tra b»ng mét lÖnh if như sau:

if cậmset = cb^.mset then

NÕu chóng chưa ®ưîc nèi th× ta ph¸ bøc tưêng (®Æt trưêng wall = 0 ) vµ nèi chóng l¹i b»ng thñ tôc

VIETBOOK

ConnectSets:

procedure ConnectSets(mset,add:PMazeCell);

begin

(* Chuyển đến cuối danh sách *)

while mset^.next<>nil do mset:=mset^.next;

(* Trỏ đến đầu danh sách *)

add:=add^.mset;

(* Gắn vào các ô mới *)

mset^.next:=add;

(* Thay đổi tính đồng nhất của các ô mới *)

while add <> nil do

begin

add^.mset:=mset^.mset;

add:=add^.next;

end;

end;

4 Ghi kết quả:

Công việc còn lại bây giờ chỉ là ghi kết quả ra mảng output Trước hết ta đặt tất cả các bức tường ở các cạnh của mê cung Và sau đó thì chép các bức tường từ mảng tường vào mảng output

Trên đây là một thuật toán để tạo mê cung, rất mong nhận được sự góp ý của các bạn

Nguyễn Minh Thắng

11A Tin Đại Học Khoa Học Tự Nhiên, Hà Nội

uses crt,graph;

type

PMazeCell = ^MazeCell;

MazeCell = record

mset,next:PMazeCell;

end;

PMazeWall=^MazeWall;

MazeWall = record

wall:byte;

x,y:integer;

end;

const

Vert=1;

Horiz=2;

var

maze:array[0 100,0 100] of byte;

gd,gm,w,h:integer;

procedure ConnectSets(mset,add:PMazeCell);

begin

while mset^.next<>nil do mset:=mset^.next;

add:=add^.mset;

mset^.next:=add;

while add<> nil do

begin

add^.mset:=mset^.mset;

add:=add^.next;

end;

end;

procedure GenerateMaze(width,height:integer);

VIETBOOK

var

cells:PMazeCell;

walls:PMazeWall;

ncells,nwalls:integer;

i,x,y:integer;

ca,cb:PMazeCell;

w,temp:PMazeWall;

wt:MazeWall;

function CellAt(x,y:integer):pointer;

begin

CellAt:=pointer(longint(cells)+(x+y*width)*sizeof(MazeCell)); end;

begin

randomize;

ncells:=width*height;

GetMem(cells,sizeof(MazeCell)*ncells);

nwalls:=(width-1)*height+(height-1)*width;

GetMem(walls,sizeof(MazeWall)*nwalls);

ca:=cells;

for i:=1 to ncells do

begin

cậmset:=ca;

cậnext:=nil;

ca:=pointer(longint(ca)+sizeof(MazeCell));

end;

w:=walls;

for x:=1 to width-1 do

for y:=0 to height-1 do

begin

w^.wall:=Vert;

w^.x:=x;

w^.y:=y;

w:=pointer(longint(w)+sizeof(mazewall));

end;

for y:=1 to height-1 do

for x:=0 to width-1 do

begin

w^.wall:=Horiz;

w^.x:=x;

w^.y:=y;

w:=pointer(longint(w)+sizeof(MazeWall));

end;

for i:=nwalls-1 downto 1 do

begin

w:=pointer(longint(walls)+random(i)*sizeof(MazeWall)); wt:=w^;

temp:=pointer(longint(walls)+i*sizeof(MazeWall));

w^:=temp^;

temp^:=wt;

end;

w:=walls;

for i:=0 to nwalls-1 do

begin

VIETBOOK

ca:=CellAt(w^.x,w^.y);

if w^.wall=Horiz then

cb:=CellAt(w^.x,w^.y-1)

else

cb:=CellAt(w^.x-1,w^.y);

if cậmset <> cb^.mset then

begin

ConnectSets(ca,cb);

w^.wall:=0;

end;

w:=pointer(longint(w)+sizeof(mazewall))

end;

FillChar(maze,SizeOf(maze),0);

for x:=0 to width-1 do

begin

maze[x,0]:=Horiz;

maze[x,height]:=Horiz;

end;

for y:=0 to height-1 do

begin

maze[0,y]:=Vert;

maze[width,y]:=Vert;

end;

w:=walls;

for i:=0 to nwalls-1 do

begin

maze[w^.x,w^.y]:=maze[w^.x,w^.y] or w^.wall;

w:=pointer(longint(w)+sizeof(mazewall))

end;

FreeMem(cells,sizeof(MazeCell)*ncells);

FreeMem(walls,sizeof(MazeWall)*nwalls);

end;

procedure TestMaze;

var

i,j:integer;

ch:char;

begin

clrscr;

Writeln('Hay nhap vao kich thuoc me cung');

Write('Rong (<=55): ');readln(w);

Write('Cao (<=55): ');readln(h);

gd:=detect;

InitGraph(gd,gm,'');

Inc(w);Inc(h);

repeat

cleardevice;

GenerateMaze(w,h);

MoveTo((GetMaxX-(w-1)*8) div 2,(GetMaxY-(h-1)*8) div 2); Rectangle(GetX,GetY,GetX+(w-1)*8,GetY+(h-1)*8);

for i:=1 to w-1 do

for j:=1 to h-1 do

begin

if (maze[i,j] and Vert)<>0 then

VIETBOOK

Line(GetX+i*8,GetY+(j-1)*8,GetX+i*8,GetY+j*8);

if (maze[i,j] and Horiz)<>0 then

Line(GetX+(i-1)*8,GetY+j*8,GetX+i*8,GetY+j*8); end;

repeat

ch:=readkey;

until (ch=#27) or (ch=#13);

until ch=#27;

end;

begin

TestMaze;

end