c# - 当你遇到死胡同时如何以编程方式穿越迷宫

Question

向前穿过迷宫很容易，但我似乎无法弄清楚一旦你遇到死胡同而不会返回太远，如何在迷宫中倒退以尝试新路线？

Answer 1

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

Answer 2

最简单（实现）的算法是只保留一堆您去过的位置，以及您从每个位置采取的路线，除非回溯为您提供该信息。

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

通过每次都以相同的顺序始终测试出口，如果您知道回溯到某个位置是从 down 开始的（即上次您在您下降的旧位置），那么您只需在down之后选择下一个方向。

不过，我不完全确定您说的返回太远是什么意思，我假设您想回到以前有未经测试的路线的地方，这不是您想要的吗？

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

一个简单的递归方法，它标记它所走的路径并且从不进入被标记的区域，可以很容易地做到这一点。

此外，如果您在迷宫中移动的东西比仅仅能够移动并撞到（停在）墙壁稍微聪明一点，因为它可以从当前点看到各个方向，我还有其他算法可能会有所帮助。

Answer 3

Eric Lippert 写了一系列关于创建A* 的 C# 实现的文章，这可能更有效。