Kra*_*ken 13 algorithm a-star path-finding
我正在使用A-star算法,我有一个2D网格和一些障碍.现在,我只有纵向和横向障碍物,但它们可以密集地变化.
现在,A-star效果很好(即大多数情况下找到的最短路径),但是如果我尝试从左上角到右下角,那么我有时会看到路径不是最短的,即有一些笨拙在路上.
这条道路似乎偏离了最短路径应该是什么.
现在我正在使用我的算法.我从源头开始,在计算邻居的值时向外移动,距离源+目的地的距离,我一直选择最小的单元格,并继续重复直到我遇到的单元格是目的地,此时我停.
我的问题是,为什么A-star不能保证给我最短的路径.或者是吗？我做错了什么？
谢谢.
Pie*_*ens 21
如果您的启发式是"可接受的",A-star可以保证根据您的度量函数提供最短的路径(不一定是"像苍蝇一样"),这意味着它永远不会过度估计剩余距离.
请检查此链接:http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
为了帮助确定您的实施错误,我们需要有关您的指标和启发式的详细信息.
更新:
OP的度量函数对于正交移动是10,对于对角移动是14.
OP的启发式只考虑正交移动,因此是"不可接受的"; 它忽略了更便宜的对角线移动而高估了.
过于保守的启发式方法的唯一成本是在找到最小路径之前访问其他节点; 过于激进的启发式算法的成本是可能返回的非最佳路径.OP应该使用启发式:
Run Code Online (Sandbox Code Playgroud)7 * (deltaX + deltaY)
这是一个非常轻微的低估直接对角路径的可能性,因此也应该是高性能的.
更新#2:
要真正挤出性能,这接近最佳状态,同时仍然非常快:
7*min(deltaX,deltaY)+ 10*(max(deltaX,deltaY) - min(deltaX,deltaY))
更新#3:上面
的7来自14/2,其中14是指标中的对角线成本.
只有你的启发式变化; 该指标是"业务规则"并驱动所有其他指标.如果您对六角网格的A-star感兴趣,请查看我的项目:http://hexgridutilities.codeplex.com/
更新#4(关于性能):
我对A-star的印象是它在O(N ^ 2)性能区域和几乎O(N)性能区域之间错开.但这很依赖于网格或图形,障碍物放置以及起点和终点,很难概括.对于已知特定形状或风味的网格和图形,有各种更有效的算法,但它们通常也变得更复杂; TANSTAAFL.