Implementing a randomly generated maze using Prim's Algorithm

Question

I am trying to implement a randomly generated maze using Prim's algorithm.

I want my maze to look like this:

however the mazes that I am generating from my program look like this:

I'm currently stuck on correctly implementing the steps highlighted in bold:

1. Start with a grid full of walls.
2. Pick a cell, mark it as part of the maze. Add the walls of the cell to the wall list.
3. While there are walls in the list:
   • **1. Pick a random wall from the list. If the cell on the opposite side isn't in the maze yet:
     • 1. Make the wall a passage and mark the cell on the opposite side as part of the maze.**
     • 2. Add the neighboring walls of the cell to the wall list.
   • 2. Remove the wall from the list.

from this article on maze generation.

How do I determine whether or not a cell is a valid candidate for the wall list? I would like to change my algorithm so that it produces a correct maze. Any ideas that would help me solve my problem would be appreciated.

Answer 1

A simple Java implementation of Prim's algorithm:

import java.util.LinkedList;
import java.util.Random;

public class Maze {
    public static final char PASSAGE_CHAR = ' ';
    public static final char WALL_CHAR = '▓';
    public static final boolean WALL    = false;
    public static final boolean PASSAGE = !WALL;

    private final boolean map[][];
    private final int width;
    private final int height;

    public Maze( final int width, final int height ){
        this.width = width;
        this.height = height;
        this.map = new boolean[width][height];

        final LinkedList<int[]> frontiers = new LinkedList<>();
        final Random random = new Random();
        int x = random.nextInt(width);
        int y = random.nextInt(height);
        frontiers.add(new int[]{x,y,x,y});

        while ( !frontiers.isEmpty() ){
            final int[] f = frontiers.remove( random.nextInt( frontiers.size() ) );
            x = f[2];
            y = f[3];
            if ( map[x][y] == WALL )
            {
                map[f[0]][f[1]] = map[x][y] = PASSAGE;
                if ( x >= 2 && map[x-2][y] == WALL )
                    frontiers.add( new int[]{x-1,y,x-2,y} );
                if ( y >= 2 && map[x][y-2] == WALL )
                    frontiers.add( new int[]{x,y-1,x,y-2} );
                if ( x < width-2 && map[x+2][y] == WALL )
                    frontiers.add( new int[]{x+1,y,x+2,y} );
                if ( y < height-2 && map[x][y+2] == WALL )
                    frontiers.add( new int[]{x,y+1,x,y+2} );
            }
        }
    }

    @Override
    public String toString(){
        final StringBuffer b = new StringBuffer();
        for ( int x = 0; x < width + 2; x++ )
            b.append( WALL_CHAR );
        b.append( '\n' );
        for ( int y = 0; y < height; y++ ){
            b.append( WALL_CHAR );
            for ( int x = 0; x < width; x++ )
                b.append( map[x][y] == WALL ? WALL_CHAR : PASSAGE_CHAR );
            b.append( WALL_CHAR );
            b.append( '\n' );
        }
        for ( int x = 0; x < width + 2; x++ )
            b.append( WALL_CHAR );
        b.append( '\n' );
        return b.toString();
    }
}

A sample output of new Maze(20,20).toString() is:

▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓   ▓     ▓       ▓ ▓▓
▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓ ▓▓▓ ▓▓
▓     ▓ ▓ ▓ ▓   ▓ ▓ ▓▓
▓ ▓▓▓▓▓ ▓ ▓ ▓▓▓ ▓ ▓ ▓▓
▓   ▓ ▓ ▓   ▓       ▓▓
▓ ▓ ▓ ▓ ▓ ▓▓▓▓▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓   ▓ ▓   ▓ ▓▓
▓ ▓▓▓ ▓ ▓▓▓ ▓ ▓ ▓▓▓▓▓▓
▓   ▓     ▓ ▓ ▓   ▓ ▓▓
▓ ▓▓▓▓▓ ▓▓▓ ▓ ▓ ▓▓▓ ▓▓
▓   ▓   ▓           ▓▓
▓ ▓ ▓ ▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓▓
▓ ▓   ▓   ▓       ▓ ▓▓
▓ ▓▓▓▓▓▓▓ ▓ ▓▓▓▓▓ ▓ ▓▓
▓ ▓     ▓   ▓   ▓ ▓ ▓▓
▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓▓▓▓ ▓▓
▓   ▓               ▓▓
▓▓▓ ▓ ▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓
▓   ▓ ▓   ▓     ▓ ▓ ▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓

Answer 2

The following is a commented Java implementation base on the accepted answer:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

/**
 * Generate a maze using Prime's algorithm
 * Based on: https://stackoverflow.com/a/29758926/3992939
 *
 * @author c0der
 * 25 Jun 2020
 *
 */
public class PrimeMazeGenerator implements Runnable {

    private static final int[][] DIRECTIONS = { //distance of 2 to each side
            { 0 ,-2}, // north
            { 0 , 2}, // south
            { 2 , 0}, // east
            {-2 , 0}, // west
    };

    private long delay = 0;
    private final CellModel[][] cells;
    private final Random random;

    public PrimeMazeGenerator(CellModel[][] cells) {
        this.cells = cells;
        random = new Random();
    }

    @Override
    public void run() {
        primMazeGeneration();
    }

    public void execute() {
        new Thread(this).start();
    }

    void primMazeGeneration() {

        //Start with a grid full of cellModelViews in state wall (not a path).
        for(int i = 0; i < cells.length; i++){
            for(int j = 0; j < cells[0].length ; j++){
                cells[i][j].setWall(true);
            }
        }

        //Pick a random cell
        int x = random.nextInt(cells.length);
        int y = random.nextInt(cells[0].length);

        cells[x][y].setWall(false); //set cell to path
        //Compute cell frontier and add it to a frontier collection
        Set<CellModel> frontierCells = new HashSet<>(frontierCellsOf(cells[x][y]));

        while (!frontierCells.isEmpty()){

            //Pick a random cell from the frontier collection
            CellModel frontierCell = frontierCells.stream().skip(random.nextInt(frontierCells.size())).findFirst().orElse(null);

            //Get its neighbors: cells in distance 2 in state path (no wall)
            List<CellModel> frontierNeighbors =  passageCellsOf(frontierCell);

            if(!frontierNeighbors.isEmpty()) {
                //Pick a random neighbor
                CellModel neighbor = frontierNeighbors.get(random.nextInt(frontierNeighbors.size()));
                //Connect the frontier cell with the neighbor
                connect(frontierCell, neighbor);
            }

            //Compute the frontier cells of the chosen frontier cell and add them to the frontier collection
            frontierCells.addAll(frontierCellsOf(frontierCell));
            //Remove frontier cell from the frontier collection
            frontierCells.remove( frontierCell);
            try {
                Thread.sleep(delay);
            } catch (InterruptedException ex) { ex.printStackTrace();}
        }
    }

    //Frontier cells: wall cells in a distance of 2
    private List<CellModel> frontierCellsOf(CellModel cell) {

        return cellsAround(cell, true);
    }

    //Frontier cells: passage (no wall) cells in a distance of 2
    private List<CellModel> passageCellsOf(CellModel cell) {

        return cellsAround(cell, false);
    }

    private List<CellModel> cellsAround(CellModel cell, boolean isWall) {

        List<CellModel> frontier = new ArrayList<>();
        for(int[] direction : DIRECTIONS){
            int newRow = cell.getRow() + direction[0];
            int newCol = cell.getColumn() + direction[1];
            if(isValidPosition(newRow, newCol) && cells[newRow][newCol].isWall() == isWall){
                frontier.add(cells[newRow][newCol]);
            }
        }

        return frontier;
    }

    //connects cells which are distance 2 apart
    private void connect( CellModel frontierCellModelView, CellModel neighbour) {

        int inBetweenRow = (neighbour.getRow() + frontierCellModelView.getRow())/2;
        int inBetweenCol = (neighbour.getColumn() + frontierCellModelView.getColumn())/2;
        frontierCellModelView.setWall(false);
        cells[inBetweenRow][inBetweenCol].setWall(false);
        neighbour.setWall(false);
    }

    private boolean isValidPosition(int row, int col) {
        return row >= 0 && row < cells.length
                    && col >= 0 && col < cells[0].length;
    }

    public PrimeMazeGenerator setDelay(long delay) {
        this.delay = delay;
        return this;
    }
}

CellModel.java:

/**
 * Maze cell representation
 *
 * @author c0der
 * 25 Jun 2020
 *
 */
public class CellModel{

    private final int row, column;
    private boolean isWall;
    //support to fire property change events
    private PropertyChangeSupport pcs;

    public CellModel(int row, int column)  {
       this(row, column, false);
    }

    public CellModel(int row, int column, boolean isWall) {
        this.row = row;
        this.column = column;
        this.isWall = isWall;
    }

    @Override
    public boolean equals(Object obj) {
        if(!(obj instanceof CellModel)) return false;
        CellModel other = (CellModel)obj;
        return row == other.getRow() && column == other.getColumn();
    }

    public void setPropertChangeSupport(PropertyChangeSupport pcs) {
        this.pcs = pcs;
    }

    private void firePropertyChange(String name, Object oldValue, Object newValue) {
        if(pcs != null) {
            pcs.firePropertyChange(name, oldValue, newValue);
        }
    }

    /**
    * Get {@link #isWall}
    */
    public boolean isWall() {
        return isWall;
    }

    /**
    * Set {@link #isWall}
    */
    public void setWall(boolean isWall) {
        Object old = this.isWall;
        this.isWall = isWall;
        firePropertyChange("Wall", old, isWall);
    }

    /**
    * Get {@link #row}
    */
    public int getRow() {
        return row;
    }

    /**
    * Get {@link #column}
    */
    public int getColumn() {
        return column;
    }

    @Override
    public String toString() {
        return  "["+ (isWall ? "Wall " : "Path " ) +  row + "-" + column + "]";
    }

    /* (non-Javadoc)
     * @see java.lang.Object#hashCode()
     */
    @Override
    public int hashCode() {
        return 17*row + 31*column;
    }
}

CellModel[][] cells can be obtained from MazeModel:

/**
 * Maze representation
 *
 * @author c0der
 * 25 Jun 2020
 *
 */
public class MazeModel {

    /**
     * Collection to represent an entire maze
     */
    private final CellModel[][] cellModels;

    public MazeModel(int rows, int columns) {

        cellModels = new CellModel[rows][columns];
        for(int row=0; row <cellModels.length; row++) {
            for(int col=0; col<cellModels[row].length; col++) {
                CellModel cellModel = new CellModel(row, col);
                cellModels[row][col] = cellModel;
            }
        }
    }

    /**
    * Get {@link #cellModels}
    */
    public CellModel[][] getCellModels() {
        return cellModels;
    }
}

A complete runnable code including Swing as well as JavaFx gui is available on this repository.

---