在迷宫中前进很容易，但是我似乎无法弄清楚一旦遇到死角而又不走得太远，如何在迷宫中后退以尝试新的路线？

解决方案

回答

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

回答

最简单(实现)的算法是仅保留一堆我们曾经去过的位置以及我们从每个位置走的路线，除非回溯为我们提供该信息。

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

通过每次都以相同顺序对出口进行连续测试，如果我们知道回溯到某个位置是向下的(即，上次我们在旧位置时我们是向下走的)，那么我们只需在向下走后选择下一个方向即可。

我不能完全确定返回太远是什么意思，我假设我们想回到未测试路线的先前位置，这不是我们想要的吗？

请注意，除非我们尝试跟踪从起点到当前位置的路径，并在尝试查找新路线时避免使用这些正方形，否则最终可能会绕圈走，最终会使堆栈太大。

一个简单的递归方法可以标记它所经过的路径，并且永远不会进入标记的区域，因此很容易做到这一点。

另外，如果我们在迷宫中移动的东西比仅能移动并撞到(停在)墙壁上要聪明得多，因为它可以从当前点向各个方向查看，那么我可以使用其他算法来提供帮助。

回答

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