[Unity] 二维洞穴地图随机生成

看的别人的示例：
https://blog.csdn.net/l773575310/article/details/72803191
https://github.com/ZeroChiLi/CaveGeneration

1.地图生成方法

1.新建一个枚举类型的二维数组 map，每个元素代表着每一个格子，枚举内容代表格子的种类，例如空地、墙
2.自定义随机填充算法初始化 map
3.自定义平滑算法处理 map
例如：遍历 map 每个元素，计算其周围 8 个元素为墙的个数，等于 4 个时保持不变，大于一半则自己也变成墙，反之为空地
4.清除小的墙体、空洞
要清除的墙体和空洞是 map 中一些连续的同一枚举类型的元素，用 List<Vector2> 表示，通过广度优先找出
先删掉小墙体，这样有些房间就会变大，找小空洞时，所有房间的大小是最终大小
再删掉小空洞，并且把没删掉的作为房间存起来
最后把房间最大的作为主房间
5.房间连接
遍历所有房间，对其中每一个房间，寻找可能存在的，距离自己最近的，与自己尚未连接的房间
连接时遍历两个房间的边节点，找到两个房间之间距离最近的一对边节点，计算两个点产生的直线的斜率，通过斜率计算直线上的节点，放入列表，遍历这个列表，在以给定的通道宽度为半径，列表元素为圆心的，圆内的所有地图节点，都置为空地
重复遍历若干次，直至连接至主房间的房间数等于所有房间的数量-1

之后的 mesh 相关我不一定用得到，就不想看了hhh

2.对示例代码的修改

Assets/Scripts/Room.cs 中 UpdateEdgeTiles 函数可能会放入重复的边界点

    // 更新房间边缘瓦片集
    public void UpdateEdgeTiles(TileType[,] map)
    {
    
        edgeTiles.Clear();

        // 遍历上下左右四格，判断是否有墙
        foreach (Coord tile in tiles)
            for (int i = 0; i < 4; i++)
            {
    
                int x = tile.tileX + upDownLeftRight[i, 0];
                int y = tile.tileY + upDownLeftRight[i, 1];
                if (map[x, y] == TileType.Wall)
                {
    
                    edgeTiles.Add(tile);
                    continue;
                }
            }
    }

将 Coord 结构体改成 Vector2Int 然后使用 Contain 判断是否已经放过

    // 更新房间边缘瓦片集
    public void UpdateEdgeTiles(TileType[,] map)
    {
    
        edgeTiles.Clear();
        
        // 遍历上下左右四格，判断是否有墙
        foreach (Vector2Int tile in tiles)
            for (int i = 0; i < 4; i++)
            {
    
                int x = tile.x + upDownLeftRight[i, 0];
                int y = tile.y + upDownLeftRight[i, 1];
                if (map[x, y] == TileType.Wall && !edgeTiles.Contains(tile))
                {
    
                    edgeTiles.Add(tile);
                }
            }
    }

---

源代码连接房间的这一步看不懂捏……

    //连接各个房间。每个房间两两比较，找到最近房间（相对前一个房间）连接之，对第二个房间来说不一定就是最近的。
    //第二个参数为False时，第一步操作：为所有房间都连接到最近房间。
    //第二个参数为True时，第二步操作：就是把所有房间都连接到主房间。
    private void ConnectClosestRooms(List<Room> allRooms, bool forceAccessibilityFromMainRoom = false)
    {
    
        #region 属于第二步操作：roomListA 是还没连接到主房间的房间队列， roomListB 是已经连接到房间B的队列。
        List<Room> roomListA = new List<Room>();
        List<Room> roomListB = new List<Room>();

        if (forceAccessibilityFromMainRoom)                         //是否需要强制连接（直接或间接）到主房间。
        {
    
            foreach (Room room in allRooms)
                if (room.isAccessibleFromMainRoom)
                    roomListB.Add(room);                            //已经连接到主房间的加到ListB。
                else
                    roomListA.Add(room);                            //没有连接到主房间的加到ListA。为空时将结束递归。
        }
        else
        {
    
            roomListA = allRooms;
            roomListB = allRooms;
        }
        #endregion

        int bestDistance = 0;
        Vector2Int bestTileA = new Vector2Int();
        Vector2Int bestTileB = new Vector2Int();
        Room bestRoomA = new Room();
        Room bestRoomB = new Room();
        bool possibleConnectionFound = false;

        foreach (Room roomA in roomListA)                           //遍历没连接到主房间的ListA。
        {
    
            if (!forceAccessibilityFromMainRoom)                    //第一步：如果没有要求连到主房间。
            {
    
                possibleConnectionFound = false;                    //那就不能完成连接任务，需要不止一次连接。
                if (roomA.connectedRooms.Count > 0)                 //有连接房间，跳过，继续找下一个连接房间。
                    continue;
            }
            #region 遍历roomListB，找到距离当前roomA最近的roomB。
            foreach (Room roomB in roomListB)
            {
    
                if (roomA == roomB || roomA.IsConnected(roomB))
                    continue;

                foreach (var tileA in roomA.edgeTiles)
                    foreach (var tileB in roomB.edgeTiles)
                    {
    
                        int distanceBetweenRooms = (tileA - tileB).sqrMagnitude;

                        //如果找到更近的（相对roomA）房间，更新最短路径。
                        if (distanceBetweenRooms < bestDistance || !possibleConnectionFound)
                        {
    
                            bestDistance = distanceBetweenRooms;
                            possibleConnectionFound = true;
                            bestTileA = tileA;
                            bestTileB = tileB;
                            bestRoomA = roomA;
                            bestRoomB = roomB;
                        }
                    }
            }
            #endregion
            //第一步：找到新的两个连接房间,但是没有要求连接主房间。创建通道。
            if (possibleConnectionFound && !forceAccessibilityFromMainRoom)
                CreatePassage(bestRoomA, bestRoomB, bestTileA, bestTileB);
        }

        //第一步到第二步：当连接完所有房间，但是还没有要求全部连接到主房间，那就开始连接到主房间。
        if (!forceAccessibilityFromMainRoom)
            ConnectClosestRooms(allRooms, true);

        //第二步：当成功找到能连接到主房间，通路，继续找一下个能需要连到主房间的房间。
        if (possibleConnectionFound && forceAccessibilityFromMainRoom)
        {
    
            CreatePassage(bestRoomA, bestRoomB, bestTileA, bestTileB);
            ConnectClosestRooms(allRooms, true);
        }
    }

本着简单第一的原则我改成了

    /// <summary>
    /// 把所有房间都连接到主房间
    /// </summary>
    private void ConnectAllRoomsToMainRoom(List<Room> allRooms)
    {
    
        Room mainRoom = null;

        foreach (var room in allRooms)
        {
    
            if (room.isMainRoom)
            {
    
                mainRoom = room;
                break;
            }
        }

        if (mainRoom == null)
            return;
        
        foreach (var room in allRooms)
        {
    
            ConnectToClosestRoom(room, allRooms);
        }

        if (mainRoom.connectedRooms.Count != allRooms.Count - 1)
        {
    
            ConnectAllRoomsToMainRoom(allRooms);
        }
    }

    /// <summary>
    /// 连接本房间与距离自己最近的一个与自己尚未连接的房间
    /// 可能找不到满足条件的待连接房间
    /// </summary>
    /// <param name="roomA"></param>
    /// <param name="roomListB"></param>
    private void ConnectToClosestRoom(Room roomA, List<Room> roomListB)
    {
    
        int bestDistance = Int32.MaxValue;
        Vector2Int bestTileA = new Vector2Int();
        Vector2Int bestTileB = new Vector2Int();
        Room bestRoomB = null;
        
        foreach (Room roomB in roomListB)
        {
    
            if (roomA == roomB || roomA.IsConnected(roomB))
                continue;

            foreach (var tileA in roomA.edgeTiles)
            foreach (var tileB in roomB.edgeTiles)
            {
    
                int distanceBetweenRooms = (tileA - tileB).sqrMagnitude;

                //如果找到更近的（相对roomA）房间，更新最短路径。
                if (distanceBetweenRooms < bestDistance)
                {
    
                    bestDistance = distanceBetweenRooms;
                    bestTileA = tileA;
                    bestTileB = tileB;
                    bestRoomB = roomB;
                }
            }
        }
        
        if(bestRoomB != null)
            CreatePassage(roomA, bestRoomB, bestTileA, bestTileB);
    }

效果一样

3.地图生成相关全部代码

Assets/Scripts/MapGenerator.cs

using UnityEngine;
using System.Collections.Generic;
using System;

public enum TileType {
     Empty, Wall }

public class MapGenerator : MonoBehaviour
{
    
    #region Public Variables
    public int width = 64;
    public int height = 36;

    public string seed;                     //随机种子。
    public bool useRandomSeed;

    [Range(0, 100)]
    public int randomFillPercent = 45;      //随机填充百分比，越大洞越小。

    [Range(0, 20)]
    public int smoothLevel = 4;             //平滑程度。

    public int wallThresholdSize = 50;      //清除小墙体的阈值。
    public int roomThresholdSize = 50;      //清除小孔的的阈值。

    public int passageWidth = 4;            //通道（房间与房间直接）宽度。

    public int borderSize = 1;

    public bool showGizmos;
    #endregion

    private TileType[,] map;                     //地图集，Empty为空洞，Wall为实体墙。

    readonly int[,] upDownLeftRight = new int[4, 2] {
     {
     0, 1 }, {
     0, -1 }, {
     -1, 0 }, {
     1, 0 } };

    //存放最后实际有效的空洞房间。
    private List<Room> survivingRooms = new List<Room>();

    private void Start()
    {
    
        GenerateMap();
    }

    private void Update()
    {
    
        if (Input.GetMouseButtonDown(0))
        {
    
            survivingRooms.Clear();
            GenerateMap();
        }
    }

    //生成随机地图。
    private void GenerateMap()
    {
    
        map = new TileType[width, height];
        RandomFillMap();

        for (int i = 0; i < smoothLevel; i++)
            SmoothMap();

        //清除小洞，小墙。
        ProcessMap();

        //连接各个幸存房间。
        ConnectAllRoomsToMainRoom(survivingRooms);
    }

    //随机填充地图。
    private void RandomFillMap()
    {
    
        if (useRandomSeed)
            seed = Time.time.ToString();

        System.Random pseudoRandom = new System.Random(seed.GetHashCode());

        for (int x = 0; x < width; x++)
            for (int y = 0; y < height; y++)
                if (x == 0 || x == width - 1 || y == 0 || y == height - 1)
                    map[x, y] = TileType.Wall;
                else
                    map[x, y] = (pseudoRandom.Next(0, 100) < randomFillPercent) ? TileType.Wall : TileType.Empty;
    }

    //平滑地图
    private void SmoothMap()
    {
    
        for (int x = 0; x < width; x++)
            for (int y = 0; y < height; y++)
            {
    
                int neighbourWallTiles = GetSurroundingWallCount(x, y);

                if (neighbourWallTiles > 4)             //周围大于四个实体墙，那自己也实体墙了。
                    map[x, y] = TileType.Wall;
                else if (neighbourWallTiles < 4)        //周围大于四个为空洞，那自己也空洞了。
                    map[x, y] = TileType.Empty;
                //还有如果四四开，那就保持不变。
            }
    }

    //获取该点周围8个点为实体墙（map[x,y] == 1）的个数。
    private int GetSurroundingWallCount(int gridX, int gridY)
    {
    
        int wallCount = 0;
        for (int neighbourX = gridX - 1; neighbourX <= gridX + 1; neighbourX++)
            for (int neighbourY = gridY - 1; neighbourY <= gridY + 1; neighbourY++)
                if (neighbourX >= 0 && neighbourX < width && neighbourY >= 0 && neighbourY < height)
                {
    
                    if (neighbourX != gridX || neighbourY != gridY)
                        wallCount += map[neighbourX, neighbourY] == TileType.Wall ? 1 : 0;
                }
                else
                    wallCount++;

        return wallCount;
    }

    //加工地图，清除小洞，小墙，连接房间。
    private void ProcessMap()
    {
    
        //获取最大房间的索引
        int currentIndex = 0, maxIndex = 0, maxSize = 0;
        //获取墙区域
        List<List<Vector2Int>> wallRegions = GetRegions(TileType.Wall);
        foreach (List<Vector2Int> wallRegion in wallRegions)
            if (wallRegion.Count < wallThresholdSize)
                foreach (Vector2Int tile in wallRegion)
                    map[tile.x, tile.y] = TileType.Empty;                //把小于阈值的都铲掉。


        //获取空洞区域
        List<List<Vector2Int>> roomRegions = GetRegions(TileType.Empty);
        foreach (List<Vector2Int> roomRegion in roomRegions)
        {
    
            if (roomRegion.Count < roomThresholdSize)
                foreach (Vector2Int tile in roomRegion)
                    map[tile.x, tile.y] = TileType.Wall;                //把小于阈值的都填充。
            else
            {
    
                survivingRooms.Add(new Room(roomRegion, map));      //添加到幸存房间列表里。
                if (maxSize < roomRegion.Count)
                {
    
                    maxSize = roomRegion.Count;
                    maxIndex = currentIndex;                        //找出最大房间的索引。
                }
                ++currentIndex;
            }
        }

        if (survivingRooms.Count == 0)
            Debug.LogError("No Survived Rooms Here!!");
        else
        {
    
            survivingRooms[maxIndex].isMainRoom = true;                 //最大房间就是主房间。
            survivingRooms[maxIndex].isAccessibleFromMainRoom = true;
        }
    }

    //获取区域
    private List<List<Vector2Int>> GetRegions(TileType tileType)
    {
    
        List<List<Vector2Int>> regions = new List<List<Vector2Int>>();
        bool[,] mapFlags = new bool[width, height];

        for (int x = 0; x < width; x++)
            for (int y = 0; y < height; y++)
                if (mapFlags[x, y] == false && map[x, y] == tileType)
                    regions.Add(GetRegionTiles(x, y, tileType, ref mapFlags));

        return regions;
    }

    //从这个点开始获取区域，广度优先算法。
    private List<Vector2Int> GetRegionTiles(int startX, int startY, TileType tileType, ref bool[,] mapFlags)
    {
    
        List<Vector2Int> tiles = new List<Vector2Int>();
        Queue<Vector2Int> queue = new Queue<Vector2Int>();
        queue.Enqueue(new Vector2Int(startX, startY));
        mapFlags[startX, startY] = true;

        while (queue.Count > 0)
        {
    
            Vector2Int tile = queue.Dequeue();                       //弹出队列第一个，添加到要返回的列表里面。
            tiles.Add(tile);

            // 遍历上下左右四格
            for (int i = 0; i < 4; i++)
            {
    
                int x = tile.x + upDownLeftRight[i, 0];
                int y = tile.y + upDownLeftRight[i, 1];
                if (IsInMapRange(x, y) && mapFlags[x, y] == false && map[x, y] == tileType)
                {
    
                    mapFlags[x, y] = true;
                    queue.Enqueue(new Vector2Int(x, y));
                }
            }
        }

        return tiles;
    }

    /// <summary>
    /// 把所有房间都连接到主房间
    /// </summary>
    private void ConnectAllRoomsToMainRoom(List<Room> allRooms)
    {
    
        Room mainRoom = null;

        foreach (var room in allRooms)
        {
    
            if (room.isMainRoom)
            {
    
                mainRoom = room;
                break;
            }
        }

        if (mainRoom == null)
            return;
        
        foreach (var room in allRooms)
        {
    
            ConnectToClosestRoom(room, allRooms);
        }

        if (mainRoom.connectedRooms.Count != allRooms.Count - 1)
        {
    
            ConnectAllRoomsToMainRoom(allRooms);
        }
    }

    /// <summary>
    /// 连接本房间与距离自己最近的一个与自己尚未连接的房间
    /// 可能找不到满足条件的待连接房间
    /// </summary>
    /// <param name="roomA"></param>
    /// <param name="roomListB"></param>
    private void ConnectToClosestRoom(Room roomA, List<Room> roomListB)
    {
    
        int bestDistance = Int32.MaxValue;
        Vector2Int bestTileA = new Vector2Int();
        Vector2Int bestTileB = new Vector2Int();
        Room bestRoomB = null;
        
        foreach (Room roomB in roomListB)
        {
    
            if (roomA == roomB || roomA.IsConnected(roomB))
                continue;

            foreach (var tileA in roomA.edgeTiles)
            foreach (var tileB in roomB.edgeTiles)
            {
    
                int distanceBetweenRooms = (tileA - tileB).sqrMagnitude;

                //如果找到更近的（相对roomA）房间，更新最短路径。
                if (distanceBetweenRooms < bestDistance)
                {
    
                    bestDistance = distanceBetweenRooms;
                    bestTileA = tileA;
                    bestTileB = tileB;
                    bestRoomB = roomB;
                }
            }
        }
        
        if(bestRoomB != null)
            CreatePassage(roomA, bestRoomB, bestTileA, bestTileB);
    }
    
    //创建两个房间的通道。
    private void CreatePassage(Room roomA, Room roomB, Vector2Int tileA, Vector2Int tileB)
    {
    
        Room.ConnectRooms(roomA, roomB);
        //Debug.DrawLine(Vector2IntToWorldPoint(tileA), Vector2IntToWorldPoint(tileB), Color.green, 100);

        List<Vector2Int> line = GetLine(tileA, tileB);
        foreach (Vector2Int coord in line)
            DrawCircle(coord, passageWidth);
    }

    //获取两点直接线段经过的点。
    private List<Vector2Int> GetLine(Vector2Int from, Vector2Int to)
    {
    
        List<Vector2Int> line = new List<Vector2Int>();

        int x = from.x;
        int y = from.y;

        int dx = to.x - from.x;
        int dy = to.y - from.y;

        bool inverted = false;
        int step = Math.Sign(dx);
        int gradientStep = Math.Sign(dy);

        int longest = Mathf.Abs(dx);
        int shortest = Mathf.Abs(dy);

        if (longest < shortest)
        {
    
            inverted = true;
            longest = Mathf.Abs(dy);
            shortest = Mathf.Abs(dx);

            step = Math.Sign(dy);
            gradientStep = Math.Sign(dx);
        }

        int gradientAccumulation = longest / 2;         //梯度积累，最长边的一半。
        for (int i = 0; i < longest; i++)
        {
    
            line.Add(new Vector2Int(x, y));

            if (inverted)
                y += step;
            else
                x += step;

            gradientAccumulation += shortest;           //梯度每次增长为短边的长度。
            if (gradientAccumulation >= longest)
            {
    
                if (inverted)
                    x += gradientStep;
                else
                    y += gradientStep;
                gradientAccumulation -= longest;
            }
        }

        return line;
    }

    //以点c为原点，r为半径，画圈（拆墙）。
    private void DrawCircle(Vector2Int c, int r)
    {
    
        for (int x = -r; x <= r; x++)
            for (int y = -r; y <= r; y++)
                if (x * x + y * y <= r * r)
                {
    
                    int drawX = c.x + x;
                    int drawY = c.y + y;
                    if (IsInMapRange(drawX, drawY))
                        map[drawX, drawY] = TileType.Empty;
                }
    }

    //判断坐标是否在地图里，不管墙还是洞。
    private bool IsInMapRange(int x, int y)
    {
    
        return x >= 0 && x < width && y >= 0 && y < height;
    }
}

Assets/Scripts/Room.cs

using System;
using System.Collections.Generic;
using UnityEngine;

class Room : IComparable<Room>
{
    
    public List<Vector2Int> tiles;                           //所有坐标。
    public List<Vector2Int> edgeTiles = new List<Vector2Int>();   //靠边的坐标。
    public List<Room> connectedRooms;                   //与其直接相连的房间。
    public int roomSize;                                //就是tiles.Count。
    public bool isAccessibleFromMainRoom;               //是否能连接到主房间。
    public bool isMainRoom;                             //是否主房间（最大的房间）。

    readonly int[,] upDownLeftRight = new int[4, 2] {
     {
     0, 1 }, {
     0, -1 }, {
     -1, 0 }, {
     1, 0 } };

    public Room() {
     }

    public Room(List<Vector2Int> roomTiles, TileType[,] map)
    {
    
        tiles = roomTiles;
        roomSize = tiles.Count;
        connectedRooms = new List<Room>();
        UpdateEdgeTiles(map);
    }
    
    // 更新房间边缘瓦片集
    public void UpdateEdgeTiles(TileType[,] map)
    {
    
        edgeTiles.Clear();
        
        // 遍历上下左右四格，判断是否有墙
        foreach (Vector2Int tile in tiles)
            for (int i = 0; i < 4; i++)
            {
    
                int x = tile.x + upDownLeftRight[i, 0];
                int y = tile.y + upDownLeftRight[i, 1];
                if (map[x, y] == TileType.Wall && !edgeTiles.Contains(tile))
                {
    
                    edgeTiles.Add(tile);
                }
            }
    }

    //如果本身能连到主房间，标记其他相连的房间也能相连到主房间。
    public void MarkAccessibleFromMainRoom()
    {
    
        if (!isAccessibleFromMainRoom)
        {
    
            isAccessibleFromMainRoom = true;
            foreach (Room connectedRoom in connectedRooms)      //和他连一起的房间都能连到主房间。
                connectedRoom.MarkAccessibleFromMainRoom();
        }
    }

    // 连接房间
    public static void ConnectRooms(Room roomA, Room roomB)
    {
    
        //任何一个房间如果能连接到主房间，那另一个房间也能连到。
        if (roomA.isAccessibleFromMainRoom)
            roomB.MarkAccessibleFromMainRoom();
        else if (roomB.isAccessibleFromMainRoom)
            roomA.MarkAccessibleFromMainRoom();

        roomA.connectedRooms.Add(roomB);
        roomB.connectedRooms.Add(roomA);
    }

    // 是否连接另一个房间
    public bool IsConnected(Room otherRoom)
    {
    
        return connectedRooms.Contains(otherRoom);
    }

    // 比较房间大小
    public int CompareTo(Room otherRoom)
    {
    
        return otherRoom.roomSize.CompareTo(roomSize);
    }
}