1
\$\begingroup\$

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);
            }
        }
    }
}
```
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to CodeReview@SE. Every question here is required to be about (coding) an implementation, and I can tell Java from the "required" language tag: leave both from the title and tell what to find, and possibly where to search. \$\endgroup\$ – greybeard Apr 1 at 5:09
0
\$\begingroup\$

Review

  • private final int x; and private final int y; part in Cell.java, do you consider to use Point2D class?

  • In CellMap class, do you expect the value null is returned if the location passing into public Cell getNeighbor(AdjacentDirection dir, int x, int y) method is out of boundary? Or IllegalStateException can be used here?

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I don't believe the dependency on the java.desktop module is worth for the single Point2D class. Though you are correct that an out of bounds index into the cell map is an exceptional state. \$\endgroup\$ – DrUnderscore Apr 2 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.