【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 打通所有房间 生成算法的核心是随机深度优先搜索从(0, 0)开始查找尚未访问的上下左右邻居随机选择一个邻居打通中间墙体把邻居压栈并继续没有未访问邻居时弹栈回退。关键代码如下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区域写为 0privateclearRoom(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(cell1||cell2||cell4) { 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 个种子生成时是否均不越界大地图生成耗时是否在预算内。十二、总结 ✨适合坦克战斗的程序化迷宫不是单一算法的结果而是一条生成流水线用逻辑房间和实际格子分离通路宽度全墙初始化迭代 DFS 建立必然连通的基础树随机拆墙增加环路打通局部区域形成竞技场按完整墙段添加可破坏砖墙重新清理出生区域用实体体积校验所有刷新位置。当迷宫同时服务于移动、射击、AI、道具和关卡节奏时算法正确只是第一步“生成后真正可玩”才是最终标准。推荐标签OpenHarmonyHarmonyOSArkTS随机迷宫DFS程序化生成