每日算法 — 使用java实现地牢生成：BSP分割与房间走廊连通图生成

游戏简介

地牢生成（Dungeon Generation）是Roguelike游戏的核心技术之一。与迷宫生成不同，地牢通常由一系列随机分布的房间和连接它们的走廊组成，形成更自然、更具探索感的地下空间。本文将用Java实现一套完整的地牢生成系统，讲解BSP（Binary Space Partitioning，二叉空间分割）算法、房间放置策略、走廊连接算法，以及基于图论的最小生成树优化。

核心设计思路

一个典型的地牢生成流程包括四个阶段：

1. 空间分割：使用BSP将大矩形区域递归分割成若干小区域
2. 房间生成：在每个叶节点区域内随机放置房间
3. 走廊连接：在相邻区域之间创建走廊，确保所有房间连通
4. 图优化：用最小生成树去除冗余走廊，同时保留少量环路增加探索性

BSP二叉空间分割

BSP算法递归地将矩形区域沿水平或垂直方向分割，直到每个区域的大小低于阈值。分割时引入随机性，使地牢更具变化。

import java.util.*;

public class BSPTree {

    /**
     * BSP节点，表示一个矩形区域
     */
    public static class Node {
        public int x, y, width, height; // 区域位置和大小
        public Node left, right;        // 左右子节点
        public Room room;               // 叶节点上的房间

        public Node(int x, int y, int width, int height) {
            this.x = x;
            this.y = y;
            this.width = width;
            this.height = height;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }
    }

    /**
     * 房间定义
     */
    public static class Room {
        public int x, y, width, height;
        public int centerX, centerY;

        public Room(int x, int y, int width, int height) {
            this.x = x;
            this.y = y;
            this.width = width;
            this.height = height;
            this.centerX = x + width / 2;
            this.centerY = y + height / 2;
        }
    }

    private static final int MIN_LEAF_SIZE = 10;  // 叶节点最小尺寸
    private static final int MAX_LEAF_SIZE = 24;  // 超过此尺寸继续分割
    private static final Random RANDOM = new Random();

    /**
     * 构建BSP树
     */
    public static Node buildTree(int rootX, int rootY, int rootWidth, int rootHeight) {
        Node root = new Node(rootX, rootY, rootWidth, rootHeight);
        List<Node> leaves = new ArrayList<>();
        leaves.add(root);

        boolean split = true;
        while (split) {
            split = false;
            List<Node> newLeaves = new ArrayList<>();

            for (Node leaf : leaves) {
                if (leaf.isLeaf()) {
                    // 如果区域太大，尝试分割
                    if (leaf.width > MAX_LEAF_SIZE || leaf.height > MAX_LEAF_SIZE) {
                        if (splitNode(leaf)) {
                            newLeaves.add(leaf.left);
                            newLeaves.add(leaf.right);
                            split = true;
                            continue;
                        }
                    }
                }
                newLeaves.add(leaf);
            }
            leaves = newLeaves;
        }

        // 在所有叶节点上生成房间
        for (Node leaf : leaves) {
            leaf.room = generateRoom(leaf);
        }

        return root;
    }

    /**
     * 分割节点，随机选择水平或垂直分割
     */
    private static boolean splitNode(Node node) {
        // 决定分割方向：如果宽度大于高度150%，优先垂直分割；反之优先水平分割
        boolean splitH = RANDOM.nextBoolean();
        if (node.width > node.height * 1.5) {
            splitH = false; // 垂直分割
        } else if (node.height > node.width * 1.5) {
            splitH = true;  // 水平分割
        }

        int maxSize = splitH ? node.height : node.width;
        if (maxSize < MIN_LEAF_SIZE * 2) {
            return false; // 太小，无法分割
        }

        // 随机选择分割位置（至少留MIN_LEAF_SIZE给两边）
        int splitPos = MIN_LEAF_SIZE + RANDOM.nextInt(maxSize - MIN_LEAF_SIZE * 2 + 1);

        if (splitH) {
            // 水平分割（上下）
            node.left = new Node(node.x, node.y, node.width, splitPos);
            node.right = new Node(node.x, node.y + splitPos, node.width, node.height - splitPos);
        } else {
            // 垂直分割（左右）
            node.left = new Node(node.x, node.y, splitPos, node.height);
            node.right = new Node(node.x + splitPos, node.y, node.width - splitPos, node.height);
        }

        return true;
    }

    /**
     * 在叶节点内随机生成房间，四周留走廊空间
     */
    private static Room generateRoom(Node leaf) {
        // 房间四周至少留1格作为墙/走廊空间
        int padding = 2;
        int maxRoomWidth = leaf.width - padding * 2;
        int maxRoomHeight = leaf.height - padding * 2;

        if (maxRoomWidth < 3 || maxRoomHeight < 3) {
            // 区域太小，直接填满
            return new Room(leaf.x + 1, leaf.y + 1, leaf.width - 2, leaf.height - 2);
        }

        int roomWidth = 3 + RANDOM.nextInt(maxRoomWidth - 2);
        int roomHeight = 3 + RANDOM.nextInt(maxRoomHeight - 2);

        int roomX = leaf.x + padding + RANDOM.nextInt(maxRoomWidth - roomWidth + 1);
        int roomY = leaf.y + padding + RANDOM.nextInt(maxRoomHeight - roomHeight + 1);

        return new Room(roomX, roomY, roomWidth, roomHeight);
    }
}

走廊连接算法

生成房间后，需要在房间之间建立走廊。最常用的方法是连接兄弟节点的房间，然后递归向上连接。走廊可以是L形（先水平后垂直，或先垂直后水平）。

public class DungeonGenerator {

    public static final int TILE_WALL = 0;
    public static final int TILE_FLOOR = 1;
    public static final int TILE_CORRIDOR = 2;
    public static final int TILE_DOOR = 3;

    private int[][] map;
    private int width, height;
    private List<BSPTree.Room> rooms;
    private List<Corridor> corridors;

    public DungeonGenerator(int width, int height) {
        this.width = width;
        this.height = height;
        this.map = new int[height][width];
        this.rooms = new ArrayList<>();
        this.corridors = new ArrayList<>();
        // 初始化为墙
        for (int y = 0; y < height; y++) {
            Arrays.fill(map[y], TILE_WALL);
        }
    }

    /**
     * 使用BSP生成地牢
     */
    public void generate() {
        // 1. BSP分割
        BSPTree.Node root = BSPTree.buildTree(1, 1, width - 2, height - 2);

        // 2. 收集所有房间
        collectRooms(root);

        // 3. 在BSP树上连接兄弟房间
        connectRooms(root);

        // 4. 渲染到地图
        renderRooms();
        renderCorridors();
    }

    private void collectRooms(BSPTree.Node node) {
        if (node == null) return;
        if (node.isLeaf() && node.room != null) {
            rooms.add(node.room);
        } else {
            collectRooms(node.left);
            collectRooms(node.right);
        }
    }

    /**
     * 递归连接兄弟节点的房间
     */
    private void connectRooms(BSPTree.Node node) {
        if (node == null || node.isLeaf()) return;

        // 先递归连接子树内部
        connectRooms(node.left);
        connectRooms(node.right);

        // 连接左右子树的最近房间
        BSPTree.Room roomA = findNearestRoom(node.left, node.right.room);
        BSPTree.Room roomB = findNearestRoom(node.right, node.left.room);

        if (roomA != null && roomB != null) {
            createCorridor(roomA, roomB);
        }
    }

    /**
     * 找到子树中距离目标房间最近的房间
     */
    private BSPTree.Room findNearestRoom(BSPTree.Node node, BSPTree.Room target) {
        if (node == null) return null;
        if (node.isLeaf() && node.room != null) {
            return node.room;
        }

        BSPTree.Room leftRoom = findNearestRoom(node.left, target);
        BSPTree.Room rightRoom = findNearestRoom(node.right, target);

        if (leftRoom == null) return rightRoom;
        if (rightRoom == null) return leftRoom;

        double leftDist = distance(leftRoom, target);
        double rightDist = distance(rightRoom, target);
        return leftDist < rightDist ? leftRoom : rightRoom;
    }

    private double distance(BSPTree.Room a, BSPTree.Room b) {
        return Math.sqrt(Math.pow(a.centerX - b.centerX, 2) + Math.pow(a.centerY - b.centerY, 2));
    }

    /**
     * 创建L形走廊连接两个房间
     */
    private void createCorridor(BSPTree.Room a, BSPTree.Room b) {
        int startX = a.centerX;
        int startY = a.centerY;
        int endX = b.centerX;
        int endY = b.centerY;

        // 随机决定先水平还是先垂直
        if (RANDOM.nextBoolean()) {
            // 先水平后垂直
            corridors.add(new Corridor(startX, startY, endX, startY, true));
            corridors.add(new Corridor(endX, startY, endX, endY, false));
        } else {
            // 先垂直后水平
            corridors.add(new Corridor(startX, startY, startX, endY, false));
            corridors.add(new Corridor(startX, endY, endX, endY, true));
        }
    }

    /**
     * 将房间渲染到地图
     */
    private void renderRooms() {
        for (BSPTree.Room room : rooms) {
            for (int y = room.y; y < room.y + room.height; y++) {
                for (int x = room.x; x < room.x + room.width; x++) {
                    if (y >= 0 && y < height && x >= 0 && x < width) {
                        map[y][x] = TILE_FLOOR;
                    }
                }
            }
        }
    }

    /**
     * 将走廊渲染到地图
     */
    private void renderCorridors() {
        for (Corridor c : corridors) {
            if (c.horizontal) {
                int minX = Math.min(c.x1, c.x2);
                int maxX = Math.max(c.x1, c.x2);
                for (int x = minX; x <= maxX; x++) {
                    if (c.y1 >= 0 && c.y1 < height && x >= 0 && x < width) {
                        map[c.y1][x] = TILE_CORRIDOR;
                    }
                }
            } else {
                int minY = Math.min(c.y1, c.y2);
                int maxY = Math.max(c.y1, c.y2);
                for (int y = minY; y <= maxY; y++) {
                    if (y >= 0 && y < height && c.x1 >= 0 && c.x1 < width) {
                        map[y][c.x1] = TILE_CORRIDOR;
                    }
                }
            }
        }
    }

    static class Corridor {
        int x1, y1, x2, y2;
        boolean horizontal;

        Corridor(int x1, int y1, int x2, int y2, boolean horizontal) {
            this.x1 = x1; this.y1 = y1;
            this.x2 = x2; this.y2 = y2;
            this.horizontal = horizontal;
        }
    }

    public void print() {
        char[] symbols = {'#', '.', '+', 'D'};
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                System.out.print(symbols[map[y][x]]);
            }
            System.out.println();
        }
    }

    public int[][] getMap() {
        return map;
    }

    public List<BSPTree.Room> getRooms() {
        return rooms;
    }
}

最小生成树优化冗余走廊

BSP递归连接会生成大量冗余走廊。我们可以通过构建房间连通图，计算最小生成树（MST）来保留必要连接，同时额外添加少量边形成环路，增加地牢的探索性和非线性。

public class DungeonOptimizer {

    /**
     * 房间连通图的边
     */
    static class Edge implements Comparable<Edge> {
        int from, to;
        double weight;

        Edge(int from, int to, double weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge other) {
            return Double.compare(this.weight, other.weight);
        }
    }

    /**
     * 使用Kruskal算法计算最小生成树，并额外添加环路边
     * @param rooms 房间列表
     * @param extraEdgeRatio 额外环路边的比例（0.0-1.0）
     * @return MST边 + 额外边
     */
    public static List<Edge> optimizeConnections(List<BSPTree.Room> rooms, double extraEdgeRatio) {
        int n = rooms.size();
        List<Edge> allEdges = new ArrayList<>();

        // 构建完全图
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double dist = distance(rooms.get(i), rooms.get(j));
                allEdges.add(new Edge(i, j, dist));
            }
        }

        Collections.sort(allEdges);

        // Kruskal算法
        UnionFind uf = new UnionFind(n);
        List<Edge> mst = new ArrayList<>();
        List<Edge> nonMst = new ArrayList<>();

        for (Edge e : allEdges) {
            if (uf.find(e.from) != uf.find(e.to)) {
                uf.union(e.from, e.to);
                mst.add(e);
            } else {
                nonMst.add(e);
            }
        }

        // 添加额外环路边
        int extraCount = (int) (nonMst.size() * extraEdgeRatio);
        Collections.shuffle(nonMst);
        for (int i = 0; i < Math.min(extraCount, nonMst.size()); i++) {
            mst.add(nonMst.get(i));
        }

        return mst;
    }

    private static double distance(BSPTree.Room a, BSPTree.Room b) {
        return Math.sqrt(Math.pow(a.centerX - b.centerX, 2) + Math.pow(a.centerY - b.centerY, 2));
    }

    /**
     * 并查集
     */
    static class UnionFind {
        int[] parent;

        UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }

        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        void union(int x, int y) {
            parent[find(x)] = find(y);
        }
    }
}

完整可运行示例

public class DungeonMain {
    public static void main(String[] args) {
        int dungeonWidth = 80;
        int dungeonHeight = 40;

        DungeonGenerator generator = new DungeonGenerator(dungeonWidth, dungeonHeight);
        generator.generate();

        System.out.println("=== 生成的地牢 ===");
        generator.print();

        System.out.println("\n房间数量: " + generator.getRooms().size());

        // 使用MST优化连接
        List<DungeonOptimizer.Edge> optimized = DungeonOptimizer.optimizeConnections(
            generator.getRooms(), 0.15); // 15%额外环路
        System.out.println("优化后边数: " + optimized.size());
    }
}

复杂度分析

总结

本文实现了一套完整的地牢生成系统，核心亮点包括：

• BSP二叉空间分割：递归随机分割确保地牢布局的自然多样性和层次结构
• 房间与走廊生成：在叶节点内放置房间，通过L形走廊连接兄弟节点，保证连通性
• 最小生成树优化：使用Kruskal算法去除冗余连接，在保持连通的前提下降低走廊密度
• 环路控制：通过extraEdgeRatio参数精确控制额外环路比例，平衡线性和非线性探索体验

读者可以进一步扩展，例如添加门、陷阱、宝箱等元素的随机放置，或引入Perlin噪声进行地形细节雕刻，打造更丰富的地下世界。