我实现的一个 A*算法，效率极低，不知道为啥。

[liamxd]

我在我的小游戏中添加了 A*的寻路算法。

结果寻路效率极低， open list 膨胀的特别快。稍微远点的路程就几乎死机状态。

代码在这里：
https://github.com/modouRPG/MoDouClient.git

[MOsky]

mark 下，睡一觉再看

[zhicheng]

https://github.com/zhicheng/pathfinder

我以前写的一个，很快啊，不过代码写很烂，不要学我。

[liamxd]

@zhicheng 看了一下，算法几乎相同啊。你那里不会遇到 open list 膨胀过快导致计算很慢的问题么？

我这里在遇到墙比较长的时候，起点和重点刚好在墙两侧比较对称的位置的时候， open list 会变的很长。然后就几乎死机。

[zhicheng]

@liamxd 只是很早很早以前写的一个 demo ，你能跑起来吗？有个 OpenGL 写的测试。

[zhicheng]

@liamxd 修了个编译错误加了 License 。可以直接在 Mac 上编译了。左键是加障碍，右键第一下是设置起点，第二下是设置终点，然后计算出路径。

[yuchting]

A*研究在学生时代研究良久，后来在工作全是用得广度优先了，效率完全跟得上。学生时代全是 std 容器，然后工作看别人写的全是数组，效率自然没法比，但是 std 容器多漂亮哇。。。

[liamxd]

解决了。现在效率还可以了。

改的地方就是：
点是使用的 class 。因为要比较相等，所以重载了一个==操作符。
在比较 A 点==B 点的时候使用操作符比较的。
我换成了直接比较点的 X 和 Y 值之后，速度嗖嗖的了。

真是叫人不解啊。

[zerh925]

不错！
也可以尝试 Dijkstra 或者蚁群算法 TSP 问题

[jiangzhuo]

出去程序实现上的问题，在有大块墙和封闭区间的时候加入 JPS 能快很多

[WKPlus]

你原来的代码比较的是两个指针是否相等，也就是比较两个指针是否指向同一个对象，而不是比较对象中的 x,y 值是否相等。改为*(*it ) == *point 才是调用重载的==进行比较。

大概看了一下原来的代码， childrenList 每次都是新生成点对象的，对象当然和原来的 openlist 的对象不一样，所以你的 openlist 会一直变大。

[WKPlus]

另外， operator==接受的参数一般是对象的引用而不是指针。

[acros]

直接打开看晕了···· 还是得下下来看才行。

其实我只想吐槽两点：
我写游戏还还真没用过 try catch··· 游戏引擎代码中，运行时的部分里也没有类似的印象。
构建路径列表那里好多 new delete ，肯定快不了。

[sigroma]

https://github.com/qiao/PathFinding.js
以前写 A star 的时候参考了一下这个项目中的 Trace 算法
这个算法会优先选择靠墙 /墙角的位置，面对大墙时速度比原始 A star 快很多