我在我的小游戏中添加了 A*的寻路算法。
结果寻路效率极低， open list 膨胀的特别快。稍微远点的路程就几乎死机状态。
This topic created in 4081 days ago, the information mentioned may be changed or developed.
 |
MOskySep 7, 2015 via iPhone
1
mark 下，睡一觉再看
|
 |
zhichengSep 7, 2015
2
|
 |
3
@zhicheng 看了一下，算法几乎相同啊。你那里不会遇到 open list 膨胀过快导致计算很慢的问题么？
我这里在遇到墙比较长的时候，起点和重点刚好在墙两侧比较对称的位置的时候， open list 会变的很长。然后就几乎死机。 |
 |
yuchtingSep 7, 2015
6
A*研究在学生时代研究良久，后来在工作全是用得广度优先了，效率完全跟得上。学生时代全是 std 容器，然后工作看别人写的全是数组，效率自然没法比，但是 std 容器多漂亮哇。。。
|
|
7
解决了。现在效率还可以了。
改的地方就是： 点是使用的 class 。因为要比较相等，所以重载了一个==操作符。 在比较 A 点==B 点的时候使用操作符比较的。 我换成了直接比较点的 X 和 Y 值之后，速度嗖嗖的了。 真是叫人不解啊。 |
 |
zerh925Sep 7, 2015 via iPhone
8
不错！
也可以尝试 Dijkstra 或者蚁群算法 TSP 问题 |
 |
jiangzhuoSep 7, 2015
9
出去程序实现上的问题，在有大块墙和封闭区间的时候加入 JPS 能快很多
|
 |
WKPlusSep 7, 2015
10
你原来的代码比较的是两个指针是否相等，也就是比较两个指针是否指向同一个对象，而不是比较对象中的 x,y 值是否相等。改为*(*it ) == *point 才是调用重载的==进行比较。
大概看了一下原来的代码， childrenList 每次都是新生成点对象的，对象当然和原来的 openlist 的对象不一样，所以你的 openlist 会一直变大。 |
|
WKPlusSep 7, 2015
11
另外， operator==接受的参数一般是对象的引用而不是指针。
|
 |
acrosSep 7, 2015
12
直接打开看晕了···· 还是得下下来看才行。
其实我只想吐槽两点： 我写游戏还还真没用过 try catch··· 游戏引擎代码中，运行时的部分里也没有类似的印象。 构建路径列表那里好多 new delete ，肯定快不了。 |
 |
sigromaSep 8, 2015
13
https://github.com/qiao/PathFinding.js
以前写 A star 的时候参考了一下这个项目中的 Trace 算法 这个算法会优先选择靠墙 /墙角的位置，面对大墙时速度比原始 A star 快很多 |
Select Language