用Javascript實做簡單的路徑搜尋-找出最佳路徑（續）
Tue, 12 Sep 2006 15:11:20 +0800前一篇的方法有一個壞處，就是需要掃描迷宮陣列，浪費掉許多迭代運算，影響到速度。
我把計算步數的方法改成由起點向外推算，方法如下：
- 依然用while迴圈來重複運算，直到到達目標或是無法到達目標
- 由起點開始，將起點存入currStep陣列
- 進入while迴圈
- 接著每次迭代均起始tmp陣列
- 從currStep取出所有同步數的點，測試八個方向的鄰接點，如果可到達並尚未計算步數，則將此方向之鄰接點步數設為目前點的步數加一，將其Node.parent設為目前點，並將鄰接點存入tmp陣列
- 所有同步數的點搜尋完畢後，將tmp陣列assign給currStep陣列，作為下一次迭代要處理的點
- 如果要測試的點是目標點時，由目標點透過Node.parent建立由起點到目標的路徑，並用return回傳路徑，跳出迴圈
大致測試了一下，大概至少可以減少迭代次數到原來的50%左右。
這兩種方法都會找到需要步數最少的路徑，但是在八個方向的條件下，做出來的路徑不一定美觀（目前方向並不影響權重，所以看起來會繞路....不一定會走直線，但是就我的定義來說（以步數計算）仍然算是最佳路徑）
以下是我測試的連結（迷宮都改成32*32，並增加迭代次數的提示）：
程式原始碼仍然內嵌在網頁內。