algorithm - 如何向 A* 启发式算法添加比距离更多的参数？

Question

对于小型 2D 游戏中的寻路，我使用 A* 算法，目前基于简单的欧氏距离启发式算法。我的游戏世界被表示为一个单元格网格，要么被障碍物占据，要么不被障碍物占据。必须使用 A* 计算路径的角色可以向任何方向移动(如果未被阻挡)，而不仅仅是 N/E/S/W。

好的，这样基本上就可以正常工作了。现在我需要向 A* 启发式函数添加另一个参数，即与每个网格单元相关联的成本值。该成本值越高，我们的角色就越应该尝试避开该单元格。

但是，我无法将启发式函数更改为仅使用每个网格单元的成本值，因为单元到 A* 目标位置的距离仍然很重要。角色应尽量避开任何高成本单元格，但同时也不能离目标位置太远。因此，我需要在像元的距离和成本值之间进行某种“权衡”。

理想情况下，我想找到一种解决方案，使我能够轻松调整/优化像元距离与其成本值之间的这种关系，以便我可以微调启发式。

有什么想法可以实现吗？

Answer 1

当您使用任何最短路径算法(A* 或 Dijkstrs)时，每个节点都需要一个成本值。
所以你必须自己想一个公式，如何将距离(你的单元格)与障碍成本结合起来。
您可以创建一个 cost() 函数，它采用长度成本加上障碍成本。