如何保證所有開放節點都可以穿越

在一個項目中，我目前使用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

如何保證所有開放節點都可以穿越

回答

相關問題