时间戳

首页 > 解决方案 > 修复 C# 中的 A* 实现

c# - 修复 C# 中的 A* 实现

问题描述

所以我在 Unity C# 中实现了一个 A* 算法来做一些测试，以便构建一个基于 2D 的游戏。我知道有几个组件可以帮助您解决这个问题，但我想尝试自己来迎接挑战。

我基本上已经阅读了 A* 应该如何表现并将行为转换为代码。它几乎可以工作。但是在某些情况下，相邻图块的分数完全相同（曼哈顿距离 + 到原点的距离），您最终会得到一条通往目的地但不是最短的路径。正如您在图像中看到的，那两个相邻的图块具有相同的分数，但我在那个点随机选择了一个......（在下图中，起点是猫，红十字是目标点.绿色半透明文件为计算路径）

在此处输入图像描述

我在想，因为没有太多的瓦片，我可以从 4 个初始相邻瓦片计算 4 条不同的路径，将有效路径存储在一个数组中，然后基本上只使用最短的，但这可能会太多开销还有另一种解决方案吗？

要计算我使用基本计算的距离：

private int CalculateManhattanDistance(int x1, int x2, int y1, int y2)
{
        return Mathf.Abs(x1 - x2) + Mathf.Abs(y1 - y2);
}

标签： c#unity3da-star

解决方案

也许这可以帮助您了解@Zdeněk Jelínek 和@Peter Wishart 都指出了什么。openSet（也称为 frontier）通常是PriorityQueue。队列中的节点根据它们的优先级排序。节点的优先级计算为到目前为止的成本（在您的情况下为步数）和启发式距离（在您的情况下为曼哈顿）的总和。因此，一旦 A* 到达优先级为 11 的节点，它将停止探索该路径并继续探索其他路径（蓝色圆圈）

推荐阅读