如何生成含obsticles且无enclaves的连通2D网格地图？

针对全随机生成导致非障碍单元出现飞地（enclaves）、无法保证全局连通的问题，以下是几种可靠的实现方案：

方案1：随机生成后连通性修复 #

• 先按需求比例随机生成初始障碍网格
• 用BFS或DFS遍历所有非障碍单元，识别出所有连通块
• 保留规模最大的连通块，将其余小连通块的单元全部设为障碍
• 在最大连通块内随机选取起点和终点，确保二者必然连通
• 可选补充：若需要维持特定障碍比例，可在修复后的网格上尝试添加少量障碍，每次添加后检查全局连通性，若破坏连通则撤销操作

方案2：增量式添加障碍（全程保证连通） #

• 初始化全可通行的空白网格
• 先随机确定起点和终点，标记为不可转为障碍的单元
• 循环随机选中一个可通行单元（非起点/终点），尝试转为障碍
• 每次转换后，通过BFS/DFS验证：所有可通行单元是否仍属于同一连通块，且起点到终点路径存在
• 若验证失败，回滚本次转换；直到达到预设的障碍比例后停止

方案3：基于迷宫生成算法改造 #

• 使用Prim、Kruskal等经典迷宫生成算法，生成天然全局连通的路径网络
• 在生成的迷宫基础上，将部分路径单元转为障碍（转换时需确保剩余可通行区域仍保持连通）
• 直接复用迷宫的起点终点，或在连通区域内重新选择新的起点终点

核心实现要点 #

• 连通性校验：每次操作后，从起点出发执行BFS/DFS，若遍历到的可通行单元数量等于总可通行单元数，则说明无飞地且全局连通
• 效率优化：对于大尺寸网格，使用**并查集（Union-Find）**数据结构跟踪连通关系，比单次BFS/DFS的校验效率更高
• 障碍比例控制：提前设定目标障碍占比，在生成过程中实时统计障碍数量，达到阈值后终止操作

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