algorithm - A *启发式创建布雷森纳姆线

根据我对a*启发式和bresenham算法工作原理的理解，这可能是不可能的，因为只有当前状态和目标状态被传递给启发式函数。但也许有人能聪明地解决这个问题。
我用一个*在网格上规划一条路径，我想要一个启发式的方法，当当前状态和目标之间或者下一个转弯绕过障碍物时，可以使最佳路径遵循bresenham的路线。
这里有一些图片来说明这个问题。
曼哈顿距离：
如果世界上的运动像格子上的跳棋一样，这将是非常好的，但我最终会把a*路径转换成连续平面上的运动，所以这确实非常有效。
欧氏距离：
更好，但仍然不完美。注意末端的直线。对角线可以很容易地保持对角线，这就是我想要的。
我想要的是：
布雷森汉姆线将被拉到下一个回合或进球。
我在这里找到了一个很好的资源，http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html它触及了我所寻找的东西，但似乎只对从一开始到进球的布雷森汉姆线起作用。我想要的是布雷森汉姆线也被拉到下一个转身的障碍。
有什么好办法解决这个问题吗？

最佳答案

你能动态地修改成本函数，使未来的成本随着累积误差的增加而增加吗？
其思想是，在算法开始时，按照标准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。在所有其他成本都相等的地图中，这应该是正确的。
另外，当路径绕过障碍物时，可能需要特殊处理，否则可能会出现奇怪的墙跟随路径，类似于链接文章中的“带obatacles的交叉产品”示例。只要邻居节点不在+x或+y方向，就可以通过重新计算dx和dy来处理这种情况。（不幸的是，这可能需要为每个节点跟踪单独的dx、dy和错误，这可能会带来太多的开销）
免责声明，我已经很多年没有实现a*或bresneham算法了。整个想法可能行不通

关于algorithm - A *启发式创建布雷森纳姆线，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5762417/