迷宮代使用DFS失敗，我不知道爲什麼

Question

我只是想利用產生最簡單的算法一些迷宮，但我所有的迷宮看起來像下列操作之一：

這裏是一塊Java代碼（一whatVisit功能的工作原理是正確的，不要看它）：

private void dfs(Point start, boolean[][] visited) { 
    Point nextCell = whatVisit(start, visited); 
    if(nextCell == null)  // if there's nothing to visit 
     return; 

    // mark current cell as visited 
    visited[start.y][start.x] = true; 
    // destroy the wall between current cell and the new one 
    borders[(start.y + nextCell.y)/2][(start.x + nextCell.x)/2] = true; 

    // start a new search from found cell 
    dfs(nextCell, visited); 
} 

private Point whatVisit(Point p, boolean[][] visited) { 
    Vector<Point>cells = new Vector<Point>(); // to store acessible cells 

    // lookaround 
    if(p.x - 2 >= 0 && !visited[p.y][p.x - 2]) 
     cells.add(new Point(p.x - 2, p.y)); 
    if(p.x + 2 < visited[0].length && !visited[p.y][p.x + 2]) 
     cells.add(new Point(p.x + 2, p.y)); 
    if(p.y - 2 >= 0 && !visited[p.y - 2][p.x]) 
     cells.add(new Point(p.x, p.y - 2)); 
    if(p.y + 2 < visited.length && !visited[p.y + 2][p.x]) 
     cells.add(new Point(p.x, p.y + 2)); 

    // instead of Random 
    Collections.shuffle(cells); 

    // returns null if there are no acessible cells around 
    if(cells.size() > 0) 
     return cells.get(0); 
    else return null; 
} 

而且我知道爲什麼它不工作！當DFS終於來到沒有可訪問單元的地方時，它就會返回開始。

如何解決這個問題，並強制工作正確？

謝謝。

Answer 1

其實我還是不明白你想要生成的迷宮的目的是什麼。但我有一些建議供您參考：

1. 創建通過隨機座標，使迷宮不會是單調的DFS算法的2或3的起點。

2. 在您的算法中，您只能在每次移動中嘗試1個可訪問的單元格。嘗試在每次移動中訪問更容易訪問的單元格，以便路徑不會是完成的單向路徑。 （這也是爲什麼你的DFS回去開始後將無法找到允許接入的小區）

這裏是我的我的上述想法第2的代碼（從上面的代碼編輯）：

private void dfs(Point start, boolean[][] visited) { 
    ArrayList<Point> nextCell = whatVisit(start, visited); 
    if(nextCell == null)  // if there's nothing to visit 
     return; 

    // mark current cell as visited 
    visited[start.y][start.x] = true; 

    for (Point next : nextCell) // try new accessible cells 
    { 
     // destroy the wall between current cell and the new one 
     borders[(start.y + next.y)/2][(start.x + next.x)/2] = true;  
     // start a new search from found cell 
     dfs(next, visited); 
    } 
} 

private ArrayList<Point> whatVisit(Point p, boolean[][] visited) { 
    Vector<Point>cells = new Vector<Point>(); // to store acessible cells 

    // lookaround 
    if(p.x - 2 >= 0 && !visited[p.y][p.x - 2]) 
     cells.add(new Point(p.x - 2, p.y)); 
    if(p.x + 2 < visited[0].length && !visited[p.y][p.x + 2]) 
     cells.add(new Point(p.x + 2, p.y)); 
    if(p.y - 2 >= 0 && !visited[p.y - 2][p.x]) 
     cells.add(new Point(p.x, p.y - 2)); 
    if(p.y + 2 < visited.length && !visited[p.y + 2][p.x]) 
     cells.add(new Point(p.x, p.y + 2)); 

    // returns null if there are no accessible cells around 
    if(cells.size() > 0) 
    { 
     ArrayList<Point> tmp = new ArrayList<Point>(); 
     // randomize how many cell that will be returned 
     int x = (int)(Math.random()*cells.size()) + 1; 
     if (x > cells.size()) 
      x = cells.size(); 
     Collections.shuffle(cells); 
     for (int i = 0; i < x; i++) 
      tmp.add(cells.get(i)); 
     return tmp; 
    } 
    else return null; 
} 

希望這將幫助;）

Answer 2

看起來你只是想逃出來並退出每當你到達一個死衚衕。相反，你應該回溯，直到找到一個仍然具有可訪問鄰居的單元，然後從那裏繼續算法。通常的做法是使用堆棧：在您訪問它們時推送項目，彈出到回溯。事情是這樣的：

if (nextCell == null) { // You've reached a dead-end 
    if (stack.empty()) // base-case, bail out 
    return; 

    dfs(stack.pop(), visited); // backtrack 
} else { 
    stack.push(nextCell); 

    visited[start.y][start.x] = true; 
    borders[(start.y + nextCell.y)/2][(start.x + nextCell.x)/2] = true; 
    dfs(nextCell, visited); 
}