求推箱子自动解题算法

hlsl

呃。。版面上没法贴代码啊。至于评估函数，除非你实在是想优化，大多数实现只是使用几何距离或几何上的差即可。在推箱子的问题上就是“现在箱子们的位置和最终箱子们的位置上的几何差”，求两点间距离。即使不用向量，用一点三角计算就好啦。

已经有基本想法了，楼主还是看看A*相关的算法解释好了，要不PM在下也行。不要去看有关寻路方面的，那些东西把A*用的太狭隘（何况现在3D游戏很少用动态寻路了）。A*其实是一种启发式搜索。具体这个“搜索”用途在哪里就看应用了。

bluespark

    用A*算出来的都是最优路径啊 但是推箱子有时候走的并不是最优的路径啊

hlsl

楼上：A*是一种搜索方法。如果没有估值函数，它退化下去就是深度优先搜索。很多人用它做“最优几何路径”的求解，这只是它的用途之一。

如果你的状态迁移和估值函数是为寻路而写的，那A*自然会为寻路生成最优路径。而恰恰是“最优”二字的定义，又是取决于状态迁移和估值函数的。如果你的迁移和估值不是为了寻路，而是求解其他问题，那么A*生成的是求解这个问题的最佳“途径”

bluespark

     哦 ， 这个倒是没有注意到了， 要好好理解一下

lights

推箱子是一个复杂度很高的问题！我设计的算法具有很高的效率，但有两个因素可能和你不太相符。
1.只考虑了一个箱子的情况。
2.用c++实现的。

只能说一下思路。
首先是把起点到目标点的路径全部标出。（参考我以前写的小范围寻路）
然后计算地图上每个位置可行走方向和优先级。
当需要人箱分离时单独计算人走过的路径。
当遇到不能到达或是重复路径就回朔。

如需代码请联系我:qq 1905202

tjpanda88

hlsl: Re:求推箱子自动解题算法

楼上：A*是一种搜索方法。如果没有估值函数，它退化下去就是深度优先搜索。很多人用它做“最优几何路径”的...

对于A*看来我还有很多不太明白的地方,我找到的例子也都是关于路径搜索的,您有关于A*的资料吗?如果有的话可以给我看看吗?我的信箱是tjpanda88@sina.com

lights

A*很简单，觉得难是因为你没有尝试自己写过。a*就是深度优先的改良。深度优先在子节点的选择上是无序或者顺序的，a*则是根据估价值排序的。只有这里不同，那么只要你先写出个深度优先就已经完成了70%，然后子节点的搜索顺序这部分加入估价函数，就好了。估价函数也绝没你想的那么复杂，只要你对深度优先寻路理解了，这个估价函数一点就透，而且现成的估价公式也一大堆。