algorithm – Iterative Random Depth First Search implementation in Java

I implemented the iterative randomized depth-first search, with my goal for it to be performant, and have code that made complete sense.

It utilizes AtomicReference<T> inside of Cell to keep track of it’s walls (as multiple cells can share walls). The randomization does not utilize Java 8 streams at all.

AdjacentDirection.java:

public enum AdjacentDirection
{
    TOP,
    BOTTOM,
    LEFT,
    RIGHT;

    static final AdjacentDirection() VALUES = values();
}

Cell.java:

import java.util.HashMap;
import java.util.Map;
import java.util.StringJoiner;
import java.util.concurrent.atomic.AtomicReference;

public class Cell
{
    private final int x;
    private final int y;
    private boolean visited;
    // Cells can share walls, so make this a reference.
    private final Map<AdjacentDirection, AtomicReference<Boolean>> walls = new HashMap<>();

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

    public boolean isVisited()
    {
        return visited;
    }

    void setVisited(boolean visited)
    {
        this.visited = visited;
    }

    void setWall(AdjacentDirection dir, AtomicReference<Boolean> wall)
    {
        walls.put(dir, wall);
    }

    AtomicReference<Boolean> getWall(AdjacentDirection dir)
    {
        return walls.get(dir);
    }

    public int getX()
    {
        return x;
    }

    public int getY()
    {
        return y;
    }

    @Override
    public String toString()
    {
        return new StringJoiner(", ", Cell.class.getSimpleName() + "(", ")")
                .add("x=" + x)
                .add("y=" + y)
                .add("visited=" + visited)
                .add("walls=" + walls)
                .toString();
    }
}

CellMap.java:

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.atomic.AtomicReference;

// This map assumes that the bottom-left most cell is point (0, 0)
public class CellMap
{
    private final Cell()() cells;

    public CellMap(int width, int height)
    {
        if (width <= 0 || height <= 0)
            throw new IllegalArgumentException("Width and height must be > 0");

        cells = new Cell(height)();

        for (var y = 0; y < cells.length; y++)
        {
            cells(y) = new Cell(width);
            for (var x = 0; x < cells(y).length; x++)
            {
                var cell = cells(y)(x) = new Cell(x, y);
                // Let's resolve references to the cell walls.
                // Because we go left to right, bottom to top, there will never:
                // Be a cell above us generated yet.
                // Be a cell to our right generated yet.
                // The other ones will always be there, unless x = 0 or y = 0
                var leftNeighborIndex = x - 1;
                var bottomNeighborIndex = y - 1;

                // The wall to our left is the right wall of the cell to our left.
                if (leftNeighborIndex >= 0)
                    cell.setWall(AdjacentDirection.LEFT, cells(y)(leftNeighborIndex).getWall(AdjacentDirection.RIGHT));
                else
                    cell.setWall(AdjacentDirection.LEFT, new AtomicReference<>(true));

                // The wall beneath us is the top wall of the cell beneath us.
                if (bottomNeighborIndex >= 0)
                    cell.setWall(AdjacentDirection.BOTTOM, cells(bottomNeighborIndex)(x).getWall(AdjacentDirection.TOP));
                else
                    cell.setWall(AdjacentDirection.BOTTOM, new AtomicReference<>(true));

                cell.setWall(AdjacentDirection.TOP, new AtomicReference<>(true));
                cell.setWall(AdjacentDirection.RIGHT, new AtomicReference<>(true));
            }
        }
    }

    public void randomDepthFirstSearch(Random rnd)
    {
        randomDepthFirstSearch(rnd, 0, 0);
    }

    // https://en.wikipedia.org/wiki/Maze_generation_algorithm#Iterative_implementation
    public void randomDepthFirstSearch(Random rnd, int initialX, int initialY)
    {
        var stack = new ArrayDeque<Cell>();
        // Choose the initial cell, mark it as visited and push it to the stack
        var initial = cells(initialY)(initialX);
        initial.setVisited(true);
        stack.push(initial);

        // While the stack is not empty
        while (!stack.isEmpty())
        {
            // Pop a cell from the stack and make it a current cell
            var current = stack.pop();
            var unvisitedNeighbors = getNeighbors(current.getX(), current.getY()).entrySet();
            unvisitedNeighbors.removeIf(kv -> kv.getValue().isVisited());

            // If the current cell has any neighbours which have not been visited
            if (!unvisitedNeighbors.isEmpty())
            {
                // Push the current cell to the stack
                stack.push(current);
                // Choose one of the unvisited neighbours
                Map.Entry<AdjacentDirection, Cell> chosen;
                var toSkip = rnd.nextInt(unvisitedNeighbors.size());
                var unvisitedIter = unvisitedNeighbors.iterator();

                for (var i = 0; i < toSkip; i++)
                    unvisitedIter.next();

                chosen = unvisitedIter.next();

                // Remove the wall between the current cell and the chosen cell
                current.getWall(chosen.getKey()).set(false);
                // Mark the chosen cell as visited and push it to the stack
                chosen.getValue().setVisited(true);
                stack.push(chosen.getValue());
            }
        }
    }

    public Cell getAt(int x, int y)
    {
        return cells(y)(x);
    }

    public int getHeight()
    {
        return cells.length;
    }

    public int getWidth()
    {
        return cells(0).length;
    }

    public Map<AdjacentDirection, Cell> getNeighbors(int x, int y)
    {
        var map = new HashMap<AdjacentDirection, Cell>();
        for (var dir : AdjacentDirection.VALUES)
        {
            var cell = getNeighbor(dir, x, y);
            if (cell != null)
                map.put(dir, cell);
        }
        return map;
    }

    public Cell getNeighbor(AdjacentDirection dir, int x, int y)
    {
        switch (dir)
        {
            case TOP:
            {
                var ind = y + 1;
                if (ind >= cells.length)
                    return null;
                return cells(ind)(x);
            }
            case BOTTOM:
            {
                var ind = y - 1;
                if (ind < 0)
                    return null;
                return cells(ind)(x);
            }
            case RIGHT:
            {
                var ind = x + 1;
                if (ind >= cells(y).length)
                    return null;
                return cells(y)(ind);
            }
            case LEFT:
            {
                var ind = x - 1;
                if (ind < 0)
                    return null;
                return cells(y)(ind);
            }

            default:
                throw new IllegalArgumentException("Invalid direction?");
        }
    }
}

The following class is a swing JPanel, that helps with visualization of CellMap. I am not explicitly asking for anyone to review this.

CellMapPanel.java:

import javax.swing.*;
import java.awt.*;

public class CellMapPanel extends JPanel
{
    private final CellMap map;
    private final int cellSize;

    public CellMapPanel(CellMap map, int cellSize)
    {
        this.map = map;
        this.cellSize = cellSize;
    }

    @Override
    protected void paintComponent(Graphics g)
    {
        super.paintComponent(g);
        g.setColor(Color.BLACK);
        g.fillRect(0, 0, getWidth(), getHeight());

        g.setColor(Color.WHITE);
        for (var x = 0; x < map.getWidth(); x++)
        {
            for (var y = 0; y < map.getHeight(); y++)
            {
                var visualX = x;
                // Graphics in Java have (0, 0) in the top-left -- we need it in the bottom-left.
                var visualY = map.getHeight() - y - 1;

                var cell = map.getAt(x, y);
                if (cell.getWall(AdjacentDirection.LEFT).get())
                    g.drawLine(visualX * cellSize, visualY * cellSize, visualX * cellSize, visualY * cellSize + cellSize);
                if (cell.getWall(AdjacentDirection.TOP).get())
                    g.drawLine(visualX * cellSize, visualY * cellSize, visualX * cellSize + cellSize, visualY * cellSize);
                if (cell.getWall(AdjacentDirection.RIGHT).get())
                    g.drawLine(visualX * cellSize + cellSize, visualY * cellSize, visualX * cellSize + cellSize, visualY * cellSize + cellSize);
                if (cell.getWall(AdjacentDirection.BOTTOM).get())
                    g.drawLine(visualX * cellSize, visualY * cellSize + cellSize, visualX * cellSize + cellSize, visualY * cellSize + cellSize);
            }
        }
    }
}
```