閑來(lái)無(wú)事擦俐，到Unity官網(wǎng)上看看有沒(méi)有好玩的東西，然后就看到了這個(gè)自動(dòng)生成隨機(jī)地圖的教程披摄。話說(shuō)暗黑破壞神還有很多Roguelike的游戲都是隨機(jī)生成地圖的方式馆铁，因?yàn)橐煌Ｋ⑺⑺⑴苋啵S機(jī)生成方式能讓人覺(jué)得不無(wú)聊。但是具體是怎么做的我卻不知道埠巨，于是決定好好看看這個(gè)案例历谍。例子雖然簡(jiǎn)單一些是2D的，但是相信原理是相通的辣垒。

官方教程地址
官方教程分為了9小結(jié)望侈，我這里就之間按順序?qū)懴氯ゲ环至恕?br> 第一個(gè)教程十分簡(jiǎn)單，就是使用一個(gè)腳本勋桶，用隨機(jī)二維數(shù)組的方式生成一個(gè)地圖脱衙，0表示可以移動(dòng)區(qū)域，用Gizmos畫白色方框表示哥遮，1表示不可移動(dòng)區(qū)域，用黑色方塊表示陵究，并且點(diǎn)擊鼠標(biāo)可以生成一個(gè)新地圖眠饮。

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

public class MapGenerator : MonoBehaviour
{

    public int width; 
    public int height;

    public string seed; //使用時(shí)間作為seed生成隨機(jī)數(shù)
    public bool useRandomSeed; //是否使用隨機(jī)地圖

    [Range(0, 100)]
    public int randomFillPercent; //地圖中不可以移動(dòng)區(qū)域的比例

    int[,] map;

    void Start()
    {
        GenerateMap();
    }

    void Update()
    {
        if (Input.GetMouseButtonDown(0)) //按鍵生成新地圖
        {
            GenerateMap();
        }
    }

    void GenerateMap()
    {
        map = new int[width, height];
        RandomFillMap();

        for (int i = 0; i < 5; i++)
        {
            SmoothMap(); //迭代五次來(lái)使地圖更平滑
        }
    }
    void RandomFillMap()
    {
        if (useRandomSeed)
        {
            seed = Time.time.ToString();
        }

        System.Random pseudoRandom = new System.Random(seed.GetHashCode()); //使用時(shí)間的hashcode作為隨機(jī)數(shù)

        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] = 1;  //地圖邊緣設(shè)為墻壁
                }
                else
                {
                    map[x, y] = (pseudoRandom.Next(0, 100) < randomFillPercent) ? 1 : 0; //Next(0, 100)可以設(shè)置隨機(jī)數(shù)范圍。這里按照randomFillPercent設(shè)置墻壁和空地
                }
            }
        }
    }
    void SmoothMap() //根據(jù)周圍八塊地的墻壁塊數(shù)來(lái)smooth這個(gè)地圖
    {
        for (int x = 0; x < width; x++)
        {
            for (int y = 0; y < height; y++)
            {
                int neighbourWallTiles = GetSurroundingWallCount(x, y);

                if (neighbourWallTiles > 4) //大于4塊則這塊為墻
                    map[x, y] = 1;
                else if (neighbourWallTiles < 4) //小于4塊則這塊為地面铜邮，注意最好不要設(shè)置等于4的情況仪召，這樣會(huì)導(dǎo)致地圖就邊緣是墻寨蹋，中間是空地，缺少變化有些單調(diào)扔茅，不設(shè)置4可以讓地圖內(nèi)部也出現(xiàn)墻壁
                    map[x, y] = 0;

            }
        }
    }
    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)//只有非邊緣才計(jì)算已旧，邊緣地塊都設(shè)置為墻
                {
                    if (neighbourX != gridX || neighbourY != gridY)
                    {
                        wallCount += map[neighbourX, neighbourY];
                    }
                }
                else
                {
                    wallCount++;
                }
            }
        }

        return wallCount;
    }
    void OnDrawGizmos()
    {
        if (map != null)
        {
            for (int x = 0; x < width; x++)
            {
                for (int y = 0; y < height; y++)
                {
                    Gizmos.color = (map[x, y] == 1) ? Color.black : Color.white;
                    Vector3 pos = new Vector3(-width / 2 + x + .5f, 0, -height / 2 + y + .5f);
                    Gizmos.DrawCube(pos, Vector3.one);
                }
            }
        }
    }

}

以下為運(yùn)行截圖：

Capture.PNG

注意游戲視窗需要選中Gizmos，否則無(wú)法正常顯示地圖召娜，fill percent為45到50值的時(shí)候地圖看起來(lái)比較好运褪。
如果SmoothMap()的時(shí)候使用了大于等于或者小于等4，則地圖看下來(lái)像這樣：

Capture.PNG

第一個(gè)小結(jié)里面給出了生成地圖形狀的方法秸讹，但是它還只是一個(gè)形狀，沒(méi)有mesh雅倒。第二節(jié)里面介紹了隨機(jī)地圖的自定義結(jié)構(gòu)璃诀。第一節(jié)里面每畫出的一個(gè)方塊，第二節(jié)里面定義了一個(gè)叫做Square的類來(lái)表示它蔑匣，所有的方塊(Squares)放在一個(gè)SquareGrid類里面劣欢。
每個(gè)Square包含了8個(gè)node，分別是topLeft, topRight, bottomRight, bottomLeft 4個(gè)ControlNodes和centreTop, centreRight, centreBottom, centreLeft 4個(gè)Nodes裁良。這8個(gè)Nodes會(huì)在之后生成mesh的時(shí)候用到凿将，并且他們可以用來(lái)表示16種mesh的組合，具體原理和完整源代碼可以從這里了解趴久，這里我簡(jiǎn)單解釋一下丸相。
第一節(jié)里面講到每個(gè)方塊狀態(tài)是1則表示是墻，0則表示不是墻彼棍，現(xiàn)在想象把每個(gè)方塊縮小灭忠，則每個(gè)方塊實(shí)際上表示一個(gè)方形的一角。

下面來(lái)看這個(gè)圖

它相當(dāng)于把一個(gè)方形放大來(lái)看座硕，1弛作，2，3华匾，4四個(gè)角分別是縮小的方塊映琳，它相當(dāng)于一個(gè)開關(guān)，1表示是墻蜘拉，0表示不是墻萨西，每個(gè)角代表4位數(shù)字的一位，所有角為0時(shí)這個(gè)四位數(shù)字是0旭旭，全是1時(shí)表示15. 這四個(gè)node就是之前說(shuō)到的ControlNodes谎脯。每?jī)蓚€(gè)ControlNode中間有一個(gè)node，它們是用來(lái)構(gòu)建mesh的持寄。

可以看到由ControlNode和Node順時(shí)針構(gòu)建的三角形帶形成了獨(dú)一無(wú)二的mesh，沒(méi)種mesh對(duì)應(yīng)一個(gè)數(shù)字編號(hào)废麻。下面來(lái)看代碼荠卷，我們是如何實(shí)現(xiàn)這Square和SquareGrid的。
首先來(lái)看Node類和ControlNode類

    public class Node
    {
        public Vector3 position;
        public int vertexIndex = -1;

        public Node(Vector3 _pos)
        {
            position = _pos;
        }
    }
    public class ControlNode : Node
    {
        public bool isWall;
        public Node above, right;
        public ControlNode(Vector3 _pos, bool _isWall, float squareSize) :base(_pos)
        {
            isWall = _isWall;
            above = new Node(position + Vector3.forward * squareSize / 2f);
            right = new Node(position + Vector3.right * squareSize / 2f);
        }
    }

Node很簡(jiǎn)單烛愧，只包含位置信息油宜，ControlNode繼承自Node，除了位置信息外屑彻，還包含了它右側(cè)和上放兩個(gè)node的信息验庙。
接下來(lái)是Square類，每個(gè)square有4個(gè)ControlNode和4個(gè)node

    public class Square
    {
        public ControlNode topLeft, topRight, bottomLeft, bottomRight;
        public Node centerTop, centerBottom, centerLeft, centerRight;

        public Square(ControlNode _topLeft, ControlNode _topRight, ControlNode _bottomLeft, ControlNode _bottomRight)
        {
            topLeft = _topLeft;
            topRight = _topRight;
            bottomLeft = _bottomLeft;
            bottomRight = _bottomRight;

            centerTop = topLeft.right;
            centerLeft = bottomLeft.above;
            centerBottom = bottomLeft.right;
            centerRight = bottomRight.above;
        }
    }

然后是SquareGrid(即整個(gè)網(wǎng)格)類的初始化過(guò)程社牲，它讀取MapGenerator的map信息（數(shù)組大小以及是否為墻）,構(gòu)建整個(gè)網(wǎng)格粪薛。首先循環(huán)一遍數(shù)組初始化所有的ControlNodes，然后遍歷每一個(gè)Square(注意SquareGrid的寬和高分別為ControlNodes的寬高減一)搏恤，為每一個(gè)square設(shè)置它包含的CotrolNodes违寿。(注意Nodes已經(jīng)在初始化ControlNodes的時(shí)候完成了，因?yàn)槊總€(gè)ControlNode管兩個(gè)node)

public class SquareGrid
    {
        public Square[,] squares;
        public SquareGrid(int[,] map, float squareSize)
        {
            int nodeCountX = map.GetLength(0);
            int nodeCountY = map.GetLength(1);
            float mapWidth = nodeCountX * squareSize;
            float mapHeight = nodeCountY * squareSize;
            ControlNode[,] controlNodes = new ControlNode[nodeCountX, nodeCountY];
            for (int x = 0; x < nodeCountX; x++)
            {
                for (int y = 0; y < nodeCountY; y++)
                {
                    Vector3 position = new Vector3(-1 * mapWidth / 2 + squareSize * x + squareSize / 2f, 0, -1 * mapHeight / 2 + squareSize * y + squareSize / 2f);
                    controlNodes[x, y] = new ControlNode(position, map[x, y] == 1, squareSize);
                }

            }
            squares = new Square[nodeCountX - 1, nodeCountY - 1];
            for (int x = 0; x < nodeCountX - 1; x++)
            {
                for (int y = 0; y < nodeCountY - 1; y++)
                {
                    squares[x, y] = new Square(controlNodes[x, y + 1], controlNodes[x + 1, y + 1], controlNodes[x, y], controlNodes[x + 1, y]);
                }
            }
        }
    }

創(chuàng)建一個(gè)方法初始化SquareGrid熟空，并在MapGenerator中調(diào)用會(huì)這個(gè)方法藤巢。

    public void GenerateMesh(int[,] map, float squareSize)
    {
        squareGrid = new SquareGrid(map, squareSize);
    }

    void GenerateMap()
    {
        map = new int[width, height];
        RandomFillMap();

        for (int i = 0; i < 5; i++)
        {
            SmoothMap(); //迭代五次來(lái)使地圖更平滑
        }

        MeshGenerator meshGen = GetComponent<MeshGenerator>();
        meshGen.GenerateMesh(map, 1);
    }

最后使用OnDrawGizmos()把我們生成的網(wǎng)格結(jié)構(gòu)畫出來(lái)（記得注釋掉MapGenerator里面的OnDrawGizmos()）

void OnDrawGizmos()
    {
        if (squareGrid != null)
        {
            for (int x = 0; x < squareGrid.squares.GetLength(0); x++)
            {
                for (int y = 0; y < squareGrid.squares.GetLongLength(1); y++)
                {
                    Gizmos.color = (squareGrid.squares[x, y].topLeft.isWall) ? Color.black : Color.white;
                    Gizmos.DrawCube(squareGrid.squares[x, y].topLeft.position, Vector3.one * 0.4f);

                    Gizmos.color = (squareGrid.squares[x, y].topRight.isWall) ? Color.black : Color.white;
                    Gizmos.DrawCube(squareGrid.squares[x, y].topRight.position, Vector3.one * 0.4f);

                    Gizmos.color = (squareGrid.squares[x, y].bottomLeft.isWall) ? Color.black : Color.white;
                    Gizmos.DrawCube(squareGrid.squares[x, y].bottomLeft.position, Vector3.one * 0.4f);

                    Gizmos.color = (squareGrid.squares[x, y].bottomRight.isWall) ? Color.black : Color.white;
                    Gizmos.DrawCube(squareGrid.squares[x, y].bottomRight.position, Vector3.one * 0.4f);
                
                    Gizmos.color = Color.gray;
                    Gizmos.DrawCube(squareGrid.squares[x, y].centerBottom.position, Vector3.one * 0.15f);
                    Gizmos.DrawCube(squareGrid.squares[x, y].centerLeft.position, Vector3.one * 0.15f);
                    Gizmos.DrawCube(squareGrid.squares[x, y].centerTop.position, Vector3.one * 0.15f);
                    Gizmos.DrawCube(squareGrid.squares[x, y].centerRight.position, Vector3.one * 0.15f);
                }
            }
        }
    }

以下是運(yùn)行截圖

網(wǎng)格結(jié)構(gòu)已經(jīng)搭建好了，下一節(jié)就是生成Mesh了

前面我們已經(jīng)說(shuō)過(guò)息罗，一個(gè)square分成了16種情況代表不同的mesh掂咒，我們說(shuō)每一種mesh是一個(gè)configuration，所以我們要往Square類里面添加一個(gè)configuration屬性并把它初始化迈喉。

  public class Square {

        public ControlNode topLeft, topRight, bottomRight, bottomLeft;
        public Node centreTop, centreRight, centreBottom, centreLeft;
        public int configuration;

        public Square (ControlNode _topLeft, ControlNode _topRight, ControlNode _bottomRight, ControlNode _bottomLeft) {
            topLeft = _topLeft;
            topRight = _topRight;
            bottomRight = _bottomRight;
            bottomLeft = _bottomLeft;

            centreTop = topLeft.right;
            centreRight = bottomRight.above;
            centreBottom = bottomLeft.right;
            centreLeft = bottomLeft.above;

            if (topLeft.active)
                configuration += 8;
            if (topRight.active)
                configuration += 4;
            if (bottomRight.active)
                configuration += 2;
            if (bottomLeft.active)
                configuration += 1;
        }
    }

接下來(lái)對(duì)于每一個(gè)square绍刮，我們需要把它的三角形網(wǎng)格生成出來(lái)。Unity生成Mesh需要用到兩個(gè)component挨摸，分別是MeshFilter和MeshRenderer孩革。MeshFilter需要指定一個(gè)Mesh，我們需要設(shè)定這個(gè)Mesh的Vertices和Triangles得运，這兩個(gè)分別是頂點(diǎn)的坐標(biāo)和三角形的頂點(diǎn)索引膝蜈，由頂點(diǎn)索引找到坐標(biāo)，3個(gè)坐標(biāo)就是一個(gè)三角形了熔掺。
更新的GenerateMesh()如下

    public void GenerateMesh(int[,] map, float squareSize) {
        squareGrid = new SquareGrid(map, squareSize);

        vertices = new List<Vector3>();
        triangles = new List<int>();

        for (int x = 0; x < squareGrid.squares.GetLength(0); x ++) {
            for (int y = 0; y < squareGrid.squares.GetLength(1); y ++) {
                TriangulateSquare(squareGrid.squares[x,y]);
            }
        }

        Mesh mesh = new Mesh();
        GetComponent<MeshFilter>().mesh = mesh;

        mesh.vertices = vertices.ToArray();
        mesh.triangles = triangles.ToArray();
        mesh.RecalculateNormals();
    }

那么vertices和triangles是如何得到的呢饱搏？我們看到在循環(huán)內(nèi)對(duì)于每一個(gè)square都調(diào)用了TriangulateSquare(）,這個(gè)方法會(huì)根據(jù)square的configuration來(lái)調(diào)用MeshFromPoints方法，這個(gè)方法根據(jù)傳入的多個(gè)node置逻，把這些node的坐標(biāo)添加到vertices數(shù)組推沸，然后把這些nodes編隊(duì)成不同的三角形。
先來(lái)看TriangulateSquare

   void TriangulateSquare(Square square) {
        switch (square.configuration) {
        case 0:
            break;

        // 1 points:
        case 1:
            MeshFromPoints(square.centreBottom, square.bottomLeft, square.centreLeft);
            break;
        case 2:
            MeshFromPoints(square.centreRight, square.bottomRight, square.centreBottom);
            break;
        case 4:
            MeshFromPoints(square.centreTop, square.topRight, square.centreRight);
            break;
        case 8:
            MeshFromPoints(square.topLeft, square.centreTop, square.centreLeft);
            break;

        // 2 points:
        case 3:
            MeshFromPoints(square.centreRight, square.bottomRight, square.bottomLeft, square.centreLeft);
            break;
        case 6:
            MeshFromPoints(square.centreTop, square.topRight, square.bottomRight, square.centreBottom);
            break;
        case 9:
            MeshFromPoints(square.topLeft, square.centreTop, square.centreBottom, square.bottomLeft);
            break;
        case 12:
            MeshFromPoints(square.topLeft, square.topRight, square.centreRight, square.centreLeft);
            break;
        case 5:
            MeshFromPoints(square.centreTop, square.topRight, square.centreRight, square.centreBottom, square.bottomLeft, square.centreLeft);
            break;
        case 10:
            MeshFromPoints(square.topLeft, square.centreTop, square.centreRight, square.bottomRight, square.centreBottom, square.centreLeft);
            break;

        // 3 point:
        case 7:
            MeshFromPoints(square.centreTop, square.topRight, square.bottomRight, square.bottomLeft, square.centreLeft);
            break;
        case 11:
            MeshFromPoints(square.topLeft, square.centreTop, square.centreRight, square.bottomRight, square.bottomLeft);
            break;
        case 13:
            MeshFromPoints(square.topLeft, square.topRight, square.centreRight, square.centreBottom, square.bottomLeft);
            break;
        case 14:
            MeshFromPoints(square.topLeft, square.topRight, square.bottomRight, square.centreBottom, square.centreLeft);
            break;

        // 4 point:
        case 15:
            MeshFromPoints(square.topLeft, square.topRight, square.bottomRight, square.bottomLeft);
            break;
        }
    }

可以看到16同情況诽偷，根據(jù)一個(gè)suaqre中為1的ControlNode個(gè)數(shù)分開了坤学，然后按照順時(shí)針的方式把這些ControlNodes和包含的Nodes傳入MeshFromPoints，在這個(gè)函數(shù)里把它們組裝报慕。

    void MeshFromPoints(params Node[] points) {
        AssignVertices(points);

        if (points.Length >= 3)
            CreateTriangle(points[0], points[1], points[2]);
        if (points.Length >= 4)
            CreateTriangle(points[0], points[2], points[3]);
        if (points.Length >= 5) 
            CreateTriangle(points[0], points[3], points[4]);
        if (points.Length >= 6)
            CreateTriangle(points[0], points[4], points[5]);
    }

    void AssignVertices(Node[] points) {
        for (int i = 0; i < points.Length; i ++) {
            if (points[i].vertexIndex == -1) {
                points[i].vertexIndex = vertices.Count;
                vertices.Add(points[i].position);
            }
        }
    }

    void CreateTriangle(Node a, Node b, Node c) {
        triangles.Add(a.vertexIndex);
        triangles.Add(b.vertexIndex);
        triangles.Add(c.vertexIndex);
    }

可以看到在MeshFromPoints里深浮，首先把所有nodes加入vertices并設(shè)置vertexIndex為當(dāng)前vertices內(nèi)元素的個(gè)數(shù)(如果之前沒(méi)有加入的話)，并根據(jù)輸入的node個(gè)數(shù)的不同眠冈，分別創(chuàng)建了1到4個(gè)triangle飞苇，把三角形頂點(diǎn)的index加入triangle的數(shù)組中。 這樣蜗顽，triangles數(shù)組中就包含了所有三角形的信息布卡，每三個(gè)元素代表一個(gè)三角形，單個(gè)元素代表三角形頂點(diǎn)坐標(biāo)的索引雇盖，可以根據(jù)索引去vertices里找到對(duì)應(yīng)node的坐標(biāo)忿等。這樣Unity就能畫出mesh了。
我們把OnDrawGizmos注釋崔挖，然后代碼更代碼更新后(不要忘記給腳本所在Gameobject添加MeshFilter和MeshRenderer)贸街，運(yùn)行游戲，可以看到如下的Mesh狸相。(我給Mesh添加了一個(gè)紅色material膜楷，所以是紅色的)

這樣我們的Mesh就生成好了

生成好了Mesh缝裤，下一節(jié)需要把我們這個(gè)2D的mesh面變成3D的,大體思路是找到地圖中的邊緣節(jié)線(outline)然后生成一個(gè)Wall。

Capture.PNG

Thanks for the tutorial Sebastian, really enjoying it so far! I think there's some confusion in your reasoning about the outline edge fix at the beginning of the video though. It shouldn't matter whether you define a triangle ABC or CAB or any clockwise permutation, as long as you're keeping edge direction consistent in other places. In both ABC and CAB, CA has the same direction. It looks like the issue arises from GetConnectedOutlineVertex(), which doesn't preserve edge direction. Consider a triangle ABC, where CA is an outline edge (and clockwise with respect to the triangle and our perspective because we defined the triangle that way). As written, if you call GetConnectedOutlineVertex() on vertex A, it will look at AB first, which is clockwise, but not an outline edge. Then it will continue onto AC and determine that AC is an outline edge, but AC is counterclockwise with respect to the triangle, which causes the outline direction to run the wrong way. I've re-written GetConnectedOutlineVertex() at the gist below such that it preserves the clockwise edge direction by only looking at clockwise edges: https://gist.github.com/anonymous/e7ead60368e53440d93655e73bf7853e

視頻的下一步為我們的Map添加了一個(gè)邊，即擴(kuò)展了地圖的邊緣山叮，以確保地圖邊緣不會(huì)是鏤空的著榴，更改MapGenerator的GenerateMap方法，把border寬設(shè)為1屁倔，border的部分全是墻壁：

 void GenerateMap() {
        map = new int[width,height];
        RandomFillMap();

        for (int i = 0; i < 5; i ++) {
            SmoothMap();
        }

        int borderSize = 1;
        int[,] borderedMap = new int[width + borderSize * 2,height + borderSize * 2];

        for (int x = 0; x < borderedMap.GetLength(0); x ++) {
            for (int y = 0; y < borderedMap.GetLength(1); y ++) {
                if (x >= borderSize && x < width + borderSize && y >= borderSize && y < height + borderSize) {
                    borderedMap[x,y] = map[x-borderSize,y-borderSize];
                }
                else {
                    borderedMap[x,y] =1;
                }
            }
        }

        MeshGenerator meshGen = GetComponent<MeshGenerator>();
        meshGen.GenerateMesh(borderedMap, 1);
    }

回到MeshGenrerator, 上一節(jié)我們有vertices來(lái)儲(chǔ)存所有頂點(diǎn)坐標(biāo)脑又，已經(jīng)triangles來(lái)儲(chǔ)存三角形的索引，但是我們還需要一個(gè)三角形類來(lái)讓我們更加方便的獲取某個(gè)三角形的三個(gè)頂點(diǎn)

   struct Triangle {
        public int vertexIndexA;
        public int vertexIndexB;
        public int vertexIndexC;
        int[] vertices;

        public Triangle (int a, int b, int c) {
            vertexIndexA = a;
            vertexIndexB = b;
            vertexIndexC = c;

            vertices = new int[3];
            vertices[0] = a;
            vertices[1] = b;
            vertices[2] = c;
        }

        public int this[int i] {
            get {
                return vertices[i];
            }
        }

        public bool Contains(int vertexIndex) {
            return vertexIndex == vertexIndexA || vertexIndex == vertexIndexB || vertexIndex == vertexIndexC;
        }
    }

這個(gè)類定義了一個(gè)三角形锐借，里邊包括獲取頂點(diǎn)索引以及判斷一個(gè)頂點(diǎn)是否屬于這個(gè)三角形的方法挂谍。然后由于我們要判斷一個(gè)edge是不是outline edge，我們需要知道一個(gè)頂點(diǎn)屬于哪些三角形瞎饲，以判斷兩個(gè)相鄰頂點(diǎn)組成的edge是否只有一個(gè)公共三角形口叙，如果是，它就是一條outline edge嗅战。所以我們建立一個(gè)dictionary妄田，key為頂點(diǎn)索引，value是一個(gè)三角形列表

Dictionary<int,List<Triangle>> triangleDictionary = new Dictionary<int, List<Triangle>> ();

既然有了三角形類驮捍，那么在之前創(chuàng)建三角形的時(shí)候就要同時(shí)創(chuàng)建具體的三角形對(duì)象疟呐，并把
它們加入dictionary里面。

  void CreateTriangle(Node a, Node b, Node c) {
        triangles.Add(a.vertexIndex);
        triangles.Add(b.vertexIndex);
        triangles.Add(c.vertexIndex);

        Triangle triangle = new Triangle (a.vertexIndex, b.vertexIndex, c.vertexIndex);
        AddTriangleToDictionary (triangle.vertexIndexA, triangle);
        AddTriangleToDictionary (triangle.vertexIndexB, triangle);
        AddTriangleToDictionary (triangle.vertexIndexC, triangle);
    }

    void AddTriangleToDictionary(int vertexIndexKey, Triangle triangle) {
        if (triangleDictionary.ContainsKey (vertexIndexKey)) {
            triangleDictionary [vertexIndexKey].Add (triangle);
        } else {
            List<Triangle> triangleList = new List<Triangle>();
            triangleList.Add(triangle);
            triangleDictionary.Add(vertexIndexKey, triangleList);
        }
    }

有了triangleDictionary东且，我們可以寫一個(gè)方法启具，判斷兩個(gè)node組成的edge是不是outline edge。獲取第一個(gè)node所屬于的所有三角形珊泳，逐個(gè)判斷該三角形是否包含第二個(gè)node鲁冯，若有一個(gè)以上三角形包括，則不是outline edge色查。

    bool IsOutlineEdge(int vertexA, int vertexB) {
        List<Triangle> trianglesContainingVertexA = triangleDictionary [vertexA];
        int sharedTriangleCount = 0;

        for (int i = 0; i < trianglesContainingVertexA.Count; i ++) {
            if (trianglesContainingVertexA[i].Contains(vertexB)) {
                sharedTriangleCount ++;
                if (sharedTriangleCount > 1) {
                    break;
                }
            }
        }
        return sharedTriangleCount == 1;
    }

下面我們創(chuàng)建一個(gè)方法薯演，給定一個(gè)outline vertex，找到它的outline edge

int GetConnectedOutlineVertex(int vertexIndex) {
    // given a vertex, if it is in an outline, return the next vertex in the outline.
    //   returns -1 if vertexIndex is not in an outline.
    List<Triangle> triangles = triangleDict[vertexIndex];
    foreach (Triangle triangle in triangles) {
        for (int i = 0; i < 3; i++) {
            // we want to examine the clockwise edge in the triangle which starts with vertexIndex (there is only one).
            //   since we defined the vertices in clockwise order, we just have to wrap around to the first vertex
            //   in the case where vertexIndex is the third vertex.
            if (vertexIndex == triangle.Vertices[i]) {
                int nextVertexIndex = triangle.Vertices[(i + 1) % 3];  // mod 3 wraps the index
                if (IsOutlineEdge(vertexIndex, nextVertexIndex)) {
                    return nextVertexIndex;
                }
            }
        }
    }
    return -1;
}

要注意的是這個(gè)方法的實(shí)現(xiàn)和作者是不一樣的秧了，而是取自我之前引用的評(píng)論里面的實(shí)現(xiàn)跨扮。沒(méi)有使用作者的實(shí)現(xiàn)是因?yàn)槲覜](méi)有使用作者關(guān)于上一節(jié)TriangulateSquare的修改，不知道他那么改是如何保證outline edge是順時(shí)針的，而這個(gè)實(shí)現(xiàn)就很清楚了衡创，一個(gè)節(jié)點(diǎn)在一個(gè)三角形中連著兩條邊帝嗡，只有它和順時(shí)針的下一個(gè)節(jié)點(diǎn)組成的edge是outline edge時(shí), 我們才需+要返回。如圖所示璃氢，當(dāng)我們找尋A節(jié)點(diǎn)的outline edge時(shí)丈探，其實(shí)只需考慮順時(shí)針?lè)较虻牡腂節(jié)點(diǎn)，至于CA是不是outline edge拔莱，我們會(huì)在找尋C節(jié)點(diǎn)的outline edge的時(shí)候判斷。所以上面的代碼就很好理解隘竭，我們只考慮輸入的節(jié)點(diǎn)所在三角的下一個(gè)頂點(diǎn)塘秦，如果那個(gè)點(diǎn)是outline，則返回动看，否則返回-1.

然后我們需要一個(gè)數(shù)組來(lái)儲(chǔ)存outlines尊剔，每個(gè)outline又是多個(gè)vertex組成的，所以需要一個(gè)list的list菱皆。同時(shí)為了不搜索重復(fù)的node须误，我們創(chuàng)建一個(gè)HashSet來(lái)保存已經(jīng)搜索過(guò)的node。

    Dictionary<int,List<Triangle>> triangleDictionary = new Dictionary<int,   List<Triangle>> ();
    List<List<int>> outlines = new List<List<int>> ();
    HashSet<int> checkedVertices = new HashSet<int>();

接下來(lái)我們需要遍歷所有的vertex仇轻，然后得到所有的outlines

    void CalculateMeshOutlines() {

        for (int vertexIndex = 0; vertexIndex < vertices.Count; vertexIndex ++) {
            if (!checkedVertices.Contains(vertexIndex)) {
               
                int newOutlineVertex = GetConnectedOutlineVertex(vertexIndex); //得到下一個(gè)outline vertex
                if (newOutlineVertex != -1) {     
                     checkedVertices.Add(vertexIndex);  //vertexIndex 是outline中的一個(gè)vertex
                    List<int> newOutline = new List<int>();
                    newOutline.Add(vertexIndex);
                    outlines.Add(newOutline);
                    FollowOutline(newOutlineVertex, outlines.Count-1);
                    outlines[outlines.Count-1].Add(vertexIndex);
                }
            }
        }
    }

    void FollowOutline(int vertexIndex, int outlineIndex) {
        outlines [outlineIndex].Add (vertexIndex); //遞歸的找尋outline 上的下一個(gè)vertex
        checkedVertices.Add (vertexIndex);
        int nextVertexIndex = GetConnectedOutlineVertex (vertexIndex);

        if (nextVertexIndex != -1) {
            FollowOutline(nextVertexIndex, outlineIndex);
        }
    }

這樣我們就有了所有我們創(chuàng)建outline wall的信息了京痢，在真正創(chuàng)建之前還有兩個(gè)優(yōu)化可以做。因?yàn)槲覀儎?chuàng)建了checkedVertices數(shù)組篷店，所以在GetConnectedOutlineVertex的時(shí)候如果vertex已經(jīng)check過(guò)了祭椰，說(shuō)明它已經(jīng)被加入了一條outline中，我們就不需要再做處理疲陕。

if (vertexIndex == triangle.Vertices[i]) {
                int nextVertexIndex = triangle.Vertices[(i + 1) % 3];  // mod 3 wraps the index
                if (!checkedVertices.Contains(nextVertexIndex) && IsOutlineEdge(vertexIndex, nextVertexIndex)) {
                    return nextVertexIndex;
                }
            }

另一個(gè)優(yōu)化是當(dāng)一個(gè)suqare的4個(gè)control node都為1時(shí)方淤，這4個(gè)vertex則一定不屬于outline edge，所以更改TriangulateSquare函數(shù)

 case 15:
            MeshFromPoints(square.topLeft, square.topRight, square.bottomRight, square.bottomLeft);
            checkedVertices.Add(square.topLeft.vertexIndex);
            checkedVertices.Add(square.topRight.vertexIndex);
            checkedVertices.Add(square.bottomRight.vertexIndex);
            checkedVertices.Add(square.bottomLeft.vertexIndex);
            break;

接下來(lái)就是生成WallMesh了蹄殃，在GenerateMesh里先reset triangleDictionary携茂，outlines和checkedVertices，然后調(diào)用生成WallMesh的方法诅岩。

 public void GenerateMesh(int[,] map, float squareSize) {
        triangleDictionary.Clear ();
        outlines.Clear ();
        checkedVertices.Clear ();
        ......
        CreateWallMesh ();
}

在CreateWallMesh小調(diào)用CalculateMeshOutlines得到outlines讳苦。對(duì)于每一條outline，遍歷其vertex并手動(dòng)添加墻面所需vertex到wallVertices里吩谦。要注意因?yàn)槲覀兊膲κ菑睦锩婵吹模ㄒ曨l說(shuō)法view from inside医吊，我不是很理解），所以我們需要逆時(shí)針安排這些vertex組成三角形逮京。

  void CreateWallMesh() {

        CalculateMeshOutlines ();

        List<Vector3> wallVertices = new List<Vector3> ();
        List<int> wallTriangles = new List<int> ();
        Mesh wallMesh = new Mesh ();
        float wallHeight = 5;

        foreach (List<int> outline in outlines) {
            for (int i = 0; i < outline.Count -1; i ++) {
                int startIndex = wallVertices.Count;
                wallVertices.Add(vertices[outline[i]]); // left
                wallVertices.Add(vertices[outline[i+1]]); // right
                wallVertices.Add(vertices[outline[i]] - Vector3.up * wallHeight); // bottom left
                wallVertices.Add(vertices[outline[i+1]] - Vector3.up * wallHeight); // bottom right

                wallTriangles.Add(startIndex + 0);
                wallTriangles.Add(startIndex + 2);
                wallTriangles.Add(startIndex + 3);

                wallTriangles.Add(startIndex + 3);
                wallTriangles.Add(startIndex + 1);
                wallTriangles.Add(startIndex + 0);
            }
        }
        wallMesh.vertices = wallVertices.ToArray ();
        wallMesh.triangles = wallTriangles.ToArray ();
        walls.mesh = wallMesh;
    }

不要忘記在前面新建一個(gè)mesh filter

 public MeshFilter walls;

在editor的gameobject里新建一個(gè)子物體Walls卿堂，給他添加Mesh filter和Mesh renderer，并把這個(gè)mesh filter分配給MeshGenerator。
運(yùn)行游戲草描，可以看到墻面已經(jīng)正常生成出來(lái)了览绿，點(diǎn)擊鼠標(biāo)可以生成帶墻面的新地圖

Capture.PNG

我試了下順時(shí)鐘添加墻面三角形頂點(diǎn)，出來(lái)的墻面果然有問(wèn)題

下一步是清理地圖中的很小的墻體或者很小的空洞穗慕，讓地圖看起來(lái)更平滑漂亮饿敲，思路就是用flood fill算法得到所有的空洞放到一個(gè)數(shù)組里，得到所有的相連墻塊放到一個(gè)數(shù)組里逛绵，然后設(shè)定一個(gè)閾值怀各，小于閾值的墻體設(shè)為空地，空地設(shè)為墻體术浪。
首先為了更方便的flood fill瓢对，我們創(chuàng)建一個(gè)struct用來(lái)記錄tile的坐標(biāo)，在MapGenerator中：

    struct Coord {
        public int tileX;
        public int tileY;

        public Coord(int x, int y) {
            tileX = x;
            tileY = y;
        }
    }

我們想用list來(lái)保存數(shù)組胰苏，所以

using System.Collections.Generic;

然后創(chuàng)建flood fill的方法硕蛹，該方法返回Coord的list。

 List<Coord> GetRegionTiles(int startX, int startY) {
        List<Coord> tiles = new List<Coord> ();
        int[,] mapFlags = new int[width,height];//表示這個(gè)tile是否已經(jīng)搜索過(guò)
        int tileType = map [startX, startY];//確定這個(gè)tile是墻還是地

        Queue<Coord> queue = new Queue<Coord> ();//下面是flood fill
        queue.Enqueue (new Coord (startX, startY));
        mapFlags [startX, startY] = 1;

        while (queue.Count > 0) {
            Coord tile = queue.Dequeue();
            tiles.Add(tile); //彈出的時(shí)候加入數(shù)組

            for (int x = tile.tileX - 1; x <= tile.tileX + 1; x++) { //查看tile的所有相鄰tile
                for (int y = tile.tileY - 1; y <= tile.tileY + 1; y++) {
                    if (IsInMapRange(x,y) && (y == tile.tileY || x == tile.tileX)) {//tile的位置必須是合法的并且flood fill只考慮上下左右不考慮斜方向
                        if (mapFlags[x,y] == 0 && map[x,y] == tileType) {
                            mapFlags[x,y] = 1; //滿足條件的設(shè)為已搜索并加入隊(duì)列
                            queue.Enqueue(new Coord(x,y));
                        }
                    }
                }
            }
        }
        return tiles;
    }

IsInMapRange是一個(gè)用來(lái)判斷一個(gè)tile是否合法的方法

  bool IsInMapRange(int x, int y) {
        return x >= 0 && x < width && y >= 0 && y < height;
    }

以上的方法能夠從一個(gè)tile找到這個(gè)tile所在的空地或墻體包含的所有tile硕并，一張地圖有多個(gè)獨(dú)立空地或者獨(dú)立墻體法焰，所以我們需要一個(gè)方法來(lái)得到所有的獨(dú)立空地或墻體。

List<List<Coord>> GetRegions(int tileType) {
        List<List<Coord>> regions = new List<List<Coord>> ();
        int[,] mapFlags = new int[width,height];

        for (int x = 0; x < width; x ++) {
            for (int y = 0; y < height; y ++) {
                if (mapFlags[x,y] == 0 && map[x,y] == tileType) {
                    List<Coord> newRegion = GetRegionTiles(x,y);
                    regions.Add(newRegion);

                    foreach (Coord tile in newRegion) {
                        mapFlags[tile.tileX, tile.tileY] = 1;
                    }
                }
            }
        }
        return regions;
    }

這個(gè)方法輸入一個(gè)類型倔毙，返回這個(gè)類型的所有Regions埃仪，方法是遍歷整個(gè)地圖，從第一個(gè)tile開始調(diào)用GetRegionTiles(如果tile類型正確)陕赃，得到它的region并把region里的tile都設(shè)置為已經(jīng)搜索過(guò)贵试，循環(huán)下去。
然后只需要寫一個(gè)方法來(lái)遍歷regions并吧小于閾值的tile改變類型即可凯正。

void ProcessMap() {
        List<List<Coord>> wallRegions = GetRegions (1);
        int wallThresholdSize = 50; //墻的region內(nèi)的tile數(shù)量小于50則設(shè)為空地
        foreach (List<Coord> wallRegion in wallRegions) {
            if (wallRegion.Count < wallThresholdSize) {
                foreach (Coord tile in wallRegion) {
                    map[tile.tileX,tile.tileY] = 0;
                }
            }
        }
        List<List<Coord>> roomRegions = GetRegions (0);
        int roomThresholdSize = 50;//空地的region內(nèi)的tile數(shù)量小于50則設(shè)為墻
        foreach (List<Coord> roomRegion in roomRegions) {
            if (roomRegion.Count < roomThresholdSize) {
                foreach (Coord tile in roomRegion) {
                    map[tile.tileX,tile.tileY] = 1;
                }
            }
        }
    }

最后只需要在生成地圖邊框前調(diào)用ProcessMap即可毙玻。
不使用ProcesMap：

下一節(jié)是要在離散的Room中創(chuàng)建一條把兩個(gè)Room相連起來(lái)，這里我們定義兩個(gè)Room相連是他們有一條公共的通道廊散，如果A連B桑滩，B連C，AC是并不相連的允睹。
首先我們創(chuàng)建一個(gè)Room類來(lái)儲(chǔ)存我們所有需要的Room信息：

class Room {
        public List<Coord> tiles;
        public List<Coord> edgeTiles;
        public List<Room> connectedRooms;
        public int roomSize;

        public Room() {
        }

        public Room(List<Coord> roomTiles, int[,] map) {
            tiles = roomTiles;
            roomSize = tiles.Count;
            connectedRooms = new List<Room>();

            edgeTiles = new List<Coord>();
            foreach (Coord tile in tiles) {
                for (int x = tile.tileX-1; x <= tile.tileX+1; x++) {
                    for (int y = tile.tileY-1; y <= tile.tileY+1; y++) {
                        if (x == tile.tileX || y == tile.tileY) {
                            if (map[x,y] == 1) {
                                edgeTiles.Add(tile);
                            }
                        }
                    }
                }
            }
        }

        public static void ConnectRooms(Room roomA, Room roomB) {
            roomA.connectedRooms.Add (roomB);
            roomB.connectedRooms.Add (roomA);
        }

        public bool IsConnected(Room otherRoom) {
            return connectedRooms.Contains(otherRoom);
        }
    }
}

可以看到他的構(gòu)造方法根據(jù)ROOM的所有tiles坐標(biāo)計(jì)算得到edge tile运准，并且有連接相鄰room的方法，以及判斷room是否相鄰的方法缭受。
在PrcessMap中我們除去了過(guò)小的Room胁澳，我們需要把剩下的Room儲(chǔ)存起來(lái)并且相連：

List<List<Coord>> roomRegions = GetRegions (0);
        int roomThresholdSize = 50;
        List<Room> survivingRooms = new List<Room> ();

        foreach (List<Coord> roomRegion in roomRegions) {
            if (roomRegion.Count < roomThresholdSize) {
                foreach (Coord tile in roomRegion) {
                    map[tile.tileX,tile.tileY] = 1;
                }
            }
            else {
                survivingRooms.Add(new Room(roomRegion, map));
            }
        }
        ConnectClosestRooms (survivingRooms);

連接Room的方法非常暴力，循環(huán)所有的rooms米者，每?jī)蓚€(gè)room再對(duì)他們所有的tile做循環(huán)比較距離韭畸，取最短的距離：

void ConnectClosestRooms(List<Room> allRooms) {

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

        foreach (Room roomA in allRooms) {
            possibleConnectionFound = false;

            foreach (Room roomB in allRooms) {
                if (roomA == roomB) {
                    continue;
                }
                if (roomA.IsConnected(roomB)) {//防止已經(jīng)找到AB后又找BA
                    possibleConnectionFound = false;
                    break;
                }

                for (int tileIndexA = 0; tileIndexA < roomA.edgeTiles.Count; tileIndexA ++) {
                    for (int tileIndexB = 0; tileIndexB < roomB.edgeTiles.Count; tileIndexB ++) {
                        Coord tileA = roomA.edgeTiles[tileIndexA];
                        Coord tileB = roomB.edgeTiles[tileIndexB];
                        int distanceBetweenRooms = (int)(Mathf.Pow (tileA.tileX-tileB.tileX,2) + Mathf.Pow (tileA.tileY-tileB.tileY,2));

                        if (distanceBetweenRooms < bestDistance || !possibleConnectionFound) { //沒(méi)有找到過(guò)潛在的連接或者新距離小于目前最好距離宇智，則視為找到了新連接
                            bestDistance = distanceBetweenRooms;
                            possibleConnectionFound = true;
                            bestTileA = tileA;
                            bestTileB = tileB;
                            bestRoomA = roomA;
                            bestRoomB = roomB;
                        }
                    }
                }
            }
            if (possibleConnectionFound) { //對(duì)新連接創(chuàng)造Pass
                CreatePassage(bestRoomA, bestRoomB, bestTileA, bestTileB);
            }
        }
    }

然后我們?cè)趦蓚€(gè)tile之間畫一條debug線

    void CreatePassage(Room roomA, Room roomB, Coord tileA, Coord tileB) {
        Room.ConnectRooms (roomA, roomB);
        Debug.DrawLine (CoordToWorldPoint (tileA), CoordToWorldPoint (tileB), Color.green, 100);
    }

    Vector3 CoordToWorldPoint(Coord tile) {
        return new Vector3 (-width / 2 + .5f + tile.tileX, 2, -height / 2 + .5f + tile.tileY);
    }

我們稍微調(diào)大randomFillPercent，然后運(yùn)行游戲

可以看到一條綠色的線表示兩個(gè)Room連起來(lái)了胰丁，但是我們目前只保證一個(gè)Room一定會(huì)和另一個(gè)相連随橘，卻不保證所有Room最后是連通的。我們將在下一節(jié)處理這個(gè)問(wèn)題锦庸。

作者在這一節(jié)使用的連接所有房間的方法emm非常繞机蔗，我沒(méi)有看懂，但是我在Youtube的評(píng)論里面發(fā)現(xiàn)了更好理解的方法甘萧，那就是在部分Room連接之后萝嘁，對(duì)于整個(gè)地圖再做一遍和之前一樣的flood fill，形成新的room regions扬卷，然后再把最近的rooms相連接牙言，知道最后做flood fill的時(shí)候只出現(xiàn)一個(gè)region，所有的room就連通了邀泉。但是這樣做的話需要先把上一節(jié)中用debugdraw連起來(lái)的room確確實(shí)實(shí)的連起來(lái)。這是下一節(jié)的內(nèi)容钝鸽。我把它提前放到這一節(jié)來(lái)講汇恤。而且我使用的找到相連的square的方法和作者介紹的也有所不同。
基本思路是這樣的拔恰，前面一節(jié)CreatePassage中我們已經(jīng)得到需要連接的兩個(gè)room中的點(diǎn)因谎，我們把靠左邊的點(diǎn)作為起始點(diǎn)，另一個(gè)作為終點(diǎn)颜懊。然后計(jì)算這條線的斜率财岔。設(shè)定一個(gè)當(dāng)前的探索點(diǎn)為起始點(diǎn)。
如果斜率為正河爹，而且斜率大于1匠璧，則這條線向上的趨勢(shì)大，我們就把探索點(diǎn)的Y坐標(biāo)加一咸这，重新計(jì)算該點(diǎn)到終點(diǎn)的斜率夷恍，并把新探索點(diǎn)加入path的列表中，重復(fù)該步驟媳维。如果斜率小于一酿雪，則說(shuō)明向右的趨勢(shì)大，我們就把探索點(diǎn)的X坐標(biāo)加一侄刽，并重新計(jì)算斜率指黎，并把新探索點(diǎn)加入path的列表中，重復(fù)該步驟州丹。需要注意如果探索點(diǎn)和目標(biāo)點(diǎn)X相同醋安，計(jì)算斜率會(huì)出現(xiàn)除0，這時(shí)需要手動(dòng)把斜率設(shè)為無(wú)窮大。
如果斜率為負(fù)茬故，而且斜率小于-1盖灸，則這條線向下的趨勢(shì)大，我們就把探索點(diǎn)的Y坐標(biāo)減一磺芭，重新計(jì)算該點(diǎn)到終點(diǎn)的斜率赁炎，并把新探索點(diǎn)加入path的列表中，重復(fù)該步驟钾腺。如果斜率大于-1徙垫，則說(shuō)明向右的趨勢(shì)大，我們就把探索點(diǎn)的X坐標(biāo)加一放棒，并重新計(jì)算斜率姻报，并把新探索點(diǎn)加入path的列表中，重復(fù)該步驟间螟。需要注意如果探索點(diǎn)和目標(biāo)點(diǎn)X相同吴旋，計(jì)算斜率會(huì)出現(xiàn)除0，這時(shí)需要手動(dòng)把斜率設(shè)為無(wú)窮小厢破。
這樣計(jì)算完畢之后列表里就會(huì)有從一個(gè)Room到另一個(gè)Room的完整路徑坐標(biāo)荣瑟，把這些坐標(biāo)的map對(duì)應(yīng)值設(shè)置為0鼻由，就可以挖出一條通道了间聊，注意這樣挖通道的寬度只有1，所以我使用了作者下一節(jié)提到的DrawCircle函數(shù)來(lái)拓展通道的寬度氢妈。

   void CreatePassage(Room roomA, Room roomB, Coord tileA, Coord tileB)
    {
        Room.ConnectRooms(roomA, roomB);
        Debug.Log("connnect:"+"("+tileA.tileX+","+tileA.tileY+")"+" and "+ "(" + tileB.tileX + "," + tileB.tileY + ")");
        Debug.DrawLine(CoordToWorldPoint(tileA), CoordToWorldPoint(tileB), Color.green, 100);
        RemovePassageWalls(tileA,  tileB);
    }

    void RemovePassageWalls(Coord tileA, Coord tileB)
    {
        List<Coord> pendingRemove = new List<Coord>
        {
            tileA,
            tileB
        };
        Coord startTile = tileA.tileX <= tileB.tileX ? tileA : tileB;
        Coord endTile = tileA.tileX > tileB.tileX ? tileA : tileB;
        float gradient = (endTile.tileY - startTile.tileY)*1.0f / (endTile.tileX - startTile.tileX);
        Coord searchTile = startTile;
        if(gradient>=0)
        {
            while(!searchTile.Equal(endTile))
            {
                if(gradient>=1)
                {
                    searchTile.tileY++;
                }
                else
                {
                    searchTile.tileX++;
                }
                if (endTile.tileX != searchTile.tileX)
                {
                    gradient = (endTile.tileY - searchTile.tileY) * 1.0f / (endTile.tileX - searchTile.tileX);
                }
                else
                {
                    gradient = Mathf.Infinity;
                }
                Coord nextTile = searchTile;
                pendingRemove.Add(nextTile);
            }
        }
        else
        {
            while (!searchTile.Equal(endTile))
            {
                if (gradient < -1.0f)
                {
                    searchTile.tileY--;
                }
                else
                {
                    searchTile.tileX++;
                }
                if (endTile.tileX != searchTile.tileX)
                {
                    gradient = (endTile.tileY - searchTile.tileY)*1.0f / (endTile.tileX - searchTile.tileX);
                }
                else
                {
                    gradient = Mathf.NegativeInfinity;
                }
                Coord nextTile = searchTile;
                pendingRemove.Add(nextTile);
            }
        }

        foreach (Coord pendCoord in pendingRemove)
        {
            DrawCircle(pendCoord, 1);
        }

    }
    void DrawCircle(Coord 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.tileX + x;
                    int drawY = c.tileY + y;
                    if (IsInMapRange(drawX, drawY))
                    {
                        map[drawX, drawY] = 0;
                    }
                }
            }
        }
    }

運(yùn)行游戲见坑，可以看到地圖是這樣的

創(chuàng)建通道前

創(chuàng)建通道后

然后為了把所有的Room連接起來(lái)嚷掠，我們修改ProcessMap函數(shù)，再做flood fill荞驴，直到Region的數(shù)目只有1.

void ProcessMap()
    {
        List<List<Coord>> wallRegions = GetRegions(1);
        int wallThresholdSize = 50; //墻的region內(nèi)的tile數(shù)量小于50則設(shè)為Room
        foreach (List<Coord> wallRegion in wallRegions)
        {
            if (wallRegion.Count < wallThresholdSize)
            {
                foreach (Coord tile in wallRegion)
                {
                    map[tile.tileX, tile.tileY] = 0;
                }
            }
        }
        List<List<Coord>> roomRegions = GetRegions(0);
        int roomThresholdSize = 50;//Room的region內(nèi)的tile數(shù)量小于50則設(shè)為墻
        List<Room> survivingRooms = new List<Room>();

        foreach (List<Coord> roomRegion in roomRegions)
        {
            if (roomRegion.Count < roomThresholdSize)
            {
                foreach (Coord tile in roomRegion)
                {
                    map[tile.tileX, tile.tileY] = 1;
                }
            }
            else
            {
                survivingRooms.Add(new Room(roomRegion, map));
            }
        }
        ConnectClosestRooms(survivingRooms);
        int numRooms = survivingRooms.Count;
        while (numRooms > 1)
        {
            List<List<Coord>> updatedRoomRegions = GetRegions(0);
            List<Room> updatedSurvivingRooms = new List<Room>();
            foreach (List<Coord> roomRegion in updatedRoomRegions)
            {
                updatedSurvivingRooms.Add(new Room(roomRegion, map));
            }
            ConnectClosestRooms(updatedSurvivingRooms);
            numRooms = updatedSurvivingRooms.Count;
        }
    }

只進(jìn)行一次flood fill

多次flood fill

最后一節(jié)作者給地圖添加了Collision和Texture不皆。并且Collision分為了3D和2D模式。
我們只看3DCollision熊楼。想要了解2D的可以前往：
這里查看源碼與步驟
作者首先改變了一下我們Map的hierachy粟焊。在Wall的同級(jí)建了一個(gè)Cave的Object，并且把原來(lái)父Object的mesh filter和renderer都移動(dòng)了進(jìn)來(lái)孙蒙。然后創(chuàng)建了一個(gè)ground平面项棠，和新建了一個(gè)player的object，寫了一個(gè)簡(jiǎn)單操控player的腳本挎峦。

public class Player : MonoBehaviour
{

    Rigidbody rigidbody;
    Vector3 velocity;

    void Start()
    {
        rigidbody = GetComponent<Rigidbody>();
    }

    void Update()
    {
        velocity = new Vector3(Input.GetAxisRaw("Horizontal"), 0, Input.GetAxisRaw("Vertical")).normalized * 10;
    }

    void FixedUpdate()
    {
        rigidbody.MovePosition(rigidbody.position + velocity * Time.fixedDeltaTime);
    }
}

然后代碼里MeshGenerator創(chuàng)建一個(gè)cave的Meshfilter

public MeshFilter Caves; 
 public bool is2D; //2D不生成墻

GenerateMesh中

 Caves.mesh = mesh; //原來(lái)是 GetComponent<MeshFilter>().mesh = mesh;

CreateWallMesh中給墻添加Collision:

MeshCollider wallCollider = walls.gameObject.AddComponent<MeshCollider>();
wallCollider.sharedMesh = wallMesh;

運(yùn)行游戲發(fā)現(xiàn)小方塊已經(jīng)會(huì)被墻阻擋了香追。

接下來(lái)添加Texture。
我們?cè)贕enerateMesh方法設(shè)定Mesh的vertices和triangles之后添加下面的代碼來(lái)個(gè)Texture設(shè)定UV

        int tileAmount = 10;//這個(gè)值可以作坊Texture,讓它出現(xiàn)tile的重復(fù)效果
        Vector2[] uvs = new Vector2[vertices.Count];
        for (int i = 0; i < vertices.Count; i++)
        {
            float percentX = Mathf.InverseLerp(-map.GetLength(0) / 2 * squareSize, map.GetLength(0) / 2 * squareSize, vertices[i].x) * tileAmount;
            float percentY = Mathf.InverseLerp(-map.GetLength(1) / 2 * squareSize, map.GetLength(1) / 2 * squareSize, vertices[i].z) * tileAmount;
            uvs[i] = new Vector2(percentX, percentY);
        }
        mesh.uv = uvs;

然后給Cave的MeshRenderer添加一個(gè)Texture坦胶，效果如下

這樣官網(wǎng)的這個(gè)自動(dòng)生成地圖教程就完成了透典，學(xué)無(wú)止盡晴楔。