程序化地牢生成算法中如何绘制顶点为指定大小矩形、边不重叠房间的graph

核心逻辑：力导向图布局 + 碰撞修正 + 走廊校验 #

1. 预生成拓扑与基础属性 #

• 先确定地牢的拓扑关系：可通过Delaunay三角剖分、最小生成树加随机边，或是自定义的graph结构生成，保证每个顶点对应一个房间，边对应需要连通的走廊
• 提前为每个顶点分配固定宽高，特殊房间（出生房、Boss房、宝箱房）可单独指定尺寸

2. 力导向算法生成初始坐标 #

力导向算法可以直接把拓扑关系转化为2D空间位置，自定义两个受力规则即可：

• 有边连接的相邻房间之间施加吸引力，保证后续走廊长度可控
• 所有房间之间施加排斥力，避免初始阶段完全重叠
• 迭代100~500次就能得到空间关系基本合理的初始坐标，不需要完全避免重叠。JS环境可直接调用d3-force库实现，其他语言也有对应封装好的计算模块，无需从零写迭代逻辑

3. 矩形碰撞修正，确保房间无重叠 #

用上一步的初始坐标做迭代碰撞检测：

• 每次遍历所有房间对，检测轴对齐矩形是否重叠
• 若重叠，按两个房间的中心点连线方向，将两个房间向相反方向推开重叠距离，可给大房间更高的权重，避免小房间被推到过远的位置
• 迭代直到所有房间无重叠，或是达到迭代次数阈值后做一次位置收敛

4. 走廊生成与重叠校验 #

房间位置固定后生成走廊，推荐用曼哈顿路径或A*寻路实现：

• 提前在每个房间的四条边上预留1~2个门位，取两个连通房间的门点作为走廊端点，避免走廊直接穿房间中心
• 用水平+垂直的两段式曼哈顿路径生成走廊，宽度固定为1~2格
• 生成后校验走廊的矩形区域是否和除两个端点房间外的其他房间重叠，若重叠可微调门点位置，或是轻微调整两个房间的坐标后重新生成
• 多次调整仍重叠的话，直接返回步骤2重新算力导向布局即可

可选优化项 #

• 需要固定特殊房间位置的话，可在力导向迭代时将对应房间的坐标设为固定值，不参与受力位移
• 可给不同类型房间设置不同排斥力系数，比如Boss房排斥力更高，保证周围有足够空间生成连通走廊
• 走廊生成后可做圆角、随机凹凸处理，提升地牢自然度

内容的提问来源于stack exchange，提问作者陳冠曄