Is there an ELI5 explanation on Prim’s algorithm for generating maze in Java?

I am trying to implement a randomly generated maze using Prim’s algorithm in Java.

However, after reading up on Wikipedia and other answers, there’s minimal explanation on how the implementation I found actually works.

For example:

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

What is a simple explanation for what the LinkedList is doing?

Answer

It’s the queue that backs a BFS (Breadth First Search) algorithm.

See A* Search Algorithm for a generally applicable and interesting BFS use case.

Advertisement

Answer