用Javascript實做簡單的路徑搜尋-找出最佳路徑
Thu, 07 Sep 2006 13:56:19 +0800這個方法是我在方格紙上畫圖時想到的，應該有名字，但是我不知道....
這個方法需要在迷宮的地圖陣列中不斷迭代搜尋直到計算出起點到地圖中各點的步數。在迷宮大的情況下，速度可能會比較慢。但是在只要目標可以到達，就可以得到到達目標的最小步數以及路徑（應該吧？）。
我的方法如下：
- 起點步數為0
- 搜尋陣列，在每一點找尋已計算出步數的所有鄰接點，這一點的步數等於鄰接點最小步數加一
- 如果搜尋完整個陣列都沒有計算步數，表示可計算步數的點都處理完畢
在計算的過程中，可發現每一點的步數都是由上一點決定的，因此可以用一個單向Linked List來存放上一點，這樣當目標的步數算出來時，同時也會建立一個可以從目標回溯到起點的Linked List。
我不確定這個方法會不會有漏洞（例如目標應該可以到達，但是計算不出步數），不過目前大略測試過是可行的。
由於把程式post在這裡似乎會有問題，還是請有興趣的人到我的網頁上看一下結果吧：
http://www.fillano.idv.tw/test36.html
Javascript的程式就在網頁內。至於A*？我還是沒做出來......