簡單易懂的亂數迷宮創造
Maze generation algorithm
DFS
Recursive backtracker
Maze generation algorithm
DFS
Recursive backtracker
狀態顯示:還在發燒中
~已經連放兩天還沒退真是意外~還是差不多到極限了啊
總之考慮的結果還是在期中考前丟這篇整理一下
不然我看之後就忘光了
﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍參考﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍
How to Build a Maze
Step by step perfect maze generation with php
Maze generation algorithm『維基』
Maze Classification
﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍
不曉得為啥我找不到中文資料= =|||
因為身體狀況不佳~所以寫出來的東西就ㄎㄎㄎ
我覺得這個就是Recursive backtracker法啦~不過不確定就是
流程如下
創造一個A*B矩陣全部先標記為未訪問過
隨便選一點(或選0,0當起點)M設為訪問過
---------------------------------------------------------------
假如M四周有未訪問的點
亂數選擇一個M四周未訪問的點N設為訪問過
把M,N之間的牆敲掉
PUSH(M)
M=N;
else
M=pop();//把M設為上一個訪問過得點
﹍﹍﹍一直重複到所有點都訪問過﹍﹍﹍﹍﹍
創造完成~可喜可賀可喜可賀
這時我居然糾結在很蠢的地方~迷宮點1代表不能走0代表可以走......哪來的牆= =|||
果然生病狀態腦子沒清醒啊~
我的點 0
真正的點
0
000
0
我把通路也當作一個點了~(yay)
流程如下
創造一個A*B矩陣全部先標記為未訪問過
隨便選一點(或選0,0當起點)M設為訪問過
---------------------------------------------------------------
假如M四周有未訪問的點
亂數選擇一個M四周未訪問的點N設為訪問過
把M,N之間的牆敲掉
PUSH(M)
M=N;
else
M=pop();//把M設為上一個訪問過得點
﹍﹍﹍一直重複到所有點都訪問過﹍﹍﹍﹍﹍
創造完成~可喜可賀可喜可賀
這時我居然糾結在很蠢的地方~迷宮點1代表不能走0代表可以走......哪來的牆= =|||
果然生病狀態腦子沒清醒啊~
我的點 0
真正的點
0
000
0
我把通路也當作一個點了~(yay)
範例~也就是說5*5迷宮只會有3*3個節點~(標示為1的部份)其他都是通路罷了~
也因為寫法是只拆點跟點之間的牆~所以其實有四個位置一定不能走
此種寫法會造成
點跟點一定能連通~所以如果起點跟終點都是節點位置絕對能通行
不過偶數情況的迷宮會造成
也因為寫法是只拆點跟點之間的牆~所以其實有四個位置一定不能走
此種寫法會造成
點跟點一定能連通~所以如果起點跟終點都是節點位置絕對能通行
不過偶數情況的迷宮會造成
終點位置不在節點~所以會有無解得情況
而且如果是偶數方陣會造成旁邊通通都是牆XDDDD
解決方法可以自己敲一下路讓終點可以跟最近的節點相通即可
最後:亂數出來的一個迷宮裡面可以走得區域的數量一定是節點數量*2
也就是說如果是27*27的迷宮能走得數量只有196*2=392
這關係到解這個迷宮所需要的堆疊大小~(還真小XD)
而且如果是偶數方陣會造成旁邊通通都是牆XDDDD
解決方法可以自己敲一下路讓終點可以跟最近的節點相通即可
最後:亂數出來的一個迷宮裡面可以走得區域的數量一定是節點數量*2
也就是說如果是27*27的迷宮能走得數量只有196*2=392
這關係到解這個迷宮所需要的堆疊大小~(還真小XD)
補充說明:
其實stack可以直接用stl裡面的~不過因為想順便拿去教作業所以就自己寫勒
ps.top初值設0 是我的習慣
方向數組x,y各一個陣列也是我的習慣
#include<ctime>為了time()
#include<cstdlib>為了rand()
*為不可走 -為可走 o為起點 x為終點
雖然stack能存2000個點不過因為最多只能創27*27所以根本用不到這麼多
﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍
因為頭暈害我維基都沒有好好看完所有的創造方法(誰叫維基都只寫英文)
能修正的地方搞不好很多~不過我再不看書會被21吧(苦笑
而且還有個騙錢計畫申請書的樣子QQ~不曉得無聊的東西能不能叫人代寫
電網(3)電子(3)+行動(3)+英文(2)=11
.....凎!剛好二分之一!吃到鐵板了我,還有線代(3)耶
.....都是給我胡亂排必修的錯
我還想去翻譯pA跟pG耶QwQ
期中考真是有夠浪費時間~考試方式還有夠老古
抱怨結束~去背一背隨便GOOGLE就能知道的東西應付考試去
PS.別一直跟我說最小生成樹啦!就說我圖論很爛嘛QQ
其實stack可以直接用stl裡面的~不過因為想順便拿去教作業所以就自己寫勒
ps.top初值設0 是我的習慣
方向數組x,y各一個陣列也是我的習慣
#include<ctime>為了time()
#include<cstdlib>為了rand()
*為不可走 -為可走 o為起點 x為終點
雖然stack能存2000個點不過因為最多只能創27*27所以根本用不到這麼多
﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍
因為頭暈害我維基都沒有好好看完所有的創造方法(誰叫維基都只寫英文)
能修正的地方搞不好很多~不過我再不看書會被21吧(苦笑
而且還有個騙錢計畫申請書的樣子QQ~不曉得無聊的東西能不能叫人代寫
電網(3)電子(3)+行動(3)+英文(2)=11
.....凎!剛好二分之一!吃到鐵板了我,還有線代(3)耶
.....都是給我胡亂排必修的錯
我還想去翻譯pA跟pG耶QwQ
期中考真是有夠浪費時間~考試方式還有夠老古
抱怨結束~去背一背隨便GOOGLE就能知道的東西應付考試去
PS.別一直跟我說最小生成樹啦!就說我圖論很爛嘛QQ