穿过迷宫的算法
我们目前正在编写一个游戏（这是一种相当未知的语言：模块 2）， 我们遇到的问题如下：我们有一个 17 x 12 网格的迷宫（不是完美的迷宫）。计算机必须生成一条从起点 (9, 12) 到终点 (9, 1) 的路线。我找到了一些算法，但当机器人必须返回时它们不起作用：
xxxxx
x
=> x
x
xxx
或者：
xxxxx
x
xxxxxx x
x x
x x
xxxxxx x
=> x
xxxxxxxxx
我找到了第一种示例类型的解决方案，但随后无法解决第二种类型，而我为第二种类型编写的解决方案将导致机器人陷入了第一种情况。
这是很多代码，所以我会给出这个想法：
WHILE（未到达最终目的地）DO { 尝试向右走，如果没有什么阻碍你：向右走 如果遇到障碍，就尝试向上，直到可以向右走，如果不能再向上，就尝试向下，直到可以向右走，（从第一次被阻挡的地方开始），如果不能再向下，尝试一步离开并用块填充您测试的空间。 这
适用于第一类问题……不适用于第二类问题。 现在可能是我一开始就错了，所以我愿意寻求更好的算法或解决方案，特别是如何改进我的算法。
多谢！！
We are currently programming a game (its a pretty unknown language: modula 2),
And the problem we encountered is the following: we have a maze (not a perfect maze) in a 17 x 12 grid. The computer has to generate a way from the starting point (9, 12) to the end point (9, 1). I found some algorithms but they dont work when the robot has to go back:
xxxxx
x
=> x
x
xxx
or:
xxxxx
x
xxxxxx x
x x
x x
xxxxxx x
=> x
xxxxxxxxx
I found a solution for the first example type but then the second type couldn't be solved and the solution I made up for the second type would cause the robot to get stuck in the first type of situation.
It's a lot of code so i'll give the idea:
WHILE (end destination not reached) DO {
try to go right, if nothing blocks you: go right
if you encounter a block, try up until you can go right, if you cant go up anymore try going down until you can go right, (starting from the place you first were blocked), if you cant go down anymore, try one step left and fill the spaces you tested with blocks.
}
This works for the first type of problem ... not for the second one.
Now it could be that i started wrong so i am open for better algorithms or solutions specificaly to how i could improve my algorithm.
Thanks a lot!!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我想我记得你的算法只有当你通过入口进入迷宫、拥抱墙壁并尝试出去时才起作用。例如，如果你从迷宫中间的一个“岛”开始，它将不起作用。
查看广度优先搜索。这也将为您提供到达您想去的任何单元格的最短路径。基本上，这个想法是您不想两次访问同一个单元（没有理由），因此从每个单元中进行分支。
对于你的第一个例子。您可能可以识别该模式，其中数字是从箭头开始到达每个单元格所需的步骤数。
当然，如果您愿意，您可以通过跟踪每个单元格之前到达该单元格的最佳路径来重建所采用的路径。
广度优先搜索的工作原理是假设每个网格单元之间的距离是恒定的。如果相邻单元格之间的距离变化，您可能会看一下此类问题：最短路径问题。
I think I recall your algorithm only working when you enter the maze through an entrance, hug a wall, and try to go out. For example, if you start at an "island" in the middle of the maze, it will not work.
Take a look into Breadth-first search. This will also give you the shortest path to any cell you want to go. Basically the idea is that you don't want to visit the same cell twice (there's no reason to) so from each cell you branch out.
For your first example. You can probably recognize the pattern, with the numbers being the number of steps it takes to get to each cell starting from the arrow.
You can, of course, reconstruct the path taken if you like, by keeping track, for each cell, of the best previous path taken to this cell.
Breadth-first search works assuming that the distance between each grid cell is a constant one. If the distance between adjacent cell varies, you might take a look at this class of problems: Shortest path problem.
您可能需要实现路径查找算法，因为您不仅想找到任何路径，还想找到可能的最短路径。最流行的路径查找算法是 Dijkstra 和 A*。如果您知道整个迷宫的布局，它将为您提供从一个点到另一个点的最短路径。
You will probably need to implement a path finding algorithm cause you not only want to find any way, you also want to find the shortest way possible. The most popular path finding algorithms are the Dijkstra and the A*. If you know the layout of your whole maze it will give you the shortest possible path from one point to another.
你将这个问题想象成一个角色正在穿过迷宫。我不会那样做。我将迷宫想象成一系列隧道，水流过它们（意味着答案会流向各个方向）。因此，如果您要将迷宫表示为 2 个空间的字符串数组，其中 null（或其他一些字符作为墙），不同的分隔符作为尚未发现的位置（例如“o”），其余的作为到达该方块的最短路径（使用“n”、“e”、“s”和“w”）。然后，迭代一个循环，每次，每个方块都会查看是否可以扩展到另一个方块（如果该方块中有一个“o”），然后，它将添加该方块的字符串的串联版本已经到下一个方格，其中的字符代表到达那里所需的移动。当你找到终点方块时，你就完成了。
You're thinking of the problem as a character going through the maze. I wouldn't do that. I would imagine the maze as a series of tunnels with water flowing through them (meaning that the answer would flow in all directions). So if you were to represent the maze as a 2 space array of strings, with null (or some other char as a wall), a different delimiter as places that haven't been discovered (say 'o'), and the rest as the shortest path to get to that square (using 'n', 'e', 's', and 'w'). Then, iterate through a loop, each time, each square will look to see if it can spread out to another square (if the square has a 'o' in it), then, it will add a concatenated version of the string that square has to the next square, with the char representing the move it took to get there. When you find the end square, you're done.
您试图解决的问题称为寻路。方法有很多，从简单的暴力破解到令人惊叹的 A*。维基百科在此处提供了非常好的概述。
The problem you are trying to solve is called pathfinding. There are lots of methods, from simple brute force to the amazing A*. Wikipedia has a very good overview here.