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

pdf
Số trang Thuật toán xây dựng mê cung 5 Cỡ tệp Thuật toán xây dựng mê cung 50 KB Lượt tải Thuật toán xây dựng mê cung 0 Lượt đọc Thuật toán xây dựng mê cung 2
Đánh giá Thuật toán xây dựng mê cung
4 ( 3 lượt)
Nhấn vào bên dưới để tải tài liệu
Để tải xuống xem đầy đủ hãy nhấn vào bên trên
Chủ đề liên quan

Nội dung

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^.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); 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 (<=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 Trang 4 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
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.