零、为什么要写这篇文章
近期看了一下生成迷宫的算法，有的算法要么生成的迷宫过于复杂，要么太过明显的有一条大通路，权衡之下，Prim算法生成的迷宫比较适中，写这篇文章就是为了分享一下这个算法的思想。当然，所有的迷宫生成算法如果不进行再处理的话，生成的迷宫解决路径往往不止一条，这个不在本篇的的讲解范围内。
一、讲一下Prim算法
普里姆算法（英语：Prim’s algorithm）是图论中的一种贪心算法，可在一个加权连通图中找到其最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·C·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
二、迷宫用Prim算法实现
思想：因为迷宫每条路的权重都一样，所有不存在选择权重大小的问题，只用随机选择下个点即可。
定义：一个存储已访问过节点列表数组visitedList，当前节点currentNode。
具体思维逻辑：
- 生成奇数行奇数列的二维数组，最外层是墙（第一行，最后一行，第一列，最后一列），偶数行都是墙，奇数行奇数列为路，偶数列为墙，所有路状态为未访问。
- 随机选择一个路的点（奇数行奇数列），此路状态改为已访问，标记为
currentNode，放入visitedList。 - 执行循环，当
visitedList长度为0的时候跳出循环到5，否则执行4。 - 判断
currentNode邻近的上下左右是否存在路及路是否访问过（隔一层墙的路）。
4.1 存在未访问过的路：将这些路放入临时列表，再从临时列表中随机取一个，两个路之间的墙变为路，且标记为已访问，将随机取的路标记为currentNode，状态改为已访问，将此路放入visitedList，重复4。
4.2 不存在未访问过的路或不存在路：将currentNode从visitedList中移出，此时当visitedList长度大于0，在visitedList随机选一个路标记为currentNode，执行4，否则到5。 - 生成最终迷宫。
三、动画呈现原理
四、代码实现
class MazeGrid {
x: number;
y: number;
value: number;
isVisited: boolean = false;
constructor({ x, y, value, isVisited = false }: { x: number, y: number, value: number, isVisited?: boolean }) {
this.x = x;
this.y = y;
this.value = value;
this.isVisited = isVisited
}
}
const EMPTY_MAZE_GRID = new MazeGrid({ x: 0, y: 0, value: 0, isVisited: true }); //当四边的路不存在邻近路用这个节点代替
class GenerateMaze {
width: number = 19;
height: number = 19;
constructor(width?: number, height?: number) {
if (width) {
this.width = width;
}
if (height) {
this.height = height;
}
}
getMaze() {
if (this.width % 2 == 0) {
this.width += 1;
}
if (this.height % 2 == 0) {
this.height += 1;
}
const list: MazeGrid[][] = [];
for (let i = 0; i < this.height; i++) {
const row: MazeGrid[] = [];
for (let j = 0; j < this.width; j++) {
if (i % 2 == 0 || j % 2 == 0) {
row.push(new MazeGrid({ x: i, y: j, value: 0 }));
} else {
row.push(new MazeGrid({ x: i, y: j, value: j % 2 }));
}
}
list.push(row);
}
let currentNode: MazeGrid;
let randomRow = 2 * Math.floor(this.height / 2 * Math.random()) + 1;
let randowColumn = 2 * Math.floor(this.width / 2 * Math.random()) + 1;
while (!currentNode) {
if(randomRow > this.height - 1 || randowColumn > this.width - 1) {
randomRow = 2 * Math.floor(this.height / 2 * Math.random()) + 1;
randowColumn = 2 * Math.floor(this.width / 2 * Math.random()) + 1;
continue;
}
currentNode = list[randomRow][randowColumn];
}
let visitedNodeList: MazeGrid[] = [currentNode];
while (visitedNodeList.length > 0) {
const left = currentNode.y - 2 >= 0 ? list[currentNode.x][currentNode.y - 2] : EMPTY_MAZE_GRID;
const right = currentNode.y + 2 < this.width - 1 ? list[currentNode.x][currentNode.y + 2] : EMPTY_MAZE_GRID;
const up = currentNode.x - 2 >= 0 ? list[currentNode.x - 2][currentNode.y] : EMPTY_MAZE_GRID;
const down = currentNode.x + 2 < this.height - 1 ? list[currentNode.x + 2][currentNode.y] : EMPTY_MAZE_GRID;
const neighborNodes: MazeGrid[] = [];
if (!up.isVisited) {
neighborNodes.push(up);
}
if (!down.isVisited) {
neighborNodes.push(down);
}
if (!left.isVisited) {
neighborNodes.push(left);
}
if (!right.isVisited) {
neighborNodes.push(right);
}
if (neighborNodes.length > 0) {
const randowNode: MazeGrid = neighborNodes[Math.floor(Math.random() * neighborNodes.length)];
randowNode.isVisited = true;
visitedNodeList.push(randowNode);
list[(randowNode.x + currentNode.x) / 2][(randowNode.y + currentNode.y) / 2].value = 1;
currentNode = randowNode;
} else {
visitedNodeList = visitedNodeList.filter(node => node != currentNode);
if (visitedNodeList.length === 0) {
break;
} else {
currentNode = visitedNodeList[Math.floor(Math.random() * visitedNodeList.length)];
currentNode.isVisited = true;
visitedNodeList = visitedNodeList.filter(node => node != currentNode);
}
}
}
return list;
}
}五、小提示
用算法生成的迷宫，偶尔会出现一些特别长的单向通路，这种时候可能就需要自己去调整，如果想迷宫游戏体验更好，就需要手动调参或者用别的算法去优化。
六、运用Prim算法开发的迷宫小游戏（Cocos Creator）
最终用这个算法开发了一款迷宫小游戏，这个小游戏中随机模式和挑战模式生成的地图均为Prim算法生成，具体这个游戏的开发后续可能会单独写一篇文章分享给大家，下面是小游戏的二维码，可以用微信扫码体验或搜索重力迷宫试玩。
正文完
