Maze generation using DFS fails and I don't know why

Question

I just wanted to generate some mazes using the easiest algorithm, but all my mazes look like the following one:

Here is a piece of Java code (a whatVisit function works correct, don't look at it):

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

And I know why it doesn't work! When DFS finally come to the place where there are no accessible cells, it just going out back to start.

How to fix this and force to work correct?

Thanks.

Answer 1

Actually I still don't get what the purpose of the maze that you want to generate is. But I have some suggestions for you:

1. Create 2 or 3 start point of your dfs algorithm by randomize the coordinate, so that the maze won't be monotonous.

2. In your algorithm, you only try 1 accessible cell in each move. Try to access more accessible cell in each move so that the path wouldn't be a 1-way path to finish. (and this is also the reason why your dfs go back to start after it can't find accessible cell)

Here is my code of my 2nd idea above (edited from your code above) :

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

Hope this will help ;)

Answer 2

It looks like you're just bailing out and quitting whenever you reach a dead-end. Instead, you should backtrack until you find a cell that still has accessible neighbors, and continue the algorithm from there. The usual way to do this is with a stack: push items as you visit them, pop to backtrack. Something like this:

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