体素游戏中生成全连通1的3D数组所有变体的技术问询

核心思路 #

放弃「随机生成后过滤」的低效方案，改用从起始点逐步扩展连通区域的生成方式——所有变体从起始连通点出发，仅向相邻未激活体素扩展，天然保证所有1与起始点连通，从根源上杜绝孤立1的产生，无需事后连通性检查。

具体实现步骤 #

1. 初始化状态 #

• 标记起始坐标(x0,y0,z0)为激活状态（设为1）。
• 构建候选扩展集合：收集起始点所有相邻的未激活体素（即上下左右前后6个方向中，在数组边界内且当前为0的位置）。

2. 递归/迭代生成所有变体 #

对候选集合中的每个位置，分两种分支处理：

• 分支1：激活当前位置
  1. 将该位置设为1，加入已激活集合。
  2. 遍历该位置的6个相邻体素，将其中未激活且不在候选集合中的位置加入候选集合。
  3. 以更新后的候选集合和已激活集合为基础，递归继续生成后续变体。
  4. 回溯：将该位置设回0，从候选集合中移除新增的相邻体素，恢复到处理前的状态。
• 分支2：不激活当前位置
  直接跳过该位置，用原候选集合继续处理剩余位置。

3. 终止条件 #

当候选集合为空时，当前的体素数组状态即为一个合法连通变体，记录或输出该状态。

关键优化点 #

• 避免重复变体：固定候选位置的处理顺序（例如按x→y→z升序遍历），确保每个变体仅被生成一次，不会因选择顺序不同产生重复。
• 空间优化：无需保存整个数组副本，用哈希集合或位掩码（适用于小维度）记录已激活位置，大幅降低内存占用。
• 定向剪枝：如果有额外约束（如最大激活体素数量、特定区域限制），可在递归过程中提前终止不符合条件的分支，进一步减少计算量。
• 随机生成合法变体：若无需枚举所有变体，仅需随机生成合法布局，可在候选集合中随机选择位置激活，直到满足需求（如达到目标体素数量），效率远高于随机过滤。

对比旧方案的优势 #

对于两位数维度的体素数组（如20×20×20），随机生成后过滤的复杂度是2^(8000)级别的天文数字，完全无法处理；而扩展法仅遍历所有合法连通子集，计算量与连通变体的数量正相关，能适配大维度场景。

示例验证（3×3×3数组，起始点(1,1,1)） #

初始候选集合是(0,1,1)、(2,1,1)、(1,0,1)、(1,2,1)、(1,1,0)、(1,1,2)：

• 选择激活(1,0,1)，则新的候选集合会加入(0,0,1)、(2,0,1)、(1,0,0)、(1,0,2)，后续生成的变体必然包含连通的(1,1,1)和(1,0,1)，以及可选扩展的相邻体素。
• 所有生成的变体均不会出现孤立1，完全符合需求。

内容的提问来源于stack exchange，提问作者AoKishuba