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

Question

我需要我的 C 程序才能在电路板上移动。棋盘由 2D int 数组表示（其中 0 和 7 是空方格，其他都是障碍物）。从一个方格移动到另一个方格的成本始终相同，但不应沿对角线移动。

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

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

编辑：板是 24x25 或 25x24 我不记得哪个

Answer 1

由于您的电路板很小，您可以使用广度优先搜索 (BFS)来完整搜索最佳路径。我认为性能即使不比 A* 算法更好也可以相提并论。

该算法比 A* 更简单，并且互联网上有许多 C 语言实现。以下是网格上的 BFS 横向示例：

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

现在由您来考虑并弄清楚如何实现它:)