hexagon grid（六边形网格）随机生成连通分组的算法求助

下面是两种经过验证、可以完美满足你需求的实现思路：

思路1：优先级扩展法 #

天然保证所有分组连通，适合需要分组大小相对均匀的场景：

• 先确定你需要的分组总数，提前标记好需要留空的空隙瓦片，剩下的作为可分配瓦片。
• 在可分配瓦片中随机抽取N个互不相邻的瓦片作为N个分组的起始点，分别标记对应分组ID。
• 维护一个全局待扩展队列，把所有起始点的相邻可分配、未标记瓦片都存入队列，每条记录附带所属分组的ID、该瓦片距离对应分组起始点的步数。
• 循环从队列中随机取出瓦片做分配判断：
  • 如果该瓦片的相邻已标记瓦片仅属于一个分组，直接将其划入该分组，同时把该瓦片的相邻未分配瓦片加入队列。
  • 如果该瓦片相邻有多个不同分组的已标记瓦片，按各分组当前已分配数量做加权随机分配，已分配数量越少的分组权重越高，保证各组大小趋近均匀。
• 所有分组达到你预设的大小阈值、或队列空时停止流程，剩余未分配瓦片直接标记为空隙即可。

思路2：随机泛洪填充法 #

实现更简单，适合需要分组大小错落、更有随机性的场景：

• 先把所有你想要留成空隙的瓦片标记为不可分配状态。
• 从可分配、未标记的瓦片中随机选一个作为当前分组的起始点，使用DFS/BFS做随机游走填充：每填充一个瓦片后生成0-1区间的随机数，当随机数大于动态调整的停止阈值时继续填充下一个相邻未分配瓦片，否则停止当前分组的填充。停止阈值可随分组已填充数量增大而提升，避免出现过大的分组。
• 重复上一步操作，直到不存在可分配的未标记瓦片即可。

两种方案都能保证每个分组内部100%连通，不会出现你原思路里的异常问题。

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