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

Question

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

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

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

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

1. 从充满墙壁的网格开始.
2. 选择一个单元格,将其标记为迷宫的一部分.将单元格的墙添加到墙列表中.
3. 虽然列表中有墙:
   • **1.从列表中选择一个随机墙.如果对面的细胞尚未进入迷宫:
     • 1. 使墙成为通道,并将对面的单元标记为迷宫的一部分.**
     • 2. 将单元格的相邻墙添加到墙列表中.
   • 2. 从列表中删除墙.

从 这篇关于迷宫生成的文章.

如何确定单元格是否是墙列表的有效候选者？我想改变我的算法,以便产生正确的迷宫.任何有助于我解决问题的想法都将不胜感激.

Answer 1

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

本文的第一个令人困惑的部分是,随机化Prim算法的描述没有详细说明算法使用的假设数据结构.因此,像"对立细胞"这样的短语变得令人困惑.

基本上有两种主要方法"迷宫发生器程序员"可以选择:

1. 细胞有4个邻居的墙壁或通道.存储和操纵有关墙/通道的信息.
2. 单元可以是阻塞(墙)或通道,而不存储任何额外的连接信息.

根据读者在阅读算法描述时所考虑的模型(1)或(2),他们要么理解要么不理解.

我,我个人更喜欢使用细胞作为墙壁或通道,而不是摆弄专用的通道/墙壁信息.

然后,"边界"贴片与通道的距离为2(而不是1).选择来自边界斑块列表的随机边界斑块并通过使边界斑块和相邻通道之间的细胞成为通道而连接到随机相邻通道(距离2).

这是我的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. 网格由2维单元格组成.
2. Cell有2种状态:Blocked或Passage.
3. 从状态为Blocked的Grid充满Grid.
4. 选择一个随机单元格,将其设置为状态Passage并计算其边界单元格.Cell的边界单元是具有距离2处于阻塞状态且在网格内的单元.
5. 边界单元格列表不为空:
   1. 从边界单元列表中选择一个随机前沿单元格.
   2. 让邻居(frontierCell)=状态Passage中距离2的所有单元格.选择一个随机邻居并通过将其间的单元格设置为状态Passage来将边界单元与邻居连接.计算所选前沿单元格的边界单元格并将它们添加到前沿列表中.从边界单元列表中删除选定的前沿单元格.

Answer 2

Prim 算法的简单 Java 实现：

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

的示例输出new Maze(20,20).toString()是：

??????????????????????
?   ?     ?       ? ??
? ??? ????????? ??? ??
?     ? ? ? ?   ? ? ??
? ????? ? ? ??? ? ? ??
?   ? ? ?   ?       ??
? ? ? ? ? ??????? ? ??
? ? ? ? ?   ? ?   ? ??
? ??? ? ??? ? ? ??????
?   ?     ? ? ?   ? ??
? ????? ??? ? ? ??? ??
?   ?   ?           ??
? ? ? ? ??? ??????????
? ?   ?   ?       ? ??
? ??????? ? ????? ? ??
? ?     ?   ?   ? ? ??
??? ??? ??? ? ????? ??
?   ?               ??
??? ? ??? ??? ??? ? ??
?   ? ?   ?     ? ? ??
??????????????????????
??????????????????????