Unity中用Minimum Spanning Tree生成连通房间走廊的问题排查

问题概述 #

当前实现基于种子生成独立房间，但走廊连接存在三个核心问题：

• 未形成单一连通树状结构，出现多个不连通的房间集群
• 走廊从房间中心而非墙体起始（使用Kruskal算法实现最小生成树）
• 走廊宽度不一致，且部分区域与房间地板重叠

问题根源与修复方案 #

1. 不连通的房间集群：错误的Kruskal算法实现 #

原代码用takenIndices列表判断房间连通性的逻辑完全错误，Kruskal算法需要**并查集（Union-Find）**结构高效检测和合并连通分量，确保最终生成单一连通树。

2. 走廊从房间中心起始：缺少房间边界信息 #

原代码仅存储房间中心坐标，无法定位墙体位置。需要记录每个房间的完整边界数据，计算房间之间的墙体入口点作为走廊起止点。

3. 走廊宽度不一且重叠：错误的走廊生成逻辑 #

原代码生成的是两点间的矩形区域，导致宽度随距离变化，且未标记走廊 tiles 为已使用，造成与房间地板重叠。需改为生成固定宽度的L形/直线走廊，并标记tiles状态。

修改后的完整代码 #

using UnityEngine;
using System.Collections.Generic;

public class LevelGenerator1 : MonoBehaviour
{
    public GameObject floorPrefab;
    public GameObject wallPrefab;
    public GameObject corridorPrefab;
    public int mapWidth = 100;
    public int mapHeight = 100;
    public int roomSizeMin = 5;
    public int roomSizeMax = 15;
    public int seed = 12345;
    public int corridorWidth = 1; // 固定走廊宽度

    private Transform mapHolder;
    private bool[,] usedTiles;
    private List<Room> rooms = new List<Room>();
    private int[] parent; // 并查集父节点数组

    void Start()
    {
        GenerateLevel();
    }

    void GenerateLevel()
    {
        mapHolder = new GameObject("Generated Map").transform;
        usedTiles = new bool[mapWidth, mapHeight];

        Random.InitState(seed);

        for (int x = 0; x < mapWidth; x++)
        {
            for (int y = 0; y < mapHeight; y++)
            {
                if (!usedTiles[x, y])
                {
                    if (Random.Range(0f, 1f) > 0.8f)
                    {
                        int roomWidth = Random.Range(roomSizeMin, roomSizeMax);
                        int roomHeight = Random.Range(roomSizeMin, roomSizeMax);

                        int startX = x - roomWidth / 2;
                        int startY = y - roomHeight / 2;

                        if (IsSpaceAvailable(startX, startY, roomWidth, roomHeight))
                        {
                            int xMin = startX;
                            int xMax = startX + roomWidth - 1;
                            int yMin = startY;
                            int yMax = startY + roomHeight - 1;
                            Vector2Int center = new Vector2Int((xMin + xMax) / 2, (yMin + yMax) / 2);
                            
                            GenerateRoom(startX, startY, roomWidth, roomHeight);
                            rooms.Add(new Room { center = center, xMin = xMin, xMax = xMax, yMin = yMin, yMax = yMax });
                            MarkTilesUsed(startX, startY, roomWidth, roomHeight);
                        }
                    }
                }
            }
        }

        ConnectRooms();
    }

    bool IsSpaceAvailable(int x, int y, int width, int height)
    {
        for (int i = x; i < x + width; i++)
        {
            for (int j = y; j < y + height; j++)
            {
                if (i < 0 || i >= mapWidth || j < 0 || j >= mapHeight || usedTiles[i, j])
                {
                    return false;
                }
            }
        }
        return true;
    }

    void MarkTilesUsed(int x, int y, int width, int height)
    {
        for (int i = x; i < x + width; i++)
        {
            for (int j = y; j < y + height; j++)
            {
                usedTiles[i, j] = true;
            }
        }
    }

    void GenerateRoom(int x, int y, int width, int height)
    {
        for (int i = x; i < x + width; i++)
        {
            for (int j = y; j < y + height; j++)
            {
                Vector3 tilePosition = new Vector3(i, j, 0);

                if (i == x || i == x + width - 1 || j == y || j == y + height - 1)
                {
                    GameObject wallTile = Instantiate(wallPrefab, tilePosition, Quaternion.identity);
                    wallTile.transform.parent = mapHolder;
                }
                else
                {
                    GameObject floorTile = Instantiate(floorPrefab, tilePosition, Quaternion.identity);
                    floorTile.transform.parent = mapHolder;
                }
            }
        }
    }

    void ConnectRooms()
    {
        if (rooms.Count <= 1) return;

        // 初始化并查集
        parent = new int[rooms.Count];
        for (int i = 0; i < rooms.Count; i++)
        {
            parent[i] = i;
        }

        List<Edge> edges = new List<Edge>();
        for (int i = 0; i < rooms.Count; i++)
        {
            for (int j = i + 1; j < rooms.Count; j++)
            {
                float distance = Vector2Int.Distance(rooms[i].center, rooms[j].center);
                edges.Add(new Edge(i, j, distance));
            }
        }

        edges.Sort((a, b) => a.distance.CompareTo(b.distance));

        foreach (Edge edge in edges)
        {
            int rootA = Find(edge.from);
            int rootB = Find(edge.to);

            if (rootA != rootB)
            {
                Union(rootA, rootB);
                GenerateCorridor(rooms[edge.from], rooms[edge.to]);
            }
        }
    }

    // 并查集查找方法（带路径压缩）
    private int Find(int x)
    {
        if (parent[x] != x)
        {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }

    // 并查集合并方法
    private void Union(int x, int y)
    {
        parent[y] = x;
    }

    void GenerateCorridor(Room roomA, Room roomB)
    {
        // 计算两个房间之间的连接点（墙体上的入口）
        Vector2Int startPoint = GetRoomEntrance(roomA, roomB);
        Vector2Int endPoint = GetRoomEntrance(roomB, roomA);

        // 先生成水平段，再生成垂直段（L形走廊）
        int minX = Mathf.Min(startPoint.x, endPoint.x);
        int maxX = Mathf.Max(startPoint.x, endPoint.x);
        int minY = Mathf.Min(startPoint.y, endPoint.y);
        int maxY = Mathf.Max(startPoint.y, endPoint.y);

        // 生成水平部分
        for (int x = minX; x <= maxX; x++)
        {
            for (int w = 0; w < corridorWidth; w++)
            {
                int y = startPoint.y + w - corridorWidth / 2;
                if (IsValidTile(x, y) && !usedTiles[x, y])
                {
                    SpawnCorridorTile(x, y);
                }
            }
        }

        // 生成垂直部分
        for (int y = minY; y <= maxY; y++)
        {
            for (int w = 0; w < corridorWidth; w++)
            {
                int x = endPoint.x + w - corridorWidth / 2;
                if (IsValidTile(x, y) && !usedTiles[x, y])
                {
                    SpawnCorridorTile(x, y);
                }
            }
        }
    }

    // 获取房间朝向目标房间的入口点（墙体位置）
    private Vector2Int GetRoomEntrance(Room fromRoom, Room toRoom)
    {
        Vector2Int entrance = fromRoom.center;

        // 判断目标房间在当前房间的哪个方向
        if (toRoom.center.x > fromRoom.xMax)
        {
            // 目标在右侧，入口在右墙
            entrance.x = fromRoom.xMax;
            entrance.y = Mathf.Clamp(toRoom.center.y, fromRoom.yMin, fromRoom.yMax);
        }
        else if (toRoom.center.x < fromRoom.xMin)
        {
            // 目标在左侧，入口在左墙
            entrance.x = fromRoom.xMin;
            entrance.y = Mathf.Clamp(toRoom.center.y, fromRoom.yMin, fromRoom.yMax);
        }
        else if (toRoom.center.y > fromRoom.yMax)
        {
            // 目标在上侧，入口在上墙
            entrance.y = fromRoom.yMax;
            entrance.x = Mathf.Clamp(toRoom.center.x, fromRoom.xMin, fromRoom.xMax);
        }
        else if (toRoom.center.y < fromRoom.yMin)
        {
            // 目标在下侧，入口在下墙
            entrance.y = fromRoom.yMin;
            entrance.x = Mathf.Clamp(toRoom.center.x, fromRoom.xMin, fromRoom.xMax);
        }

        return entrance;
    }

    private bool IsValidTile(int x, int y)
    {
        return x >= 0 && x < mapWidth && y >= 0 && y < mapHeight;
    }

    private void SpawnCorridorTile(int x, int y)
    {
        Vector3 tilePosition = new Vector3(x, y, 0);
        GameObject corridorTile = Instantiate(corridorPrefab, tilePosition, Quaternion.identity);
        corridorTile.transform.parent = mapHolder;
        usedTiles[x, y] = true;
    }

    struct Edge
    {
        public int from;
        public int to;
        public float distance;

        public Edge(int from, int to, float distance)
        {
            this.from = from;
            this.to = to;
            this.distance = distance;
        }
    }

    struct Room
    {
        public Vector2Int center;
        public int xMin, xMax, yMin, yMax;
    }
}

关键修改说明 #

1. 并查集实现：通过Find和Union方法正确实现Kruskal算法，确保所有房间合并为单一连通分量
2. Room结构体：存储房间边界信息，用于计算墙体入口点
3. 固定宽度走廊：生成L形固定宽度走廊，避免宽度随距离变化
4. Tile标记：生成走廊时标记tiles为已使用，防止与房间地板重叠
5. 入口点计算：根据房间相对位置确定墙体入口，确保走廊从墙体而非中心起始

内容的提问来源于stack exchange，提问作者Rejwen