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

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:

1. Cells have walls or passages to their 4 neighbors. The information about walls/passages is stored and manipulated.
2. 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:

1. A Grid consists of a 2 dimensional array of cells.
2. A Cell has 2 states: Blocked or Passage.
3. Start with a Grid full of Cells in state Blocked.
4. 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.
5. While the list of frontier cells is not empty:
   1. Pick a random frontier cell from the list of frontier cells.
   2. 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.