我们目前正在编写一个游戏（它是一种非常未知的语言：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 回答
我想我记得你的算法只有当你通过一个入口进入迷宫，拥抱一堵墙并试着出去时才有效 . 例如，如果你从迷宫中间的“岛屿”开始，它将无法工作 .
看看Breadth-first search . 这也将为您提供前往任何单元格的最短路径 . 基本上这个想法是你没有理由，所以你从每个细胞分支出来 .
第一个例子 . 您可以识别模式，数字是从箭头开始到达每个单元格所需的步骤数 .
当然，如果您愿意，您可以通过跟踪每个单元格来获取此单元格中最佳的先前路径，从而重建所采用的路径 .
广度优先搜索工作假设每个网格单元之间的距离是常数 . 如果相邻单元格之间的距离不同，您可能会看一下这类问题：Shortest path problem .
您可能需要实现路径查找算法，因为您不仅希望找到任何方法，还希望找到最短路径 . 最流行的路径寻找算法是Dijkstra和A* . 如果您了解整个迷宫的布局，它将为您提供从一个点到另一个点的最短路径 .
你把这个问题想象成一个穿过迷宫的角色 . 我不会这样做 . 我会把迷宫想象成一系列隧道，水流过它们（这意味着答案会向各个方向流动） . 因此，如果您将迷宫表示为2个空格字符串数组，使用null（或其他一些字符作为墙），将不同的分隔符表示为尚未发现的地方（例如“o”），其余为到达那个广场的最短路径（使用'n'，'e'，'s'和'w'） . 然后，迭代循环，每次，每个方块将查看它是否可以展开到另一个方块（如果方块中有一个'o'），那么，它将添加一个连接的字符串版本必须到下一个广场，其中的char代表了到达那里的举动 . 当你找到最终方块时，你已经完成了 .
您尝试解决的问题称为寻路 . 有很多方法，从简单的蛮力到惊人的A* . 维基百科有一个非常好的概述here .