当您遇到死胡同时，如何以编程方式穿越迷宫
向前穿过迷宫很容易，但我似乎不知道如何在遇到死胡同的情况下在迷宫中后退以尝试新路线而不需要后退太远？
Moving through the maze forward is pretty easy, but I can't seem to figure out how to back up through the maze to try a new route once you hit a dead end without going back too far?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
Eric Lippert 撰写了一系列关于创建 A* 的 C# 实现< /a>，这可能会更有效。
Eric Lippert did a series of articles on creating a C# implemention of A*, which might be more efficient.
通过保留一堆先前的方向决策来使用回溯。
Use backtracking by keeping a stack of previous direction decisions.
最简单（实现）的算法是只保留一堆你去过的位置，以及你从每个位置出发的路线，除非回溯给你提供了这些信息。
要返回，只需从堆栈中弹出旧位置并检查该位置是否有更多出口，直到找到具有未经测试出口的旧位置。
通过每次以相同的顺序一致地测试出口，如果您知道回溯到某个位置来自向下（即上次您在向下的旧位置），那么您只需在 之后选择下一个方向下来。。
我不完全确定你所说的回溯太远是什么意思，但我认为你会想回到之前没有测试过的路线的地方，这不是你想要的吗？
请注意，除非您尝试跟踪从起点到当前位置的路径，并在尝试寻找新路线时避开这些方块，否则您可能最终会陷入循环，这最终会使堆栈太大。
一个简单的递归方法可以轻松地做到这一点，该方法标记其所经过的路径并且从不进入已标记的区域。
另外，如果你穿过迷宫的东西比仅仅能够移动并撞到（停在）墙壁上稍微聪明一点，因为它可以从当前点向各个方向看，我有其他可能有帮助的算法。
The simplest (to implement) algorithm would be to just keep a stack of locations you've been at, and the route you took from each, unless backtracking gives you that information.
To go back, just pop off old locations from the stack and check for more exits from that location until you find an old location with an untested exit.
By consistently testing the exits in the same order each time, if you know that backtracking to a location comes from down (ie. last time you were at the old location you went down), then you simply pick the next direction after down.
I am not entirely sure what you mean by going back too far though, I would assume you would want to go back to the previous place you have untested routes, is that not what you want?
Note that unless you try to keep track of the path from the starting point to your current location, and avoiding those squares when you try to find new routes, you might end up going in circle, which would eventually make the stack too large.
A simple recursive method which marks the path it takes and never enters areas that are marked can easily do this.
Also, if your thing that moves through the maze is slightly smarter than just being able to move, and hit (stop at) walls, in that it can see from its current point in all directions, I have other algorithms that might help.