A* 启发式创建 Bresenham 线
根据我对 A* 启发式算法以及 Bresenham 算法工作原理的了解，这可能是不可能的，因为只有当前状态和目标状态会传递给启发式函数。但也许有人对这个问题有一个聪明的解决方案。
我正在使用 A* 在网格上规划一条路径，并且我想要一种启发式方法，当当前状态和目标之间存在自由空间或绕过障碍物的下一个转弯时，它会导致最佳路径遵循 Bresenham 线。
这是一些图片来说明问题。
曼哈顿距离：
如果世界中的运动就像网格上的跳棋一样，那就完全没问题，但我最终会将 A* 路径转换为连续平面上的运动，所以这效果很好。
欧几里德距离：
更好，但仍然不完美。注意末端的直线。对角线可以很容易地保持对角线，这就是我想要的。
我想要的：
Bresenham 线是抽到下一个回合或目标。
我在这里找到了一个很好的资源，http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html触及了我正在寻找的东西，但似乎只适用于绘制从起点到终点的布雷森纳姆线。我想要的是布雷森汉姆线也被吸引到绕过障碍物的下一个转弯。
对于解决这个问题的好方法有什么想法吗？
From what I understand about A* heuristics and how the Bresenham algorithm works, this may not be be possible since only the current state and goal state are passed to the heuristic function. But maybe someone has a clever solution to this problem.
I am using A* to plan a path on a grid, and I would like a heuristic that would cause the best path to follow a Bresenham's line when there are free spaces between the current state and the goal or the next turn around an obstacle.
Here are some images to illustrate the problem.
Manhattan distance:
If movements in the world acted like a checkers on a grid, this would be perfectly fine, but I'm eventually going to convert the A* path to motions on a continuously plane, so this does work very well.
Euclidean distance:
Better, but still not perfect. Notice the straight line at the end. The diagonal could have just as easily remained a diagonal, which is what I want.
What I Want:
Bresenham lines are draw to the next turn or goal.
I found a good resource here, http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html that touches on what I am looking for, but only seems to work for drawing Bresenham lines from the start to the goal. What I want are Bresenham lines being draw to the next turn around an obstacle too.
Any ideas for a good approach to this problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您能否即时修改成本函数，以便继续前进的成本随着累积误差而增加？
这个想法是，在算法开始时，像标准 Bresenham 一样计算 DX 和 DY。 （假设示例的其余部分 DX > DY > 0。针对其他方向进行相应修改。）
然后，对于每个访问的邻居节点，跟踪 Bresnaham 错误：
然后修改您的成本函数以支持增加 X，但添加
if (err >= DX/2) then cost=cost+FACTOR。在所有其他成本都相等的地图中，这应该追踪正确的线。您可能需要的另一件事是当路径绕过障碍物时进行特殊处理，否则您可能会得到奇怪的沿着墙壁的路径，类似于链接文章中的“与障碍物的叉积”示例。只要邻居节点不在 +X 或 +Y 方向，您就可以通过重新计算 DX 和 DY 来处理这种情况。 （不幸的是，这可能需要跟踪每个节点的单独 DX、DY 和错误，这可能会产生太大的开销）
免责声明，我还没有实现 A* 或 Bresneham 算法年。这整个想法可能行不通
Can you modify the cost function on the fly so that the cost of going forward increases with the accumulated error?
The idea is, at the start of the algorithm, calculate DX and DY as in standard Bresenham. (Assume for the rest of the example that DX > DY > 0. Modify accordingly for other directions.)
Then for every visited neighbor node, track the Bresnaham error:
Then modify your cost function to favor increasing X, but add
if (err >= DX/2) then cost=cost+FACTOR. In a map where all other costs are equal, this should trace the right line.The other thing you might need is special handling when the path steps around an obstacle, otherwise you could get strange wall-following paths similar to the "cross-product with obatacles" example in your linked article. You could possibly handle that situation by recalculating DX and DY whenever the neighbor node is not in the +X or +Y direction. (Unfortunately, this likely requires tracking a separate DX, DY, and error for each node, which may be too much overhead)
Disclaimer, I haven't implemented an A* or Bresneham algorithm in years. This whole idea may be unworkable
让所有的移动选择都是从当前位置可见的角点（或者目标，如果可见的话），一旦找到最短路径，在所有停靠点之间绘制布雷森汉姆线。
Have all your move alternatives be the corners visible from your current position (or the goal if it is visible), and once you find the shortest path, draw Bresenham lines between all your stops.
正如您链接到的文章的打破关系部分中所述，也许您可以在启发式中添加一个因素，即该节点位于其父节点和目标之间的线上的距离有多近。这样，如果可能的话，它会更愿意保持在直线路径上。
As described in the breaking ties section of the article you linked to, maybe you could add a factor to the heuristic that is how close does this node lie on a line between its parent and the goal. That way it would prefer staying on a straight line path when possible.
您可以使用 Bresenham 算法（也许是自适应 Bresenham）进行碰撞检测，例如使用空间填充曲线吗？
Can you use a collision detection with the Bresenham algorithm, perhaps an adaptive Bresenham, for example with a space-filling-curve?