这是一个创建于 3383 天前的主题，其中的信息可能已经有所发展或是发生改变。
我在我的小游戏中添加了 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