在網路上說明A*的網站非常多，方法我就不贅述了。直接來看結果吧：

http://www.fillano.idv.tw/test39.html

Javascript程式原始碼同樣內嵌在網頁中。

前一篇的方法有一個壞處，就是需要掃描迷宮陣列，浪費掉許多迭代運算，影響到速度。

我把計算步數的方法改成由起點向外推算，方法如下：

1. 依然用while迴圈來重複運算，直到到達目標或是無法到達目標
2. 由起點開始，將起點存入currStep陣列
3. 進入while迴圈

1. 接著每次迭代均起始tmp陣列
2. 從currStep取出所有同步數的點，測試八個方向的鄰接點，如果可到達並尚未計算步數，則將此方向之鄰接點步數設為目前點的步數加一，將其Node.parent設為目前點，並將鄰接點存入tmp陣列
3. 所有同步數的點搜尋完畢後，將tmp陣列assign給currStep陣列，作為下一次迭代要處理的點
4. 如果要測試的點是目標點時，由目標點透過Node.parent建立由起點到目標的路徑，並用return回傳路徑，跳出迴圈

大致測試了一下，大概至少可以減少迭代次數到原來的50%左右。

這兩種方法都會找到需要步數最少的路徑，但是在八個方向的條件下，做出來的路徑不一定美觀（目前方向並不影響權重，所以看起來會繞路....不一定會走直線，但是就我的定義來說（以步數計算）仍然算是最佳路徑）

以下是我測試的連結（迷宮都改成32*32，並增加迭代次數的提示）：

1. 新的方法：http://www.fillano.idv.tw/test37.html
2. 舊的方法：http://www.fillano.idv.tw/test37a.html

程式原始碼仍然內嵌在網頁內。

這個方法是我在方格紙上畫圖時想到的，應該有名字，但是我不知道....

這個方法需要在迷宮的地圖陣列中不斷迭代搜尋直到計算出起點到地圖中各點的步數。在迷宮大的情況下，速度可能會比較慢。但是在只要目標可以到達，就可以得到到達目標的最小步數以及路徑（應該吧？）。

我的方法如下：

1. 起點步數為0
2. 搜尋陣列，在每一點找尋已計算出步數的所有鄰接點，這一點的步數等於鄰接點最小步數加一
3. 如果搜尋完整個陣列都沒有計算步數，表示可計算步數的點都處理完畢

在計算的過程中，可發現每一點的步數都是由上一點決定的，因此可以用一個單向Linked List來存放上一點，這樣當目標的步數算出來時，同時也會建立一個可以從目標回溯到起點的Linked List。

我不確定這個方法會不會有漏洞（例如目標應該可以到達，但是計算不出步數），不過目前大略測試過是可行的。

由於把程式post在這裡似乎會有問題，還是請有興趣的人到我的網頁上看一下結果吧：

http://www.fillano.idv.tw/test36.html

Javascript的程式就在網頁內。至於A*？我還是沒做出來......

其實這個方法是在書上看到的，只是把它改成用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;
}

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

原始的方法：

• 目標可到達：http://www.fillano.idv.tw/test28.html
• 目標不可到達：http://www.fillano.idv.tw/test31.html

改良過的方法：

• 障礙較複雜：http://www.fillano.idv.tw/test32.html
• 障礙較簡單：http://www.fillano.idv.tw/test33.html

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