Implementing a randomly generated maze using Prim's Algorithm
The description in the Wikipedia article truly deserves improvement.
The first confusing part of the article is, that the description of the randomized Prim's algorithm does not elaborate on the assumed data structure used by the algorithm. Thus, phrases like "opposite cell" become confusing.
Basically there are 2 main approaches "maze generator programmers" can opt for:
- Cells have walls or passages to their 4 neighbors. The information about walls/passages is stored and manipulated.
- Cells can either be Blocked (walls) or Passages, without storing any extra connectivity information.
Depending on which model (1) or (2) the reader has in mind when reading the description of the algorithm, they either understand or do not understand.
Me, personally I prefer to use cells as either walls or passages, rather than fiddling with dedicated passage/wall information.
Then, the "frontier" patches have a distance of 2 (rather than 1) from a passage. A random frontier patch from the list of frontier patches is selected and connected to a random neighboring passage (at distance 2) by means of also making the cell between frontier patch and neighboring passage a passage.
Here my F# implementation of how it looks like:
let rng = new System.Random()
type Cell = | Blocked | Passage
type Maze =
{
Grid : Cell[,]
Width : int
Height : int
}
let initMaze dx dy =
let six,siy = (1,1)
let eix,eiy = (dx-2,dy-2)
{
Grid = Array2D.init dx dy
(fun _ _ -> Blocked
)
Width = dx
Height = dy
}
let generate (maze : Maze) : Maze =
let isLegal (x,y) =
x>0 && x < maze.Width-1 && y>0 && y<maze.Height-1
let frontier (x,y) =
[x-2,y;x+2,y; x,y-2; x, y+2]
|> List.filter (fun (x,y) -> isLegal (x,y) && maze.Grid.[x,y] = Blocked)
let neighbor (x,y) =
[x-2,y;x+2,y; x,y-2; x, y+2]
|> List.filter (fun (x,y) -> isLegal (x,y) && maze.Grid.[x,y] = Passage)
let randomCell () = rng.Next(maze.Width),rng.Next(maze.Height)
let removeAt index (lst : (int * int) list) : (int * int) list =
let x,y = lst.[index]
lst |> List.filter (fun (a,b) -> not (a = x && b = y) )
let between p1 p2 =
let x =
match (fst p2 - fst p1) with
| 0 -> fst p1
| 2 -> 1 + fst p1
| -2 -> -1 + fst p1
| _ -> failwith "Invalid arguments for between()"
let y =
match (snd p2 - snd p1) with
| 0 -> snd p1
| 2 -> 1 + snd p1
| -2 -> -1 + snd p1
| _ -> failwith "Invalid arguments for between()"
(x,y)
let connectRandomNeighbor (x,y) =
let neighbors = neighbor (x,y)
let pickedIndex = rng.Next(neighbors.Length)
let xn,yn = neighbors.[pickedIndex]
let xb,yb = between (x,y) (xn,yn)
maze.Grid.[xb,yb] <- Passage
()
let rec extend front =
match front with
| [] -> ()
| _ ->
let pickedIndex = rng.Next(front.Length)
let xf,yf = front.[pickedIndex]
maze.Grid.[xf,yf] <- Passage
connectRandomNeighbor (xf,yf)
extend ((front |> removeAt pickedIndex) @ frontier (xf,yf))
let x,y = randomCell()
maze.Grid.[x,y] <- Passage
extend (frontier (x,y))
maze
let show maze =
printfn "%A" maze
maze.Grid |> Array2D.iteri
(fun y x cell ->
if x = 0 && y > 0 then
printfn "|"
let c =
match cell with
| Blocked -> "X"
| Passage -> " "
printf "%s" c
)
maze
let render maze =
let cellWidth = 10;
let cellHeight = 10;
let pw = maze.Width * cellWidth
let ph = maze.Height * cellHeight
let passageBrush = System.Drawing.Brushes.White
let wallBrush = System.Drawing.Brushes.Black
let bmp = new System.Drawing.Bitmap(pw,ph)
let g = System.Drawing.Graphics.FromImage(bmp);
maze.Grid
|> Array2D.iteri
(fun y x cell ->
let brush =
match cell with
| Passage -> passageBrush
| Blocked -> wallBrush
g.FillRectangle(brush,x*cellWidth,y*cellHeight,cellWidth,cellHeight)
)
g.Flush()
bmp.Save("""E:\temp\maze.bmp""")
initMaze 50 50 |> generate |> show |> render
A resulting maze then can look like this:
Here an attempt to describe my solution in wikipedia "algorithm" style:
- A Grid consists of a 2 dimensional array of cells.
- A Cell has 2 states: Blocked or Passage.
- Start with a Grid full of Cells in state Blocked.
- Pick a random Cell, set it to state Passage and Compute its frontier cells. A frontier cell of a Cell is a cell with distance 2 in state Blocked and within the grid.
- While the list of frontier cells is not empty:
- Pick a random frontier cell from the list of frontier cells.
- Let neighbors(frontierCell) = All cells in distance 2 in state Passage. Pick a random neighbor and connect the frontier cell with the neighbor by setting the cell in-between to state Passage. Compute the frontier cells of the chosen frontier cell and add them to the frontier list. Remove the chosen frontier cell from the list of frontier cells.
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:
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓ ▓▓▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓ ▓ ▓ ▓▓▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓▓▓▓▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓ ▓ ▓▓▓ ▓ ▓ ▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓ ▓▓▓ ▓ ▓ ▓▓▓ ▓▓
▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓▓▓ ▓ ▓▓▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓▓▓▓ ▓▓
▓ ▓ ▓▓
▓▓▓ ▓ ▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
Try weighting the walls with uniquely random weights at the very beginning of the procedure. That list of weights will never change. When you choose your next wall from the list of available walls, choose the wall with minimal weight.