※ 引述《H45 (!H45)》之銘言： : ※ 引述《TonyQ (骨頭)》之銘言： : BFS 不行嗎...? : 覺得廣度優先走訪太笨的話，就用 Best first search : 其中的 A* algorithm 應該是最「聰明」的吧？ (當然有許多元素要自己定義) 嗯 後來採用A* cost不高(距離是20格內的小地圖 , 每次約0~5 ms) 又很自然，是很不錯的東西。 貼上一點當時的參考資料和我的實作code 參考資料 (這兩篇其實是翻譯同一篇文章 不過對照著看有不同收穫) http://www.roboticfan.com/college/knowledge/200606/147.shtml http://swf.com.tw/?p=67 code實作 http://tony1223.no-ip.info:1223/bmore?Flyword&4642 (因為碼有點長，我直接貼我的webbs連結。 如果連結跑掉了可以來信跟我說T^T) 底下是一點點的心得 , 有錯的地方歡迎提出來討論 .(冏) 1.基本原理 g = 路徑成本 , h=到達目標的"估計"成本 , F=總成本(g+h) 它並不直接找出一條路徑，而是透過計算成本後指定前一格的方式。 當到達終點時，透過終點回推最低成本的路徑， 從終點的的前一格→前一格→前一格→起始格‧找到路徑。 有點類似LinkedList的那種串聯的概念... 這邊看起來還蠻抽象的T^Ta 失敗了三四次才成功 2.它的發展並不是就單一條線的發展 而是就目前的視野(openlist) 去找出以目前的視野底下成本最低的路徑(F值最低) 我一開始一直以為它是沿線尋找...所以把cango寫錯了... 這是蠢點1 orz 3.它的作法是建立一個大地圖的陣列(whichlist)，然後每次查詢給與不 同的onClose跟onOpen，感覺上是為了方便連續多次的查找的時候， 不會互相混淆。 不過我的case由於地圖本身座標值蠻高的， 幾百個地圖又沒有一個固定的size，所以建表法對我來講不實際。 我採用的是把xy先做hash , f(x,y) = x*最大長度 +y 的狀況， (in my case f(x,y) = 50000*x+y) 把看過的點(onOpen and onClose) 建立在 allpoint 這個HashMap裡面。 只要透過查找Hash值就可以馬上知道這個點是不是已經存在， 而且也可以知道這個點是 onClose或onOpen 。(透過Node的type紀錄) 4.另外openList採用BinaryHeap維護 ... (minHeap) 降低查找最低F的成本 (這個增進效能非常多) ──────────────────────────────── 3跟4 如果是用List再用 O(n) 的列舉法取做查找,效能差蠻多的 以底下的測資來說，我採用前者時是 106ms，採用後者時16 ms...￣▽￣ 不過我前者的code沒留下來，所以可能也是我哪裡有沒寫好的地方...XD 另外影響這演算法的地方有兩個... 1.G值的計算, 會直接影響到取點的優先度... 在我的case是以角色為中心的八格損耗都一樣。 在參考文章的範例則是走斜角會加大損耗。 2.cango的地方可以決定哪些點是可以走的 另外 掃點的時候不見得要掃九宮格... 視case不同的情況而定 -- 11001100111111110101 01001000001100011001 11010010100111101111 10011100000010100100 10111001011100100101 11101000111111100101 10001101000010000100 11110101010110000100 11101111100010011101 10111000101010011110 11001000011111001101 01101001110100010110 00111100101011111010 10001001110111110011 00001010111010010001 11111101001001101011 10010101111011111010 10111011010110110111 11101001101000011100 00011111001110011111 -- 　▄▅▆▇███▇▆▅▄▃　　　　　　　　╰┼╯─╮ ╮　　　　　 　 　◥███████████◣　　　　　　　╰┼╯＝│=│　　　　　　　　 ◥██████───────◣　　　　＊．　╯　 ╯ ╯ の　物　語　．＊ 　◥███████──────◣　～　◢◣　　　　　　　　　　　　 ◢◣ 　◥██████───────◤　　　◥◤＊　　空白的世界．翼 ＊◥◤ 　◥██▁▂▃▄▅▆▇███▆▅▄▃▂▂～telnet://tony1223.no-ip.info --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.134.27.68 ※ 編輯: TonyQ 來自: 220.134.27.68 (05/29 05:32)