算法：用不相交集类(并查集)实现随机迷宫生成算法，并最终得到能显示迷宫图的HTML文件
程序员文章站
2022-06-22 16:10:40
...
之前我用不相交集类(并查集)辅助实现了克鲁斯卡尔(Kruskal)算法求出图的最小生成树，今天我就用并查集来再实现一个其经典的应用：随机迷宫图的生成
并查集生成迷宫图的原理如下，也是迷宫图算法实现的思路：
- 根据自定义迷宫的宽高，有一系列 宽×高 的矩阵点，从0开始编号
- 刚开始这些矩阵点都是不连通的，对应并查集也是都不相交
- 我们随机找到两个相邻的矩阵点，然后通过并查集的find算法，查看相邻矩阵点是否连通
- 如果该相邻矩阵点对连通，则需要继续寻找不连通的相邻点对
- 如果该相邻矩阵点对不连通，则他们之间的墙就拆掉，然后二者在并查集里面做union操作，表示他们已经连通
- 生成一个迷宫图，需要拆掉矩阵点-1面墙，也就是N个元素，得求N-1次union，才能全部相交
- 算法也就是不停地寻找随机的相邻两位置，并且不连通，就记录下来，拆掉二者中间的墙，求union记录，算法执行矩阵点-1次后即刻终止
- 整理算法的结果，按照HTML格式整理内容，然后IO输出流写出HTML文件，用浏览器打开即可查看生产的迷宫图
接下来就是我用Java实现的不相交集类(并查集)实现随机迷宫生成的算法，算法的思想和精髓都在代码和其间的详细注释中：
import java.io.*;
import java.util.*;
/**
* @author LiYang
* @ClassName DrawMaze
* @Description 迷宫图生成算法
* @date 2019/11/29 15:55
*/
public class DrawMaze {
/**
* 不相交集工具类，按高度来合并
* 实现代码根之前的不相交集类一样
* 这里作为内部类，辅助实现迷宫生成算法
*/
static class DisjointSetUnionByHeight {
//不相交集类(并查集)的元素数组
private int[] elements;
/**
* 不相交集类(并查集)的构造方法，入参元素个数
* @param elementNum 元素个数
*/
public DisjointSetUnionByHeight(int elementNum) {
if (elementNum <= 0) {
throw new IllegalArgumentException("元素个数要大于零");
}
//实例化不相交集类(并查集)的元素数组
this.elements = new int[elementNum];
//初始化元素树的高度都为-1(如果是根，值就是负数，连通元素组成的树
//的高度是多少，则根元素就是负几)
for (int i = 0; i < elements.length; i++) {
this.elements[i] = -1;
}
}
/**
* 查询不相交集类(并查集)的元素个数
* @return 元素个数
*/
public int size() {
return elements.length;
}
/**
* 查询不相交集类(并查集)的某个元素的根元素
* 输入的是下标查，如果两个元素的根元素相同，
* 则这两个元素就是等价的。实际中还会有一个
* 与elements等长的数组，装的是元素的名字，
* elements只是相当于代号，记录连通关系，
* 二者通过下标，来映射真实元素
* @param element 待查询的元素
* @return 该元素的根元素
*/
public int find(int element) {
//如果记录小于0，那就是根元素
if (elements[element] < 0) {
//返回根元素
return element;
//如果记录不小于0，那还不是根，
//是等价森林中的上一个节点
} else {
//递归向上继续寻找根
return find(elements[element]);
}
}
/**
* 将不相交集类(并查集)的两个元素进行连通操作
* 注意，两个元素连通，代表这两个元素所在的子树
* 全部变成一个图中的大的子树。如果这
* 两个元素本来就连通，则不进行连通操作，舍弃该边。
* 注意，这里同样是入参下标，下标映射真实元素
* 此实现类，根据树的高度来决定谁合并到谁上面，
* 矮的树的根节点，会作为大的树的根节点的子节点
* @param element1 元素下标1
* @param element2 元素下标2
*/
public void union(int element1, int element2) {
//找到两个元素的根元素
int root1 = find(element1);
int root2 = find(element2);
//如果两个元素本就连通
if (root1 == root2) {
//不作处理
return;
}
//比高度：如果root1比root2的树要高
if (elements[root1] < elements[root2]) {
//将较矮的root2合并到较高的root1上
elements[root2] = root1;
//比高度：如果root2比root1的树要高
} else if (elements[root2] < elements[root1]) {
//将较矮的root1合并到较高的root2上
elements[root1] = root2;
//比高度：如果root1和root2一样高
} else {
//将root1合并到root2上
elements[root1] = root2;
//root2的高度增加1
root2 --;
}
}
}
/**
* 获取某位置的前后左右四个位置（可能不到四个）
* @param position 需要寻找相邻位置的当前位置
* @param width 迷宫宽
* @param height 迷宫高
* @return 当前位置的相邻位置集合
*/
private static List<Integer> getAdjacentPosition(int position, int width, int height) {
//当前位置上面的位置
int top = position - width;
//当前位置下面的位置
int bottom = position + width;
//当前位置左边的位置
int left = position - 1;
//当前位置右边的位置
int right = position + 1;
//收集有效的相邻位置
List<Integer> adjacentPosition = new ArrayList<>();
//上面的会更小，因此需要为非负数
if (top >= 0) {
adjacentPosition.add(top);
}
//下面的会更大，不能超过最大位置
if (bottom < width * height) {
adjacentPosition.add(bottom);
}
//左边的不能越界到上一行
if ((left + 1) % width != 0) {
adjacentPosition.add(left);
}
//右边的不能越界到下一行
if (right % width != 0) {
adjacentPosition.add(right);
}
//返回当前位置所有的有效相邻位置
return adjacentPosition;
}
/**
* 对迷宫进行拆墙的操作，返回全部需要拆掉的墙
* @param width 迷宫宽
* @param height 迷宫高
* @return 所有需要拆掉的墙，由两个相邻位置决定
*/
private static List<String> breakWall(int width, int height) {
//算出总的位置数
int totalPosition = width * height;
//创建不相交集(并查集)类，作为迷宫生成辅助工具类
DisjointSetUnionByHeight disjointHeight = new DisjointSetUnionByHeight(totalPosition);
//算出需要破坏的墙的数量(n个独立元素连通，需要合并n-1次)
int wallNeedToBreak = width * height - 1;
//记录破坏的墙的信息 pos1-pos2，且pos1 < pos2
List<String> breakWallList = new ArrayList<>();
//随机数类
Random random = new Random();
//一共需要拆掉位置数-1面墙，使得所有位置连通
for (int time = 0; time < wallNeedToBreak; time++) {
//直到遇到一对不连通的相邻位置，然后拆掉了中间的墙，完成一次拆墙
while (true) {
//随机找到一个位置
int randomPosition = random.nextInt(totalPosition - 1);
//获得随机位置的所有相邻位置
List<Integer> adjacentPosition = getAdjacentPosition(randomPosition, width, height);
//随机打乱所有相邻位置
Collections.shuffle(adjacentPosition);
//打乱的相邻位置中，取第一个相邻位置
int anotherPosition = adjacentPosition.get(0);
//并查集重要操作1：查询二者是否已连通，就看二者的根元素是否相等
boolean isConnected = disjointHeight.find(randomPosition) == disjointHeight.find(anotherPosition);
//如果未连通
if (!isConnected) {
//将二者之间的墙打掉(存的是墙的相邻两个位置)
breakWallList.add(Math.min(randomPosition, anotherPosition)
+ "-" + Math.max(randomPosition, anotherPosition));
//并查集重要操作2：设置连通状态，将两个位置求并
disjointHeight.union(randomPosition, anotherPosition);
//结束本次打墙操作
//当然，如果isConnected为true，则代表随机的相邻两位置是连通的
//此时不需要打墙和求并，得重新找两个随机相邻的不连通的顶点，
//直到找到随机相邻的不连通两位置，然后才break掉这个while循环
break;
}
}
}
//返回需要拆的墙，一共需要拆掉位置数-1面墙
return breakWallList;
}
/**
* 初始化未被破坏掉的墙
* @param width 迷宫宽
* @param height 迷宫高
* @return 未被拆墙的原图
*/
private static int[] initWall(int width, int height) {
//算出矩阵的宽高
int matrixWidth = width * 2 + 1;
int matrixHeight = height * 2 + 1;
//初始化矩阵（本算法，用的是一维数组，HTML的需要）
int[] matrix = new int[matrixWidth * matrixHeight];
//将数组全部赋初值1（同样是后面HTML的需要）
Arrays.fill(matrix, 1);
//刚开始的位置
int initStart = width * 2 + 2;
//垂直方向的步长
int verticalStep = (width * 2 + 1) * 2;
//水平方向的步长
int horizontalStep = 2;
//遍历整个初始图，先抠出初始位置
for (int i = 0; i < height; i++) {
//水平位置的开始位置
int start = initStart + i * verticalStep;
//遍历当前行
for (int j = 0; j < width; j++) {
//算出初始空格的位置，1是实体，0是空格
int blank = start + j * horizontalStep;
//初始化空格位置
matrix[blank] = 0;
}
}
//返回已经抠掉初始位置的矩阵
return matrix;
}
/**
* 根据位置号，找到方格号
* @param position 位置号
* @return 方格号，也就是对应matrix的下标
*/
private static int findMatrixByPosition(int position, int width, int height) {
//每行matrix的方格数
int lineNum = width * 2 + 1;
//返回计算好的方格下标
return (position / width * 2 + 1) * lineNum + (position % width) * 2 + 1;
}
/**
* 根据相邻位置对，返回需要拆掉的墙的方格号
* @param positionPair 相邻位置对的字符串格式
* @return 需要拆掉的墙的方格下标
*/
private static int getBreakWallNo(String positionPair, int width, int height) {
//较小位置
int minPosition = Integer.parseInt(positionPair.split("-")[0]);
//较大位置
int maxPosition = Integer.parseInt(positionPair.split("-")[1]);
//较小位置的方格下标
int minMatrix = findMatrixByPosition(minPosition, width, height);
//如果两个位置相差1，则表示是左右相邻
if (maxPosition - minPosition == 1) {
//返回较小位置方格号+1
return minMatrix + 1;
//如果两个位置不相差1，则表示是上下相邻
} else {
//返回较小位置方格号下面的方格下标
return minMatrix + width * 2 + 1;
}
}
/**
* 生成迷宫的一维矩阵数组（1是黑方块，0是白方块，也就是路）
* @param width 迷宫宽
* @param height 迷宫高
* @return 生成迷宫的一维矩阵数组
*/
private static String generateMazeArray(int width, int height) {
//根据宽高，初始化迷宫图矩阵
int[] matrix = initWall(width, height);
//求出随机生成的所有需要拆掉的墙
List<String> breakWall = breakWall(width, height);
//遍历所有需要拆掉的墙
for (String posPair : breakWall) {
//算出需要拆掉的墙的方格号
int breakIndex = getBreakWallNo(posPair, width, height);
//将对应的位置的墙拆掉，变成路
matrix[breakIndex] = 0;
}
//生成左上角入口
matrix[1] = 0;
//生成右下角出口
matrix[matrix.length - 2] = 0;
//返回迷宫一维矩阵数组的字符串（后面作为HTML文件的内容）
return Arrays.toString(matrix);
}
/**
* 生成迷宫图的HTML文件，用浏览器打开则可以看到迷宫
* @param width 迷宫宽度
* @param height 迷宫高度
* @param filePath 生成的迷宫HTML文件的路径
* @throws IOException
*/
private static void generateMazeHTML(int width, int height, String filePath) throws IOException {
//HTML文件的内容的StringBuffer
StringBuffer sbuf = new StringBuffer();
//加入必要的HTML内容
sbuf.append("<!doctype html>\n" +
"<html lang=\"en\">\n" +
"<head>\n" +
" <meta charset=\"UTF-8\">\n" +
" <title>LeeCode生成迷宫图</title>\n" +
"</head>\n" +
"<body>\n" +
" <canvas id=\"canvas1\" width=\"2000\" height=\"2000\"></canvas>\n" +
" <script>\n" +
" var map={\n" +
"\t\t\t\"data\":");
//这里加入生成的迷宫图数组数据
sbuf.append(generateMazeArray(width, height)).append("\n");
//这里加入迷宫矩阵的宽高
sbuf.append(",\"width\":").append(width * 2 + 1).append(",\n");
sbuf.append("\"height\":").append(height * 2 + 1).append("}\n");
//继续加入必要的HTML内容
sbuf.append(" var canvas = document.getElementById(\"canvas1\");\n" +
" var ctx = canvas.getContext(\"2d\");\n" +
" var W = 10;var H = 10;var l = 0;var t = 0;\n" +
" for (var i=0; i<map.data.length; i++){ \n" +
" l = i%map.width*W;\n" +
" if (i%map.width==0&&i!=0){\n" +
" t+=H;\n" +
" }\n" +
" if (map.data[i]>0){\n" +
" ctx.fillRect(l, t, W, H);\n" +
" } \n" +
" }\n" +
" </script>\n" +
"</body>\n" +
"</html>");
//HTML文件类
File file = new File(filePath);
//如果HTML文件不存在，则创建新文件
if (!file.exists()) {
file.createNewFile();
}
//生成迷宫图HTML文件的IO输出流类
FileWriter fileWriter = new FileWriter(file);
BufferedWriter bufferedWriter = new BufferedWriter(fileWriter);
//将上面StringBuffer的HTML内容写入HTML文件
bufferedWriter.write(sbuf.toString());
//冲完缓冲区
bufferedWriter.flush();
//关闭输出流
bufferedWriter.close();
fileWriter.close();
//给出迷宫已生成的提示信息
System.out.println("迷宫已生成！");
}
/**
* 运行迷宫随机生成算法，在桌面生成自定义宽高的HTML迷宫文件
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
//自定义迷宫宽
int width = 24;
//自定义迷宫高
int height = 24;
//最终生成的迷宫文件的路径
String filePath = "C:\\Users\\liyang\\Desktop\\maze_ " + System.currentTimeMillis() + ".html";
//运行迷宫随机生成算法，在桌面生成HTML迷宫文件
generateMazeHTML(width, height, filePath);
}
}
大家可以在main方法中自定义迷宫的宽高和HTML文件的输出路径。我这里是迷宫宽高都为24，然后输出路径是桌面，文件名是 “maze_” 再加上当前时间戳。运行main方法后，控制台输出 “迷宫已生成”，代表迷宫生成代码运行成功。在桌面找到迷宫的HTML文件，在浏览器里面打开后，看到了生成的迷宫图，如下所示：
大家有兴趣可以走一下这个迷宫！这个难度有点低，我们把width改为60，height改为40，再运行main方法，再生成一个更大更难的迷宫：
怎么样，是不是有一种眼花缭乱的感觉？是不是很好玩？赶紧复制上面的随机迷宫生成的算法代码，到你自己的IDE里面粘贴改参数运行吧！这个周末我们就走迷宫玩吧！O(∩_∩)O哈哈~
上一篇： SIMD补充 指令集架构类型 指令集介绍
下一篇： 不相交集