algorithm - 使用 Prim 算法实现随机生成的迷宫

Question

我正在尝试使用 Prim 算法实现一个随机生成的迷宫。

我希望我的迷宫看起来像这样:

但是我从我的程序中生成的迷宫看起来像这样:

我目前坚持正确执行以粗体突出显示的步骤:

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.

来自 this article on maze generation.

如何确定一个单元格是否是墙列表的有效候选者？我想更改我的算法以生成正确的迷宫。任何可以帮助我解决问题的想法都将不胜感激。

Answer 1

维基百科文章中的描述确实值得改进。

文章的第一个令人困惑的部分是，随机 Prim 算法的描述没有详细说明该算法使用的假定数据结构。因此，像“相反的单元格”这样的短语变得令人困惑。

“迷宫生成器程序员”基本上可以选择两种主要方法:

1. 细胞有墙壁或 channel 通往其 4 个邻居。有关墙壁/ channel 的信息被存储和操纵。
2. 细胞可以被阻挡(墙壁)或 channel ，而不存储任何额外的连接信息。

根据读者在阅读算法描述时想到的模型 (1) 或 (2)，他们要么理解要么不理解。

就我个人而言，我更喜欢将单元格用作墙或 channel ，而不是摆弄专用的 channel /墙信息。

然后，“边界”补丁与段落的距离为 2(而不是 1)。从边界 block 列表中选择一个随机边界 block 并将其连接到随机相邻 channel (距离为 2)，方法是使边界 block 和相邻 channel 之间的单元格也成为 channel 。

这是我的 F# 实现的样子:

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

由此产生的迷宫看起来像这样:

这里尝试用维基百科“算法”风格来描述我的解决方案:

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.