OpenGL游戏开发中如何程序化生成符合要求的图块集房间

针对固定种子可复现、单连通墨块状可通行区域、至少触达一侧边界的核心要求，以下是两种可直接落地的实现方案：

方案1：边界起点随机游走算法（实现复杂度最低） #

• 初始化固定尺寸的图块网格，所有格子默认设为不可通行（白色）
• 直接选择网格任意一侧边界上的点作为生成起点，将该点设为可通行（黑色），天生满足区域触达边界的要求
• 用用户传入的自定义/随机种子初始化伪随机数生成器（PRNG），后续所有随机逻辑完全依赖该PRNG输出，保证同种子生成结果100%一致，建议使用std::mt19937这类统计特性稳定的伪随机算法
• 提前设定可通行区域填充比例阈值（可根据需求调整为30%~70%），每一步从当前位置随机选择上下左右四个方向移动一格，若目标格为不可通行则改为可通行，循环直到可通行格子数量达到阈值
• 可选优化：给随机方向增加权重，朝向已有可通行格子的方向移动概率提升20%~50%，可生成更紧凑的墨块状区域，避免出现细长条的不合理布局

方案2：元胞自动机+连通域筛选（生成效果更自然） #

• 用指定种子初始化PRNG后，先在固定尺寸网格中随机生成占比40%~50%的可通行格子
• 执行3~5轮元胞自动机规则迭代：任意格子周围8邻域内可通行格子数量≥4时保留为可通行，否则改为不可通行，迭代完成后会自动生成大块连续的类墨状区域，细碎噪声点极少
• 遍历网格内所有连通域，仅保留面积最大的连通域，其余区域全部改为不可通行，直接保证单连通要求
• 检查留存的连通域是否接触网格边界，若未接触则从连通域边缘点往最近的边界方向打通一条1格宽的直线路径，即可满足入口要求

通用注意事项 #

• 全程仅使用同一个绑定了目标种子的PRNG实例生成所有随机值，不要调用系统全局随机函数、不要引入其他随机变量，即可保证同种子生成结果完全一致
• 若需要标准化入口位置，可在生成逻辑结束后，强制保留指定边界位置（如下方中间、左侧中间）为可通行，若该位置原本为不可通行，从该点往最近的可通行区域打通1格宽路径即可

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