MC 中的房间检测

楔子

故事要从我的一个家具模组说起：我想让空调在房间里积雪。

于是有了这套基于 BFS 的房间检测器。

实测数据？给你看个有劲儿的： [房间检测]（林地府邸） 完成: 39756 方块，用时 28ms。 对，四万方块级别，二十多毫秒！

源码地址：Github

---

一、目标

• 给定起点（玩家脚下、方块中心、或任意种子点），找到与其连通的“可通过体素空间”，作为候选房间。
• 构造层面规避“无限扩张”风险：限定搜索半径、限定体积、限定最大时长。
• 为“封闭/非封闭”的业务判定提供基础：房间轮廓、体积、是否触达边界等。

---

二、算法选型：为什么是 BFS

• BFS（广度优先搜索）天然适合“从一个种子点出发的连通空间增长”。
• 相比 DFS，BFS 没有栈深度风险，更适合大体积开放空间。
• 递归 Flood Fill 虽然写着顺手，但 JVM 栈深度 + 大体积图形，轻则爆栈，重则崩服。
• 我们只关心 6 邻域（上/下/左/右/前/后），与方块-体素的渲染/碰撞规则天然契合。

---

三、实现拆解（以 RoomDetector 为例）

主入口 findRoom

• 入参：Level level, BlockPos startPos

• 输出：Set<BlockPos>（连通的“可通过”方块集合，失败返回空集）

• 核心约束：

  1. 超时中断（maxSearchTimeMs）
  2. 最大体积（maxRoomSize）
  3. 分批检查（每 1000 方块检查一次）

• 其他关键点：

  • 边界盒：以起点为中心限定搜索半径（maxSearchDistance）
  • 区块安全：level.hasChunkAt(pos)，避免未加载区块
  • 可通过性判定：空气 / 流体 / OPEN=true 的方块

代码骨架（简化版，方便理解）：

long startTime = System.currentTimeMillis();

Set<BlockPos> visited = new HashSet<>(8192);
ArrayDeque<BlockPos> queue = new ArrayDeque<>(1024);
Set<BlockPos> roomBlocks = new HashSet<>(8192);

if (!isPassable(level, startPos)) return Collections.emptySet();

// 从配置读取约束
final int maxRadius = RoomDetectionConfig.maxSearchDistance;
final int maxVolume = RoomDetectionConfig.maxRoomSize;
final long maxTime = RoomDetectionConfig.maxSearchTimeMs;

// 构造边界盒
final int minX = startPos.getX() - maxRadius;
final int maxX = startPos.getX() + maxRadius;
final int minY = Math.max(level.getMinBuildHeight(), startPos.getY() - maxRadius);
final int maxY = Math.min(level.getMaxBuildHeight(), startPos.getY() + maxRadius);
final int minZ = startPos.getZ() - maxRadius;
final int maxZ = startPos.getZ() + maxRadius;

queue.offer(startPos);
visited.add(startPos);
roomBlocks.add(startPos);

int processed = 0;
while (!queue.isEmpty()) {
    if (++processed % 1000 == 0) {
        if (System.currentTimeMillis() - startTime > maxTime) return Collections.emptySet();
        if (roomBlocks.size() >= maxVolume) return Collections.emptySet();
    }

    var current = queue.poll();
    int x = current.getX(), y = current.getY(), z = current.getZ();

    // 六邻域扩张
    checkAndAdd(level, new BlockPos(x, y + 1, z), visited, queue, roomBlocks, minX, maxX, minY, maxY, minZ, maxZ);
    checkAndAdd(level, new BlockPos(x, y - 1, z), visited, queue, roomBlocks, minX, maxX, minY, maxY, minZ, maxZ);
    checkAndAdd(level, new BlockPos(x + 1, y, z), visited, queue, roomBlocks, minX, maxX, minY, maxY, minZ, maxZ);
    checkAndAdd(level, new BlockPos(x - 1, y, z), visited, queue, roomBlocks, minX, maxX, minY, maxY, minZ, maxZ);
    checkAndAdd(level, new BlockPos(x, y, z + 1), visited, queue, roomBlocks, minX, maxX, minY, maxY, minZ, maxZ);
    checkAndAdd(level, new BlockPos(x, y, z - 1), visited, queue, roomBlocks, minX, maxX, minY, maxY, minZ, maxZ);
}

邻接检查 checkAndAdd

• 越界拦截：不在边界盒直接返回
• 区块检查：未加载区块不推进
• 可通过判定：通过才入队

private static void checkAndAdd(Level level, BlockPos pos, Set<BlockPos> visited,
                                ArrayDeque<BlockPos> queue, Set<BlockPos> roomBlocks,
                                int minX, int maxX, int minY, int maxY, int minZ, int maxZ) {
    int x = pos.getX(), y = pos.getY(), z = pos.getZ();

    if (x < minX || x > maxX || y < minY || y > maxY || z < minZ || z > maxZ) return;

    if (visited.add(pos)) {
        if (!level.hasChunkAt(pos)) return;
        if (isPassable(level, pos)) {
            queue.offer(pos);
            roomBlocks.add(pos);
        }
    }
}

可通过性 isPassable

• 空气：通过
• 流体：通过
• 具 OPEN=true 的方块（如门）：通过

public static boolean isPassable(Level level, BlockPos pos) {
    BlockState state = level.getBlockState(pos);
    if (state.isAir()) return true;
    if (!state.getFluidState().isEmpty()) return true;
    return state.hasProperty(BlockStateProperties.OPEN) && state.getValue(BlockStateProperties.OPEN);
}

---

四、算法运行流程与关键细节

1. 流程图解

很多读者第一次看 BFS 可能有点抽象，先上一个流程图（ASCII 画），展示搜索的大致过程：

          起点
           │
           ▼
        入队列
           │
           ▼
       [循环开始]
           │
           ▼
         出队列
           │
           ▼
   ┌── 检查相邻 6 个方向 ──┐
   │                       │
   ▼                       ▼
 是否可通过？            否 → 忽略
   │
   ▼
 未访问过？─── 否 → 忽略
   │
   ▼
 入队列 + 标记已访问
           │
           ▼
   队列空 / 超时 / 超体积？
           │
       是 ─┴──→ 返回结果
       否
           │
           └──→ 回到 [循环开始]

可以把它想象成“放风筝”：搜索空间就是风筝能飞的范围，而边界盒就是拉住风筝的那根线，保证它不会飞出天际。

---

2. 关键细节解释

源码里有几个小细节，其实是 性能和正确性的关键点：

(1) visited.add(pos)

• HashSet.add 会在元素第一次加入时返回 true，之后再加同样的元素就返回 false。
• 这是 BFS 的“灵魂”，确保不会重复访问。

(2) 每 1000 方块检查一次（仅针对调试或有此需求的）

• 为什么不是每次循环都检查？因为 System.currentTimeMillis() 是系统调用，开销不小。如果不需要可丢弃。
• 批量检查可以显著减少调用次数，同时仍能及时发现“超时/超体积”。

(3) 边界盒剪枝

• minX/maxX、minY/maxY、minZ/maxZ 构成一个立方体笼子，越界就直接丢弃。
• 避免 BFS 无限扩张成“全世界搜索”。

(4) level.hasChunkAt(pos)

• 只在区块已加载时才继续，否则跳过。
• 防止误触 IO，把未加载的区块强行拉进来，避免卡顿甚至卡死。

注意：MC 世界数据并非线程安全。

• 方案 A：改回主线程执行（提交任务到主线程队列）。
• 方案 B：扫描前做区块快照（更安全）。
• 方案 C：客户端只读渲染缓存做可视化，服务端逻辑仍在主线程执行。

---

五、如何判断“封闭房间”？

当前实现 ≈ 连通空间采样器 + 约束器。 它并不严格证明“封闭”，而是通过触边/体积过大/超时来过滤掉“非房间”。

改进方案：

1. 触边即失败：若 BFS 访问到边界盒面或世界顶/底层，直接判定非封闭。
2. 外部连通性测试：从边界外壳再做一次 BFS，看是否能连回采样空间。

---

六、使用示例

BlockPos start = player.blockPosition();
RoomDetector.findRoomAsync(player.level(), start).thenAccept(room -> {
    if (room.isEmpty()) {
        player.displayClientMessage(Component.literal("未找到封闭房间（或空间过大/超时）"), true);
        return;
    }

    // 渲染反馈（伪代码）
    room.forEach(p -> spawnParticleAt(p));
    player.displayClientMessage(Component.literal("房间体积：" + room.size()), true);
});

配置参数（RoomDetectionConfig）：

• maxSearchDistance：搜索半径
• maxRoomSize：最大体积
• maxSearchTimeMs：最大耗时

---

七、性能秘诀（39756 方块 / 28ms 的幕后）

• 仅 6 邻域扩张，避免指数增长
• 无递归，全迭代，避免栈溢出
• 预分配容器，减少扩容和 rehash
• 边界剪枝，降低无效访问
• 区块已加载检查，避免触发 IO

---

八、魔改思路

• 自定义可通过性

  • 判定 getCollisionShape
  • 门/活板门/栅栏门更细分条件
  • 玻璃板/栅栏视为墙体

• 优化 visited

  • 用 BlockPos.asLong + LongOpenHashSet
  • 或分片 BitSet

• 更快队列

  • 自写环形队列替换 ArrayDeque

• 更强封闭性判定

  • 触边失败 + 标记泄露方向
  • 渲染边缘提示玩家修补

• 多阶段搜索

  • 小半径试探，大空间早停
  • 优先检测“弱点区域”

• 服务器友好

  • 分 tick 扫描，平滑执行
  • 主线程写结果，子线程做快照

• 房间特征提取

  • 输出 AABB（做光照、混响、家居摆放）
  • 计算几何/质量中心

---

九、最后

本文技术力不高，只是为部分人的特殊需求所做，如持有不同意见，欢迎批评指出。

如果本文对你有用，那就夸我两句吧~