14

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

我正在使用 A* 来规划网格上的路径,并且我想要一个启发式方法,当当前状态和目标之间或下一次绕过障碍物之间有空闲空间时,它会导致最佳路径遵循 Bresenham 的线。

这里有一些图片来说明这个问题。

曼哈顿距离:

如果世界上的运动就像一个网格上的跳棋,这将是非常好的,但我最终会将 A* 路径转换为连续平面上的运动,所以这确实很好用。

使用曼哈顿距离启发式从红到绿的最短路径

欧几里得距离:

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

使用欧几里得距离启发式从红色到绿色的最短路径

我想要的是:

布雷森汉姆线被绘制到下一个转弯或目标。

我真正想要的最佳路径,它使用布雷森汉姆线到达目标

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

有什么想法可以解决这个问题吗?

4

4 回答 4

3

您能否即时修改成本函数,使前进的成本随着累积误差的增加而增加?

这个想法是,在算法开始时,像标准 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 算法了。这整个想法可能行不通

于 2011-04-24T16:14:55.103 回答
1

让你所有的移动选择都是从你当前位置可见的角落(或者目标,如果它是可见的),一旦你找到最短的路径,在你所有的停靠点之间画出 Bresenham 线。

于 2011-04-24T17:29:55.370 回答
0

您能否将碰撞检测与 Bresenham 算法一起使用,也许是自适应 Bresenham,例如使用空间填充曲线?

于 2011-04-24T16:40:16.537 回答
0

如您链接到的文章的打破关系部分所述,也许您可​​以在启发式中添加一个因素,即该节点位于其父节点和目标之间的直线上的距离。这样,如果可能,它宁愿保持在直线路径上。

于 2011-04-24T21:10:30.053 回答