1

我们目前正在编写一个游戏（它是一种非常未知的语言：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 { 尝试向右走，如果没有任何阻碍：如果遇到障碍，请向右走，直到可以向右走，如果您不能再向上走，请尝试向下走，直到可以向右走， （从你第一次被阻挡的地方开始），如果你不能再下去了，试着往左走一步，用方块填充你测试的空间。}

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

非常感谢！！

4

4 回答 4

2

我想我记得你的算法只有在你通过一个入口进入迷宫，拥抱一堵墙，然后尝试出去时才有效。例如，如果你从迷宫中间的一个“岛”开始，它是行不通的。

看看广度优先搜索。这也将为您提供到您想去的任何单元格的最短路径。基本上这个想法是你不想两次访问同一个单元格（没有理由），所以你从每个单元格中分支出来。

对于你的第一个例子。您可能可以识别出这种模式，数字是从箭头开始到达每个单元格所需的步数。

xxxxx
3212x
2101x
3212x
43xxx

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

广度优先搜索的工作原理是假设每个网格单元之间的距离是一个常数。如果相邻单元格之间的距离不同，您可以查看此类问题：最短路径问题。

于 2010-03-19T14:32:20.803 回答
2

您可能需要实现寻路算法，因为您不仅想找到任何方法，还想找到可能的最短路径。最流行的寻路算法是Dijkstra和A*。如果您知道整个迷宫的布局，它将为您提供从一个点到另一个点的最短路径。

于 2010-03-19T14:32:58.027 回答
1

你把这个问题想象成一个穿过迷宫的角色。我不会那样做的。我会把迷宫想象成一系列隧道，水流过它们（这意味着答案会流向各个方向）。因此，如果您要将迷宫表示为 2 空间字符串数组，使用 null（或其他一些字符作为墙），使用不同的分隔符作为尚未发现的位置（例如“o”），其余为到达该方格的最短路径（使用“n”、“e”、“s”和“w”）。然后，遍历一个循环，每次，每个方格都会查看它是否可以扩展到另一个方格（如果方格中有一个 'o'），然后，它将添加该方格的串联版本的字符串必须到下一个方格，char 代表到达那里所需的移动。

于 2010-03-19T17:35:36.367 回答
0

您要解决的问题称为寻路。有很多方法，从简单的蛮力到惊人的 A*。维基百科在这里有一个很好的概述。

于 2010-03-19T14:36:31.263 回答