generazione Maze utilizzando DFS non riesce e non so il motivo per cui

Question

Volevo solo generare alcuni labirinti utilizzando l'algoritmo più semplice, ma tutti i miei labirinti apparire come il seguente:

Ecco un pezzo di codice Java (una funzione whatVisit funziona correttamente, non guardare):

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

E so il motivo per cui non funziona! Quando finalmente DFS arriva nel punto in cui non ci sono celle accessibili, torna indietro per iniziare.

Come risolvere questo problema e forzare il corretto funzionamento?

Grazie.

Answer 1

In realtà non riesco ancora a capire quale sia lo scopo del labirinto che si desidera generare. Ma ho alcuni suggerimenti per voi:

1. Crea punto 2 o 3 all'inizio del vostro algoritmo DFS casuale l'coordinata, in modo che il labirinto non sarà monotono.

2. Nel tuo algoritmo, provi solo 1 cella accessibile in ogni mossa. Prova ad accedere alla cella più accessibile in ogni mossa in modo che il percorso non sia un percorso a 1 via per finire. (E questo è anche il motivo per cui i DFS tornare per iniziare dopo che non riesce a trovare cellule accessibile)

Ecco il mio codice della mia seconda idea sopra (a cura dal codice di cui sopra):

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

Spero che questo vi aiuterà;)

Answer 2

sembra che tu sei solo salvataggio e smettere ogni volta che si raggiunge un vicolo cieco. Invece, dovresti tornare indietro finché non trovi una cella che ha ancora dei vicini accessibili e continua l'algoritmo da lì. Il solito modo di farlo è con una pila: spinge gli oggetti mentre li visiti, fai un salto indietro. Qualcosa del genere:

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