生成迷宫的常见算法有递归回溯、递归分治等等；生成树算法可以用来生成完美迷宫，即任何两个可达点之间只有一条通路；本文采用Kruskal最小生成树算法生成一个完美迷宫

算法介绍

Kruskal 算法

生成树：对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树；生成树必须符合两个条件：1）包含连通图中所有的顶点；2）任意两顶点之间有且仅有一条通路
最小生成树：无向连通图边权和最小的生成树
可见生成树的特点和完美迷宫非常契合（可达点之间有且仅有一条通路），所以生成树算法都可以用来生成迷宫
Kruskal算法：一种常见的最小生成树算法，该算法维护一堆集合，查询两个元素（节点）是否属于同一集合，合并两个集合，直到形成一棵树

#### Kruskal 算法描述 ####
1. 输入：一个加权连通图，其中顶点集合为V，边集合为E
2. 初始化：E'为新的边集，初始为空
3. 排序E，依次取E中最小边，若两边节点不属于同一集合，则合并节点，将边加入E'；否则忽略
4. 重复 步骤3 知道E'中边数量达到n-1(节点总数为n)，则生成树完成
5. 使用E'描述最小生成树

并查集

并查集：一种属性数据结构，支持两种操作：1）确定某个元素处于哪个子集；2）将两个子集合并成一个集合
关于并查集，有个广为流传的形象比喻：几个家族进行宴会（也有说门派的），但是家族普遍长寿，所以人数众多。由于长时间的分离以及年龄的增长，这些人逐渐忘掉了自己的亲人，只记得自己的爸爸是谁了，而最长者（称为「祖先」）的父亲已经去世，他只知道自己是祖先。为了确定自己是哪个家族，他们想出了一个办法，只要问自己的爸爸是不是祖先，一层一层的向上问，直到问到祖先。如果要判断两人是否在同一家族，只要看两人的祖先是不是同一人就可以了
并查集的思想就类似于此，一层层向上查找
路径压缩：很明显，这里存在一个问题：当家族链过长时，一层层向上查找祖先是谁明显非常浪费时间；这里维护了父亲辈、爷爷辈这些跟祖先没有关系的信息，完全可以忽略，只需要记录某人的祖先是谁即可；这样，原本高度很高的树就变成了一颗高度为2的树了
合并操作：合并操作很简单，例如合并A和B，因为并不在意合并后的祖先是fa还是fb，只要有一个即可，所以只需要把其中一个集合挂到另一个几个下面即可；某些情况下，合并时子集节点地数量可能会影响效率，这时候可以考虑按秩合并，即按照A和B的节点数或者树高等因素来选择最后祖先是fa还是fb

''' 参考实现 '''
fa = [0] * MAXN                  # 记录某个人的爸爸是谁，特别规定，祖先的爸爸是他自己

# 不带路径压缩
def find(x):
    if fa[x] == x:               # 如果x是祖先则返回
        return x
    else:
        return find(fa[x])       # 如果不是则x的爸爸问x的爷爷
    
# 带路径压缩
def findEx(x):
    if x != fa[x]:               # x不是自身的父亲，即x不是该集合的代表
        fa[x] = find(fa[x])      # 查找x的祖先直到找到代表,于是顺手路径压缩
    return fa[x]
    
# 合并
def union(x, y):
    x = find(x)
    y = find(y)
    fa[x] = y                    # 把 x 的祖先变成 y 的祖先的儿子

实现迷宫

思路

1. 墙和可达点都占一个地图格
2. 初始化地图为墙和可达点相间隔，任意两个可达点不连通
3. 去除规划路径上的墙，使之成为一个可达点，从而形成一条路径
4. 这里将障碍墙视为无向图的边，因为不需要考虑权重，只需要随机选择即可
5. 运行Kruskal算法需要确认查询可达点是否属于同一个集合，利用并查集优化效率
   参考下图：黑色块为墙，白色块为可达点，路径（红色线）上的墙需要去除成为可达点（在Kruskal算法意为中为选择的生成树的边集）
   

实现

import random


class Maze():
    def init(self, width, height):
        '''初始化'''
        self.wt = width           # 宽度，初始每行拥有可达点数量
        self.ht = height          # 高度，初始每列拥有可达点数量

        self.fa = {}              # 用于并查集
        self.mp = []              # 地图
        for i in range(0, height * 2 + 1):
            self.mp.append([1] * (width * 2 + 1))
        for i in range(1, height * 2, 2):
            for j in range(1, width * 2, 2):
                self.mp[i][j] = 0
                self.fa[(i, j)] = (i, j)

    def show(self):
        '''输出地图（特殊符号受控制台字体影响）'''
        for i in range(0, self.ht * 2 + 1, 1):
            print(''.join('■' if j else '  ' for j in self.mp[i]))

    def gen(self):
        '''生成算法实现'''
        # 统计所有边（障碍）
        wait = []
        for i in range(1, self.ht * 2, 2):
            for j in range(2, self.wt * 2, 2):
                wait.append((i, j))
        for i in range(2, self.ht * 2, 2):
            for j in range(1, self.wt * 2, 2):
                wait.append((i, j))

        while len(wait):
            idx = random.randint(0, len(wait) - 1)
            e = wait.pop(idx)
            p1, p2 = self.arround(e)
            if self.find(p1) != self.find(p2):
                self.union(p1, p2)
                self.mp[e[0]][e[1]] = 0

    def arround(self, e):
        '''取得障碍两边的可达点'''
        if e[0] % 2:
            return (e[0], e[1] - 1), (e[0], e[1] + 1)
        else:
            return (e[0] - 1, e[1]), (e[0] + 1, e[1])

    def find(self, p1):
        '''并查集查找'''
        if p1 != self.fa[p1]:
            self.fa[p1] = self.find(self.fa[p1])
        return self.fa[p1]

    def union(self, p1, p2):
        '''并查集合并'''
        pp1 = self.find(p1)
        pp2 = self.find(p2)
        self.fa[pp1] = pp2

maze = Maze(19, 19)
maze.gen()
maze.show()

生成效果如下图：

参考资料：
生成树 https://oi-wiki.org/graph/mst/
并查集 https://oi-wiki.org/ds/dsu/

• 还没有人评论，欢迎说说您的想法！

相关课程

基于 OpenVINO™ 的 AI 视觉应用基础课

56037 0元 限免

英特尔® OpenVINO™工具套件初级课程

293049 0元 限免

基于 OpenVINO™ 的 AI 视觉应用进阶课

42044 0元 限免