网格系统中的寻路

Question

我目前正在使用 SDL 在 C++ 中构建一个基于网格的小型游戏。我制作了一个瓦片类，它代表地图上的每个瓦片。该瓦片类用于二维向量，一维表示 X 轴，另一维表示 Y 轴。

我遇到了算法问题，我什至不知道从哪里开始，假设我有这张地图：

 0 0 1 1 0 E
0 0 0 1 0 1
0 C 0 1 0 1
0 1 0 1 0 1
0 1 1 1 1 1

C是我的角色，E是出口，1是地砖。

我想找出最好的方法来确定角色是否有办法到达出口。我知道我可以使用一个函数来手动检查 C 周围的每一块地砖，并且对于 C 周围的每一块地砖，我会再次检查周围的每一块地砖，直到找到通往 E 的一致路径，但这似乎不是最优的。

我可以有一个线索或某种方向来定位自己吗？

原文由 Sefam 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

有很多算法可以找到两点之间的路径。三种算法易于实现和理解。

1. 深度优先搜索（DFS）
2. 广度优先搜索（BFS）
3. Dijkstra 算法

深度优先搜索

该算法获取当前节点，找到所有邻居，将它们放入堆栈，弹出一个并遍历到最后或找到路径。

广度优先搜索

该算法获取当前节点，找到所有邻居，将它们放入队列中，逐个出列并遍历直到结束或找到路径。

DFS 和 BFS 的区别在于，DFS 不能保证最优解。考虑这种情况。

 S 1 1
1 1 1
1 1 E

假设 S 是 (0,0) 而 E 是 (2, 2)。这个迷宫有很多最优解。由于 DFS 会检查其邻居的路径直到最后，它可能需要 S -> (1,0) -> (2,0) -> (2,1) -> (1,1) -> (1,2) -> E 并且它将返回 6 作为路径的成本。然而，BFS 找到所有邻居，所有邻居的邻居并继续。如果邻居之一是 E，则返回成本。这将保证是最佳的。所以，BFS 可能会这样。 S -> (1,0) -> (2,0) -> (2,1) -> E （它找到邻居的邻居，它不会与每个邻居一起走到最后）。

Dijkstra 算法

它类似于 BFS，但它可以有权重。在示例中，我们假设从一个节点移动到另一个节点的成本为 1 个单位。在 Dijkstra 的算法中，它允许我们使用任何正整数作为代价，并且对于每个链接它可以是不同的。

结论

如果您想要最佳结果，请选择 BFS 或 Dijkstra 算法。对于您的情况，BFS 应该可以工作。

原文由 thefourtheye 发布，翻译遵循 CC BY-SA 3.0 许可协议