穿越迷宫的算法

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

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

非常感谢！

来源

2010-03-19 Sam

我想我记得你的算法只有当你通过一个入口进入迷宫，拥抱一堵墙，并尝试出去时，你的算法才起作用。例如，如果你从迷宫中间的一个“岛屿”开始，它将无法工作。

看看Breadth-first search。这也会给你想要去的任何细胞的最短路径。基本上这个想法是，你不希望从你分支的每个单元访问同一个单元两次（没有理由）。

您的第一个例子。您可以识别该模式，数字是从箭头开始到达每个单元格所需的步骤数。

xxxxx 
3212x 
2101x 
3212x 
43xxx

你可以，当然，重建所采取的路径，如果你喜欢，通过跟踪，对每个小区，采取这种电池的最佳前一路径的。

广度优先搜索假定每个网格单元之间的距离是恒定的。如果相邻单元格之间的距离有所不同，那么可以看看这类问题：Shortest path problem。

来源

2010-03-19 14:32:20 Larry

你可能会需要实现搜索算法的路径，因为你不仅想找到什么办法，你也想找到最短可能的方式。最流行的路径搜寻算法是Dijkstra和A*。如果你知道整个迷宫的布局，它将为你提供从一点到另一点的最短路径。

来源

2010-03-19 14:32:58 Daff

您试图解决的问题叫做寻路。有很多方法，从简单的蛮力到惊人的A*。维基百科有一个非常好的概述here。

来源

2010-03-19 14:36:31

你正在考虑这个问题是否是一个穿过迷宫的角色。我不会那样做。我会将迷宫想象成一系列隧道，水流经它们（意味着答案会流向各个方向）。因此，如果您要将迷宫表示为2个空格字符串数组，其中包含null（或其他字符作为墙），与未发现的地方（如'o'）不同的分隔符，其余为到达那个广场的最短路径（使用'n'，'e'，'s'和'w'）。然后，循环遍历一个循环，每次，每个正方形都会查看它是否可以传播到另一个正方形（如果正方形中有'o'），那么它将添加一个连接版本的字符串，该正方形已经到了下一个广场，char代表了它到达那里的动作。当你找到结束方块时，你就完成了。

来源

2010-03-19 17:35:36

穿越迷宫的算法

回答

相关问题