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



3 comments:

Unknown said...
This comment has been removed by the author.
Unknown said...

請問生成迷宮牆的GameObject物件要放哪,文章中沒提到GameObject物件要放哪,還有DepthFirstSearchMaze
是要把這段程式放哪裡使用?

IVerv said...

我上面有提這個Component只是單純產生迷宮Cell[][]的陣列資料,只是做為參考用的,你可以把裡面一些private的field或method改成public讓外部去呼叫或讀取,或是把你要的功能(例如建立迷宮object)直接加在這個component裡面,這個component沒有包含Instantiate的流程,需要自己去做

Post a Comment