猴子都能看懂的迷宫生成算法

犯困嫌疑人 · 发表于 2024-7-19 13:59:24

本帖最后由犯困嫌疑人于 2024-7-19 14:00 编辑

prim算法和迷宫生成
1.迷宫生成和最小生成树的联系通过如下方法将迷宫生成问题和求最小生成树建立联系：

把迷宫看做这个样子，左边是用类似数组表示的迷宫，把墙简化后比较容易看

这是迷宫初始化的样子，所有墙壁都是封死的，路径格处于独立状态。如果把迷宫看作带权图G，则点集V即4为简化图中显示的9个路径格，边集E则是任意相邻两路径格间连线的集合，可以看作所有路径权值都相等。
设迷宫入口为左上角的路径格，出口为右下角的路径格，则生成一个迷宫的实质就是找G的一个最小生成树T，T包含所有路径格，不成环，且其中任意两个路径格连通。（事实上当不必连通所有格，只要连通了起点和终点，也可以算迷宫生成完毕，只是这样的迷宫不完整）
把起点加入空集A，则森林Ga中包含9棵根节点状态的树，接下来要不断在E中找安全边，使Ga中的根节点状态的树元素都加入到集合A中，直到Ga中只剩A一个元素（或者Ga中某树包含起点和终点）为止。

2.prim迷宫生成算法思想初始化迷宫为墙壁全部封死状态（如上图）
把起点加入集合A
找集合A中点周围的墙（非边界墙），选择其中任意一个判断墙两边的两个路径点是否都属于集合A，若不是则打破此墙，使新路径点加入集合A
重复，直到A中包含所有路径点为止

具体落实到编程上（注意，以下流程中要把墙的厚度看做 0，即使用上图右侧的那种视角）
让迷宫全是墙.
选一个单元格作为迷宫的通路，然后把它的邻墙放入列表
当列表里还有墙时
从列表里随机选一个墙，如果这面墙分隔的两个单元格只有一个单元格被访问过，那就从列表里移除这面墙，即把墙打通，让未访问的单元格成为迷宫的通路，再把这个格子的墙加入列表
如果墙两面的单元格都已经被访问过，那就从列表里移除这面墙
列表里已经没有墙了，结束

MW实现的过程
先填充一个全是都是墙的状态

这里使用了六边形作为墙。

选择一个点作为起始点位。

这里以正方形标识一个路。而圆柱体表示被选中的墙。

我们选择一个随机的被选中墙，然后将其上下左右都置为待选择点，然后再随机一个待选择点继续进行遍历。

如果这个点满足附近只有方向是有路的，则将其附近的点继续推入待选择点

重复以上操作，
最后选择一个点位作为进入点和出去的点，就可以得到一个迷宫了。

const L = 10;export let step: boolean = true;export const onInsNewWall: Action3<number, number, number> = new Action3();InputUtil.onKeyDown(Keys.O, () => { step = true;})export async function CreateMaze() { let Maze = []; for (let index = 0; index < L; index++) { Maze[index] = new Array(L).fill(0, 0, L); } //最外围设置为路，可以有效的保护里面一层墙体，并防止挖出界 for (let i = 0; i < L; i++) { Maze[0] = 1; Maze[0] = 1; Maze[L - 1] = 1; Maze[L - 1] = 1; } //任取初始值 let posArr: Vector2[] = []; posArr.push(new Vector2(2, 2)) //当墙队列为空时结束循环 while (posArr.length != 0) { //在墙队列中随机取一点 let r = MathUtil.randomInt(0, posArr.length); let x = posArr[r].x; let y = posArr[r].y; await new Promise((resolve) => { const interval = setInterval(() => { if (step) { resolve(0) clearInterval(interval); } }, 100); }); step = false; //判读上下左右四个方向是否为路 let count = 0; for (let i = x - 1; i < x + 2; i++) { for (let j = y - 1; j < y + 2; j++) { if (Math.abs(x - i) + Math.abs(y - j) == 1 && Maze[j] > 0) { ++count; } } } if (count <= 1) { Maze[x][y] = 1; onInsNewWall.call(x, y, 0); //在墙队列中插入新的墙 for (let i = x - 1; i < x + 2; i++) { for (let j = y - 1; j < y + 2; j++) { if (Math.abs(x - i) + Math.abs(y - j) == 1 && Maze[j] == 0) { posArr.push(new Vector2(i, j)); onInsNewWall.call(i, j, 1); } } } } console.log("curWay" + posArr.length); //删除当前墙 posArr.splice(r, 1); onInsNewWall.call(x, y, 2); } //设置迷宫进出口 Maze[2][1] = 1; onInsNewWall.call(2, 1, 0); for (let i = L - 3; i >= 0; i--) { if (Maze[L - 3] == 1) { Maze[L - 2] = 1; onInsNewWall.call(i, L - 2, 0); break; } } return Maze;}