Unity - 簡易亂數迷宮產生1(Depth-first search)

　　這次來玩玩亂數迷宮產生，感覺好像很複雜，事實上如果真要研究下去是可以花不少時間的，不過如果只是單純的產生一張圖或做些簡易的變化，其實只要了解基本的概念後就可以很快地建立一張圖了，後續要做變化就需要再花時間了。

　　本次使用的演算法概念是Depth-first search(https://en.wikipedia.org/wiki/Maze_generation_algorithm)，也有看到好像叫Growing tree，也就是先亂數從陣列中取一個格子作為起始點，然後從這個起始點開始隨機往四周某一個方向開一個洞到下一格，再從下一格隨機往四周開一個洞過去，一直到四周已經無法開洞或是已經走過的格子就停止，此時倒回上一格在嘗試往另一個方向做同樣的事；雖然講起來有點繁瑣，但也就是一個遞迴的概念了。


　　實作測試（WebGL build，似乎會載入久一點），點擊Generate產生迷宮，點Enter可以進入隨機位置，用鍵盤的前後左右按鍵移動跟旋轉。

---

　　首先假設每一個格子都有四個方向牆壁，這邊使用方形格子，同樣也可以改為六面格或其他類型的格子，因此做一個類別來包裝四個牆壁的數值跟座標，之後再用這個展生一個陣列來用。

private class Cell
{
    //使用一個陣列來設定四個牆的屬性，0是有牆面，1則是打通的通道
    public int[] wall = new int[4]; //陣列四個依序為N, E, S, W
    public int x, y;
}

---

　　接著需要一些基本的數值，像是陣列的長寬以及陣列的值。

    //長寬以及陣列，或是其他的數值，像是方向的權重比，增加權重在亂數選取方向的時候讓該方向機率比較高
    //    這樣也可以讓產生出來的迷宮(水平/垂直)的線條比較多
    public int width = 10;
    public int height = 10;
    private Cell[][] cellArr;

　　然後就是簡單使用遞迴去跑出路徑，一個一個格子往下檢查，到達死路後開始往回退，一直退到該格子還有其他方向還沒檢查過的，再從那個方向檢查下去，最後這個遞迴會退回到起始格，到此全部的陣列格子就都跑過一遍了。

    //概念
    void CreatePath(...)
    {
        //先把這格加入已經踩過的列表
        visitedList.Add();

        //接著亂數四個方向，四個方向不重複
        int[] direction = new int[4] {a, b, c, d};

        //接著開始依序往亂數的四個方向檢查，這個方向必須是牆壁，而且這個方向的下一個格子是還沒踩過的，如果是就跳過
        for(int i = 0; i < 4; ++i)
        {
            //取得方向
            int dir = directions[i];

            //檢查是不是牆壁或下一格有沒有踩過
            if(isWall = false && visitedList.Contain() = true)
            {
                //如果不是牆壁，或是已經踩過，就跳過這個方向
                continue;
            }

            //打通這個方向的牆壁
            start.wall[dir] = 1;

            //進入這個方向的下一個格子重複相同步驟
            CreatePath (nextCell, visitedList);
        }
    }

　　跑完後迷宮也就產生完了，不過這個是用遞迴一次跑完，所以在產生的時候會頓一下，根據陣列的大小停頓的時間也有長短，所以最好是在遊戲建立的時候跑，不然就是使用Coroutine的方法，一格一格跑同時不會卡死其他的運作。

---

參考Component，不過要注意的是這個Component只是單純產生完Cell[][]的陣列資料，要如何運用這個資料還是需要看自己的需求去建立場景或圖片等等。

public class DepthFirstSearchMaze : MonoBehaviour
{
    private class Cell
    {
        public int[] wall = new int[4]; //n,e,s,w  0=wall, 1=passage
        public int x, y;
    }

    public int width = 10; //陣列的寬度
    public int height = 10; //陣列的長度
    private Cell[][] cellArr;

    void Start ()
    {
        CreateMaze(width, height); //建立資料
    }

    void CreateMaze(int width, int height)
    {
        //初始化陣列大小
        cellArr = new Cell[height][];
        for(int i = 0; i < height; ++i)
        {
            cellArr[i] = new Cell[width];
            for(int j = 0; j < width; ++j)
            {
                cellArr[i][j] = new Cell() {y = i, x = j};
            }
        }

        //亂數取一個格子作為起始點
        Cell startCell = cellArr[Random.Range(0,height)][Random.Range(0,width)];

        //開始建立迷宮
        CreatePath(startCell, new List<Cell>());
    }

    void CreatePath(Cell start, List<Cell> visitedList)
    {
        //把此格加入已踩過列表
        visitedList.Add(start);

        //取得可以使用的方向列表，該方向是牆面，並且沒有超出陣列大小
        List<int> directions = new List<int>();
        if(start.wall[0] == 0 && start.y != height-1) directions.Add(0);
        if(start.wall[1] == 0 && start.x != width-1) directions.Add(1);
        if(start.wall[2] == 0 && start.y != 0) directions.Add(2);
        if(start.wall[3] == 0 && start.x != 0) directions.Add(3);

        int count = directions.Count;
        for(int i = 0; i < count; ++i)
        {
            //從方向列表亂數取一個方向
            int dir = directions[Random.Range(0, directions.Count)];
            directions.Remove(dir); //把該方向移出列表

            //取得下一個方向的Cell資料
            int addY = (dir == 0) ? 1 : (dir == 2) ? -1 : 0;
            int addX = (dir == 1) ? 1 : (dir == 3) ? -1 : 0;
            int nextY = start.y + addY;
            int nextX = start.x + addX;
            Cell nextCell = cellArr[nextY][nextX];

            //檢查是否踩過
            if(visitedList.Contains(nextCell))
            {
                continue; //Skip this direction
            }

            //建立通道
            start.wall[dir] = 1;
            nextCell.wall[(dir+2)%4] = 1;

            //到下一個方向的Cell繼續
            CreatePath (nextCell, visitedList);
        }
    }
}