Map Connectivity——地图连通性

MapGenerator

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

public class MapGenerator : MonoBehaviour
{
    public Transform tilePrefab;//瓦片预制体
    public Transform obstaclePrefab;//障碍物预制体
    public Vector2 mapSize;//地图尺寸

    [Range(0f, 1f)]
    public float outlinePercent;//瓦片间隙
    [Range(0f, 1f)]
    public float obstaclePercent;//障碍物比例

    List<Coord> allTileCoords;//所有瓦片坐标
    Queue<Coord> shuffledTileCoords;//乱序后的瓦片坐标

    public int seed = 10;
    Coord mapCentre;

    void Start()
    {
        GenerateMap();
    }

    public void GenerateMap()
    {
        //记录所有瓦片位置
        allTileCoords = new List<Coord>();
        for (int x = 0; x < mapSize.x; x++)
        {
            for (int y = 0; y < mapSize.y; y++)
            {
                allTileCoords.Add(new Coord(x, y));
            }
        }
        //乱序后的瓦片坐标存为队列
        shuffledTileCoords = new Queue<Coord> (Utility.ShuffleArray(allTileCoords.ToArray(), seed));
        mapCentre = new Coord((int)mapSize.x / 2, (int)mapSize.y / 2);

        string holderName = "Generated Map";
        if (transform.Find(holderName))
        {
            DestroyImmediate(transform.Find(holderName).gameObject);
        }

        Transform mapHolder = new GameObject(holderName).transform;//创建Generated Map集合瓦片
        mapHolder.parent = transform;//将Generated Map父对象设置为为MapGenerator

        //循环创建瓦片
        for (int x = 0; x < mapSize.x; x++)
        {
            for (int y = 0; y < mapSize.y; y++)
            {
                Vector3 tilePosition = CoordToPosition(x,y);//居中
                Transform newTile = Instantiate(tilePrefab, tilePosition, Quaternion.Euler(Vector3.right * 90)) as Transform;
                newTile.localScale = Vector3.one * (1 - outlinePercent);
                newTile.parent = mapHolder;//将瓦片父对象设置为Generated Map
            }
        }

        //生成障碍物
        bool[,] obstacleMap = new bool[(int)mapSize.x, (int)mapSize.y];//障碍物地图二维bool形地图

        int obstacleCount = (int)(mapSize.x * mapSize.y * obstaclePercent);//障碍物数量
        int currentObstacleCount = 0;//当前障碍物数量

        for (int i = 0; i < obstacleCount; i++)
        {
            //先默认找到的一处位置可生成障碍物
            Coord randomCoord = GetRandomCoord();//获得队列中第一个的坐标
            obstacleMap[randomCoord.x, randomCoord.y] = true;
            currentObstacleCount++;

            if (randomCoord != mapCentre && MapIsFullyAccessible(obstacleMap, currentObstacleCount))//此处位置不为中心位置且能够生成障碍物
            {
                Vector3 obstaclePosition = CoordToPosition(randomCoord.x,randomCoord.y);//坐标到实际坐标转换

                Transform newObstacle = Instantiate(obstaclePrefab, obstaclePosition + Vector3.up * 0.5f, Quaternion.identity) as Transform;
                newObstacle.parent = mapHolder;//将障碍物父对象设置为Generated Map
            }
            else
            {
                obstacleMap[randomCoord.x,randomCoord.y] = false;
                currentObstacleCount--;
            }

        }
    }

    bool MapIsFullyAccessible(bool[,] obstacleMap, int currentObstacleCount)//采用四邻域洪水填充算法判断是否能够生成障碍物
    {
        bool[,] mapFlags = new bool[obstacleMap.GetLength(0),obstacleMap.GetLength(1)];

        Queue<Coord> queue = new Queue<Coord>();//所有的坐标都会“筛选后”储存在这个队列中，一一检测
        queue.Enqueue(mapCentre);
        mapFlags[mapCentre.x,mapCentre.y] = true;//中心点标记为【已检测】

        int accessibleTileCount = 1;//中心点一直为可行走

        while(queue.Count > 0 )//队列大于0，就一直检测下去
        {
            Coord tile = queue.Dequeue();//当前检测的需要被移除出来

            for (int x = -1; x <= 1; x++)//检测相邻四周坐标点X轴
            {
                for (int y = -1; y <= 1; y++)//检测相邻四周坐标点Y轴
                {
                    int neighbourX = tile.x + x;
                    int neighbourY = tile.y + y;
                    if (x == 0 || y == 0)//保证上下左右四个位置，排除对角线上的坐标位置
                    {
                        //防止相邻点超出地图临界位置
                        if (neighbourX >= 0 && neighbourX < obstacleMap.GetLength(0) && neighbourY >= 0 && neighbourY < obstacleMap.GetLength(1))
                        {
                            //保证相邻点：未被检测；未有障碍物
                            if (!mapFlags[neighbourX,neighbourY] && !obstacleMap[neighbourX,neighbourY])
                            {
                                mapFlags[neighbourX, neighbourY] = true;
                                queue.Enqueue(new Coord(neighbourX,neighbourY));
                                accessibleTileCount ++;
                            }
                        }
                    }
                }
            }
        }

        int targetAccessibleTileCount = (int)(mapSize.x * mapSize.y - currentObstacleCount);
        return targetAccessibleTileCount == accessibleTileCount;
    }

    //坐标到实际坐标转换
    Vector3 CoordToPosition(int x, int y)
    {
        return new Vector3(-mapSize.x / 2f + 0.5f + x, 0, -mapSize.y / 2f + 0.5f + y);
    }

    //
    public Coord GetRandomCoord()
    {
        Coord randomCoord = shuffledTileCoords.Dequeue();//移除并返回在 Queue 的开头的对象。
        shuffledTileCoords.Enqueue(randomCoord);//向 Queue 的末尾添加一个对象。
        return randomCoord;
    }

    //定义每个瓦片坐标信息
    public struct Coord 
    {
        //Coord结构体存储坐标
        public int x;
        public int y;

        public Coord(int _x, int _y)
        {
            x = _x;
            y = _y;
        }

        public static bool operator ==(Coord a, Coord b) { return a.x == b.x&& a.y == b.y; }
        public static bool operator !=(Coord a, Coord b) { return !(a == b); }
    }
}

洪水填充(Flood fill)算法：

从一个起始节点开始把附近与其连通的节点提取出或填充成不同颜色颜色，直到封闭区域内的所有节点都被处理过为止，是从一个区域中提取若干个连通的点与其他相邻区域区分开(或分别染成不同颜色)的经典算法。目前有许多实现方式，基本上都显式的或隐式的使用了队列或者栈。洪水填充算法实现最常见有四邻域填充法(不考虑对角线方向的节点)，八邻域填充法(考虑对角线方向的节点)，基于扫描线填充方法。

根据实现又可以分为递归与非递归(基于栈)。最简单的实现方法是采用深度优先搜索的递归方法，也可以采用广度优先搜索的迭代来实现。

拓展：

• 通过洗牌算法实现随机地图生成器（附加：队列先进先出，Swap思路，Lerp方法、自定义结构体、Quad和Plane的区别、List转Array，深度冲突等）
• 参考洪水填充算法实现绝对通畅的随机地图生成器（附加：重载内置运算符，NavMeshObs障碍物，敌人攻击，血量缓冲，延时动画，找Bugs等）