网格系统中的寻路

Question

我目前正在使用SDL在C++中构建一个基于网格的小游戏.我创建了一个tile类,它代表地图上的每个单独的tile.该图块类用于二维矢量,一维表示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的一致路径,但这似乎不是最佳的.

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

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应该工作.

Answer 2

看看最常用的路径查找算法.

http://qiao.github.io/PathFinding.js/visual/

这是在JS中完成的,但您应该能够找到适合您需求的C++实现,或者编写自己的C++实现.