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, 2021 at 5:09

2 Answers 2

1
\$\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\$
2
  • 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\$ Apr 2, 2021 at 17:45
  • \$\begingroup\$ @DrUnderscore The java.awt package is already included in the project. The problem with Point2D in this case is that it is a floating point data type. \$\endgroup\$ Dec 28, 2021 at 5:31
1
\$\begingroup\$

[here's code for some traversal], with

  1. my goal for it to be performant,
    The usual caveat: Save that for later
  2. and have code that made complete sense.
    A worthwhile goal.
    One stance I'm trying to make:
    Code the way you think about the problem and the solution.
    Which is harder to discern given nothing but naked code:
    Document your code. In the code.
    (I see the comments in randomDepthFirstXYZ().
     I lament missing documentation of "the external requirement specification".)

Taking the (external to the code) hyperlinked coarse pseudo-code description from en.wikipedia for a specification, I see it followed closely.
Especially in modelling Cells explicitly, and walls.

When "feeling" something is off and changes may be coming up, it is tempting to think the first step was separating what needs to stay the same from what is free to change, if not needing improvement.
In a way, it is:

  • Make sure you have "the machine" check the code performs to specification.

The other side may include specification of interfaces (extraction from an implementation where your development environment supports this). (I introduced a type Wall for tinkering.) For Cell, I get

@SuppressWarnings("serial")
/** Wall between Cells. Starts solid, but can be torn down. */
class Wall extends java.util.concurrent.atomic.AtomicBoolean {
    Wall() { super(true); }
    /** @return stood before */
    boolean tearDown() { return getAndSet(false); }
}

/** a cell in a periodic planar grid */
interface Cell {
    boolean isVisited();
    /** @return previous visited state */
    boolean setVisited(boolean visited);  // "unvisit", too?

    Wall getWall(AdjacentDirection dir);
//  void setWall(AdjacentDirection dir, Wall wall);  construction, only?

    int getX();
    int getY();
}
interface CellInit extends Cell {
    void setWall(AdjacentDirection dir, Wall wall);
}

abstract class CellXY
{
    final int
        x,
        y;
    CellXY(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class CellIDM extends CellXY implements CellInit
{
    // main change:
    private final Map<AdjacentDirection, Wall> 
        walls = new java.util.EnumMap<>(AdjacentDirection.class);
}

: accessors, only.
And, more importantly, modelling Adjacent, Direction and (shareable) "ownership" of walls.

The main use of package java.util.concurrent.atomic is lock-free thread-safe programming on "single" variables.
Seeing no "abcAndXyz()-methods" used, you don't profit from using AtomicReference.
Java's way of handling Objects (referencing rather than embedding) is quite enough for "shared ownership". Now, if there were concurrent inspections&updates to Cell.visited or "the walls", AtomicBoolean.compareAndSet(required, toSet) quite likely was the way to go.

I guess I don't like all the subscripts and conditional statements in the "map" constructor:

    Cell newCell(int x, int y) { return new CellIDM(x, y); }
    
    /** @return a solid Wall */
    Wall newWall() { return new Wall(); }

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

        cells = new Cell[height][];
        Cell lower[] = new Cell[width];
        // fill with one single mock Cell
        Arrays.fill(lower, new CellIDM(-1, -1) {
                @Override
                public Wall getWall(AdjacentDirection dir) {
                    return newWall();  // or theOneAndOnlyOuterWall?
                }
            });

        for (int y = 1 ; y < cells.length ; y++)
        {
            final Cell row[] = cells[y] = new Cell[width];
            Wall wall = newWall();
            for (int x = 0; x < row.length; x++)
            {
                Cell cell = row[x] = newCell(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 wall to our left is the right wall just created.
                cell.setWall(AdjacentDirection.LEFT, wall);

                // The wall beneath us is the top wall of the cell beneath us.
                cell.setWall(AdjacentDirection.BOTTOM, 
                        lower[x].getWall(AdjacentDirection.TOP));
                cell.setWall(AdjacentDirection.TOP, newWall());
                cell.setWall(AdjacentDirection.RIGHT, wall = newWall());
            }
            lower = row;
        }
    }

"Obviously", one could reduce special casing adding dummy rows and columns, not least in getNeighbor(). Exercise in terseness/DRY:

    public Cell getNeighbor(AdjacentDirection dir, int x, int y) {
        switch (dir) {
        case TOP:
            if (cells.length <= ++y)
                return null;
            break;
        case BOTTOM:
            if (--y < 0)
                return null;
            break;
        case RIGHT:
            if (cells[y].length <= ++x)
                return null;
            break;
        case LEFT:
            if (--x < 0)
                return null;
            break;
        default:
            throw new IllegalArgumentException("Invalid direction?");
        }
        return cells[y][x];
    }

Modelling adjacent wall with a "direction map", but leaving adjacent cell up to CellMap is inconsistent. (And yes, I feel having "multiple direction maps" more irritating than two arrays. Probably due to notation - in Python or C++, I'd just keep to [].)
Alternatively, keep walls in arrays, too.
I mused about separate arrays for "vertical and horizontal walls", to keep indexing just using x/y, or using java.util.BitSet[height](/width).
Make Cell implementations inner to CellMap for access.

Don't spend time on guesses what makes a difference regarding performance when you can model&measure. (Don't roll your own microbenchmarking mechanism - use a framework.)
(Do as I say, not as you see me doing:
I guess most time is spent "in" CellMapPanel.paintComponent(). And drawing walls just once is an improvement, just as drawing longer walls (think BitSet.next/previousClear/SetBit()) using a single call to drawLine().
Quite literally: Almost all walls got drawn twice, and only the "outer wall" makes average wall length exceed 2.)

Odds&ends:

  • In getNeighbors(), an optional predicate would be useful to select which neighbours to include
  • I don't see how this algorithm could profit from concurrency. The remaining reason to use AtomicBoolean was that it can be extended, in contrast to Boolean.
\$\endgroup\$
1
  • \$\begingroup\$ (I dislike search without a Found! allowing incomplete traversal.) \$\endgroup\$
    – greybeard
    Dec 29, 2021 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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