推 linjack:我純粹只是覺得 BFS 比 A* 好寫 ....... XD 10/13 15:57
→ linjack:(因為其實我沒寫過 A*，趕快逃跑XD) 10/13 15:58
推 TonyQ:以前在找A*的資料的時候看到 BFS vs A* XD 10/13 17:25
→ TonyQ:我覺得BFS比較適合不確定目標位置的時候(ex.工人採礦) 10/13 17:25
推 qrtt1:mining 通常不是即時的用途 10/13 22:11
※ 引述《linjack (嗯)》之銘言：
: ※ 引述《taroson (想想)》之銘言：
: [刪去部份]
: 我是覺得這題應該還用不到 A* 那個 level
: 有在寫 PacMan，那老鼠走迷宮應該寫過了吧
: 這兩者的路徑搜尋應該是一樣的東西
: 只是老鼠走迷宮裡，老鼠要走的出口不會動，只有老鼠會動
: 所以 BFS 掃一次就走完最短了
: 現在是老鼠(Ghost)會動，出口(PacMan)也會動
: 那就是 PacMan 的位置只要動了，Ghost 在走下一步之前
: (下一個 Frame 或下一個 Step ... anyway 看你程式怎麼寫的)
: 就必需重新做一次 BFS 建立新的最短路徑
: well, Breadth-First-Search 應該是找 Shortest path
: 的簡單辦法之一吧 XD 如果我記得沒錯的話 .......(汗)
會動的狀況下
A*不失為是用來解決的最佳解 , BFS cost很高 ,
前面我有發過相關心得 , 可以找找看 ...:P
雖然我後來發現我之前的code有點問題 ,
open list沒有維護好 ..XD
在下面的code我修正了 :P
--
有興趣的話可以參考我最近改寫的 A* for 老鼠迷宮
http://std1.mis.yzu.edu.tw/~s932541/java/AStar.rar
裡面有包含node(點) BinaryHeap(heap 資結實做) 跟 CFindPath
開CFindPath裡面的main有簡單的sample跟測資
--
▄▅▆▇███▇▆▅▄▃ ╰┼╯─╮ ╮
◥███████████◣ ╰┼╯＝│=│
◥██████───────◣ ＊． ╯ ╯ ╯ の 物 語 ．＊
◥███████──────◣ ～ ◢◣ ◢◣
◥██████───────◤ ◥◤＊ 空白的世界．翼 ＊◥◤
◥██▁▂▃▄▅▆▇███▆▅▄▃▂▂～telnet://tony1223.no-ip.info
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.132.59.247