我实现的一个 A*算法，效率极低，不知道为啥。
liamxd 2015-09-07 13:25:19 +08:00 6523 次点击这是一个创建于 3753 天前的主题，其中的信息可能已经有所发展或是发生改变。
我在我的小游戏中添加了 A*的寻路算法。
结果寻路效率极低， open list 膨胀的特别快。稍微远点的路程就几乎死机状态。
 | 1 MOsky 2015-09-07 13:28:19 +08:00 via iPhone mark 下，睡一觉再看 |
 | 2 zhicheng 2015-09-07 13:33:00 +08:00 |
 | 3 liamxd OP @zhicheng 看了一下，算法几乎相同啊。你那里不会遇到 open list 膨胀过快导致计算很慢的问题么？ 我这里在遇到墙比较长的时候，起点和重点刚好在墙两侧比较对称的位置的时候， open list 会变的很长。然后就几乎死机。 |
| 5 zhicheng 2015-09-07 14:29:18 +08:00 @liamxd 修了个编译错误加了 License 。可以直接在 Mac 上编译了。左键是加障碍，右键第一下是设置起点，第二下是设置终点，然后计算出路径。 |
 | 6 yuchting 2015-09-07 15:20:19 +08:00 A*研究在学生时代研究良久，后来在工作全是用得广度优先了，效率完全跟得上。学生时代全是 std 容器，然后工作看别人写的全是数组，效率自然没法比，但是 std 容器多漂亮哇。。。 |
| 7 liamxd OP 解决了。现在效率还可以了。 改的地方就是： 点是使用的 class 。因为要比较相等，所以重载了一个==操作符。 在比较 A 点==B 点的时候使用操作符比较的。 我换成了直接比较点的 X 和 Y 值之后，速度嗖嗖的了。 真是叫人不解啊。 |
 | 8 zerh925 2015-09-07 17:48:21 +08:00 via iPhone 不错！ 也可以尝试 Dijkstra 或者蚁群算法 TSP 问题 |
 | 9 jiangzhuo 2015-09-07 18:30:18 +08:00 出去程序实现上的问题，在有大块墙和封闭区间的时候加入 JPS 能快很多 |
 | 10 WKPlus 2015-09-07 18:41:50 +08:00 你原来的代码比较的是两个指针是否相等，也就是比较两个指针是否指向同一个对象，而不是比较对象中的 x,y 值是否相等。改为*(*it ) == *point 才是调用重载的==进行比较。 大概看了一下原来的代码， childrenList 每次都是新生成点对象的，对象当然和原来的 openlist 的对象不一样，所以你的 openlist 会一直变大。 |
| 11 WKPlus 2015-09-07 18:43:38 +08:00 另外， operator==接受的参数一般是对象的引用而不是指针。 |
 | 12 acros 2015-09-07 19:01:23 +08:00 直接打开看晕了 还是得下下来看才行。 其实我只想吐槽两点： 我写游戏还还真没用过 try catch 游戏引擎代码中，运行时的部分里也没有类似的印象。 构建路径列表那里好多 new delete ，肯定快不了。 |
 | 13 sigroma 2015-09-08 12:20:46 +08:00 https://github.com/qiao/PathFinding.js 以前写 A star 的时候参考了一下这个项目中的 Trace 算法 这个算法会优先选择靠墙 /墙角的位置，面对大墙时速度比原始 A star 快很多 |
Select Language