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