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