我在我的小游戏中添加了 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 快很多 |