如何保证所有开放节点都是可遍历的
How to guarantee that all open nodes are traversable
在一个项目中，我目前正在使用 A* 查找路径。我先放下了我的经纪人。然后我将所有的阻断器放在任何空闲的节点上。 代理需要能够到达任何打开的节点。但是，可能会发生以下情况：
A = Agent
B = Node that's blocked
X = An open node that's impossible to reach
[A] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ]
[B] [B] [ ] [ ] [ ]
[X] [B] [ ] [ ] [ ]
为了避免这种情况，可以回答以下问题（回答其中任何一个都可以解决此问题）：
- 我如何检测到没有到 X 的路径，然后以最佳方式修复它（或者至少是不需要对每个节点调用 A*，然后随机选择不同节点的可接受方式）放置一个阻断器直到最后所有节点都可遍历）？
- 放置阻挡器时，如何确保它们不会使任何开放节点无法到达？
我能想到的一种方法是放置所有的阻挡物。然后我可以检查他们的邻居，看看是否有任何邻居节点是开放的，并且可以通过向他们调用 A* 来遍历。这至少比我在问题 1 中解释可能的解决方案的方式好一点。
有几种生成迷宫的方法。最简单的是随机深度优先搜索（从起始单元格开始，以随机顺序访问未访问过的邻居，直到到达出口。所有未访问过的单元格都被认为是墙）。它具有所有必需的属性（由于它的终止条件，出口总是可达的，所有开放的单元都可以从起始单元到达，因为它总是只生成一个连接的组件）。您可以在此处阅读更多相关信息（以及其他一些迷宫生成算法）：http://en.m.wikipedia.org/wiki/Maze_generation_algorithm.
在一个项目中，我目前正在使用 A* 查找路径。我先放下了我的经纪人。然后我将所有的阻断器放在任何空闲的节点上。 代理需要能够到达任何打开的节点。但是，可能会发生以下情况：
A = Agent
B = Node that's blocked
X = An open node that's impossible to reach
[A] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ]
[B] [B] [ ] [ ] [ ]
[X] [B] [ ] [ ] [ ]
为了避免这种情况，可以回答以下问题（回答其中任何一个都可以解决此问题）：
- 我如何检测到没有到 X 的路径，然后以最佳方式修复它（或者至少是不需要对每个节点调用 A*，然后随机选择不同节点的可接受方式）放置一个阻断器直到最后所有节点都可遍历）？
- 放置阻挡器时，如何确保它们不会使任何开放节点无法到达？
我能想到的一种方法是放置所有的阻挡物。然后我可以检查他们的邻居，看看是否有任何邻居节点是开放的，并且可以通过向他们调用 A* 来遍历。这至少比我在问题 1 中解释可能的解决方案的方式好一点。
有几种生成迷宫的方法。最简单的是随机深度优先搜索（从起始单元格开始，以随机顺序访问未访问过的邻居，直到到达出口。所有未访问过的单元格都被认为是墙）。它具有所有必需的属性（由于它的终止条件，出口总是可达的，所有开放的单元都可以从起始单元到达，因为它总是只生成一个连接的组件）。您可以在此处阅读更多相关信息（以及其他一些迷宫生成算法）：http://en.m.wikipedia.org/wiki/Maze_generation_algorithm.