※ 引述《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)