c - A* 在 C 中用于二维数组寻路是否合理？

Question

我需要我的 C 程序能够在板上运行。棋盘由一个 2D int 数组表示(其中 0 和 7 是空方 block ，其他一切都是障碍物)。从一个正方形移动到另一个正方形的成本始终相同，但不应沿对角线移动。

我一直在查找 A*，但它令人困惑，而且我能找到的每个示例都是关于 C++ 或 Java 的，所以我开始怀疑它是否可能在 C 上实现。

那以及它是否是用于它的最佳算法。

编辑:棋盘是 24x25 还是 25x24 我不记得是哪个了

Answer 1

由于您的电路板很小，您可以使用 breadth-first search (BFS)全面搜索最佳路径。我认为即使不优于 A* 算法，性能也将是可比的。

该算法比 A* 简单，互联网上有许多 C 语言的实现。这是网格上 BFS 横向的示例:

要获取路径，您可以保存一个矩阵(例如 char 的二维数组——我们将其命名为 parent)，其中 parent[x][y]例如(0 - 如果你从左边到达那个方格，1 - 右边，2 - 向上，3 - 向下)。例如，如果您正在访问坐标为 (4,6) 的广场并将 (5,6) 放入队列，您可以执行 parent[5][6] = 2 因为( 5,6) 来自上面的行 (4,6)。因此，要检索完整路径，您可以选择目标节点并保存 parents 坐标，直到到达源方 block 。

现在由您考虑并想出如何实现它:)