结论：应采用递归分割+矩形列表+后处理连接的轻量模式，而非维护完整BSP树结构；因其更省内存、易调试，且地下城生成核心是连通性与布局合理性，非空间查询。
直接说结论：C++ 里用 BSP 树生成经典 Roguelike 地下城（比如 NetHack 或 Brogue 风格）时，不要手写完整 BSP 树结构，而是用递归分割 + 矩形列表 + 后处理连接的轻量模式——BSP 在这里是分割逻辑，不是必须持久化的树对象。
为什么不用 std::unique_ptr 构建真实树结构
真实地下城生成关注的是「可行走区域连通性」和「房间布局合理性」，不是空间查询或射线检测。维护完整 BSP 树节点（含父子指针、分割轴、分割位置、左右子树）会带来三类负担：
- 内存开销无必要：每个叶节点只需存一个
Rect（x, y, w, h），而非带指针的节点对象 - 后续连接房间时，你实际遍历的是叶节点集合，不是树遍历顺序
- 调试困难：分割失败时，树结构可能不完整，但矩形列表始终可打印验证
推荐做法是用 std::vector<rect></rect> 存所有叶节点，用栈或递归参数隐式表达树深度。
递归分割时如何避免瘦长房间和边缘贴边
常见错误是随机选分割点时不加约束，导致生成 1x20 的走廊状矩形，或房间紧贴地图边界无法开门。关键控制点：
立即学习“C++免费学习笔记（深入）”；
- 设最小房间尺寸阈值，如
MIN_ROOM_SIZE = 5，每次分割前检查当前矩形是否 ≥2 * MIN_ROOM_SIZE才允许切 - 分割位置不能太靠近边缘：若水平分割，新高度必须满足
h1 >= MIN_ROOM_SIZE && h2 >= MIN_ROOM_SIZE，计算切点用split = rand() % (h - 2 * MIN_ROOM_SIZE) + MIN_ROOM_SIZE - 强制交替分割方向：用深度 % 2 控制先横后竖，避免连续多次同向切出条状区域
示例片段（伪代码）：
void split(Rect r, int depth, vector<Rect>& leaves) {
if (r.w < MIN_ROOM_SIZE * 2 || r.h < MIN_ROOM_SIZE * 2) {
leaves.push_back(r);
return;
}
bool horizontal = depth % 2 == 0;
if (horizontal) {
int cut = rand() % (r.h - 2*MIN_ROOM_SIZE) + MIN_ROOM_SIZE;
split({r.x, r.y, r.w, cut}, depth+1, leaves);
split({r.x, r.y+cut, r.w, r.h-cut}, depth+1, leaves);
} else {
int cut = rand() % (r.w - 2*MIN_ROOM_SIZE) + MIN_ROOM_SIZE;
split({r.x, r.y, cut, r.h}, depth+1, leaves);
split({r.x+cut, r.y, r.w-cut, r.h}, depth+1, leaves);
}
}连接叶节点房间时，走廊生成容易断连或穿墙
拿到所有叶节点矩形后，连接不是“两两连”，而是按某种顺序（如 BFS 或树中序）逐对连接。典型陷阱：
- 中心点连线直接挖通道 → 可能穿过其他房间：必须用「L 型走廊」，先横向再纵向（或反之），并逐格检查是否在空地内
- 只连父子节点 → 地图呈链状，缺乏环路：应在叶节点列表上额外做 1–2 次随机配对连接（避开已连过的房间对）
- 门位置硬编码取中心 → 中心可能是墙或被其他走廊占了：应遍历矩形边上的可通行点（如顶部边 y=r.y，x∈[r.x+1, r.x+r.w-2]），随机选一个有效点作为门起点
走廊挖通后务必做连通性检查（如 flood fill），否则看似有门，实际被未清除的隔墙挡住。
生成后必须做的三件事，否则不算完成
很多实现卡在“看起来有房间”就停了，但真正可用的地图还需：
- 填充非房间区域为墙：遍历整个地图二维数组，对每个格子判断是否被任一
Rect覆盖，未覆盖处设为墙 - 确保至少一个房间含起始点（如
player_spawn）：随机选一个叶节点，在其内部偏移 1–2 格放玩家，避免贴墙 - 检查所有门是否双向可达：从每个门格子出发 BFS，确认能走到至少两个不同房间 —— 这步漏掉，就会出现“门开着但推不开”的逻辑漏洞
这些步骤没有高大上的算法，但缺一不可；BSP 分割只是起点，真正的地图质量藏在这些后处理细节里。
