前言

近几年国外涌现了许多诸如MythicDungeons的优秀地牢插件，以MD为例，其在近期加入了程序化地牢生成的功能，如果笔者未曾记错的话，国外做此类副本生成的插件最早可以追溯到几年前的DungeonMMO，但与此同时，国内包括网易MC在内的几乎所有服务器还在使用传统的固定地牢方案，比如单例副本的教父插件DungeonPlus（已经不再活跃），近期的高版本新地牢插件QueDP也未曾提供过程序化副本生成的功能，看起来此概念在国内还未曾散布开来，故笔者自己写了一个类似MD的插件，并计划在此文章将原理公布并详细介绍

注：笔者的项目不开源（大部分的原因是因为本项目的一部分地牢生成是通过修改MC服务端源码实现的），但本文章包含大部分的核心代码

为什么你的地牢需要"长出来"

程序化生成的价值，以及我们要构建的这套系统的全貌

从一个无奈的需求说起

假设读者正在开发一个 Minecraft 副本插件，策划提了一个看似简单的需求：做一个地牢，玩家从入口进去，一路探索，最后击败 Boss。
读者可能会想：
::: align-center
这不难啊？

:::

于是打开 WorldEdit，花一下午手搓了十来个房间，仔细摆好位置，用走廊连起来，测试通过，上线。
然后你的策划活爹说：
::: align-center
玩家反馈每次进去都一样，没意思，能不能每次布局都不同？

:::

这时候问题来了——手工摆放十个房间是可行的，但要实现"每次都不一样"，需要多少套预设？一百套？一千套？就算真的肝出来，玩家玩多了照样会腻。更麻烦的是，如果后期要加新房间、调整难度曲线、修改房间出现概率，每一套预设都得改一遍。这种维护成本是指数级增长的。

所以我们需要换一个思路：
::: align-center
不是"摆放"地牢，而是让地牢自己"长出来"。

:::

程序化生成到底在做什么

所谓程序化生成（Procedural Generation），说白了就是用算法代替人工。给定一些规则和素材，让程序自动组合出结果。这不是什么新概念。1980 年的 Rogue 就用程序化生成创造了无限的地牢，后来的 Diablo、Minecraft、Dead Cells、Hades 都在用类似的技术。

对于 Minecraft 地牢来说，程序化生成能带来三件事：

其一，无限的变化

每次生成的布局都不同。玩家永远不知道下一个房间是什么，这种"未知感"是预设方案很难做到的。当然，这里的"无限"是相对的——变化的上限取决于房间池的丰富程度和算法的复杂度。

其二，可控的随机

注意，是"可控的"随机，不是纯粹的乱数。我们可以设定规则：

Boss 房只能出现在最后
宝箱房最多两个
商店必须在前半段
走廊不能连续出现三个

随机是手段，可控是目的。

其三，配置驱动

想调整生成规则？改配置文件。想加新房间？往房间池里扔一个。想做个新主题的地牢？复制一份配置，换一批房间素材。这种灵活性在长期运营中价值很大。

核心问题：房间怎么拼起来

程序化地牢生成的核心挑战，其实就一个问题：怎么让房间正确地拼接在一起。

这个问题比看上去要复杂。考虑以下情况：

房间有不同的尺寸，大房间和小房间怎么对齐？
房间可能需要旋转，旋转后坐标怎么算？
房间不能重叠，怎么检测碰撞？
有些房间只能从特定方向进入，怎么保证朝向正确？
Boss 房只能有一个入口，怎么限制连接数？

最朴素的做法是"找空地放房间，然后挖走廊连起来"。这种方案能跑，但结果往往很丑——走廊会穿墙、拐弯莫名其妙、房间朝向混乱。

笔者采用的方案是连接器系统：每个房间预先定义好"可以连接的位置"（类似电器的插口），生成时房间通过连接器对接。这样连接关系是预设计的，结果可控得多。

后面的文章会详细展开这套机制。

系统架构概览

在正式开始讲技术细节之前，先给读者一个全貌。整个地牢生成系统可以分成四个阶段：

复制代码

房间定义  →  布局规划  →  布局生成  →  世界放置

第一阶段：房间定义

定义有哪些房间可用。每个房间包含：

基本信息：ID、尺寸、结构文件
连接器列表：哪些位置可以对接其他房间
生成规则：权重、出现次数限制、深度约束

这是"素材准备"阶段，决定了地牢的内容丰富度。

第二阶段：布局规划

根据配置，规划这次生成要用哪些房间、用多少个、什么布局算法。

比如配置说"8-12 个房间，主干+分支布局"，规划器就会：

从房间池里挑选 8-12 个房间
保证起点房间、终点房间、特殊房间被选中
选择对应的布局引擎

第三阶段：布局生成

布局引擎接管，开始真正的生成工作。它会：

放置起始房间
根据算法逻辑，依次放置后续房间
处理坐标变换、碰撞检测
输出布局结果：每个房间放在哪、旋转多少度、和谁连接

这一阶段的输出是纯数据，还没有真正的方块。

第四阶段：世界放置

拿着布局结果，把房间结构实际放进 Minecraft 世界：

加载房间的结构文件（NBT/Schematic）
应用坐标变换（位移、旋转、镜像）
放置方块

这一步涉及性能优化（异步放置、FastAsyncWorldEdit 加速等），但逻辑上是最直观的。

用伪代码表示整个流程：

kotlin 复制代码

// 阶段一：定义房间（通常从配置文件加载）
val roomPool = loadRoomDefinitions("dungeon_rooms.yml")

// 阶段二：规划
val planner = ProceduralPlanner(roomPool)
val request = planner.prepare(
    config = ProceduralConfig(
        minRooms = 8,
        maxRooms = 12,
        layoutType = LayoutType.BRANCHING
    )
)

// 阶段三：生成布局
val engine = BranchingLayoutEngine()
val layout = engine.generate(request)
// layout.placements: 房间放置列表
// layout.connections: 房间连接列表

// 阶段四：放置到世界
layout.placements.forEach { placement ->
    val structure = loadStructure(placement.roomId)
    placeStructure(
        world = targetWorld,
        structure = structure,
        origin = placement.origin,
        rotation = placement.rotation,
        mirror = placement.mirror
    )
}

看起来很简单？魔鬼在细节里。

四种布局思路

布局引擎是整个系统的核心，它决定了房间的排列方式。笔者实现了四种不同的布局算法，每种都有自己的"性格"：

蔓延式（Minecrafty）

从起始房间开始，用队列一层层往外扩展。每次取一个未处理的连接器，尝试在那个位置接一个新房间，新房间的连接器再入队。

生成结果像藤蔓一样自然蔓延，没有明显的主线，适合探索型地牢。

主干+分支式（Branching）

先生成一条"主干道"——从起点到终点的主路线。然后从主干上随机长出若干分支。

这种布局有清晰的主线，适合有流程感的地牢。可以通过参数控制主干长度、分支数量、分支深度。

网格迷宫式（GridMaze）

先在抽象的网格上生成迷宫拓扑（DFS、Prim、Kruskal 等都可以），然后把每个网格节点替换成实际房间。

生成结果是经典的迷宫感，路径曲折、死胡同多。

随机游走式（RandomWalk）

随机选一个已有房间，随机选一个方向扩展。通过"边界偏好"参数控制是倾向于从边缘扩展还是从任意位置扩展。

生成结果比较有机、不规则，适合洞穴风格。

这四种算法没有优劣之分，只有适用场景的不同。后面的文章会逐一详细讲解。

这个系列的结构

接下来的文章会按以下顺序展开：

房间与连接器：房间的数据模型设计，连接器系统的原理
拼接的数学：方向匹配、坐标变换、碰撞检测的实现
四种布局引擎：蔓延式、主干分支式、网格迷宫式、随机游走式的详细讲解
迷宫算法：DFS、Prim、Kruskal、Sidewinder 等算法的原理与实现
房间选择策略：权重系统、深度约束、出现次数控制
环路与拓扑：如何在树形结构上添加循环
特殊房间处理：起点、终点、Boss 房的放置逻辑
落地实现：从布局数据到 Minecraft 方块
收尾：锁钥系统、调试技巧、扩展方向

笔者会尽量用清晰的推导过程来讲解，而不是直接甩结论。目标是读完这个系列，读者能理解每个设计决策背后的原因，并有能力自己实现一套。

这个系列不涉及的内容

有些东西超出了本系列的范围：

Minecraft 插件开发基础：假设读者已经精通Bukkit API和NMS(net.minecraft.server)、OBC(org.bukkit.craftbukkit)
美术与关卡设计：怎么设计一个好看的房间是美术的工作（很显然，笔者不适合干这个，这也是为什么本系列没有很多的图片）
战斗与玩法：怪物生成、战利品掉落、任务触发等是独立的系统（这不是我们讲解的范畴）

好，前言到此为止。下一章开始讲房间定义的核心——连接器系统。

房间不只是一堆方块

房间的数据模型设计，以及连接器系统的原理

最朴素的想法为什么行不通

刚开始做程序化地牢时，笔者的第一反应很直接：房间不就是一堆方块吗？存个 ID、坐标、尺寸就够了吧？

kotlin 复制代码

data class Room(
    val id: String,
    val width: Int,   // X 方向
    val height: Int,  // Y 方向
    val length: Int   // Z 方向
)

生成的时候，随机找个位置，检查会不会和已有房间重叠，不重叠就放下去。房间之间怎么连？找两个最近的房间，沿直线挖一条走廊。

这个方案能跑。但跑出来的结果很难看：

问题一：走廊丑得没法看

自动挖出来的走廊完全不考虑建筑美学。它可能从房间的天花板穿出去，可能斜着切过另一个房间的墙角，可能在地下绕一个莫名其妙的弯。玩家走进去会觉得这不像人造的地牢，更像被虫子蛀过的木头。

问题二：房间朝向丢失

很多房间是有"方向性"的。比如一个大厅，入口在南边，王座在北边，这是设计师有意为之的。但如果随机摆放，入口可能对着墙，王座可能面向角落。房间的叙事感就没了。

问题三：连接关系不可控

假设我们想实现"Boss 房只能有一个入口"或"宝箱房必须从走廊进入"这样的规则，在"找最近点挖走廊"的方案里几乎无法做到。因为连接关系完全是事后决定的，设计师无法在设计房间时就规定它的连接规则。

这些问题的根源在于：
::: align-center
我们把房间当成了"一堆方块"，信息量太少。房间不只是几何体，它还承载着"从哪里可以进、从哪里可以出"的语义信息。

:::

连接器：从电器插口得到的启发

换一个角度思考。

电器为什么能随意组合？因为它们有标准化的接口。三孔插头配三孔插座，USB-A 配 USB-A Type-C 配 Type-C，不用操心内部电路怎么实现。

房间也可以这样。我们给每个房间定义若干"连接器"（Connector），每个连接器代表一个可以对接其他房间的位置。生成地牢时，房间通过连接器相连，就像把乐高积木扣在一起。

连接器需要哪些信息？

位置：连接器在房间内的坐标。比如"房间南墙中央，地面高度"。
朝向：连接器面向哪个方向。朝南的连接器意味着"可以从南边接入另一个房间"。

这两个信息就足够描述"两个房间怎么对接"了。

kotlin 复制代码

data class Connector(
    val id: String,           // 连接器的唯一标识
    val position: Vector3i,   // 在房间局部坐标系中的位置
    val direction: Direction  // 朝向：NORTH, SOUTH, EAST, WEST, UP, DOWN
)

enum class Direction {
    NORTH,  // -Z
    SOUTH,  // +Z
    EAST,   // +X
    WEST,   // -X
    UP,     // +Y
    DOWN    // -Y
}

一个房间可以有多个连接器：

kotlin 复制代码

val hallRoom = Room(
    id = "grand_hall",
    size = Vector3i(15, 8, 20),
    connectors = listOf(
        Connector("south_entrance", Vector3i(7, 0, 0), Direction.SOUTH),
        Connector("north_exit", Vector3i(7, 0, 19), Direction.NORTH),
        Connector("east_balcony", Vector3i(14, 0, 10), Direction.EAST)
    )
)

这个大厅有三个连接器：南边入口（7, 0, 0）、北边出口（7, 0, 19）、东边阳台（14, 0, 10）。数字代表的是房间内部的局部坐标，(0, 0, 0) 是房间的原点。

连接器对接的几何原理

两个连接器要能对接，必须满足一个条件：朝向相反。

直观理解：如果房间 A 的连接器朝南（SOUTH），那它期望南边有东西可以接。房间 B 要接上去，它的连接器必须朝北（NORTH），这样两个房间才是"面对面"的。

复制代码

        房间 A                              房间 B
   ┌─────────────┐                    ┌─────────────┐
   │             │                    │             │
   │             ├── SOUTH    NORTH ──┤             │
   │             │      ↓      ↑      │             │
   └─────────────┘      └──────┘      └─────────────┘
                        对接点

判断两个方向是否相反的代码：

kotlin 复制代码

fun isOpposite(a: Direction, b: Direction): Boolean {
    return when (a) {
        Direction.NORTH -> b == Direction.SOUTH
        Direction.SOUTH -> b == Direction.NORTH
        Direction.EAST -> b == Direction.WEST
        Direction.WEST -> b == Direction.EAST
        Direction.UP -> b == Direction.DOWN
        Direction.DOWN -> b == Direction.UP
    }
}

对接时，两个连接器的世界坐标需要相邻。假设房间 A 的连接器在世界坐标 (100, 64, 200)，朝向 SOUTH，那么房间 B 的连接器应该在 (100, 64, 201)——刚好在 A 连接器的南边一格——且朝向 NORTH。

计算"某个方向的邻接坐标"：

kotlin 复制代码

fun directionVector(direction: Direction): Vector3i {
    return when (direction) {
        Direction.NORTH -> Vector3i(0, 0, -1)
        Direction.SOUTH -> Vector3i(0, 0, 1)
        Direction.EAST -> Vector3i(1, 0, 0)
        Direction.WEST -> Vector3i(-1, 0, 0)
        Direction.UP -> Vector3i(0, 1, 0)
        Direction.DOWN -> Vector3i(0, -1, 0)
    }
}

// 锚点连接器的世界坐标 + 朝向偏移 = 目标位置
val targetPos = anchorConnector.worldPos + directionVector(anchorConnector.direction)
// 如果一个新房间的连接器放在 targetPos 这个位置，那么我们就可以判断这两个房间是可以连接的

标签系统：更精细的匹配规则

只用朝向判断有时不够用。

假设我们有"大门"和"小门"两种连接器，"大走廊"和"小走廊"两种房间。大门应该连大走廊，小门应该连小走廊，混搭会很奇怪（比如一个气派的城堡大门后面接着一条狭窄的矿道）。

怎么表达这种约束？给连接器加上"标签"（Tags）。

kotlin 复制代码

data class Connector(
    val id: String,
    val position: Vector3i,
    val direction: Direction,
    val tags: List<String> = emptyList()  // 新增
)

使用示例：

kotlin 复制代码

// 大厅的主入口，只接受"大型"连接
val mainGate = Connector(
    id = "main_gate",
    position = Vector3i(7, 0, 0),
    direction = Direction.SOUTH,
    tags = listOf("large", "grand")
)

// 侧门，接受"中型"或"小型"连接
val sideDoor = Connector(
    id = "side_door",
    position = Vector3i(14, 0, 10),
    direction = Direction.EAST,
    tags = listOf("medium", "small")
)

// 大走廊的入口
val largeCorridor = Connector(
    id = "entry",
    position = Vector3i(4, 0, 0),
    direction = Direction.SOUTH,
    tags = listOf("large")
)

// 小走廊的入口
val smallCorridor = Connector(
    id = "entry",
    position = Vector3i(2, 0, 0),
    direction = Direction.SOUTH,
    tags = listOf("small")
)

匹配逻辑变成：

kotlin 复制代码

fun canConnect(a: Connector, b: Connector): Boolean {
    // 朝向必须相反
    if (!isOpposite(a.direction, b.direction)) {
        return false
    }

    // 如果双方都没有标签，直接通过
    if (a.tags.isEmpty() && b.tags.isEmpty()) {
        return true
    }

    // 如果一方没有标签，也通过（无标签意味着"百搭"）
    if (a.tags.isEmpty() || b.tags.isEmpty()) {
        return true
    }

    // 双方都有标签，则至少要有一个共同标签
    return a.tags.any { it in b.tags }
}

这样 mainGate（tags: large, grand）可以连 largeCorridor（tags: large），但不能连 smallCorridor（tags: small）。

标签系统的好处是语义化和可扩展。想加新的约束？定义新标签就行。比如 "outdoor" 表示室外连接，"secret" 表示密道入口，"vertical" 表示垂直通道……

白名单与黑名单：精确控制

标签是软性的匹配规则。有时候我们需要更硬性的约束：

Boss 房的入口只能连走廊，不能直接连另一个 Boss 房
起始房间只能连普通房间，不能连终点房间
商店房间禁止出现在 Boss 房旁边

这些规则用标签很难表达（得给每种房间都打一堆标签，很快就会混乱）。更直接的方式是使用白名单和黑名单。

kotlin 复制代码

data class Connector(
    val id: String,
    val position: Vector3i,
    val direction: Direction,
    val tags: List<String> = emptyList(),
    val whitelist: List<String> = emptyList(),  // 只允许连接这些房间 ID
    val blacklist: List<String> = emptyList()   // 禁止连接这些房间 ID
)

白名单的语义是"如果非空，则只有名单上的房间才能连接"。黑名单的语义是"名单上的房间禁止连接"。

kotlin 复制代码

// Boss 房的入口
val bossEntrance = Connector(
    id = "entrance",
    position = Vector3i(12, 0, 0),
    direction = Direction.SOUTH,
    whitelist = listOf("corridor_large", "corridor_medium"),  // 只接受走廊
    blacklist = listOf("boss_arena")  // 不能连另一个 Boss 房
)

兼容性检查的完整逻辑：

kotlin 复制代码

fun compatible(
    anchor: Connector,       // 已放置房间的连接器
    target: Connector,       // 待连接房间的连接器
    targetRoomId: String     // 待连接房间的 ID
): Boolean {
    // 1. 朝向必须相反
    if (!isOpposite(anchor.direction, target.direction)) {
        return false
    }

    // 2. 检查锚点的白名单
    if (anchor.whitelist.isNotEmpty() && targetRoomId !in anchor.whitelist) {
        return false
    }

    // 3. 检查锚点的黑名单
    if (targetRoomId in anchor.blacklist) {
        return false
    }

    // 4. 检查目标的白名单（目标也可能限制谁能连它）
    if (target.whitelist.isNotEmpty() && anchor.roomId !in target.whitelist) {
        return false
    }

    // 5. 检查目标的黑名单
    if (anchor.roomId in target.blacklist) {
        return false
    }

    // 6. 标签匹配（如果都有标签的话）
    if (anchor.tags.isNotEmpty() && target.tags.isNotEmpty()) {
        if (anchor.tags.none { it in target.tags }) {
            return false
        }
    }

    return true
}

读者可能会注意到，检查是双向的——不仅锚点可以限制谁能连上来，待连接的房间也可以限制它能连到谁身上。这种双向约束让规则设计更灵活。

连接成功率：引入随机性

有些房间设计了多个连接器，但我们不希望每个连接器都被用上。比如一个十字路口房间有四个出口，但如果每个出口都接了房间，地牢会变得太密集、太复杂。

怎么让一些连接器"偶尔不工作"？加一个成功率字段：

kotlin 复制代码

data class Connector(
    // ...前面的字段
    val successChance: Double = 1.0  // 0.0 ~ 1.0，默认 100% 成功
)

生成时，即使找到了兼容的连接器配对，也要掷骰子：

kotlin 复制代码

fun tryConnect(anchor: Connector, target: Connector, random: Random): Boolean {
    // 先检查兼容性
    if (!compatible(anchor, target)) return false

    // 掷骰子
    if (random.nextDouble() > anchor.successChance) {
        return false  // 这次不连了
    }

    // 目标连接器也有自己的成功率
    if (random.nextDouble() > target.successChance) {
        return false
    }

    return true
}

把 successChance 设成 0.7 意味着这个连接器有 70% 的概率被使用，30% 的概率保持封闭（变成死胡同或墙）。

这个机制可以用来控制地牢的"稀疏程度"。全部设成 1.0，地牢会很密集；降低一些连接器的成功率，地牢会更开阔，有更多死胡同。

房间的完整定义

把前面的内容整合起来，一个房间的完整数据结构：

kotlin 复制代码

data class RoomDef(
    // 基本信息
    val id: String,                     // 唯一标识，如 "entrance_hall"
    val name: String,                   // 显示名称，如 "入口大厅"
    val type: RoomType,                 // 类型：ROOM, CORRIDOR, START, END, SPECIAL
    val structureFile: String,          // 结构文件路径

    // 几何信息
    val size: Vector3i,                 // 尺寸 (x, y, z)
    val origin: Vector3i = Vector3i(0, 0, 0),  // 旋转中心点

    // 连接信息
    val connectors: List<ConnectorDef>, // 连接器列表

    // 生成规则
    val weight: Int = 1,                // 权重，影响被选中的概率
    val occurrences: OccurrenceRange = OccurrenceRange(),  // 出现次数限制
    val depth: OccurrenceRange = OccurrenceRange()         // 深度限制
)

data class ConnectorDef(
    val id: String,
    val position: Vector3i,
    val direction: Direction,
    val tags: List<String> = emptyList(),
    val whitelist: List<String> = emptyList(),
    val blacklist: List<String> = emptyList(),
    val successChance: Double = 1.0
)

data class OccurrenceRange(
    val min: Int = 0,   // 至少生成几个
    val max: Int = 0    // 最多生成几个，0 表示不限
)

enum class RoomType {
    ROOM,      // 普通房间
    CORRIDOR,  // 走廊
    START,     // 起始房间
    END,       // 终点房间
    SPECIAL    // 特殊房间（宝箱、商店等）
}

几个字段需要解释：

type（房间类型）

不同类型的房间在生成逻辑中有特殊待遇：

START：起始房间，必须是第一个被放置的，且深度为 0
END：终点房间，通常放在最深处
CORRIDOR：走廊，在房间选择时有特殊逻辑（避免连续放走廊或连续放房间）
SPECIAL：特殊房间，生成时会优先保证被选中

origin（旋转中心）

房间可能需要旋转，旋转是绕着某个点进行的。默认是 (0, 0, 0)，即房间的角落。但有些房间绕中心旋转更自然（比如圆形竞技场），这时可以把 origin 设成房间的几何中心。

下一篇会详细讲旋转变换的数学。

weight（权重）

权重越高，这种房间被选中的概率越大。注意，权重不是概率——权重 2 不是说有 200% 的概率被选中，而是说在候选池里，这种房间的"份额"是别人的两倍。

后面讲房间选择策略时会详细展开。

occurrences（出现次数）

min = 0, max = 0：不限制（可以不出现，也可以出现任意次）
min = 1, max = 1：必须恰好出现一次（比如 Boss 房）
min = 2, max = 5：至少 2 次，最多 5 次

depth（深度限制）

深度是指房间距离起点有多远（经过几个房间）。

min = 0, max = 3：只能出现在前 4 层（深度 0~3）
min = 5, max = 0：只能出现在深度 5 及以后
min = 0, max = 0：不限制

这个机制可以实现"商店只在前期出现"、"Boss 只在后期出现"这样的设计意图。

配置文件示例

实际项目中，房间定义通常写成配置文件。以 YAML 为例：

yaml 复制代码

rooms:
  # 起始房间
  - id: entrance_hall
    name: 入口大厅
    type: START
    structure: structures/entrance_hall.nbt
    size: [15, 8, 15]
    origin: [7, 0, 7]
    connectors:
      - id: north_exit
        position: [7, 0, 14]
        direction: NORTH
        tags: [large]
      - id: east_exit
        position: [14, 0, 7]
        direction: EAST
        tags: [medium]
        successChance: 0.6

  # 走廊
  - id: stone_corridor
    name: 石质走廊
    type: CORRIDOR
    structure: structures/stone_corridor.nbt
    size: [5, 4, 12]
    origin: [2, 0, 6]
    weight: 3
    occurrences:
      min: 2
      max: 8
    connectors:
      - id: south_entry
        position: [2, 0, 0]
        direction: SOUTH
        tags: [medium, small]
      - id: north_entry
        position: [2, 0, 11]
        direction: NORTH
        tags: [medium, small]

  # Boss 房
  - id: boss_arena
    name: Boss 竞技场
    type: END
    structure: structures/boss_arena.nbt
    size: [25, 12, 25]
    origin: [12, 0, 12]
    occurrences:
      min: 1
      max: 1
    depth:
      min: 5
    connectors:
      - id: entrance
        position: [12, 0, 0]
        direction: SOUTH
        tags: [large]
        whitelist: [stone_corridor, grand_corridor]
        blacklist: [boss_arena]

  # 宝箱房
  - id: treasure_room
    name: 宝箱房
    type: SPECIAL
    structure: structures/treasure_room.nbt
    size: [9, 6, 9]
    origin: [4, 0, 4]
    weight: 2
    occurrences:
      max: 2
    connectors:
      - id: entrance
        position: [4, 0, 0]
        direction: SOUTH
        tags: [small, medium]

读者可以注意几个设计要点：

Boss 房的 depth.min = 5：保证它不会出现在前 5 层
Boss 房的 blacklist 包含自己：防止两个 Boss 房相连
走廊的 weight = 3：走廊被选中的概率是普通房间的 3 倍，让地牢更有"通道感"
宝箱房的 occurrences.max = 2：最多两个，稀缺才有价值

小结

这一篇讲了房间定义的核心概念：

连接器是房间对外暴露的"接口"，包含位置和朝向
两个连接器对接时，朝向必须相反
标签系统实现软性的匹配规则
白名单/黑名单实现硬性的约束
successChance 控制连接的随机性
type、weight、occurrences、depth 控制房间的生成规则

有了这套数据模型，接下来的问题是：怎么把两个房间真正"拼"到一起？这涉及坐标变换、旋转镜像、碰撞检测——下一篇的主题。

让房间"拼"起来

方向匹配、坐标变换、碰撞检测的实现

放置房间的本质问题

上一篇讲了连接器的概念：每个房间有若干"插口"，房间通过插口对接。这一篇要解决的问题是：给定一个已放置房间的连接器（锚点），怎么把新房间正确地接上去？

这个问题分三步：

找到兼容的连接器配对：新房间的哪个连接器可以对上锚点？
计算新房间的放置位置：新房间应该放在哪里，才能让两个连接器严丝合缝？
检测碰撞：新房间会不会和已有房间重叠？

如果只考虑"不旋转、不镜像"的简单情况，这三步都不难。但实际上，房间通常需要旋转（甚至镜像）才能接上去。

为什么需要旋转

考虑一个具体场景：

锚点连接器朝向 EAST（东），意味着它期望东边有房间接入。新房间有一个朝向 SOUTH（南）的连接器。

按照"朝向必须相反"的规则，EAST 的对面是 WEST，而新房间的连接器朝向 SOUTH，不匹配。

但如果把新房间顺时针旋转 90°，原来朝 SOUTH 的连接器就会变成朝 WEST，此时就能和朝 EAST 的锚点对接了。

复制代码

旋转前：                     旋转后（顺时针 90°）：

    N                              N
    │                              │
 W──┼──E  连接器朝 S            W──┼──E  连接器朝 W
    │          ↓                   │          ←
    S                              S

所以，放置房间时需要遍历所有可能的旋转角度（0°、90°、180°、270°），找到一个能让连接器方向匹配的旋转。

方向的旋转变换

Minecraft 世界是离散的，旋转只能是 90° 的整数倍。顺时针旋转 90° 时，各个方向的变换关系是：

原方向	旋转后方向
NORTH	EAST
EAST	SOUTH
SOUTH	WEST
WEST	NORTH
UP/DOWN	不变

这个映射很简单，用 when 表达式就能实现。旋转 180° 就是调用两次 90° 旋转，270° 就是三次。

坐标的旋转变换

方向变了，连接器的位置也要跟着变。

假设房间尺寸是 (sizeX, sizeY, sizeZ) = (10, 5, 8)，有一个连接器在局部坐标 (7, 0, 0)。顺时针旋转 90° 后，这个连接器会跑到哪里？

直观理解：顺时针旋转 90° 相当于"原来的 Z 轴变成新的 X 轴，原来的 X 轴反向变成新的 Z 轴"。

核心公式（顺时针旋转 90°）：

复制代码

x' = z
y' = y（高度不变）
z' = sizeX - 1 - x

为什么 z' = sizeX - 1 - x 而不是 -x？因为旋转后房间的尺寸也变了——原来的 sizeX 变成了新的 sizeZ。为了保持坐标在房间范围内（非负），需要这样调整。

四种旋转的变换公式：

旋转角度	变换公式
0°	`(x, y, z)`
90°	`(z, y, sizeX - 1 - x)`
180°	`(sizeX - 1 - x, y, sizeZ - 1 - z)`
270°	`(sizeZ - 1 - z, y, x)`

镜像变换

除了旋转，有时还需要镜像。比如一个"L 形"房间，镜像后可以变成"反 L 形"，增加了布局的多样性。

镜像通常沿 X 轴进行（左右翻转）：

坐标变换：x' = sizeX - 1 - x，Y 和 Z 不变
方向变换：EAST ↔ WEST，其他不变

重要：如果同时需要旋转和镜像，顺序是先镜像、后旋转。

计算房间放置位置

现在可以回到最初的问题：给定锚点连接器，把新房间接上去。

假设：

锚点连接器在世界坐标 anchorWorldPos，朝向 anchorDir
新房间有一个连接器，局部坐标 connectorLocalPos
经过变换后，连接器朝向变成了 anchorDir 的反方向

推导过程：

计算变换后连接器的局部坐标 transformedPos
连接器需要放在锚点的"对面"，即 targetPos = anchorWorldPos + directionVector(anchorDir)
房间原点 = targetPos - transformedPos

一个直观的例子

假设我们有：

锚点在世界坐标 (100, 64, 200)，朝向 EAST
新房间尺寸 (10, 5, 8)，有一个连接器在局部坐标 (0, 0, 4)，朝向 WEST

因为 EAST 和 WEST 是相反的，这个连接器不需要旋转就能匹配。

计算放置位置：

变换后连接器位置 = (0, 0, 4)（没旋转，不变）
目标位置 = (100, 64, 200) + (1, 0, 0) = (101, 64, 200)
房间原点 = (101, 64, 200) - (0, 0, 4) = (101, 64, 196)

验证：房间原点在 (101, 64, 196)，连接器在房间内的 (0, 0, 4)，所以连接器的世界坐标是 (101, 64, 200)。这刚好在锚点东边一格，符合预期。

碰撞检测

算出房间位置后，还要检查会不会和已放置的房间重叠。

最简单的方法是用轴对齐包围盒（AABB） 检测。每个房间占据一个长方体区域，检查两个长方体是否相交：

kotlin 复制代码

data class AABB(val min: Vector3i, val max: Vector3i) {
    fun intersects(other: AABB): Boolean {
        // 在任意轴上完全分离则不相交
        if (max.x < other.min.x || min.x > other.max.x) return false
        if (max.y < other.min.y || min.y > other.max.y) return false
        if (max.z < other.min.z || min.z > other.max.z) return false
        return true
    }
}

注意旋转后包围盒也变了。原来 (10, 5, 8) 的房间，旋转 90° 后变成 (8, 5, 10)。计算时需要把房间的 8 个角点都变换一下，然后取最小/最大值得到新的包围盒。

完整的放置流程

把前面的内容串起来，尝试在锚点处放置房间的逻辑是：

遍历所有可能的 旋转×镜像×连接器 组合
对每个组合：
- 计算变换后的连接器方向，检查是否和锚点相反
- 检查标签、白名单、黑名单等兼容性
- 计算房间放置位置
- 计算包围盒，检测碰撞
找到第一个不碰撞的方案就返回成功
都不行就返回失败

四种布局算法，四种风格

蔓延式、主干分支式、网格迷宫式、随机游走式的原理与实现

布局引擎在做什么

前几篇讲了怎么定义房间、怎么把两个房间接起来。但"按什么顺序、什么规则接"——这是布局引擎的职责。

布局引擎的输入是：

房间池：有哪些房间可用
生成配置：要生成多少房间、有什么约束

输出是：

房间放置列表：每个房间放在哪、旋转多少度
连接关系列表：哪些房间之间有通道

不同的布局算法会产生风格迥异的地牢。笔者实现了四种：

算法	特点	适合场景
蔓延式（Minecrafty）	像藤蔓一样向外扩展	自由探索型地牢
主干分支式（Branching）	先拉主干，再长分支	有流程感的关卡
网格迷宫式（GridMaze）	先生成迷宫拓扑，再填房间	经典迷宫
随机游走式（RandomWalk）	随机方向扩展	洞穴、矿井

下面逐一展开。

蔓延式布局（Minecrafty）

核心思想

从起始房间开始，用 BFS（广度优先搜索） 的方式向外扩展。每次从队列里取出一个房间，遍历它的未使用连接器，尝试在每个连接器上接新房间。新房间再入队，继续扩展。

这种算法生成的地牢像藤蔓或树根，从起点向四面八方蔓延，没有明显的"主线"。

算法流程

复制代码

1. 放置起始房间，加入队列
2. while 队列不空 且 房间数未达标:
   a. 取出队首房间
   b. 遍历其未使用的连接器
   c. 对每个连接器，尝试放置新房间
   d. 成功则标记连接器为已用，新房间入队
3. 返回布局结果

特点

优点：

实现简单，容易理解
生成结果自然，没有刻意的痕迹
天然支持各种房间尺寸混搭

缺点：

没有"主线"的概念，不太适合有明确流程的关卡
可能生成很"散"的布局

生成效果示意

复制代码

        ┌───┐
        │ R │
    ┌───┼───┼───┐
    │ R │ R │ R │
┌───┼───┼───┼───┘
│ R │ S │ R │
└───┼───┼───┘
    │ R │
    └───┘

S = 起始房间，从 S 向四周蔓延

主干分支式布局（Branching）

核心思想

分两个阶段：

生成主干：从起始房间出发，尽量往一个方向走，形成一条"主路"
生成分支：从主干上随机挑几个房间，各自向外延伸若干步

这种布局有清晰的主线，玩家可以沿主干一路推进，分支提供额外的探索内容。

关键参数

trunkMin/trunkMax：主干房间数范围
branchCount：分支条数
branchDepth：每条分支的长度
straightness：直走倾向（0~1），越高主干越直

算法流程

复制代码

阶段一：生成主干
1. 放置起始房间
2. 循环直到达到主干目标长度:
   a. 选择一个连接器（优先选和上一步方向相同的）
   b. 放置新房间
   c. 记录方向，继续

阶段二：生成分支
1. 从主干随机选若干房间作为分支起点
2. 对每个起点，用类似的方式延伸若干步

straightness 参数的效果

straightness = 1.0：主干几乎是直线

复制代码

S ─ T ─ T ─ T ─ T ─ T ─ E

straightness = 0.3：主干会拐弯

复制代码

生成效果示意

复制代码

                        ┌───┐
                        │ B │  ← 分支末端
                        └─┬─┘
                          │
┌───┬───┬───┬───┬───┬───┬─┴─┬───┐
│ S │ T │ T │ T │ T │ T │ T │ E │  ← 主干
└───┴───┴─┬─┴───┴───┴───┴───┴───┘
          │
        ┌─┴─┐
        │ B │  ← 另一条分支
        └───┘

S: 起始房间 E:结束房间

网格迷宫式布局（GridMaze）

核心思想

这种方法分两步：

在抽象网格上生成迷宫：用经典的迷宫生成算法（DFS、Prim 等）在一个 N×M 的网格上生成迷宫拓扑
把格子替换成实际房间：遍历网格，在每个格子位置放置房间，根据通道关系连接

这种方法的好处是可以复用大量成熟的迷宫算法，而且生成的地牢有经典的"迷宫感"。

算法流程

复制代码

1. 根据目标房间数计算网格尺寸
2. 用迷宫算法生成网格拓扑（哪些格子之间有通道）
3. BFS 遍历网格:
   a. 对每个格子，放置一个房间
   b. 根据迷宫拓扑中的通道关系连接房间
4. 返回布局结果

不同迷宫算法的"性格"

DFS：长走廊、少分岔，像蛇

复制代码

┌─────────────┐
│ ┌─────┐ ┌─┐ │
│ │ ┌─┐ │ │ │ │
│ │ │ └─┘ │ │ │
│ │ └─────┘ │ │
│ └─────────┘ │
└─────────────┘

Prim：短走廊、多分岔，均匀扩散

复制代码

┌─┬───┬─┬───┐
│ │   │ │   │
├─┼─┬─┼─┴─┬─┤
│   │     │ │
├───┼─┬───┼─┤
│   │ │   │ │
└───┴─┴───┴─┘

下一篇会详细讲各种迷宫算法的区别。

随机游走式布局（RandomWalk）

核心思想

从起始位置开始，每一步随机选择一个方向扩展。已占用的位置不能重复占用，走不动了就换个位置继续。

这种算法生成的布局非常不规则，像是有机生长的洞穴或蚁穴。

关键参数

boundaryBias：边界偏好（0~1）
- 接近 1.0：倾向于从"边界"节点扩展，生成更蔓延的形状
- 接近 0.0：从任意已有节点扩展，生成更紧凑的团块

算法流程

复制代码

1. 放置起始节点，加入边界列表
2. while 节点数未达标:
   a. 根据 boundaryBias 选择扩展起点（边界 or 任意）
   b. 随机选一个未占用的相邻方向
   c. 在那个方向放置新节点
   d. 更新边界列表
3. 把抽象节点替换成实际房间

boundaryBias 的效果

boundaryBias = 0.9：从边缘扩展，形成触手状

复制代码

      ┌───┐
      │   │
  ┌───┼───┘
  │   │
┌─┴─┬─┴─┐
│ S │   │
└───┴───┴───┐
            │
        ┌───┴───┐
        │       │
        └───────┘

boundaryBias = 0.3：更紧凑的团块

复制代码

┌───┬───┬───┐
│   │   │   │
├───┼───┼───┤
│   │ S │   │
├───┼───┼───┤
│   │   │   │
└───┴───┴───┘

如何选择布局算法

没有"最好"的算法，只有"最合适"的算法：

场景	推荐算法
有主线剧情的副本	主干分支式
自由探索的地牢	蔓延式
经典迷宫、解谜关卡	网格迷宫式
洞穴、蚁穴、矿井	随机游走式

也可以组合使用。比如用主干分支式生成主体结构，然后用随机游走式在某些区域生成洞穴。

迷宫算法小百科

DFS、Prim、Kruskal、Sidewinder 等算法的原理与特点

为什么要了解迷宫算法

上一篇提到，网格迷宫式布局会先在抽象网格上生成迷宫拓扑，再把格子替换成房间。迷宫的"形状"直接决定了地牢的体验：

长走廊多还是短走廊多？
死胡同多还是岔路多？
是均匀分布还是有明显的"主路"？

不同的迷宫生成算法会产生截然不同的结果。了解每种算法的特点，才能为你的地牢选择最合适的"性格"。

迷宫的本质：生成树

在讲具体算法之前，先理解一个关键概念：完美迷宫是网格图的一棵生成树。

把迷宫想象成一个网格，每个格子是一个节点，相邻格子之间可能有墙或通道。

"完美迷宫"是指：

任意两个格子之间恰好有一条路径（没有环路）
所有格子都是连通的

这正是"树"的定义——连通且无环。所以，生成迷宫就是在网格图上选择一些边，使得这些边构成一棵生成树。不同的选择策略就是不同的迷宫算法。

DFS 生成树

原理

从一个随机格子开始，沿着一个方向一直走，直到走不动了（周围都是已访问的格子），然后回溯到上一步，尝试其他方向。这就是"深度优先"的含义——先走到尽头，再回头。

算法流程

复制代码

1. 从随机位置开始，入栈
2. while 栈不空:
   a. 取栈顶节点
   b. 获取其未访问的邻居（随机打乱）
   c. 如果有邻居：选第一个，打通墙，入栈
   d. 如果没邻居：出栈（回溯）

特点

长走廊：因为总是沿一个方向走到底
少分岔：只有回溯时才会产生分岔
"河流"风格：像蜿蜒的河流，主干明显

生成效果

复制代码

┌─────────────────────┐
│ ┌───────────┐ ┌───┐ │
│ │ ┌───────┐ │ │   │ │
│ │ │ ┌───┐ │ │ │ │ │ │
│ │ │ │   │ │ │ │ │ │ │
│ │ │ └─┘ │ │ │ │ │ │ │
│ │ └─────┘ │ └─┘ │ │ │
│ └─────────┴─────┘ │ │
└───────────────────┘ │

很适合做需要"一路深入"的地牢。

随机化 Prim 生成树

原理

维护一个"边界墙"列表。开始时把起点的所有墙加入列表。每次随机选一面墙，如果墙另一边的格子没访问过，就打通这面墙，并把新格子的墙加入列表。

和 DFS 的区别：DFS 总是从当前位置出发，Prim 从所有边界墙中随机选择。这导致 Prim 的扩展更"均匀"。

算法流程

复制代码

1. 从随机位置开始，把其邻居加入边界列表
2. while 边界列表不空:
   a. 随机选一条边界边
   b. 如果目标未访问：打通墙，把新节点的邻居加入边界
   c. 否则跳过

特点

短走廊：因为每次从所有边界中随机选择
多分岔：扩展比较均匀，岔路口多
"爆炸"风格：从中心向四周均匀扩散

生成效果

复制代码

┌─┬───┬─┬───┬─┐
│ │   │ │   │ │
├─┼─┬─┴─┼─┬─┴─┤
│   │   │ │   │
├─┬─┼───┼─┴─┬─┤
│ │ │   │   │ │
├─┴─┼─┬─┴───┼─┤
│   │ │     │ │
└───┴─┴─────┴─┘

很适合需要频繁做选择的迷宫。

随机化 Kruskal 生成树

原理

借鉴最小生成树的 Kruskal 算法。一开始，每个格子各自为一个集合。把所有潜在的墙放入列表并打乱。依次取出每面墙，如果墙两边的格子属于不同集合，就打通墙并合并集合。

需要用到并查集优化来高效判断和合并集合。

特点

均匀分布：边是随机选择的，没有从某个点扩散的感觉
中等走廊长度：介于 DFS 和 Prim 之间
"公平"风格：每条边被选中的概率相等

和 Prim 的对比

Prim 从一个点向外扩展，有"中心"的感觉。Kruskal 没有中心，边是完全随机选择的。Kruskal 的结果往往更"杂乱"。

Binary Tree 二叉树算法

原理

遍历每个格子，对于每个格子，随机选择"向南"或"向东"（二叉链表）打通墙壁。

之所以叫"二叉树"，是因为生成的迷宫可以看作一棵每个节点最多有两个子节点的树。

生成效果

复制代码

┌───────────────────┐
│                   │
├───┬───┬───┬───┬───┤
│   │   │   │   │   │
├───┼───┼───┼───┼───┤
│   │   │   │   │   │
└───┴───┴───┴───┴───┘

这种偏向性对于某些游戏设计来说是缺点，但如果你想要有偏向性（比如引导玩家向某个方向走），反而是优点。

Sidewinder 侧风算法

原理

一行一行地处理。在每一行内，维护一个"当前组"。对于每个格子：

掷硬币决定是否"结束当前组"
如果结束，从当前组里随机选一个格子向南打通墙，然后开始新组
如果不结束，向东打通墙

第一行特殊处理：永远向东打通墙。

特点

水平偏好：走廊倾向于水平延伸
第一行是通廊：整个第一行是打通的
比 Binary Tree 更均匀：没有那么明显的对角线偏好

生成效果

复制代码

┌───────────────────┐
│                   │  ← 第一行完全打通
├───────┬───────┬───┤
│       │       │   │
├───┬───┴───┬───┴───┤
│   │       │       │
└───┴───────┴───────┘

适合需要"横向探索"感的地牢。

Growing Tree 生长树算法

原理

维护一个"活跃节点"列表。每次从列表中选一个节点，把它的一个未访问邻居加入迷宫。如果某个节点没有未访问邻居了，就移除。

关键在于怎么从列表中选节点：

总是选最后一个（最新的）→ 等价于 DFS
总是选第一个（最老的）→ 等价于 BFS
随机选 → 等价于 Prim
混合策略 → 可调节的特性

特点

可调节：通过改变选择策略，可以得到从 DFS 到 Prim 之间的任何特性
实验友好：调参看效果很方便

选择策略的影响

策略	效果
总是选最新	≈ DFS，长走廊
总是选最老	≈ BFS，短走廊
总是随机	≈ Prim，短走廊、多分岔
50% 最新 + 50% 随机	中等走廊长度

算法对比总结

算法	走廊长度	死胡同	方向偏好	复杂度	适合场景
DFS	长	少	无	O(n)	蜿蜒的河流式地牢
Prim	短	多	无	O(n log n)	频繁做选择的迷宫
Kruskal	中等	中等	无	O(n log n)	无明显特征的迷宫
Binary Tree	中等	多	强（东南）	O(n)	引导向特定方向
Sidewinder	长（水平）	中等	水平	O(n)	横向探索地牢
Growing Tree	可调	可调	无	O(n)	需要精细调控时

不是随便选房间的

权重系统、深度约束、出现次数控制——让生成结果符合设计意图

房间选择的挑战

前面几篇讲了怎么把房间拼起来、怎么组织布局结构。但有一个问题被略过了：在某个位置放房间时，从房间池里选哪一个？

如果完全随机选择，会出现各种问题：

Boss 房可能出现在第一层
同一种房间可能出现 10 次
商店可能在地牢最深处
所有房间都是走廊

程序化生成的核心矛盾是：随机性带来变化，但可控性保证设计意图。房间选择策略就是在这两者之间找平衡。

笔者实现了四种控制机制：权重、深度约束、出现次数限制、类型偏好。

权重系统

基本概念

每种房间有一个"权重"值，权重越高，被选中的概率越大。

但注意，权重不是概率。如果房间 A 的权重是 3，房间 B 的权重是 1，不是说 A 有 300% 的概率被选中。而是说 A 的"份额"是 B 的三倍——A 有 75%（3/4）的概率被选中，B 有 25%（1/4）。

加权随机选择

算法很简单：

计算所有候选的权重总和
生成一个 0 到总和之间的随机数
依次累加权重，当累加值超过随机数时，选中当前候选

权重提升机制

如果某种房间设置了"最少出现 N 次"，但当前数量还不够，它的有效权重会被提升。

举个例子：宝箱房权重是 2，要求至少出现 2 次。如果还没出现过，有效权重 = 2 × 3 = 6（boost 系数 = 3）。

这样可以保证"必须出现"的房间有更高概率被选中。

深度约束

什么是深度

"深度"是指房间距离起点有多远，以房间数量计。起始房间的深度是 0，直接连着它的深度是 1，以此类推。

复制代码

[起始] → [走廊] → [大厅] → [宝箱] → [Boss]
  0        1        2        3        4

为什么需要深度约束

关卡设计中，不同类型的房间应该出现在不同的阶段：

商店应该在前期，让玩家有机会购买装备
Boss 房应该在后期，作为最终挑战
休息点可以出现在中期，给玩家喘息机会

深度约束就是告诉生成器"这种房间只能出现在深度 X 到 Y 之间"。

配置示例

yaml 复制代码

rooms:
  - id: shop
    depth:
      min: 1
      max: 3   # 只在深度 1~3 出现

  - id: boss_arena
    depth:
      min: 5   # 只在深度 5 及以后出现
      max: 0   # 0 表示无上限

出现次数限制

每种房间可以设置出现次数的上下限：

min：至少出现几次。如果没达到，权重会被提升。
max：最多出现几次。达到后，这种房间不再参与选择。

特殊房间的强制保证

有些房间是"必须出现"的，比如 Boss 房。如果布局算法跑完了，Boss 房还没出现怎么办？

策略一：预选机制

在生成开始前，先确定要用哪些房间。预选时强制包含必须出现的房间。

策略二：替换机制

如果必须出现的房间没被放置，从已放置的房间中替换一个普通房间。

类型偏好：走廊的特殊处理

问题：走廊连走廊

如果不做特殊处理，可能出现这种情况：

复制代码

[房间] → [走廊] → [走廊] → [走廊] → [走廊] → [房间]

四个走廊连在一起，玩家跑很久都遇不到有内容的房间，体验很差。

解决方案：走廊偏好机制

当从走廊出发时，优先选择非走廊房间。当从非走廊房间出发时，优先选择走廊。

这样生成的布局会呈现"房间-走廊-房间-走廊"的节奏，更加舒适。

完整的房间选择流程

把前面的机制串起来：

复制代码

1. 获取所有候选房间
2. 排除起始房间（深度 > 0 时）
3. 应用深度过滤
4. 应用出现次数过滤
5. 应用连接器白名单/黑名单
6. 应用走廊偏好
7. 检查是否需要优先放置特殊房间
8. 加权随机选择

加点环路

打破树形结构，让地牢更有探索感

树形结构的问题

前面讲的布局算法——无论是蔓延式、主干分支式还是迷宫式——生成的都是树形结构。树形结构有一个特点：任意两个房间之间只有一条路径。

这意味着：

玩家不能"绕路"
错过的房间必须原路返回
没有捷径、没有惊喜
探索感较弱

现实中的地下城往往不是树形的。可能有暗门通向之前去过的地方，可能有多条路线通往同一个目的地。这种"环路"让探索更有乐趣。

什么是环路

环路是指地牢中存在多条路径连接同一对房间。换句话说，布局图中有"环"。

复制代码

没有环路（树形）：

A ─ B ─ C
    │
    D ─ E

A 到 E 只有一条路：A→B→D→E

有环路：

A ─ B ─ C
│   │
D ─ E

A 到 E 有两条路：A→B→D→E 或 A→D→E

添加环路的时机

环路应该在基础布局生成之后添加。原因：

基础布局算法生成的是生成树，保证连通性
在此基础上添加额外的边，不会破坏连通性，只会增加路径选择

寻找可以添加环路的位置

思路：遍历所有房间的未使用连接器，看有没有刚好"对上"的——位置相邻、方向相反、但目前没有连接。

具体步骤：

建立 位置→连接器 的映射
遍历所有未使用的连接器
计算"对面"的位置（连接器位置 + 方向向量）
看那个位置有没有方向相反、也未使用的连接器
如果有，这就是一个可以添加环路的候选

添加环路连接

找到候选位置后，根据概率决定是否添加：

复制代码

1. 找到所有候选位置，打乱顺序
2. for 每个候选:
   a. 如果已添加数量达到上限，停止
   b. 掷骰子，如果 > loopChance，跳过
   c. 检查兼容性（白名单、黑名单）
   d. 添加连接，标记连接器为已使用

参数调节

两个关键参数：

loopChance（环路概率）

每个候选位置有多大概率被添加环路。

0.05 ~ 0.10：少量环路，基本保持树形结构
0.10 ~ 0.20：适中，有一些捷径但不会迷路
0.20 ~ 0.50：大量环路，迷宫感强烈

maxLoops（最大环路数）

最多添加几条额外连接。可以设为 0 表示不限制（由概率决定）。

笔者的建议：对于 10~15 个房间的地牢，1~3 个环路比较合适。

环路的游戏设计意义

环路不只是技术实现问题，它影响玩家体验：

捷径

玩家打通一条密道后可以快速回到之前的区域。这在需要多次往返的关卡设计中很有用。

包抄

在有怪物的地牢里，环路让玩家可以绕后偷袭，增加战术深度。

迷路

环路太多会让玩家分不清方向。如果这是你想要的（恐怖游戏？），环路就是好东西；如果不是，要控制数量。

惊喜

"咦，这条路通到这里来了！"这种发现感是线性地牢给不了的。

特殊房间怎么保证放进去

起点、终点、Boss 房的放置逻辑

特殊房间的特殊在哪

在房间定义中，有几种类型是"特殊"的：

START（起点）：玩家进入地牢的第一个房间
END（终点）：地牢的最终目标，通常是 Boss 房或出口
SPECIAL：宝箱房、商店、神殿等有特殊功能的房间

这些房间之所以特殊，是因为它们有硬性要求：

起点必须是第一个放置的房间
终点必须存在且位于合理位置
特殊房间必须出现（设计师说要有宝箱，就得有宝箱）

普通房间可以随机选择、可多可少。特殊房间不行——它们是地牢设计的"锚点"。

起点房间的处理

起点的处理相对简单：它永远是第一个被放置的房间。

流程：

从起点候选池中随机选择一个
放在原点 (0, 0, 0)，不旋转、不镜像
起点房间的深度永远是 0

终点房间的处理

终点的处理复杂一些。我们希望终点：

位于地牢的"尽头"——最好是最深处
不要出现在前几层
如果配置了特定的终点房间，必须使用它

策略一：在生成过程中放置

在房间选择时，当接近目标数量时，优先选择终点房间。

具体做法：

如果 placedCount >= targetCount - 1，允许放置终点
如果允许且还没放终点，优先从终点候选中选择

策略二：后处理——选择最远叶子

如果生成完毕后发现没有终点房间，可以把"最远的叶子节点"改造成终点。

"叶子节点"是指只有一个连接的房间（死胡同）。"最远"是指深度最大。

流程：

检查是否已有终点房间，有则跳过
用 BFS 计算每个房间的深度
找到所有叶子节点（连接数 ≤ 1）
选择深度最大的叶子，标记为终点

特殊房间（SPECIAL）的保证

特殊房间（宝箱、商店等）的处理策略是预选保证 + 权重提升。

预选阶段

在生成开始前，先确定要放置哪些房间。这时强制包含特殊房间：

复制代码

1. 强制包含 SPECIAL 类型的房间
2. 确保有起点和终点
3. 补充其他房间到目标数量

生成阶段的优先处理

在选择下一个房间时，如果有特殊房间还没放，优先放特殊房间。

终点放置位置的优化

主干末端策略（用于 Branching 布局）

在主干分支布局中，可以把终点放在主干的末端，而不是随便哪个叶子。这样保证玩家沿主干走到底就能到达终点。

分支末端策略

也可以让终点出现在某条分支的末端，增加探索感。需要玩家找到正确的分支才能到达终点。

配置中可以指定：

yaml 复制代码

branching:
  trunkMin: 6
  trunkMax: 10
  endRooms: [boss_arena]  # 这些房间放在分支末端

调试：检查特殊房间是否正确放置

生成完成后，做一个验证检查：

检查起点：有且只有一个
检查终点：至少有一个
检查特殊房间：minOccurrences > 0 的房间是否都放置了

如果验证失败，输出警告或重新生成。

把布局变成真正的方块

从布局数据到 Minecraft 世界的落地实现

布局结果是什么

前面八篇讲的都是"怎么规划布局"。布局引擎跑完后，输出的是一份数据：

kotlin 复制代码

data class LayoutResult(
    val placements: List<RoomPlacement>,     // 房间放置列表
    val connections: List<RoomConnection>    // 房间连接列表
)

data class RoomPlacement(
    val roomId: String,       // 房间定义 ID
    val placementId: String,  // 放置实例 ID
    val origin: Vector3i,     // 世界坐标原点
    val rotation: Int,        // 旋转角度
    val mirror: Boolean       // 是否镜像
)

这份数据告诉我们"哪个房间放在哪、旋转多少度"，但还没有真正的方块。

这一篇讲怎么把这份"图纸"变成 Minecraft 里实实在在的建筑。

结构数据的存储格式

每个房间对应一个"结构文件"，里面存储了房间的方块信息。常见格式有：

Minecraft NBT 结构

原版 Minecraft 的结构方块可以保存为 .nbt 文件。这是最通用的格式，包含：

方块调色板（palette）
方块列表（blocks）
尺寸信息（size）

WorldEdit Schematic

WorldEdit 的 .schem 或 .schematic 格式在建筑师群体中更流行，因为 WorldEdit 更方便选区和保存。

自定义格式

如果有特殊需求（比如需要额外的元数据），也可以自定义格式。

坐标变换的再次应用

放置结构时，需要对每个方块应用旋转和镜像变换。

第三篇讲过的变换公式在这里再次派上用场：

方块位置需要变换
方块状态（朝向、连接状态等）也需要变换

比如一个朝北的门，旋转 90° 后应该朝东。Minecraft 提供了 BlockState.rotate() 和 BlockState.mirror() 方法来处理这个。

基础放置实现

最简单的放置方式——直接遍历方块，逐个设置：

复制代码

for 每个方块 in 结构:
    1. 变换坐标
    2. 计算世界坐标 = origin + 变换后坐标
    3. 变换方块状态
    4. 放置方块

这种方式简单直接，但有性能问题——大量方块操作会卡主线程。

性能优化

问题分析

一个中等大小的房间可能有几千个方块。一个地牢有十几个房间，就是几万个方块操作。

在 Minecraft 服务端，方块操作涉及：

区块加载
方块更新事件
光照重算
红石更新
客户端同步

每个方块都触发这些流程，性能会非常差。

方案一：批量操作（太复杂）

先收集所有方块更改，然后批量应用，禁用物理和光照更新。完成后统一重算光照。

方案二：WorldEdit / FAWE

WorldEdit（特别是其异步分支 FAWE）专门优化了大量方块操作。如果服务器装了 WorldEdit，可以借用它的能力。

FAWE 的优势是异步执行，不会卡主线程。但要注意它的异步特性——放置完成的时机和主线程不同步。

运行时数据构建

方块放置完成后，还需要建立一些运行时数据供游戏逻辑使用：

kotlin 复制代码

data class ProceduralRuntimeGraph(
    val instanceId: UUID,                     // 副本实例 ID
    val dungeonId: String,                    // 地牢定义 ID
    val worldName: String,                    // 世界名称
    val rooms: List<RuntimeRoomNode>,         // 房间节点
    val connections: List<RuntimeConnection>  // 连接关系
)

这份数据用于：

判断玩家当前在哪个房间
触发房间进入/离开事件
管理门的开关状态
小地图显示

完整的生成流程

把前面的内容串起来：

复制代码

1. 规划布局
   - 创建 Planner，准备生成请求

2. 生成布局
   - 选择布局引擎（Minecrafty/Branching/GridMaze/RandomWalk）
   - 执行生成，得到 LayoutResult

3. 放置结构
   - 遍历 placements
   - 加载每个房间的结构文件
   - 应用变换，放置方块

4. 构建运行时数据
   - 计算每个房间的世界坐标包围盒
   - 构建连接器的世界坐标
   - 返回 RuntimeGraph

收尾与展望

一些补充话题和后续可以探索的方向

回顾

这个系列从"为什么需要程序化生成"讲起，覆盖了：

房间与连接器的数据模型
坐标变换与碰撞检测
四种布局算法
六种迷宫生成算法
房间选择策略
环路添加
特殊房间处理
结构放置

到这里，一个能用的程序化地牢生成系统已经完整了。但还有一些话题没有展开，这里做个补充。

锁钥系统

基本概念

在一些经典地牢游戏中，玩家需要找到钥匙才能打开对应的门。这种"锁钥系统"增加了探索的深度——不再是一路直冲终点，而是要四处搜寻。

在程序化生成中，锁钥系统的核心是依赖关系：

复制代码

获得银钥匙 → 打开银门 → 获得金钥匙 → 打开金门 → Boss

实现思路

在连接器上定义门类型：

kotlin 复制代码

data class DoorDef(
    val type: String,       // 门类型：NORMAL, LOCKED, ONE_WAY
    val keyItemId: String?  // 如果是锁门，需要什么钥匙
)

data class ConnectorDef(
    // ... 其他字段
    val door: DoorDef? = null
)

生成时，在某些连接上放置锁门，并确保钥匙在门的"前面"（即不穿过这扇门就能拿到）。

这个逻辑比较复杂，可以简化为：

标记某些房间为"钥匙房"，某些连接为"锁门"
生成时确保钥匙房的深度小于对应锁门的深度

运行时管理

门的状态需要在运行时追踪：

kotlin 复制代码

class DoorManager {
    private val doorStates = mutableMapOf<String, DoorState>()

    fun tryOpen(playerId: UUID, doorId: String): Boolean {
        val door = doorStates[doorId] ?: return false

        if (door.isLocked) {
            // 检查玩家是否有钥匙
            if (playerHasKey(playerId, door.keyItemId)) {
                door.isLocked = false
                consumeKey(playerId, door.keyItemId)
                return true
            }
            return false
        }

        return true
    }
}

调试技巧

程序化生成的调试比普通代码更难——每次运行结果都不一样。这里分享一些技巧。

固定随机种子

最重要的调试手段。给生成器传入固定的种子，保证每次生成结果相同。

kotlin 复制代码

val config = ProceduralDef(
    seed = 12345L,  // 固定种子
    // ...
)

发现 bug 后，记下当时的种子，就能稳定复现。

打印生成日志

记录每一步的决策：

kotlin 复制代码

fun pickRoom(...) {
    log.debug("深度 $depth，候选房间: ${candidates.map { it.id }}")
    val chosen = pickWeightedRoom(candidates, ...)
    log.debug("选择: ${chosen?.id}")
    return chosen
}

可视化布局

把布局画出来，比盯着数字直观得多。一个简单的 ASCII 可视化：

kotlin 复制代码

fun visualizeLayout(layout: LayoutResult) {
    // 找到所有房间的坐标范围
    val minX = layout.placements.minOf { it.origin.x }
    val maxX = layout.placements.maxOf { it.origin.x + roomSize(it).x }
    // ... 类似处理 Z

    // 画一个 2D 俯视图
    for (z in minZ..maxZ) {
        for (x in minX..maxX) {
            val room = findRoomAt(layout, x, z)
            print(if (room != null) roomSymbol(room) else ".")
        }
        println()
    }
}

游戏内标记

用粒子或方块标记连接器位置，检查是否正确：

kotlin 复制代码

fun debugDrawConnectors(room: RuntimeRoomNode) {
    room.connectors.forEach { connector ->
        // 在连接器位置生成粒子
        world.spawnParticle(
            Particle.FLAME,
            connector.worldPos.x + 0.5,
            connector.worldPos.y + 0.5,
            connector.worldPos.z + 0.5,
            10
        )
    }
}

踩过的坑

生成的房间太少

可能原因：

碰撞太多：房间尺寸大，放不下。尝试缩小房间或增大生成区域。
连接器配置问题：方向、标签不匹配。检查连接器定义。
约束太严格：深度/出现次数限制太死。放宽约束。

某种房间从不出现

可能原因：

权重太低：其他房间权重太高，抢走了份额。
深度不匹配：房间的 depth 范围和实际生成的深度不重叠。
白名单/黑名单冲突：被连接器过滤掉了。

Boss 房出现在前面

可能原因：

没设置 depth.min：给 Boss 房加上最小深度限制。
预选逻辑问题：检查是否正确保证了终点房间放在后面。

房间重叠

这是 bug，检查：

碰撞检测逻辑：AABB 计算是否正确。
坐标变换：旋转后的包围盒是否正确计算。

扩展方向

这套系统还可以往很多方向扩展：

垂直地牢

目前的连接器只有水平方向（东西南北）。加入 UP/DOWN 方向，就能做多层地牢。

kotlin 复制代码

enum class Direction {
    NORTH, SOUTH, EAST, WEST,
    UP,    // 向上通道（楼梯、电梯）
    DOWN   // 向下通道
}

需要注意的是，垂直连接的"对齐"逻辑和水平不太一样。

多主题混合

一个地牢可以有多个"区域"，每个区域用不同的房间池。比如：

区域 1：石砖风格（深度 0~3）
区域 2：地狱岩风格（深度 4~7）
区域 3：末地风格（深度 8+）

实现上，可以根据深度切换房间池：

kotlin 复制代码

fun selectRoomPool(depth: Int): List<RoomDef> {
    return when {
        depth <= 3 -> stoneBrickRooms
        depth <= 7 -> netherRooms
        else -> endRooms
    }
}

动态难度

根据玩家表现调整生成参数。比如：

玩家死亡次数多 → 减少怪物房
玩家通关太快 → 增加迷宫复杂度

与其他系统联动

地牢生成只是开始。后续可以联动：

怪物生成：根据房间类型和深度决定刷什么怪
战利品系统：根据房间类型决定掉落
任务系统：在特定房间触发任务事件

在线生成

如果生成太慢，可以考虑：

预生成一批布局缓存起来
使用后台线程生成
流式生成（玩家还没到的区域慢慢生成）

这套方案的局限

这套方案也有局限：

不适合开放世界：适合封闭的副本地牢，不适合无边界的世界
房间尺寸差异大时不好看：一个 5×5 的房间和一个 50×50 的房间连在一起会很奇怪
没有自动生成走廊：走廊也是预制的房间，不是自动挖出来的
对美术资源依赖大：房间好不好看取决于预制结构的质量（现在知道为什么没图片了吧）

结语

程序化生成是一个深坑，这个系列只是入门。希望这个系列对读者有帮助。如果你真的做出了一个程序化地牢，欢迎分享。