通过迷宫的算法

Question

我们目前正在编写一个游戏(它是一种非常未知的语言:modula 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 {尝试向右走，如果没有什么阻碍你:向右走遇到障碍就往上爬，往右走，爬不上去往下爬，往右走，(从第一次被遮住的地方开始)，爬不下去就往右走一步离开并用 block 填充您测试的空间。}

这适用于第一类问题……不适用于第二类问题。现在可能是我开始错了，所以我愿意寻求更好的算法或解决方案，特别是关于如何改进我的算法。

非常感谢!!

Answer 1

我想我记得您的算法只有在您通过入口进入迷宫、紧靠墙壁并尝试走出去时才有效。例如，如果您从迷宫中间的“岛屿”开始，它就不起作用。

查看 Breadth-first search .这也将为您提供到达任何您想去的单元格的最短路径。基本上这个想法是您不想两次访问同一个单元格(没有理由)，所以您从每个单元格分支出来。

你的第一个例子。您可能会认出这种模式，其中数字是从箭头开始到达每个单元格所需的步数。

xxxxx
3212x
2101x
3212x
43xxx

当然，如果您愿意，您可以通过跟踪每个单元格的最佳先前路径来重构所采用的路径。

广度优先搜索假设每个网格单元之间的距离是一个常数。如果相邻单元格之间的距离不同，您可能会看看此类问题:Shortest path problem .