Thuật Toán Xây Dựng Mê Cung - Tài Liệu Text - 123doc

Tải bản đầy đủ (.pdf) (5 trang)

1. Trang chủ
>>
2. Giáo Dục - Đào Tạo
>>
3. Trung học cơ sở - phổ thông

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

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (50.46 KB, 5 trang )

VIETBOOKThuật toán xây dựng mê cungTrong 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ộtmê 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 đã đacho 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àngchụ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 đếnnhiề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ê cungtrong 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ộtthuậ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ờngkhá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 để lu 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 haicấ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ọihà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 theothứ 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 để đợcmộ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ỗibứ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 thenNếu chúng cha đợ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ụcTrang 1VIETBOOKConnectSets: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 dobeginadd^.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ạnhcủ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ắng11A Tin Đại Học Khoa Học Tự Nhiên, Hà Nộiuses crt,graph;typePMazeCell = ^MazeCell;MazeCell = recordmset,next:PMazeCell;end;PMazeWall=^MazeWall;MazeWall = recordwall:byte;x,y:integer;end;constVert=1;Horiz=2;varmaze:array[0..100,0..100] of byte;gd,gm,w,h:integer;procedure ConnectSets(mset,add:PMazeCell);beginwhile mset^.nextnil do mset:=mset^.next;add:=add^.mset;mset^.next:=add;while add nil dobeginadd^.mset:=mset^.mset;add:=add^.next;end;end;procedure GenerateMaze(width,height:integer);Trang 2VIETBOOKvarcells:PMazeCell;walls:PMazeWall;ncells,nwalls:integer;i,x,y:integer;ca,cb:PMazeCell;w,temp:PMazeWall;wt:MazeWall;function CellAt(x,y:integer):pointer;beginCellAt:=pointer(longint(cells)+(x+y*width)*sizeof(MazeCell));end;beginrandomize;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 dobeginca^.mset:=ca;ca^.next:=nil;ca:=pointer(longint(ca)+sizeof(MazeCell));end;w:=walls;for x:=1 to width-1 dofor y:=0 to height-1 dobeginw^.wall:=Vert;w^.x:=x;w^.y:=y;w:=pointer(longint(w)+sizeof(mazewall));end;for y:=1 to height-1 dofor x:=0 to width-1 dobeginw^.wall:=Horiz;w^.x:=x;w^.y:=y;w:=pointer(longint(w)+sizeof(MazeWall));end;for i:=nwalls-1 downto 1 dobeginw:=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 dobeginTrang 3VIETBOOKca:=CellAt(w^.x,w^.y);if w^.wall=Horiz thencb:=CellAt(w^.x,w^.y-1)elsecb:=CellAt(w^.x-1,w^.y);if ca^.mset cb^.mset thenbeginConnectSets(ca,cb);w^.wall:=0;end;w:=pointer(longint(w)+sizeof(mazewall))end;FillChar(maze,SizeOf(maze),0);for x:=0 to width-1 dobeginmaze[x,0]:=Horiz;maze[x,height]:=Horiz;end;for y:=0 to height-1 dobeginmaze[0,y]:=Vert;maze[width,y]:=Vert;end;w:=walls;for i:=0 to nwalls-1 dobeginmaze[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;vari,j:integer;ch:char;beginclrscr;Writeln('Hay nhap vao kich thuoc me cung');Write('Rong (