使用Unity中的最小生成树生成带走廊的连通房间

Question

我一直在开发一款自上而下的游戏，涉及按程序生成关卡。到目前为止，我已经成功地基于种子创建了单独的房间，但现在我在尝试使用走廊将这些房间连接在一起时面临着挑战。我最终没有实现单个连接的树状结构，而是得到了多个互不相连的房间群。

为了解决这个问题，我一直在尝试使用最小生成树算法和 Kruskal 算法来连接房间和走廊。然而，我遇到了一个障碍：走廊是从房间的中心开始的，而我希望它们是从墙壁开始的。

为了寻求解决方案，我开发了以下脚本：

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;

    private Transform mapHolder;
    private bool[,] usedTiles;

    private List<Vector2Int> rooms = new List<Vector2Int>();

    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])
                {
                    // Generate rooms
                    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))
                        {
                            GenerateRoom(startX, startY, roomWidth, roomHeight);
                            rooms.Add(new Vector2Int(startX + roomWidth / 2, startY + roomHeight / 2));
                            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()
    {
        List<Edge> edges = new List<Edge>();

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

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

        List<int> takenIndices = new List<int>();
        List<int> connectedIndices = new List<int>();

        foreach (Edge edge in edges)
        {
            if (!takenIndices.Contains(edge.from) || !takenIndices.Contains(edge.to))
            {
                connectedIndices.Add(edge.from);
                connectedIndices.Add(edge.to);
                takenIndices.Add(edge.from);
                takenIndices.Add(edge.to);

                Vector2Int roomA = rooms[edge.from];
                Vector2Int roomB = rooms[edge.to];

                GenerateCorridor(roomA, roomB);
            }
        }
    }

    void GenerateCorridor(Vector2Int pointA, Vector2Int pointB)
    {
        Vector2Int start = pointA;
        Vector2Int end = pointB;

        if (start.x > end.x)
        {
            Vector2Int temp = start;
            start = end;
            end = temp;
        }

        int corridorWidth = Mathf.Abs(end.x - start.x) + 1;
        int corridorHeight = Mathf.Abs(end.y - start.y) + 1;

        int corridorX = start.x;
        int corridorY = start.y;

        for (int i = 0; i < corridorWidth; i++)
        {
            for (int j = 0; j < corridorHeight; j++)
            {
                Vector3 tilePosition = new Vector3(corridorX + i, corridorY + j, 0);
                GameObject corridorTile = Instantiate(corridorPrefab, tilePosition, Quaternion.identity);
                corridorTile.transform.parent = mapHolder;
            }
        }
    }

    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;
        }
    }
}

实际上，我最终得到的是多个互不相连的房间集群，而不是实现单个连接的树状结构。走廊是从房间的中心开始的，而我希望它们从墙壁开始。此外，我设法生成的走廊具有不同的宽度，有时与房间的地板重叠。

Answer 1

有这样的事吗？

我通过

生成了这张图片

- 随机定位房间

我尽可能遵循你的方案，除了我使用左上角坐标存储房间位置。 （房间中心很棘手，因为你必须除以二，结果取决于奇数除以二时会发生什么。如果你使用浮点数而不是整数，你的方案会效果更好，但使用左上角的整数可以保留东西简单）

- 计算 MST

我按照你的建议计算最小生成树。效果很好！ （也许你的 MST 计算有错误？）为此，我使用了我的图论库中经过充分测试的代码（https://github.com/JamesBremner/PathFinder）

- 计算走廊终点

我认为，我们希望走廊位于由 MST 连接的两个房间的相邻房间边界的中间。这里需要一些棘手的编码才能获得完美的结果。最重要的技巧是将 MST 植根于右上角的房间，以便房间仅从左到右、从上到下相连。这是代码

void cLevelGenerator1::generateCorridor(
    cRoom &rooma, cRoom &roomb)
{
    if (rooma.y+rooma.h-1 < roomb.y)
    {
        // from bottom middle to left middle
        corridors.emplace_back(
            rooma.x + rooma.w / 2, rooma.y + rooma.h - 1,
            roomb.x + roomb.w / 2, roomb.y);
    }
    else if ( 
     rooma.x+rooma.w - 1 < roomb.x )
    {
        //from right middle to left middle
        corridors.emplace_back(
            rooma.x+rooma.w-1, rooma.y+rooma.h/2,
            roomb.x,roomb.y+roomb.h/2 );
    }
    else
    {
        // from top middle to bottom middle
        corridors.emplace_back(
            rooma.x+rooma.w/2,rooma.y,
            roomb.x+roomb.w/2,roomb.y+roomb.h-1 );
    }
}

应用程序的完整 C++ 代码位于 https://github.com/JamesBremner/corridors

（抱歉，我知道您想要 C# 代码。但是，我发现可以直接将您的 C# 代码移植到 C++，因此您可能可以再次将其移植回来）