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

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

一、先明确地图的目标

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

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

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

二、逻辑房间与实际网格

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

private readonly PATH_WIDTH = 4;
private readonly WALL_WIDTH = 1;
private readonly STRIDE = 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;

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

三、先把整张地图填成墙

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

const logicalCols = Math.floor(
  (this.width - this.WALL_WIDTH) / this.STRIDE
);
const logicalRows = Math.floor(
  (this.height - this.WALL_WIDTH) / this.STRIDE
);

const actualWidth = logicalCols * this.STRIDE + this.WALL_WIDTH;
const actualHeight = 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) {
  const width = Math.max(5, this.width);
  const height = Math.max(5, this.height);
  return Array(height).fill(null)
    .map(() => Array(width).fill(0));
}

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

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

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

关键代码如下：

const visited = Array(logicalRows).fill(null)
  .map(() => Array(logicalCols).fill(false));
const stack: { lx: number, ly: number }[] = [];

stack.push({ lx: 0, ly: 0 });
visited[0][0] = true;
this.clearRoom(0, 0);

while (stack.length > 0) {
  const current = stack[stack.length - 1];
  const neighbors = this.findUnvisitedNeighbors(
    current.lx, current.ly, visited
  );

  if (neighbors.length > 0) {
    const next = 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：

private clearRoom(lx: number, ly: number) {
  const startX = lx * this.STRIDE + this.WALL_WIDTH;
  const startY = 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 (let i = 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 (let k = 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 (let y = row - 1; y <= row + 1; y++) {
  for (let x = col - 1; x <= col + 1; x++) {
    const cell = this.maze[y][x];
    if (cell === 1 || cell === 2 || cell === 4) {
      return false;
    }
  }
}

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

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

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

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

const sizeMultiplier = 0.6
  + Math.min(2.2, (currentWave - 1) * 0.25);

const cols = Math.max(20,
  Math.floor(screenWidth * sizeMultiplier / cellSize));
const rows = Math.max(20,
  Math.floor(screenHeight * sizeMultiplier / cellSize));

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

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

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

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

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

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

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

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

十二、总结 ✨

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

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

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

---

推荐标签： OpenHarmony HarmonyOS ArkTS 随机迷宫 DFS 程序化生成