先看看效果
本來是 只有文字的版本~
不過那個版本應該只有我看得懂~
所以就把貼圖的部分也一併弄了~
來講一下 DEMO
輸入 數字後 會產生一個正方形的 迷宮!
雖然根據我的寫法可以是長方形!
但是DEMO的部分 還是使用 正方形~
兩個圓點的部分是 出口 和 入口
入口 我固定在 0,0
出口 我就讓他隨機跑了
理論上 是除了 0,0 外都可以的
白色的路 是入口到出口的路!
其他顏色的路 一種顏色是代表一種 支路
然後迷宮理論上 是從 3~? 都可以的~
但是為了 好看的部分 這個DEMO 是從
8~100來做測試~
對了裡面的時間 是包含 畫出右邊的畫面的部分
所以比文章內的還要多一點
只有主體的SWF
先來定義一下 我所謂的迷宮
就是有一個入口
一個出口
然後入口可以走到出口
路中間會有叉路的地圖~~
先來講解迷宮建立的一些方法~
下面是找幾個我看得懂的方法來講解
但是也不敢說沒有誤導別人!
我這邊說的部分都很簡單 但是是最重要的幾個大方向!
但其實其中還是有相當多的細節要處理!
1. 掘路法
一開始的地圖是沒有路的
但是一路挖~挖到出口後~
然後再慢慢的把其他的挖完. (這是最簡單 最直觀的方法)
2. 棒倒法
先建立 基本的柱子 然後 慢慢的將柱子補起來~(或是應該說柱子倒下)
但是就算是補了起來
內部都是可以移動的
不會不能到下一層的情況~
然後上一層的出口 要和下一層的連接~
直到 挖滿為止~
這樣講解可能不好明白~但是去看
http://www5d.biglobe.ne.jp/~stssk/maze/make.html
的圖片的話 應該就比較容易了解~
3. 延伸牆法
由邊邊慢慢的把牆拉出來~
重點不能讓兩個拉出的牆 相連
但是可以把拉出的牆上再拉出牆~
不可以讓路斷掉
而且要把全部個格子用光~
然後迷宮就完成了~
很神奇 很意外 很簡單 很特殊的解法!
映像中~這是最快的一種!
4. 深度遍歷 (就是下面 PS 1 和 2 還有最後一篇的方式! 基本上要有一些 數學理論的基礎!)
類似 A*的方式
一個一個把可以移動的格子記錄(或者說 拆牆 )
然後再倒回的方式
直到全部的格子用光 然後迷宮就完成了
以上的方式~
都會是要成立在 奇數格下 才能建立迷宮~
雖然有一些偶數也是可以的~
但是生成的迷宮中包含牆的方式~
最好是要奇數才能 比較方便的完成~
才不會有一層都是牆的情況
在介紹一個優化的方法!
5. 分區法
上面全部的都可以使用這種方法優化!
其實也是從棒倒法出來的~~
分成小區塊 小區塊作~
理論上 不管是 方的 長的 都是可以切成四個 兩個 等等的方式~
只是切開的入口 要接 另外一個的出口!
確保可以入口一定走的到到出口!
這樣就是迷宮了
但是 不用棒倒法的方式~(因為只有棒倒法 會讓邊邊產生多個出口!)
會變成區塊與區塊間的支路不相通!
但是這樣可以有效的減少時間!
以我自己的方法來說 (demo 的部分是包涵 貼圖的部分)
10*10 = 大概 1~2 毫秒
20*20 = 大約 15~30毫秒
100*100 = 大約 4xx~6xx毫秒
如果20*20切成 四塊
用 10*10的拼接
大概也只要 4~8毫秒!
用來拼接 100 * 100 的大約是
1xx ~ 2xx毫秒
都比直接 作一個大塊的來的快!
如果再換一個方式想!
甚至 如果出口入口走不到的就不用生產和拼接!
更省! 不過地圖會 比較貧乏!
這邊就先不談了!
來談談這段差距得原因
主要的差距是 遍歷的部分~
10*10 從頭到尾 的時間
比
20*20 從頭到尾的時間
短很多
不過這個對 遍歷的次數越多的越有效!
遍歷次數越少~
那分區法 用處就不大了
甚至還沒有節約的效果
話說我自己是怎樣想也不是1 ~ 4 的方式
所以我弄出了自己的方式!
雖然沒啥理論~
不過基本的定義可以達成~
而且直觀
但是跟上面的方法比較並沒有比較快~
但是因為生成方式中~
不包含牆 只有路
所以理論上適合各種大小尺寸的地圖~
好現在就開始講解我的做法~
其實就是 第一種方式~~
掘路法 在經過一些變型~(參考過各種方式後 自己腦補的結果)
首先 他會從 入口 出口開時同時亂挖~
亂挖結束後~
然後利用 A* 尋路將出口 和 入口
亂挖出來的路連接起來~(最佳狀況~)
如果連不起來~就使用最短路徑~
然後再尋一次路~
把亂挖的路 和 最短路徑的路 權重 設成 2
重複的路徑設成 1然後再尋一次路~
(這段沒設權重的話 會分不清主路 和 叉路的分別...如果這邊不需要的話 也是可以不作)
這條路就設成 通路~
剩下的都當成 叉路來處理~
重點是我會記下每一條路的順序~
這樣在生成地圖時 有用~
特別在沒牆的版本中這點很重要~
因為 有牆的版本中
不會有下面這樣的路! ( 0 是牆 1是路)
111
011
011
而且這樣的解釋方式 很多種!
不過我也可以不記!
因為就算不記 也不會讓路 不能從頭走到尾!
問題是看貼圖的時候 怎樣去貼!
連著的格子都貼一樣可以走 (中間不會有牆)
或
貼成房間(2*3 開口在 0,0 和 1,2)!
或者
貼成
0,0 -> 1,0->2,0->2,1->1,1->1,2->2,2(路是單格 有牆 有方向性)
這樣的路!
但是 用 1~4的做法 都是無法產出
有小房間的迷宮!
但是可以生成後再特別去挖!
還有另外一個重點~
以後尋路的時候~
不用及時運算~
利用這個記錄下來的路 就可以輕易的尋路~
其他的雖然也可以在生產得時候記錄
但是 另外的分支都還要特別的去查 和記錄
不過我的應該也算從一開始就有目的的記錄
上面都是講一些我的方式的一些優點!
或者是特點!
那在講講我的生成方式的一些缺點~
1.
路是不會相連的~
不會有一條分支 會兩個開口
當然 分支上 是會長分支的~
但是不會有 D 字型的通路~
不過要 D 字型的通路 也可以
是透過 貼圖的部分去達成 !
應該這樣講! 因為理論的哪種我搞不定牆
所以 我的路 都是
2.
因為支線一定要從某條路上長出來
所以只能用路去找
會比找空格的方式來的慢~
而且可能會有漏掉的點~
上面的 拉伸 棒倒 深度遍歷 都是以空格的方式去找~(順序 從 0,0->0,1->0,2...)
但是我的卻要從路上找! (某些特殊點 不多跑幾次遞迴 還不一定找的到)
所以我的方法比上面的都還來的慢(一般情況 但是最佳情況是不一定)
至少 迴圈跑的次數是比較多的
3.
如果不填滿~但是要生成固定數量的支路!
其實這個生成方式非常快~
理論上生成從入口到出口的路 速度是差不多的~
但是我支線是從路上去生~
而且我不管牆! 其他的都會去考慮牆的部分
所以生成固定的支線的速度
會比從空格的去生來的快
但是如果要填滿~
那這個方式就非常的慢~
以下面的例子來說明!
1113
0213
0011
要把 0,3 這個點補起來 要兩次遞迴!
如果是 1~4的那些方法~
這樣的 空格
只需要一次遞迴就能解決!
我這的遞迴都是只從第一格 跑到最後一格
不過我的方法
是跑我的方法是跑路的格子
其他的方法是
跑全迷宮的格子
關於 CODE 的部分
package maze
{
import flash.display.BitmapData;
import flash.geom.Point;
public class MazeUtils
{
static public const WallTypt:int = 0;
static public const MainWayType:int = 1;
// 建立一個都是牆 沒有路的世界
static public function ceateEmptyMap(w:int, h:int):Array
{
var world:Array = new Array();
var j:int = 0;
for(var i:int= 0;i<h;i++)
{
world.push(new Array);
for(j=0;j<w;j++)
world[i][j] = WallTypt;
}
return world;
}
// 給任意兩點 會使用路來連接
static public function twoPointOneWay(world:Array, starPoint:Point, endPoint:Point, wayType:int, wayList:Array, lockObj:Object):void
{
var sArr:Array;
if(world[starPoint.y][starPoint.x] != WallTypt)
{ // 如果起點是可以走的話
sArr = onePointFindWay(world, starPoint, lockObj);
if(sArr.length < 0 )
return;
starPoint = sArr[int(sArr.length*RAND)];
}
if(world[endPoint.y][endPoint.x] != WallTypt)
{ // 如果終點是可以走的話
sArr = onePointFindWay(world, endPoint, lockObj);
if(sArr.length < 0 )
return;
endPoint = sArr[int(sArr.length*RAND)];
}
world[starPoint.y][starPoint.x] = wayType;
world[endPoint.y][endPoint.x] = wayType;
var starList:Array = onePointRandomWay(world, starPoint, wayType, world.length, lockObj);
var endList:Array = onePointRandomWay(world, endPoint, wayType, world.length, lockObj);
var sP:Point = starList[starList.length-1];
var eP:Point = endList[endList.length-1];
clearWorld(world, sP, WallTypt);
clearWorld(world, eP, WallTypt);
var fArr:Array = AstarUtil.findWayAstar(world, sP, eP, [1]);
if(!fArr)
{ // 如果沒辦法連線 那再找一條從起點到終點的路
var world2:Array = ceateEmptyMap(world.length, world[0].length);
fArr = AstarUtil.findWayAstar(world2, starPoint, endPoint, [1]);
// 畫到列表上
for(var i:int =0; i<fArr.length;i++)
{
if(world[fArr[i].y][fArr[i].x] == MainWayType)
world[fArr[i].y][fArr[i].x] = 3;
else
world[fArr[i].y][fArr[i].x] = 2;
}
//
var fArr2:Array = AstarUtil.findWayAstar(world, starPoint, endPoint, [AstarUtil.WALLCOST,2,100,1]);
for(i = 0; i<fArr2.length;i++)
world[fArr2[i].y][fArr2[i].x] = 4;
wayList.push(fArr2);
var j:int = 0;
// 轉成基準
for(i = 0; i<world.length;i++)
{
for(j=0;j<world[0].length;j++)
{
switch(world[i][j])
{
case 0:
break;
default:
world[i][j] = -2;
break;
case 4:
world[i][j] = MainWayType;
break;
}
}
}
//
var flag:Boolean = false;
var pp:Point;
for(i = 0; i<fArr.length;i++)
{
pp = fArr[i];
if(world[pp.y][pp.x] == MainWayType)
flag = false;
else if(world[pp.y][pp.x] == -2){
if(!flag) wayList.push(new Array);
flag = true;
wayList[wayList.length-1].push(pp);
world[pp.y][pp.x] = wayList.length;
}
}
//
flag = false;
for(i = 0; i<starList.length;i++)
{
pp = starList[i];
if(world[pp.y][pp.x] == MainWayType)
flag = false;
else if(world[pp.y][pp.x] == -2){
if(!flag) wayList.push(new Array);
flag = true;
wayList[wayList.length-1].push(pp);
world[pp.y][pp.x] = wayList.length;
}
}
//
flag = false;
for(i = 0; i<endList.length;i++)
{
pp = endList[i];
if(world[pp.y][pp.x] == MainWayType)
flag = false;
else if(world[pp.y][pp.x] == -2){
if(!flag) wayList.push(new Array);
flag = true;
wayList[wayList.length-1].push(pp);
world[pp.y][pp.x] = wayList.length;
}
}
return;
}
for(i = 0; i<fArr.length;i++)
world[fArr[i].y][fArr[i].x] = 1;
starList = starList.concat(fArr.reverse());
wayList.push(starList.concat(endList.reverse()));
}
// 特別改變地圖的一點
static private function clearWorld(world:Array, p:Point, wayTye:int):void
{
world[p.y][p.x] = wayTye;
}
// 給一點任意移動
static public function onePointRandomWay(world:Array, point:Point, wayType:int, limit:int = 10, lockObj:Object=null):Array
{
if(limit<0) limit = 999;
var wayList:Array = new Array();
var sArr:Array = onePointFindWay(world, point, lockObj);
if(sArr.length<1) return wayList;
wayList.push(point);
if(world[point.y][point.x] == WallTypt) world[point.y][point.x] = wayType;
var newP:Point;
var count:int = 0;
var tempArr:Array;
while(sArr.length > 0)
{
newP = sArr[int(sArr.length*RAND)];
world[newP.y][newP.x] = wayType;
wayList.push(newP);
sArr = onePointFindWay( world, newP, lockObj);
count++;
if(count > limit) break;
}
return wayList;
}
// 給一點會傳回 可以走的路
static public function onePointFindWay(world:Array, p:Point, lockObj:Object):Array
{
var selectList:Array = new Array();
if(lockObj[p.x+'_'+p.y] == 1) return selectList;
if(!world[p.y]) return selectList;
if(world[p.y-1]){
if(world[p.y-1][p.x] == WallTypt)
selectList.push(new Point( p.x, p.y-1));
}
if(world[p.y+1]){
if(world[p.y+1][p.x] == WallTypt)
selectList.push(new Point( p.x, p.y+1));
}
if(world[p.y][p.x-1] == WallTypt) selectList.push(new Point( p.x-1, p.y));
if(world[p.y][p.x+1] == WallTypt) selectList.push(new Point( p.x+1, p.y));
if(selectList.length<1) lockObj[p.x+'_'+p.y] = 1;
return selectList;
}
// 傳回隨機變數
static private function get RAND():Number
{
return Math.random();
}
// 在路上找一個點 製造一條分叉路
static public function getPointInWayCanWalk(world:Array, WarArr:Array, lockObj:Object, saveLen:int=0):Array
{
var CanWalkPointList:Array = new Array();
var j:int;
var sArr:Array;
for(var i:int = saveLen;i<WarArr.length;i++)
{
for(j=0;j<WarArr[i].length;j++)
{
sArr = onePointFindWay(world,WarArr[i][j], lockObj);
if(sArr.length > 0) CanWalkPointList.push(WarArr[i][j]);
}
}
return CanWalkPointList;
}
static public function fillWay(world:Array, WarArr:Array, lockObj:Object, num:int = 0, saveLen:int = 0):void
{
var sArr:Array;
var objList:Array;
var j:int;
var fArr:Array;
objList = getPointInWayCanWalk(world, WarArr, lockObj, saveLen);
if(objList.length < 1) return;
saveLen = WarArr.length;
for(var i:int=0;i<objList.length;i++)
{
sArr = onePointFindWay(world, objList[i], lockObj);
for(j=0;j<sArr.length;j++)
{
fArr = onePointRandomWay(world, sArr[j], WarArr.length+1,100,lockObj);
if(fArr.length>0) WarArr.push(fArr);
}
}
num++;
if(num > 5) return;
fillWay(world, WarArr, lockObj, num, saveLen);
}
// 創建迷宮
static public function createMaze(mazeWidth:int,
mazeHeight:int,
startPoint:Point,
endPoint:Point,
branNum:int = 10,
branLen:int = 10):Object
{
var world:Array = ceateEmptyMap(mazeWidth, mazeHeight);
var WarArr:Array = new Array();
var lockObj:Object = {};
// 用起點 終點 先建立一條主要路線
twoPointOneWay(world, startPoint, endPoint, MainWayType, WarArr, lockObj);
// 產生分支路
var sArr:Array;
var objList:Array = getPointInWayCanWalk(world, WarArr, lockObj);
var fArr:Array;
for(var i:int=0;i<branNum;i++)
{
sArr = onePointFindWay(world, objList[int(objList.length*RAND)], lockObj);
if(sArr.length >0)
{
fArr = onePointRandomWay(world, sArr[int(sArr.length*RAND)], WarArr.length+1,branLen,lockObj);
if(fArr.length > 0)WarArr.push(fArr);
}
}
// 填滿所有
fillWay(world, WarArr, lockObj);
var num:int = 0;
for(i=0;i<WarArr.length;i++)
{
num+=WarArr[i].length;
trace(' WarArr[i] i= ' +i +' ' + WarArr[i]);
}
trace(' num ' + num + ' endPoint ' + endPoint );
return {world:world, way:WarArr};
}
}
}
PS:
a 迷宮生成理論 淺顯易懂
http://www.4ngel.net/article/17.htm
b 迷宮 這有一系列 想法 作法 理論 更好的作法 等等
http://hctu.blogspot.tw/2005/08/blog-post_13.html
http://hctu.blogspot.tw/2005/08/blog-post_15.html
http://hctu.blogspot.tw/2005/08/blog-post_25.html 這篇是重點
前面是想法 這篇實作 後面是尋求更好的方式
http://hctu.blogspot.tw/2005/09/blog-post_06.html
http://hctu.blogspot.tw/2005/09/blog-post_07.html
http://hctu.blogspot.tw/2005/09/blog-post_13.html
c 迷宮生成 日文版的 但是有CODE 有圖 有日文說明 orz
http://wonderfl.net/c/v7Vh
http://www5d.biglobe.ne.jp/~stssk/maze/make.html
迷宮 都是比較理論向的東西 用其他的語言的寫法
http://www.doc88.com/p-67439537442.html
http://www.doc88.com/p-65320908259.html
