Maze pokolenie używając DFS nie powiedzie się i nie wiem dlaczego

Question

Chciałem generować jakieś labirynty pomocą najprostszy algorytm, ale wszyscy moi labirynty wyglądać następująco jednym:

Oto kawałek kodu Java (funkcja whatVisit działa poprawnie, nie patrz na nią):

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; 
} 

I wiem, dlaczego to nie działa! Gdy DFS w końcu dotrze do miejsca, w którym nie ma dostępnych komórek, po prostu wychodzi, aby zacząć.

Jak to naprawić i zmusić do poprawnej pracy?

Dzięki.

Answer 1

Właściwie nadal nie rozumiem, jaki jest cel labiryntu, który chcesz wygenerować. Ale mam pewne propozycje dla Ciebie:

1. Utwórz punkt 2 lub 3 początku swojego algorytmu DFS przez losowo współrzędnych tak, że labirynt nie będzie monotonna.

2. W swoim algorytmie, próbujesz tylko 1 dostępnej komórki w każdym ruchu. Spróbuj uzyskać dostęp do bardziej dostępnej komórki w każdym ruchu, aby ścieżka nie była jednokierunkowa. (I to jest również powód, dlaczego DFS wrócić do początku po nie może znaleźć dostępne komórkę)

Oto mój kod mojego pomysłu powyżej 2 (edycja z kodu powyżej):

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; 
} 

nadzieję, że pomoże;)

Answer 2

wygląda jakbyś po prostu ratowanie i wychodzić, kiedy dojdziesz ślepa. Zamiast tego powinieneś wycofać się, aż znajdziesz komórkę, która wciąż ma dostępne sąsiadów, i kontynuować od tego algorytmu. Zwykły sposób to zrobić za pomocą stosu: pchnij elementy podczas ich odwiedzania, przejdź do ścieżki powrotnej. Coś takiego:

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); 
}