用Javascript實做簡單的路徑搜尋

 Mon, 04 Sep 2006 14:02:02 +0800

其實這個方法是在書上看到的,只是把它改成用Javascript來實現。

原來的方法適用在迷宮內可行走路徑寬度都是1時最適當,當迷宮有比較大的行走空間,就會有多餘的路徑(會在多餘空間裡來回走動)。好處是只要有可以到達的目標,就一定會找出路徑,速度也很快。

我把這個方法稍做修改,讓他至少能在起點與目標可直線到達,或是障礙不複雜的狀況下,可以用比較有效率的路徑到達目標。

程式如下:

 

var start = new Point (1,5);//開始的點座標
var end = new Point (2,3);//結束的點座標
var arr = new Array();//地圖陣列
var dim = 8;//迷宮大小,8*8
arr.push(new Array(1,1,0,0,0,0,0,1));
arr.push(new Array(0,0,0,0,0,0,0,1));
arr.push(new Array(1,0,1,1,1,0,0,1));
arr.push(new Array(1,0,0,1,1,1,0,1));
arr.push(new Array(1,1,1,1,0,0,0,1));
arr.push(new Array(1,0,0,0,0,0,0,1));
arr.push(new Array(0,0,0,0,0,0,0,1));
arr.push(new Array(1,1,0,0,0,0,0,0));
var _closed = new Array();//紀錄走過的路徑
var record = new Array(dim*dim);//紀錄可行走的路徑
//陣列內容會改變以紀錄走過的路徑,為了不破壞原來的資料,所以複製一份來用
for (var y=0; y<8; y++) {
for (var x=0; x<8; x++) {
var obj = document.getElementById(y+"_"+x);
obj.innerHTML = "    ";
if (arr[y][x] == 0) {
obj.style.background = "white";
record[y*dim+x] = 1;//可行走
} else {
obj.style.background = "black";
record[y*dim+x] = 0;//不可行走
}
}
}
//為了在表格中顯示找到的路徑用
var obj = document.getElementById(start.y+"_"+start.x);
obj.innerHTML = "S";
obj.style.background= "red";
obj = document.getElementById(end.y+"_"+end.x);
obj.innerHTML = "E";
//以上
direction = new Array();//定義方向的變數
//存放的是方向對於座標的偏移量
//依照在陣列中的索引,總共有0~7種方向
direction.push(new Point(-1,-1));
direction.push(new Point(-1,0));
direction.push(new Point(-1,1));
direction.push(new Point(0,1));
direction.push(new Point(1,1));
direction.push(new Point(1,0));
direction.push(new Point(1,-1));
direction.push(new Point(0,-1));
try {
//初始起點的狀況
var triger = true;
_closed.push(new Point(start.x, start.y));
record[start.y*dim+start.x] = 0;
while (!start.compare(end) && triger) {
alert("pause");//每次迭代都會暫停,顯示路徑搜尋的過程
getRouteNext();//決定下一個路徑的點,直到到達終點為止
}
alert(_closed.length);
} catch (e) {alert(e);}
//函數:依照兩個點的相對關係來算出方向
function getDirection (_start, _end) {
try {
var tmp = Math.atan2(_end.x-_start.x, _end.y-_start.y);
tmp = Math.floor(tmp / 2 / Math.PI * 360);
if (tmp > -157.5 && tmp < -112.5) return 0;
if (tmp > -112.5 && tmp < -67.5) return 1;
if (tmp > -67.5 && tmp < -22.5) return 2;
if (tmp > -22.5 && tmp < 22.5) return 3;
if (tmp > 22.5 && tmp < 67.5) return 4;
if (tmp > 67.5 && tmp < 112.5) return 5;
if (tmp > 112.5 && tmp < 157.5) return 6;
if (tmp > 157.5 || tmp < -157.5) return 7;
} catch (e) {alert(e);}
}
//定義點的物件,可利用move方法來移動
function Point(_x, _y) {
this.x = _x;
this.y = _y;
this.count = 0;
this.compare = function (_point) {
if (this.x==_point.x && this.y==_point.y) {
return true;
} else {
return false;
}
}
this.move = function (_direction) {
this.x += direction[_direction].x;
this.y += direction[_direction].y;
var obj = document.getElementById(this.y+"_"+this.x);
obj.innerHTML = 0;
obj.style.background = "red";
}
}
//函數:決定下一個路徑的點,直到到達終點為止
function getRouteNext () {
var dir = getDirection(start,end);//目前所在的點與目標的點的方向
var dirarr = makeDirection(dir);//依照方向產生依序要測試的點陣列
var test = 0;
for (var i=0; i -1
&& start.x + direction[dirarr[i]].x < dim 
&& start.y + direction[dirarr[i]].y > -1 
&& start.y + direction[dirarr[i]].y < dim 
&& record[(start.y+direction[dirarr[i]].y)*dim+start.x+direction[dirarr[i]].x] == 1  ) {
start.move(dirarr[i]);//如果測試的點可行走,則移動到這個點
_closed.push(new Point(start.x,start.y));//將點存入路徑中
record[start.y*dim+start.x] = 0;//將點標示為不可行走(已走過)
return dirarr[i];
}
}
//test==8時,表示目前走到的這一格無法再走下去
//必須退回前一格測試其他可行的路徑
if (test == 8) {
tmp = _closed.pop();
if (_closed.length == 0) {//退回原點表示無路可走,終點無法到達
alert("no road to target!!!");//顯示錯誤訊息
triger = false;//跳出while迴圈
} else {
//否則就後退一步
start = _closed[_closed.length-1];
var obj = document.getElementById(tmp.y+"_"+tmp.x);
obj.innerHTML = 1;
obj.style.background = "white";
}
}
}
//傳入起始方向,傳回以起始方向為中心的方向陣列
//方向的改變方式仍會影響路徑的搜尋
function makeDirection (_init) {
try {
if (_init > 7 || _init < 0) throw "Initial direction must between 0 and 7.";
var arr1 = new Array();
arr1.push(_init);
arr1.push(shiftDirection(_init,-1));
arr1.push(shiftDirection(_init,1));
arr1.push(shiftDirection(_init,-2));
arr1.push(shiftDirection(_init,2));
arr1.push(shiftDirection(_init,-3));
arr1.push(shiftDirection(_init,3));
arr1.push(shiftDirection(_init,4));
return arr1;
} catch (e) {
alert(e);
}
}
//傳入方向與要計算的偏移量,傳回正確的方向
function shiftDirection(_dir, _shift) {
var ret = _dir + _shift;
if (ret > 7) 
{
ret -= 8;
} else if (ret < 0) {
ret += 8;
}
return ret;
}

 

我用一個表格來顯示迷宮以及路徑搜尋的狀況。請參考以下的例子:

原始的方法:

改良過的方法:

改變一下起點與終點,可以發現其實改良過的方法在特定狀況下效果還是不好。在某些起點與終點的組合中,甚至會走遍迷宮才走到終點,而不是較有效率的路徑。這還是要使用A*法才能辦得到吧。