在網格迷宮中擺脫斷開的矩形

我有這樣的：

enter image description here

的問題是，我用紅色圓圈。我需要一種方法來擺脫那些不屬於謎題其餘部分的矩形。

我創建了一個簡單的算法，該算法對於正方形的工作原理：

此工作的方式是二維陣列的每個元素表示一個頂點（圖節點）。每個圖形節點都有一個它連接到的頂點列表。通過從每個頂點到每個連接繪製線來繪製該圖。

private void removeDisconnectedSquare(int x, int y) 
{ 
    GraphNode topLeft = getNodeAt(x, y); 
    GraphNode topRight = getNodeAt(x + 1, y); 
    GraphNode bottomLeft = getNodeAt(x, y + 1); 
    GraphNode bottomRight = getNodeAt(x + 1, y + 1); 

    if(topLeft != null && 
     topRight != null && 
     bottomLeft != null && 
     bottomRight != null && 
     !hasNodeToLeft(topLeft) && hasNodeToRight(topLeft) && 
     !hasNodeAbove(topLeft) && hasNodeBelow(topLeft) && 
     hasNodeToLeft(topRight) && !hasNodeToRight(topRight) && 
     !hasNodeAbove(topRight) && hasNodeBelow(topRight) && 
     !hasNodeToLeft(bottomLeft) && hasNodeToRight(bottomLeft) && 
     hasNodeAbove(bottomLeft) && !hasNodeBelow(bottomLeft) && 
     hasNodeToLeft(bottomRight) && !hasNodeToRight(bottomRight) && 
     hasNodeAbove(bottomRight) && !hasNodeBelow(bottomRight)) 
    { 
     removeVertex(x, y); 
     removeVertex(x + 1, y); 
     removeVertex(x, y + 1); 
     removeVertex(x + 1, y + 1); 
    } 
}

有沒有一種算法或方法可以檢測出verties的路徑是否不是verticies的大連接路徑的一部分？有時這會產生一條小路。

謝謝

來源

2012-10-06 jmasterx

這看起來像java代碼給我。你爲什麼給C++加上標籤？ – 11684

糟糕，從另一個問題留下標籤。 – jmasterx

一個標準模板？ 0.o – 11684

我會建議找到一個好的圖庫。然後，將每個正方形表示爲一個節點，並且如果直接路徑在它們之間打開，則在正方形之間具有邊緣。最後，從'入口節點'開始使用'連接節點'算法（由圖庫提供）。最後，您可以遍歷所有未通過連接算法標記的節點並進行適當的處理。

例如，如果您使用的是C++，則可以使用Boost Graph Library Connected Components algorithm。其他好的圖庫應該有類似的支持。

你也可以推出你自己的這種算法;例如，推送堆棧上未標記的鄰居節點，標記訪問節點，然後從堆棧中彈出節點直到完成。然而，擁有一個好的圖表庫對於這類項目中可能遇到的其他問題很有用，IMO更願意自己動手。

也可能值得注意的是，您可能會改變您的迷宮生成算法，以始終生成連通圖，從而避免在事後處理斷開連接的組件。

來源

2012-10-06 19:40:28 WeirdlyCheezy

在網格迷宮中擺脫斷開的矩形

回答

相關問題