c++ - 网格系统中的寻路

Question

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

我有一个算法问题，我什至不知道从哪里开始，假设我有这张 map :

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 周围的每一 block 地砖，对于 C 周围的每一 block 地砖，我再次检查周围的每一 block 地砖，直到找到到达 E 的一致路径，但这似乎不是最佳选择。

我能有线索或某种方向来定位自己吗？

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 应该有效。