想和代码谈谈

玮仔的个人博客

【迷宫中的算法实践】迷宫生成算法——Prim算法

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 4k 阅读时长 ≈ 4 分钟

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

——来自百度百科

当我们将Prim算法用于迷宫生成时，情况有些不同，维基百科中给出了随机Prim迷宫生成算法(Randomized Prim’s algorithm)的解释及实现过程：

我们将算法实现部分翻译成中文

  1. 让迷宫全都是墙.。
  2. 选一个格，作为迷宫的通路，然后把它的邻墙放入列表.。
  3. 当列表里还有墙时:
    1). 从列表里随机选一个墙，如果它对面的格子不是迷宫的通路:
    2). 把墙打通，让对面的格子成为迷宫的通路.。
    把那个格子的邻墙加入列表。
  4. 如果对面的格子已经是通路了，那就从列表里移除这面墙。

简单研究算法实现过程我们可以发现，Prim算法就是不断地从所有可以是通路的位置中随意选一个挖洞，直到没有可能为通路的位置。

整个实现过程还是相当于随意为路线附权值的Prim算法。

下面我们来做C#下的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/// <summary>
/// 普利姆迷宫生成法
/// </summary>
/// <param name="startX">起始点X坐标</param>
/// <param name="startY">起始点Y坐标</param>
/// <param name="widthLimit">迷宫宽度</param>
/// <param name="heightLimit">迷宫高度</param>
/// <param name="haveBorder">迷宫是否含有墙</param>
private int[,] Prim(int startX, int startY, int widthLimit, int heightLimit,bool haveBorder)
{
    //block:不可通行    unBlock:可通行
    const int block = 0,unBlock = 1;
    var r=new Random();
    //迷宫尺寸合法化
    if (widthLimit < 1)
        widthLimit = 1;
    if (heightLimit < 1)
        heightLimit = 1;
    //迷宫起点合法化
    if (startX < 0 || startX >= widthLimit)
        startX = r.Next(0, widthLimit);
    if (startY < 0 || startY >= heightLimit)
        startY = r.Next(0, heightLimit);
    //减去边框所占的格子
    if (!haveBorder)
    {
        widthLimit--;
        heightLimit--;
    }
    //迷宫尺寸换算成带墙尺寸
    widthLimit *= 2;
    heightLimit *= 2;
    //迷宫起点换算成带墙起点
    startX *= 2;
    startY *= 2;
    if (haveBorder)
    {
        startX++;
        startY++;
    }
    //产生空白迷宫
    var mazeMap = new int[widthLimit + 1, heightLimit + 1];
    for (int x = 0; x <= widthLimit; x++)
    {
        //mazeMap.Add(new BitArray(heightLimit + 1));
        for (int y = 0; y <= heightLimit; y++)
        {
            mazeMap[x, y] = block;
        }
    }

    //邻墙列表
    var blockPos = new List<int>();
    //将起点作为目标格
    int targetX = startX, targetY = startY;
    //将起点标记为通路
    mazeMap[targetX, targetY] = unBlock;

    //记录邻墙
    if (targetY > 1)
    {
        blockPos.AddRange(new int[] { targetX, targetY - 1, 0 });
    }
    if (targetX < widthLimit)
    {
        blockPos.AddRange(new int[] { targetX + 1, targetY, 1 });
    }
    if (targetY < heightLimit)
    {
        blockPos.AddRange(new int[] { targetX, targetY + 1, 2 });
    }
    if (targetX > 1)
    {
        blockPos.AddRange(new int[] { targetX - 1, targetY, 3 });
    }
    while (blockPos.Count > 0)
    {
        //随机选一堵墙
        var blockIndex = r.Next(0, blockPos.Count / 3) * 3;
        //找到墙对面的墙
        if (blockPos[blockIndex + 2] == 0)
        {
            targetX = blockPos[blockIndex];
            targetY = blockPos[blockIndex + 1] - 1;
        }
        else if (blockPos[blockIndex + 2] == 1)
        {
            targetX = blockPos[blockIndex] + 1;
            targetY = blockPos[blockIndex + 1];
        }
        else if (blockPos[blockIndex + 2] == 2)
        {
            targetX = blockPos[blockIndex];
            targetY = blockPos[blockIndex + 1] + 1;
        }
        else if (blockPos[blockIndex + 2] == 3)
        {
            targetX = blockPos[blockIndex] - 1;
            targetY = blockPos[blockIndex + 1];
        }
        //如果目标格未连通
        if (mazeMap[targetX, targetY] == block)
        {
            //联通目标格
            mazeMap[blockPos[blockIndex], blockPos[blockIndex + 1]] = unBlock;
            mazeMap[targetX, targetY] = unBlock;
            //添加目标格相邻格
            if (targetY > 1 && mazeMap[targetX, targetY - 1] == block && mazeMap[targetX, targetY - 2] == block)
            {
                blockPos.AddRange(new int[] { targetX, targetY - 1, 0 });
            }
            if (targetX < widthLimit && mazeMap[targetX + 1, targetY] == block && mazeMap[targetX + 2, targetY] == block)
            {
                blockPos.AddRange(new int[] { targetX + 1, targetY, 1 });
            }
            if (targetY < heightLimit && mazeMap[targetX, targetY + 1] == block && mazeMap[targetX, targetY + 2] == block)
            {
                blockPos.AddRange(new int[] { targetX, targetY + 1, 2 });
            }
            if (targetX > 1 && mazeMap[targetX - 1, targetY] == block && mazeMap[targetX - 1, targetY] == block)
            {
                blockPos.AddRange(new int[] { targetX - 1, targetY, 3 });
            }
        }
        blockPos.RemoveRange(blockIndex, 3);
    }
    return mazeMap;
}

欢迎关注我的其它发布渠道