每日算法 — 使用java实现塞尔达：地牢房间图生成与钥匙-门依赖拓扑排序

《塞尔达传说》系列的地牢设计以精巧的房间连通结构和钥匙-门锁机制著称。本文用 Java 模拟地牢生成过程，重点讲解随机房间图生成算法、钥匙-门依赖图的构建，以及拓扑排序验证可达性。读者将理解如何将游戏关卡设计抽象为图论问题，并确保玩家总能通关。

一、地牢设计的图论抽象

一个地牢可以抽象为有向图 $G=(V,E)$：

• 顶点 $V$：每个房间是一个节点，包含房间类型（起点、终点、普通房、宝物房、Boss房）。
• 边 $E$：门（Door）连接两个房间。门分为普通门（无需钥匙）和锁门（需要特定钥匙）。

为了让地牢可解，钥匙-门依赖必须满足：任何锁门所需的钥匙，必须在到达该门之前能够被玩家获取。这等价于依赖图必须无环，即存在拓扑序。

二、数据模型

import java.util.*;

/**
 * 房间类型枚举
 */
enum RoomType {
    START, NORMAL, TREASURE, BOSS, GOAL
}

/**
 * 单个房间
 */
class Room {
    int id;
    RoomType type;
    List<Key> keysContained = new ArrayList<>(); // 房间内可拾取的钥匙

    public Room(int id, RoomType type) {
        this.id = id;
        this.type = type;
    }
}

/**
 * 钥匙标识
 */
class Key {
    int keyId;
    String name;
    public Key(int keyId, String name) {
        this.keyId = keyId;
        this.name = name;
    }
}

/**
 * 连接两个房间的门
 */
class Door {
    Room from;
    Room to;
    Key requiredKey; // 若为 null 则表示无需钥匙
    boolean isOpen = false;

    public Door(Room from, Room to, Key requiredKey) {
        this.from = from;
        this.to = to;
        this.requiredKey = requiredKey;
    }
}

/**
 * 地牢容器
 */
class Dungeon {
    List<Room> rooms = new ArrayList<>();
    List<Door> doors = new ArrayList<>();
    Room startRoom;
    Room goalRoom;
}

三、随机房间图生成算法

我们使用随机树加边策略：先生成一棵保证连通的树，再随机添加额外边形成环路，最后分配锁门和钥匙。

class DungeonGenerator {
    private final Random rand = new Random(42);

    /**
     * 生成包含 n 个房间的地牢
     * @param n 房间数量
     * @param extraEdges 额外添加的边数（形成环路）
     * @param lockedDoorCount 锁门数量
     */
    public Dungeon generate(int n, int extraEdges, int lockedDoorCount) {
        Dungeon dungeon = new Dungeon();

        // 1. 创建房间
        for (int i = 0; i < n; i++) {
            RoomType type = RoomType.NORMAL;
            if (i == 0) type = RoomType.START;
            else if (i == n - 1) type = RoomType.GOAL;
            else if (i == n / 2) type = RoomType.BOSS;
            else if (rand.nextDouble() < 0.15) type = RoomType.TREASURE;
            dungeon.rooms.add(new Room(i, type));
        }
        dungeon.startRoom = dungeon.rooms.get(0);
        dungeon.goalRoom = dungeon.rooms.get(n - 1);

        // 2. 生成随机生成树（保证连通）
        Set<Integer> connected = new HashSet<>();
        connected.add(0);
        while (connected.size() < n) {
            int from = connected.stream().skip(rand.nextInt(connected.size())).findFirst().orElse(0);
            int to;
            do { to = rand.nextInt(n); } while (connected.contains(to));
            dungeon.doors.add(new Door(dungeon.rooms.get(from), dungeon.rooms.get(to), null));
            connected.add(to);
        }

        // 3. 添加额外随机边（允许双向）
        for (int i = 0; i < extraEdges; i++) {
            int a = rand.nextInt(n);
            int b = rand.nextInt(n);
            if (a == b) continue;
            dungeon.doors.add(new Door(dungeon.rooms.get(a), dungeon.rooms.get(b), null));
        }

        // 4. 选择部分边变为锁门
        List<Door> candidates = new ArrayList<>(dungeon.doors);
        Collections.shuffle(candidates, rand);
        int locked = Math.min(lockedDoorCount, candidates.size());
        for (int i = 0; i < locked; i++) {
            Key k = new Key(i, "Key-" + i);
            candidates.get(i).requiredKey = k;
        }

        // 5. 分配钥匙到房间（确保可解性）
        placeKeysWithTopologicalCheck(dungeon);

        return dungeon;
    }

四、钥匙放置与拓扑排序验证

这是算法的核心：我们构建一个钥匙-门依赖图，并通过拓扑排序确保玩家从起点出发时，每次遇到的锁门都能被已收集的钥匙打开。

    /**
     * 将钥匙放置到可达房间中，并确保依赖图无环
     */
    private void placeKeysWithTopologicalCheck(Dungeon dungeon) {
        // 建立反向索引：每把钥匙开哪些门
        Map<Integer, List<Door>> keyToDoors = new HashMap<>();
        for (Door d : dungeon.doors) {
            if (d.requiredKey != null) {
                keyToDoors.computeIfAbsent(d.requiredKey.keyId, k -> new ArrayList<>()).add(d);
            }
        }

        // 依赖图：钥匙 A -> 钥匙 B 表示"必须先拿 A 才能到达 B 所在的房间"
        // 这里采用贪心+拓扑验证策略：
        // 从起点开始做 BFS/DFS，每次遇到锁门时，将对应钥匙放到当前已访问的某个房间中
        Set<Room> visited = new HashSet<>();
        Queue<Room> queue = new LinkedList<>();
        queue.add(dungeon.startRoom);
        visited.add(dungeon.startRoom);

        // 记录哪些钥匙已被放置
        Set<Integer> placedKeys = new HashSet<>();

        while (!queue.isEmpty()) {
            Room current = queue.poll();

            // 遍历从当前房间出发的所有门
            for (Door d : dungeon.doors) {
                if (d.from != current) continue;

                // 检查是否可以通过此门
                boolean canPass = (d.requiredKey == null) || placedKeys.contains(d.requiredKey.keyId);
                if (!canPass) {
                    // 无法通过：将钥匙放到当前已访问的某个房间（包括当前房）
                    Room keyRoom = pickVisitedRoomForKey(dungeon, visited, d.requiredKey);
                    keyRoom.keysContained.add(d.requiredKey);
                    placedKeys.add(d.requiredKey.keyId);
                    canPass = true;
                }

                if (canPass && !visited.contains(d.to)) {
                    visited.add(d.to);
                    queue.add(d.to);
                }
            }
        }

        // 验证：拓扑排序检查所有锁门依赖是否无环
        if (!isSolvable(dungeon)) {
            throw new IllegalStateException("生成的地牢无解，请调整参数");
        }
    }

    /**
     * 在已访问房间中随机选择一个放置钥匙
     */
    private Room pickVisitedRoomForKey(Dungeon dungeon, Set<Room> visited, Key key) {
        List<Room> candidates = new ArrayList<>(visited);
        // 优先选择 TREASURE 房或普通房
        List<Room> preferred = candidates.stream()
            .filter(r -> r.type == RoomType.TREASURE || r.type == RoomType.NORMAL)
            .toList();
        if (!preferred.isEmpty()) {
            return preferred.get(rand.nextInt(preferred.size()));
        }
        return candidates.get(rand.nextInt(candidates.size()));
    }

五、可解性验证：拓扑排序

我们将每个锁门视为一个依赖约束：获取钥匙 $K$ 必须在通过门 $D$ 之前。所有约束构成有向图，若存在环则地牢无解。

    /**
     * 使用拓扑排序验证地牢是否可解
     * @return true 表示存在合法通关顺序
     */
    public boolean isSolvable(Dungeon dungeon) {
        // 节点：所有锁门所需的钥匙
        // 边：钥匙 A -> 钥匙 B 如果"必须通过需要 A 的门才能到达存放 B 的房间"
        // 简化做法：模拟玩家从起点出发，收集钥匙并开门，看能否到达终点

        Set<Integer> collectedKeys = new HashSet<>();
        Set<Room> reachable = new HashSet<>();
        Queue<Room> queue = new LinkedList<>();
        queue.add(dungeon.startRoom);
        reachable.add(dungeon.startRoom);

        boolean changed = true;
        while (changed) {
            changed = false;
            Queue<Room> nextQueue = new LinkedList<>();
            while (!queue.isEmpty()) {
                Room r = queue.poll();
                // 收集房间内的钥匙
                for (Key k : r.keysContained) {
                    if (collectedKeys.add(k.keyId)) {
                        changed = true; // 获得了新钥匙
                    }
                }

                for (Door d : dungeon.doors) {
                    if (d.from != r) continue;
                    if (!reachable.contains(d.to)) {
                        if (d.requiredKey == null || collectedKeys.contains(d.requiredKey.keyId)) {
                            reachable.add(d.to);
                            nextQueue.add(d.to);
                            changed = true;
                        }
                    }
                }
            }
            queue = nextQueue;
        }

        return reachable.contains(dungeon.goalRoom);
    }

六、打印地牢结构

    public void printDungeon(Dungeon dungeon) {
        System.out.println("=== Dungeon Map ===");
        for (Room r : dungeon.rooms) {
            String keys = r.keysContained.stream().map(k -> k.name).reduce((a, b) -> a + ", " + b).orElse("none");
            System.out.printf("Room %d [%s] keys=%s%n", r.id, r.type, keys);
        }
        System.out.println("\n=== Doors ===");
        for (Door d : dungeon.doors) {
            String lock = d.requiredKey == null ? "open" : "requires " + d.requiredKey.name;
            System.out.printf("%d -> %d [%s]%n", d.from.id, d.to.id, lock);
        }
    }

    public static void main(String[] args) {
        DungeonGenerator gen = new DungeonGenerator();
        Dungeon dungeon = gen.generate(10, 3, 4);
        gen.printDungeon(dungeon);
        System.out.println("\nSolvable: " + gen.isSolvable(dungeon));
    }
}

七、复杂度分析

• 房间图生成：$O(N^2)$，主要来自随机连边时的碰撞检测。
• 钥匙放置：$O(N + E)$，BFS 遍历房间和门。
• 拓扑验证（可解性检查）：最坏 $O(K \cdot (N + E))$，$K$ 为钥匙数量，每次获得新钥匙可能扩展可达集合。

八、总结

本文将塞尔达地牢抽象为图论问题，通过随机生成树+额外边构建基础拓扑，再用贪心 BFS + 拓扑排序验证保证钥匙-门依赖无环。核心思想是：将游戏关卡的可解性转化为有向图的可达性问题。读者可以在此基础上扩展多层级地牢、双向门、以及更复杂的钥匙消耗与回归机制。