效果预览
我制作了一个 CodePen，以动画形式展示随机迷宫的创建过程，以便更加直观的观察算法的工作原理。（点击即可访问生成新迷宫）
基本思路
使用javaScript生成随机迷宫的核心思想是使用一个“深度优先搜索”（DFS）算法。该算法可以从一个起点开始，探索未访问过的区域，并通过回溯找到所有可通行的路径。通过这种方式，我们可以在一个预定的网格中随机生成迷宫。
定义约束条件
迷宫有很多不同的类型和生成方法。在开始编写代码之前，首先思考希望得到一个什么样子的迷宫，并考虑如何避免过度复杂化，最后设定了一些基本的约束条件：
- 迷宫是矩形的。虽然六边形和圆形迷宫更美观，但它们的实现相对也 更复杂。
- 迷宫中只有一条路径。
- 这条路径从迷宫的左边缘到右边缘。
- 迷宫中的每个方格都应该是有可能经过的。
有了这些约束条件，就可以准备开始进行具体的规划。
迷宫游戏规划
把生成迷宫的过程分为三个步骤：
- 创建一个矩形网格。
- 找到从左侧到右侧的路径。
- 从主路径上分支，填充剩余的网格。
在开始编写代码之前，可以通过一些草图来理解这些步骤：
- 画一个正方形网格。
- 在这个正方形中画一条锯齿形的路径。
- 用不同的颜色标出从主路径上分出的其他路径，填充整个方格。
步骤 1：创建矩形网格
首先，需要确定网格的大小。为了简化操作从一个10x10的网格开始。将这些数值定义为变量，以便后续修改时更为方便：
const gridHeight = 10;
const gridWidth = 10;
步骤 2：寻找所有经过的路径
接下来需要找到一条从左边缘到右边缘的路径，可以将路径存储为一系列具有 X 和 Y 坐标的点。上图中的主路径如下所示：
const mainPath = [{x: -1, y: 7},{x: 0, y: 7},{x: 0, y: 6},{x: 0, y: 5},{x: 1, y: 5},/* ... 更多点 ... */{x: 9, y: 1},{x: 10, y: 1}
];
再为迷宫选择一个起点。可以随机选择一个 Y 坐标，并基于这个坐标设置两个点，一个在网格的左边缘，另一个稍微进入网格：
import { randomInt } from 'https://unpkg.com/randomness-helpers@0.0.1/dist/index.js';function mainPathStartPoints() {const yStart = randomInt(0, gridHeight - 1);return [{x: -1, y: yStart},{x: 0, y: yStart}]
}
注:使用名为randomness-helpers的npm 包中的一些辅助函数，用于帮助执行重复任务，如随机选择整数和数组项
接下来构建路径的其余部分，编写一个函数，该函数接受一个坐标点，并返回该点相邻的一个随机点：
import { randomItemInArray } from 'https://unpkg.com/randomness-helpers@0.0.1/dist/index.js';function findNextPoint(point) {// 构建相邻点的数组const potentialPoints = [];// 如果"上"在网格内，添加它作为潜在点if(point.y - 1 >= 0) {potentialPoints.push({y: point.y - 1,x: point.x});}// 如果"下"在网格内，添加它作为潜在点if(point.y + 1 < gridHeight) {potentialPoints.push({y: point.y + 1,x: point.x});}// 如果"左"在网格内，添加它作为潜在点if(point.x - 1 >= 0) {potentialPoints.push({y: point.y,x: point.x - 1});}// 如果"右"在网格内，添加它作为潜在点if(point.x + 1 < gridWidth) {potentialPoints.push({y: point.y,x: point.x + 1});}// 随机选择一个点添加到路径中 return randomItemInArray(potentialPoints);
}
可以通过多次调用此函数来构建路径，直到达到网格的最右端边缘，然后添加一个额外的坐标点，表示位于右边缘外部的终点。
function getMainPathPoints() {const mainPathPoints = mainPathStartPoints();// 一直添加点，直到最后一个点位于右边缘while(mainPathPoints.at(-1).x < gridWidth) {mainPathPoints.push(findNextPoint(mainPathPoints.at(-1)));}// 添加一个点，Y 坐标与最后一个点相同，但位于右边缘外部mainPathPoints.push({x: gridWidth,y: mainPathPoints.at(-1).y});
}
在上面的代码示例中使用数组方法获取数组中的最后点。
按理说实际效果其实已经接近了，但运作之后我发现逻辑上有一个大问题(点击的 在线预览 查看其实际运行效果)
运行之后总会运行到重复的坐标点 总结下来大概有这几个问题：
- 迷宫内的路径实在是太多了
- 从左边缘起点到达右边缘所需时间过长
- 不知道哪些格子已经走过了，所以无法知道剩下的迷宫该应该走哪些格子。
（这也导致了迷宫显示的问题，不过这些问题解决了其他的就迎经过，确保不会重复走，可以创建一个二维数组，初始时用 0 来表示每个空白格子。如果某个格子被占用，就把 0 改成 1。
const gridData = new Array(gridHeight).fill().map(() => new Array(gridWidth).fill(0)
);
这段代码会创建一个类似这样的数组：
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
]
然后可以增加一个函数，用来标记某个格子已经走过了，走过之后直接把 0 改为 1：
function markPointAsTaken(point, value = 1) {gridData[point.y][point.x] = value;
}
例如，假设已经在迷宫中绘制了一条路径并标记了占用的格子，数组就会变成类似于这样：
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 1, 1, 1],[0, 0, 1, 1, 1, 0, 1, 1, 0, 0],[0, 1, 1, 0, 1, 0, 1, 1, 1, 0],[0, 1, 1, 1, 1, 1, 1, 1, 1, 0],[1, 1, 0, 1, 1, 1, 1, 1, 1, 0],[1, 1, 1, 1, 1, 1, 1, 1, 1, 0],[1, 0, 0, 1, 1, 1, 0, 1, 1, 0],[0, 0, 0, 1, 1, 1, 0, 1, 1, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
]
接下来再增加一个辅助函数，检查某个格子是否为空且在规定区域内，修改之前写的 findNextPoint 函数，让它只返回有效的空格坐标：
function isCellEmpty(point) {// 检查格子是否在网格外if (point.x < 0 || point.x >= gridWidth || point.y < 0 || point.y >= gridHeight) {return false;}// 检查格子是否为空return gridData[point.y][point.x] === 0;
}
到目前为止已经有了寻找路径所需的所有函数，但还有一个问题：如果运行中途被“卡住”了该怎么办？（如果所有相邻的格子都已占用，应该走哪里呢？）
最简单的解决办法就是：如果卡住了就直接重置数组！重新开始，点击看看效果
这个办法还算有效，但如果尝试用它来求解更大的迷宫，可能会需要很长时间才能找到有效路径，另一个解决办法就是，可以尝试“后退”几步并从另一个位置继续寻找，从而使逻辑更加智能 点击在线体验
// 导入随机工具库，提供随机整数、随机选择数组元素和随机概率的功能
import { randomInt, randomItemInArray, randomChance } from 'https://unpkg.com/randomness-helpers@0.0.1/dist/index.js';// 获取页面中的 SVG 元素和相关的 DOM 元素
const svgEl = document.querySelector('svg'); // 用于显示迷宫路径的SVG元素
const patternEl = document.querySelector('.pattern'); // 用于渲染迷宫路径的容器
const gridEl = document.querySelector('.grid'); // 用于渲染网格的容器// 定义迷宫的基本配置
const gridWidth = 20; // 网格的宽度（列数）
const gridHeight = 20; // 网格的高度（行数）
const scale = 50; // 每个网格单元的缩放比例（用于计算位置）
const splittingChance = 0.1; // 额外路径的生成概率
const animationSpeed = 20; // 路径绘制的动画速度（毫秒）
const retryLimit = 30; // 最大重试次数，如果路径无法继续，重新开始// 初始化变量
let interval; // 动画定时器
let failedCount = 0; // 失败计数器，记录路径生成失败的次数
let mainPathPoints = []; // 主路径的点集合
let otherPaths = []; // 额外路径的集合// 创建初始的网格数据
let gridData = buildFreshGrid();// 绘制网格的函数，返回 SVG 格式的网格线条
function drawGrid() {let gridMarkup = ''; // 用于存储网格的SVG markup// 绘制横向的网格线for (let y = 0; y <= gridHeight; y++) {gridMarkup += `<line class="grid-line"x1="0" x2="${gridWidth * scale}"y1="${y * scale}"y2="${y * scale}"/>`;}// 绘制纵向的网格线for (let x = 0; x <= gridWidth; x++) {gridMarkup += `<line class="grid-line"y1="0" y2="${gridHeight * scale}"x1="${x * scale}"x2="${x * scale}"/>`;}return gridMarkup; // 返回生成的网格线的HTML字符串
}// 创建新的空网格，初始化所有单元格为0（未占用）
function buildFreshGrid() {return new Array(gridHeight).fill().map(() => new Array(gridWidth).fill(0));
}// 调整迷宫路径点的位置，转换为适应 SVG 坐标系
function adjustMazePoint(point) {return {x: scale / 2 + point.x * scale,y: scale / 2 + point.y * scale};
}// 将路径点数组转换为 SVG 路径数据
function buildPathData(points) {points = points.map(adjustMazePoint); // 调整每个路径点位置const firstPoint = points.shift(); // 移除第一个点作为起始点// SVG路径的M命令表示移动到起始点let commands = [`M ${firstPoint.x}, ${firstPoint.y}`];// 遍历路径点，使用L命令连接每个点points.forEach(point => {commands.push(`L ${point.x}, ${point.y}`);});return commands.join(' '); // 返回完整的SVG路径字符串
}// 绘制路径的函数
function drawLine(points, className = '') {return `<pathclass="maze-path ${className}" d="${buildPathData(points)}"/>`;
}// 生成主路径的起始点，随机选择一个起始位置
function mainPathStartPoints() {const yStart = randomInt(0, gridHeight - 1); // 随机选择一个Y轴上的起始位置return [{ x: -1, y: yStart }, // 主路径的起始点，X为-1表示从网格外开始{ x: 0, y: yStart } // 第二个起始点，X为0表示网格内的起点];
}// 标记网格中的一个点为已占用，值为1表示占用
function markPointAsTaken(point, value = 1) {gridData[point.y][point.x] = value;
}// 寻找当前点的相邻未占用的点，返回一个随机的相邻点
function findNextPoint(point) {const potentialPoints = [];// 判断上、下、左、右四个方向的相邻点是否未被占用if (gridData[point.y - 1]?.[point.x] === 0) {potentialPoints.push({ y: point.y - 1, x: point.x });}if (gridData[point.y + 1]?.[point.x] === 0) {potentialPoints.push({ y: point.y + 1, x: point.x });}if (gridData[point.y]?.[point.x - 1] === 0) {potentialPoints.push({ y: point.y, x: point.x - 1 });}if (gridData[point.y]?.[point.x + 1] === 0) {potentialPoints.push({ y: point.y, x: point.x + 1 });}// 如果有可用的相邻点，随机返回其中一个，否则返回undefinedreturn potentialPoints.length === 0 ? undefined : randomItemInArray(potentialPoints);
}// 重置迷宫的状态，包括路径、网格数据和失败计数器
function refreshState() {mainPathPoints = mainPathStartPoints(); // 重置主路径的起始点gridData = buildFreshGrid(); // 重置网格数据markPointAsTaken(mainPathPoints.at(-1)); // 标记起始点为占用otherPaths = []; // 清空额外路径failedCount = 0; // 重置失败计数器
}// 绘制所有的路径（包括主路径和额外路径）
function drawLines() {let markup = '';// 绘制额外路径markup += otherPaths.map(drawLine).join('');// 绘制主路径markup += drawLine(mainPathPoints, 'main');patternEl.innerHTML = markup; // 更新SVG中的内容
}// 主路径生成的函数，使用随机算法生成迷宫的主路径
function buildMainPath() {refreshState(); // 重置迷宫状态drawLines(); // 绘制当前的路径interval = setInterval(() => {const nextPoint = findNextPoint(mainPathPoints.at(-1)); // 寻找主路径的下一个点// 如果没有可用的下一个点，说明当前路径无法继续if (!nextPoint) {if (failedCount > retryLimit) { // 如果重试次数超过最大值，重新生成路径refreshState(); } else {failedCount++;for (let i = 0; i < failedCount; i++) {markPointAsTaken(mainPathPoints.pop(), 0); // 退回路径并清除占用}}} else {mainPathPoints.push(nextPoint); // 添加下一个路径点markPointAsTaken(nextPoint); // 标记该点为占用// 如果到达迷宫的右侧边界，停止路径生成if (nextPoint.x === gridWidth - 1) {mainPathPoints.push({ x: nextPoint.x + 1, y: nextPoint.y }); // 添加右边界外的点clearInterval(interval); // 停止定时器}}drawLines(); // 更新路径显示}, animationSpeed);
}// 随机生成更多的额外路径
function addMorePaths() {gridData.forEach((row, y) => {row.forEach((cell, x) => {// 如果该点已经被占用，并且符合生成额外路径的概率if (cell && randomChance(splittingChance)) {otherPaths.push([{ y, x }]); // 创建新的路径}});});
}// 判断迷宫是否已经完全生成（所有点都被占用）
function mazeComplete() {return gridData.flat().every(cell => cell === 1); // 检查所有单元格是否都已被占用
}// 生成额外路径的函数，使用定时器逐步绘制这些路径
function buildOtherPaths() {interval = setInterval(() => {addMorePaths(); // 添加更多路径// 遍历所有额外路径，尝试继续生成otherPaths.forEach((path) => {const nextPoint = findNextPoint(path.at(-1)); // 寻找下一个点if (nextPoint) {path.push(nextPoint); // 如果找到了点，加入路径markPointAsTaken(nextPoint); // 标记该点为占用}});drawLines(); // 更新显示路径if (mazeComplete()) { // 如果迷宫已完成，停止定时器clearInterval(interval);console.log('maze done');}}, animationSpeed);
}// 初始绘制函数
function draw() {gridEl.innerHTML = drawGrid(); // 绘制网格const mazeWidth = gridWidth * scale; // 计算迷宫宽度const mazeHeight = gridHeight * scale; // 计算迷宫高度// 设置 SVG 的视口大小和尺寸svgEl.setAttribute('viewBox', `0 0 ${mazeWidth} ${mazeHeight}`);svgEl.setAttribute('width', mazeWidth);svgEl.setAttribute('height', mazeHeight);patternEl.innerHTML = ''; // 清空当前的路径clearInterval(interval); // 清除现有的定时器buildMainPath(); // 开始生成主路径
}// 初始绘制网格
gridEl.innerHTML = drawGrid();// 绑定点击事件，用于重新生成迷宫
document.querySelector('.randomize').addEventListener('click', draw);
步骤 3：从主路径分支，填充剩余的网格
已经有了主路径，接下来要做的就是填充剩余的网格。首先创建一个辅助函数，检查每个单元格是否已被占用：
function mazeComplete() { // 将二维数组展平成一维数组，然后检查是否所有单元格都被设置为1return gridData.flat().every(cell => cell === 1);
}
接下来开始填充迷宫。每次循环时将执行以下操作：
- 遍历每条路径，尽可能为其添加新格子。
- 遍历所有路径上的格子，在某些格子上随机添加新路径。
- 一直循环，直到网格所有格子完全占用
import { randomChance } from 'https://unpkg.com/randomness-helpers@0.0.1/dist/index.js';const otherPaths = [];function buildOtherPaths() {while(!mazeComplete()) { // 添加一些新路径addMorePaths();// 遍历所有路径otherPaths.forEach((path) => {// 尝试在每条路径上添加一个点const nextPoint = findNextPoint(path.at(-1));if(nextPoint) {path.push(nextPoint);markPointAsTaken(nextPoint);}});}
}function addMorePaths() {// 遍历网格中的所有单元格gridData.forEach((row, y) => {row.forEach((cell, x) => {// 如果该单元格已被占用，则以10%的几率从该单元格开始新路径if(cell && randomChance(0.1)) {otherPaths.push([{y,x,}]);}})})
}
这样就完成了迷宫的生成！可以点击“随机生成” 来生成新的迷宫。
完整代码示例
