Issues with generating a maze using DFS backtracking algorithm

Question

I'm trying to implement the DFS backtracking algorithm that involves utilizing a stack (not the recursive algorithm) found on Wikipedia. I am trying to generate a maze of 0's and 1's, where 1's represent a wall and 0's represent an available path. For any given space in the maze that isn't a wall, there must always be a valid path that it can be reached by from any other non-wall cell.

I start with a maze that's a 2D array of size maze[15][20] and follow the algorithm in marking the cells that need to be marked as visited appropriately. Initially, all cells (excluding the outer borders) are marked as 'unvisited'. All cells are initialiazed with a value of '1' and the expectation is that the algorithm will dig unique paths throughout the maze.

Link to the algorithm (Recursive backtracker 2nd implementation utilizing stack):

https://en.wikipedia.org/wiki/Maze_generation_algorithm

Code I have written:

public void innerMaze() {
        List<Coordinate> listOfCoordinates = new ArrayList<>();
        List<Coordinate> coordinatesToBeRemoved = new ArrayList<>();
        Stack<Coordinate> DFS_Stack = new Stack();

        Coordinate initialCell = new Coordinate(1, 1);
        checkIfVisited.put(initialCell, true);
        DFS_Stack.push(initialCell);

        int randomInteger = 0;
        int cx = 0;
        int cy = 0;
        int gx = 0;
        int gy = 0;

        while (!DFS_Stack.empty()) {
            Coordinate currentCoordinate = DFS_Stack.pop();
            cx = currentCoordinate.getX();
            cy = currentCoordinate.getY();

            if ((cx - 2) >= 1) {
                Coordinate up = findCoordinate((cx - 2), cy);
                up.setDirection('N');
                listOfCoordinates.add(up);

            }
            if ((cx + 2) <= MAX_ROW) {
                Coordinate down = findCoordinate((cx + 2), cy);
                down.setDirection('S');
                listOfCoordinates.add(down);
            }
            if ((cy - 2) >= 1) {
                Coordinate left = findCoordinate(cx, (cy - 2));
                left.setDirection('W');
                listOfCoordinates.add(left);
            }
            if ((cy + 2) <= MAX_COL) {
                Coordinate right = findCoordinate(cx, (cy + 2));
                right.setDirection('E');
                listOfCoordinates.add(right);
            }
            for (Coordinate s : listOfCoordinates) {
                if (checkIfVisited.get(s) == true) {
                    coordinatesToBeRemoved.add(s);
                }
            }
            listOfCoordinates.removeAll(coordinatesToBeRemoved);

            if (!listOfCoordinates.isEmpty()) {
                DFS_Stack.push(currentCoordinate);
                randomInteger = ThreadLocalRandom.current().nextInt(0, listOfCoordinates.size());
                Coordinate temp = listOfCoordinates.get(randomInteger);
                char direction = temp.getDirection();
                Coordinate newWall;

                if (direction == 'N') {
                    newWall = findCoordinate((cx - 1), cy);
                } else if (direction == 'S') {
                    newWall = findCoordinate((cx + 1), cy);
                } else if (direction == 'W') {
                    newWall = findCoordinate(cx, (cy - 1));
                } else {
                    newWall = findCoordinate(cx, (cy + 1));
                }
                System.out.println(newWall);
                gx = newWall.getX();
                gy = newWall.getY();
                completeMaze[gx][gy] = 0;
                checkIfVisited.put(temp, true);
                checkIfVisited.put(newWall, true);
                listOfCoordinates.clear();
                DFS_Stack.push(temp);
            }
        }
    }

With my current implementation, each cell will either represent a wall or a path, therefore I have altered the algorithm slightly to where removing a wall between two cells becomes removing a wall two cells away, changing the one in-between to be a wall. A sample of my output is as follows:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1
1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0
1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1
1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0
1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1
1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1
1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0
1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1
1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0
1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0
1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

At first glance, the 2d array index [1][1] is encased in walls, therefore it is an unreachable area. This is also very consistent through numerous executions.

Any help would be appreciated.

Cells are all the coordinates with odd (x,y) values. When maze is done, all those coordinates should be cleared, but you only clear the wall coordinates. You need to clear both newWall and temp. --- It also means that a maze will always have odd sizes, so 15x20 is not a valid maze size. — Andreas
In normal coordinate system, the X-axis goes left-right, and the Y-axis goes up-down. Your code has reversed that, making your code confusing. — Andreas

nubDotDev nubDotDev · Accepted Answer · 2020-02-24T02:03:15

I would highly recommend using a different algorithm. I have a decent amount of experience in coding maze generation algorithms and recursive backtracking always results in really long paths with barely any choices to make. I can't see the issue in your code, but here is my own Java implementation of recursive backtracking (sorry if the code is bad, it's a few years old).

public class Maze {

    private int sizeX, sizeY;
    private Cell[][] cells;
    private List<Cell> backtracker = new ArrayList<>();

    public Maze(int sizeX, int sizeY) {
        this.sizeX = sizeX;
        this.sizeY = sizeY;
        this.cells = new Cell[sizeX][sizeY];
        for (int i = 0; i < sizeX; i++) {
            for (int j = 0; j < sizeY; j++)
                cells[i][j] = new Cell(this, i, j);
        }
        generate();
    }

    private void generate() {
        Cell current = cells[0][0];
        current.visit();
        boolean hasUnvisited = hasUnvisited();
        while (hasUnvisited) {
            current = current.pickNext();
            if (!current.isVisited()) {
                current.visit();
                backtracker.add(current);
                hasUnvisited = hasUnvisited();
            }
        }
    }

    private boolean hasUnvisited() {
        for (int i = 0; i < sizeX; i++) {
            for (int j = 0; j < sizeY; j++) {
                if (!cells[i][j].isVisited()) {
                    return true;
                }
            }
        }
        return false;
    }

    public Cell backtrack() {
        if (backtracker.size() == 0) return null;
        Cell cell = backtracker.get(backtracker.size() - 1);
        backtracker.remove(cell);
        return cell;
    }

    public Cell getCell(int x, int y) {
        return cells[x][y];
    }

}

public class Cell {

    private Maze maze;
    private int x, y;
    private boolean visited = false;
    // top, right, bottom. left
    private boolean[] walls = new boolean[]{true, true, true, true};

    public Cell(Maze maze, int x, int y) {
        this.maze = maze;
        this.x = x;
        this.y = y;
    }

    public Cell pickNext() {
        List<Cell> neighbors = new ArrayList<>();
        if (y != maze.sizeY - 1) neighbors.add(maze.getCell(x, y + 1));
        else neighbors.add(null);
        if (x != maze.sizeX - 1) neighbors.add(maze.getCell(x + 1, y));
        else neighbors.add(null);
        if (y != 0) neighbors.add(maze.getCell(x, y - 1));
        else neighbors.add(null);
        if (x != 0) neighbors.add(maze.getCell(x - 1, y));
        else neighbors.add(null);
        boolean hasUnvisitedNeighbor = false;
        for (Cell c : neighbors) {
            if (c == null) continue;
            if (!c.isVisited()) hasUnvisitedNeighbor = true;
        }
        if (hasUnvisitedNeighbor) {
            int random = (int) Math.floor(Math.random() * 4);
            Cell next = neighbors.get(random);
            while (next == null || next.isVisited()) {
                random = (int) Math.floor(Math.random() * 4);
                next = neighbors.get(random);
            }
            this.breakWall(random);
            next.breakWall((random + 2) % 4);
            return next;
        } else return maze.backtrack();
    }

    public void breakWall(int wall) {
        walls[wall] = false;
    }

    public void visit() {
        visited = true;
    }

    public boolean isVisited() {
        return visited;
    }

}

Issues with generating a maze using DFS backtracking algorithm

1 Answers