当您陷入死胡同时，如何以编程方式穿越迷宫

Question

向前穿过迷宫很容易，但我似乎不知道一旦遇到死胡同，如何在不返回太远的情况下退回迷宫以尝试新路线？

Answer 1

使用 回溯 通过保留一堆以前的方向决策。

Answer 2

最简单（实现）的算法是只保留一堆你去过的位置，以及你从每个位置出发的路线，除非回溯给你提供了这些信息。

要返回，只需从堆栈中弹出旧位置并检查该位置是否有更多出口，直到找到具有未经测试出口的旧位置。

通过每次以相同的顺序一致地测试出口，如果您知道回溯到某个位置来自向下（即上次你在你下楼的旧位置），然后你只需选择下一个方向 向下.

我不完全确定你的意思 回溯太远 不过，我假设您想回到之前未测试路线的地方，这不是您想要的吗？

请注意，除非您尝试跟踪从起点到当前位置的路径，并在尝试寻找新路线时避开这些方块，否则您可能最终会陷入循环，这最终会使堆栈太大。

一个简单的递归方法可以轻松地做到这一点，该方法标记其所经过的路径并且从不进入已标记的区域。

另外，如果您的 事物 穿过迷宫比仅仅能够移动并撞到（停在）墙壁上稍微聪明一些，因为它可以从当前点向各个方向看到，我有其他可能有帮助的算法。

Answer 3

埃里克·利珀特 (Eric Lippert) 撰写了一系列关于创建 A* 的 C# 实现, ，这可能会更有效。