A*启发式创建Bresenham线

Question

根据我对A*启发式的理解以及Bresenham算法如何工作,这可能是不可能的,因为只有当前状态和目标状态被传递给启发式函数.但也许某人有一个聪明的解决方案来解决这个问题.

我正在使用A*来计划网格上的路径,并且我想要一种启发式方法,当当前状态和目标之间存在自由空间或绕过障碍物时,可以使最佳路径遵循Bresenham线.

这里有一些图像来说明问题.

曼哈顿距离:

如果世界上的运动像一个网格上的棋子一样,这将是完美的,但我最终会将A*路径转换为连续平面上的运动,所以这确实很有效.

欧几里德距离:

更好,但仍然不完美.注意最后的直线.对角线可以很容易地保持对角线,这就是我想要的.

我想要的是:

Bresenham线被吸引到下一个回合或目标.

我在这里找到了一个很好的资源,http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html触及了我正在寻找的东西,但似乎只能用于从开始到目标绘制Bresenham线.我想要的是Bresenham线也被绕到障碍物的下一个转弯.

有什么想法可以很好地解决这个问题吗？

Answer 1

您能否即时修改成本函数，以便继续前进的成本随着累积误差而增加？

这个想法是，在算法开始时，像标准 Bresenham 一样计算 DX 和 DY。（假设示例的其余部分 DX > DY > 0。对其他方向进行相应修改。）

然后对于每个访问过的邻居节点，跟踪 Bresnaham 错误：

if (neighbor.X > this.X) 
   neighbor.err=this.err+DY 
else if (neighbor.Y > this.Y) 
   neighbor.err=this.err-DX

然后修改您的成本函数以有利于增加 X，但添加if (err >= DX/2) then cost=cost+FACTOR. 在所有其他成本都相等的地图中，这应该追踪正确的线。

您可能需要的另一件事是当路径绕过障碍物时进行特殊处理，否则您可能会得到奇怪的沿着墙壁的路径，类似于链接文章中的“与障碍物的叉积”示例。只要邻居节点不在 +X 或 +Y 方向，您就可以通过重新计算 DX 和 DY 来处理这种情况。（不幸的是，这可能需要跟踪每个节点的单独 DX、DY 和错误，这可能会带来太大的开销）

免责声明，我已经很多年没有实现 A *或 Bresneham 算法了。这整个想法可能行不通