2

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

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

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

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

任何想法如何实现这一目标？

4

2 回答 2

1

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

于 2013-02-03T01:36:22.120 回答
1

您需要使用权重（值介于 0 和 1 之间），假设 w 是距离权重，1-w 是成本权重，因此您的新 huristic 将类似于：H= w*distance+(1-w)*cost

现在你需要根据你的领域来优化 W - ampiricly。

于 2013-02-03T11:34:09.213 回答