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

Chia sẻ: Trần Bá Trung | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

135
lượt xem 34
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo về toán, cho các bạn đam mê, đào sâu hơn về kiến thức toán

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Thuật toán xây dựng mê cung

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©u. §−ê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 ra. 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èi. 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Ø qua. 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 ®¹i. 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 nhau. 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 nhau. 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µy. 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 nhau. 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µ y. 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 ca^.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 Trang 1
VIETBOOK ConnectSets: procedure ConnectSets(mset,add:PMazeCell); begin (* ChuyÓn ®Õn cuèi danh s¸ch *) while mset^.nextnil 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^.nextnil 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); Trang 2
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 ca^.mset:=ca; ca^.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 Trang 3
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 ca^.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 (
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. Trang 5