【OpenHarmony/HarmonyOS】ArkTS 随机迷宫生成实战：迭代 DFS、薄墙模型、环路与出生区安全

【OpenHarmony/HarmonyOS】ArkTS 随机迷宫生成实战：迭代 DFS、薄墙模型、环路与出生区安全

随机迷宫并不是“随便放几面墙”。它需要保证可达、控制通道宽度、留出战斗空间，还要兼顾坦克体积、出生安全和可破坏元素。本文完整拆解一个适合 Canvas 坦克游戏的程序化迷宫生成器。🧩

一、先明确地图的目标

这款游戏中的迷宫既是移动空间，也是弹道反射和 AI 寻路的基础。理想地图应满足：

• 从任意主要区域都能到达其他区域；
• 通道不能比坦克窄，否则生成后不可玩；
• 不能只有一条正确路线，需要回环和战斗区域；
• 墙体既有不可破坏墙，也有少量可破坏墙；
• 玩家和敌人的出生位置周围必须足够安全；
• 波次扩大时，生成耗时不能出现递归栈溢出。

项目采用“逻辑网格 + 实际格子”的薄墙模型，再使用迭代版深度优先回溯生成基础连通树。

二、逻辑房间与实际网格

传统迷宫经常把一个单元格同时当作房间和通道，墙体占据相邻格。项目为了让通道适配较大的坦克，定义：

privatereadonlyPATH_WIDTH =4;privatereadonlyWALL_WIDTH =1;privatereadonlySTRIDE =this.PATH_WIDTH +this.WALL_WIDTH;

每个逻辑房间在实际数组中占4 x 4的空白区域，相邻房间之间保留 1 格墙。一个逻辑单元的跨度为 5。

####### #....#. #....#. #....#. #....#. #######

其中#是墙，.是可通行区域。逻辑坐标(lx, ly)对应实际数组左上角：

const startX= lx * STRIDE + WALL_WIDTH;const startY= ly * STRIDE + WALL_WIDTH;

这种模型的价值在于：迷宫算法只关心逻辑房间之间是否连接，渲染和碰撞则使用更细的实际格子。

三、先把整张地图填成墙

根据目标宽高反推可以容纳多少逻辑房间：

constlogicalCols = Math.floor( (this.width -this.WALL_WIDTH) /this.STRIDE );constlogicalRows = Math.floor( (this.height -this.WALL_WIDTH) /this.STRIDE );constactualWidth = logicalCols *this.STRIDE +this.WALL_WIDTH;constactualHeight = logicalRows *this.STRIDE +this.WALL_WIDTH;this.maze = Array(actualHeight).fill(null) .map(() => Array(actualWidth).fill(1));

不要直接用Array(height).fill(Array(width).fill(1))。那样每一行会引用同一个数组，修改一格可能同步修改所有行。使用map为每一行创建独立数组。

当输入尺寸过小时，生成器还应提供兜底地图，而不是继续访问不存在的visited[0][0]：

if(logicalCols <=0|| logicalRows <=0) {constwidth = Math.max(5,this.width);constheight = Math.max(5,this.height);returnArray(height).fill(null) .map(() =>Array(width).fill(0)); }

四、用迭代 DFS 打通所有房间 🔨

生成算法的核心是随机深度优先搜索：

1. 从(0, 0)开始；
2. 查找尚未访问的上下左右邻居；
3. 随机选择一个邻居，打通中间墙体；
4. 把邻居压栈并继续；
5. 没有未访问邻居时弹栈回退。

关键代码如下：

constvisited =Array(logicalRows).fill(null) .map(() =>Array(logicalCols).fill(false));conststack: { lx: number, ly: number }[] = []; stack.push({ lx:0, ly:0}); visited[0][0] =true;this.clearRoom(0,0);while(stack.length >0) {constcurrent = stack[stack.length -1];constneighbors =this.findUnvisitedNeighbors( current.lx, current.ly, visited );if(neighbors.length >0) {constnext = neighbors[ Math.floor(Math.random() * neighbors.length) ];this.carveConnection(current.lx, current.ly, next.dx, next.dy); visited[next.ny][next.nx] =true;this.clearRoom(next.nx, next.ny); stack.push({ lx: next.nx, ly: next.ny }); }else{ stack.pop(); } }

项目特意使用显式栈，而不是递归函数。小地图中递归写法更简洁，但波次地图扩大后，调用深度不可控；迭代形式把深度放在堆上的数组中，稳定性更高。

为什么 DFS 生成的一定连通？

每个新房间只会从已经访问的房间进入，而且算法会持续到所有可达的未访问邻居都被处理。规则矩形网格本身连通，因此最终每个房间都被连接到起点，得到一棵生成树。

时间复杂度

每个逻辑房间只标记一次，每次检查四个方向，核心复杂度为O(rows * cols)，适合运行时生成。

五、怎样清空房间和连接墙？

清空房间就是把对应的4 x 4区域写为 0：

privateclearRoom(lx: number, ly: number) {conststartX = lx *this.STRIDE +this.WALL_WIDTH;conststartY = ly *this.STRIDE +this.WALL_WIDTH;for(let y =0; y <this.PATH_WIDTH; y++) {for(let x =0; x <this.PATH_WIDTH; x++) {this.maze[startY + y][startX + x] =0; } } }

连接两个逻辑房间时，只清除它们之间厚度为 1 的墙段。向右连接时：

if(dx ===1) { startX +=this.PATH_WIDTH; clearW =this.WALL_WIDTH; }

向下连接则移动startY并将clearH改为墙宽。由于通道开口长度等于PATH_WIDTH，坦克可以完整通过，不会只出现一格小洞。

六、纯 DFS 迷宫为什么不适合坦克对战？

深度优先搜索生成的是一棵树，任意两点之间只有一条路径。它适合解谜，却会让坦克战出现几个问题：

• 玩家被追击时没有绕行路线；
• AI 和玩家容易堵在狭长通道；
• 弹道战术单一；
• 地图缺少开阔交战区；
• 一面可破坏墙可能切断唯一通路。

因此项目在基础迷宫完成后，额外随机移除约 30% 的内部墙连接：

const loopCount =Math.floor(cols*rows*0.30);for(leti =0; i < loopCount; i++) { const lx =Math.floor(Math.random()*(cols -1)); const ly =Math.floor(Math.random()*(rows -1));if(Math.random()>0.5) { this.carveConnection(lx,ly, 1, 0); }else{ this.carveConnection(lx,ly, 0, 1); } }

基础生成树保证“至少连通”，额外拆墙只会增加路径，不会破坏可达性。这是非常稳妥的两阶段设计。

七、创建开阔战斗区域

只增加环路仍可能保留大量窄通道。项目又随机选择若干位置，把相邻2 x 2逻辑房间之间的墙打通，形成小型竞技场。

开阔区域的作用包括：

• 给坦克提供转向和躲避空间；
• 让散弹、多目标 AI 更有发挥空间；
• 形成与窄通道不同的战术节奏；
• 为传送门、道具和晶石提供更安全的刷新点。

这里必须先检查cols > 4 && rows > 4，否则随机范围可能为负数或竞技场越界。

八、可破坏墙不能按单像素随机

墙体类型约定为：

0：空地 1：不可破坏墙 2：可破坏砖墙

如果把单个墙格随机改成可破坏墙，玩家击碎后只留下宽度 1 格的缺口，而坦克直径约为 2 格，仍然无法通过。项目因此按完整墙段转换：

if(isWall &&Math.random() <0.15) {for(letk =0; k <this.PATH_WIDTH; k++) {this.maze[wallY + k][wallX] =2; } }

这是地图生成中很容易忽略的“视觉破坏”和“可通行性”一致问题。装饰单位必须与碰撞体尺寸相匹配。

九、出生点不只是一个空格 🛡️

生成完成后，项目再次清理左上角和右下角逻辑房间：

this.clearRoom(0,0);this.clearRoom(logicalCols -1, logicalRows -1);

实体刷新时还要检查中心周围3 x 3的实际格子：

for (lety= row -1; y <= row +1; y++) { for (letx= col -1; x <= col +1; x++) { constcell= this.maze[y][x];if(cell===1||cell===2||cell===4) { returnfalse; } } }

原因是坦克半径大于单格的一半。中心格为空不代表整个碰撞体不与相邻墙体重叠。安全点检测必须使用实体占用范围，而不是单点判断。

另外，敌人出生还应与玩家保持最小距离，避免地图一生成就被贴脸攻击。项目用世界坐标距离过滤小于 200 像素的候选位置。

十、波次地图如何逐渐扩大？

游戏不是固定尺寸地图。PvE 根据波次计算缩放系数：

constsizeMultiplier =0.6+ Math.min(2.2, (currentWave -1) *0.25);constcols = Math.max(20, Math.floor(screenWidth * sizeMultiplier / cellSize));constrows = Math.max(20, Math.floor(screenHeight * sizeMultiplier / cellSize));

第一波地图紧凑，后续逐步扩大，并在一定倍数封顶。这样难度增长不仅来自敌人数量，还来自探索范围、路线记忆和资源分布。

不同模式可覆盖该策略：限时模式保持小地图提高节奏，解谜模式使用固定紧凑尺寸并在远端放置真假出口。

十一、随机地图如何做到可测试？

直接调用Math.random()的缺点是问题难以复现。若玩家反馈某一局出生点被封、出口不可达，开发者无法重建同一地图。

工程化改进可以引入可播种随机数生成器：

interfaceRandomSource{ next(): number;// 返回 [0, 1)}

生成器构造时注入RandomSource，正式游戏传入带种子的实现，测试传入固定序列。随后可测试：

• 所有逻辑房间是否从起点可达；
• 边界是否全部为墙；
• 出生区域是否满足碰撞体尺寸；
• 可破坏墙被击碎后是否形成足够宽的通路；
• 1000 个种子生成时是否均不越界；
• 大地图生成耗时是否在预算内。

十二、总结 ✨

适合坦克战斗的程序化迷宫，不是单一算法的结果，而是一条生成流水线：

1. 用逻辑房间和实际格子分离通路宽度；
2. 全墙初始化；
3. 迭代 DFS 建立必然连通的基础树；
4. 随机拆墙增加环路；
5. 打通局部区域形成竞技场；
6. 按完整墙段添加可破坏砖墙；
7. 重新清理出生区域；
8. 用实体体积校验所有刷新位置。

当迷宫同时服务于移动、射击、AI、道具和关卡节奏时，算法正确只是第一步，“生成后真正可玩”才是最终标准。🎯

推荐标签：OpenHarmonyHarmonyOSArkTS随机迷宫DFS程序化生成