# 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.

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

{
walls.put(dir, wall);
}

{
return walls.get(dir);
}

public int getX()
{
return x;
}

public int getY()
{
return y;
}

@Override
public String toString()
{
return new StringJoiner(", ", Cell.class.getSimpleName() + "(", ")")
.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)
else

// The wall beneath us is the top wall of the cell beneath us.
if (bottomNeighborIndex >= 0)
else

}
}
}

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
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>();
{
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);
$$```$$