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:
![enter image description here]()
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.
