如何保证所有开放节点都可以穿越

在一个项目中，我目前使用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中解释可能的解决方案的方式要好一些。

来源

2015-04-04 Programmer_D

您是否有任何放置块的具体规则，或者您是否需要生成满足所有提及的属性的随机迷宫？ – kraskevich 2015-04-04 15:23:33

我没有放置块的具体规则。现在他们被随机放置在任何打开的节点上。但是，也许我应该有放置它们的规则？制定放置规则实际上会回答问题2，但我不知道规则会是什么。我需要满足的唯一不动产是代理必须能够到达任何开放节点。 – 2015-04-04 22:47:44

有几种方法可以生成迷宫。最简单的是随机深度优先搜索（从开始单元开始，随机访问未访问的邻居，直到到达出口为止，所有未访问的单元都被认为是墙）。它具有所有必需的属性（由于其终止条件，出口始终可到达，所有开放单元格都可从起始单元格到达，因为它始终只生成一个连接的组件）。你可以在这里阅读更多关于它（以及其他一些迷宫生成算法）：http://en.m.wikipedia.org/wiki/Maze_generation_algorithm。

来源

2015-04-05 00:48:45 kraskevich

我想让你知道我还在努力实施你的建议。一旦我得到它的工作，我会接受你的答案！ – 2015-04-06 12:59:36

我结束了使用**递归backtracker **算法（我没有尝试任何其他人，因为这个看起来最简单）。 – 2015-04-12 12:00:16

如何保证所有开放节点都可以穿越

回答

相关问题