自動生成のダンジョンを作る③

前回の続きです

ringogames.hatenablog.com

②で解説したアルゴリズムをもとに実際にUnity上で迷路を作成するプロジェクトを作成しました。

以下にプロジェクトをアップしています。

https://gitlab.com/ringogames2022/kruskalalgorithmdungeon

制作環境

• Unity 2021.3.16f1
• URP

で開発しています。

サンプルシーンを開いて実行すると以下のように迷路が作成されます。

この迷路は毎回ランダムで生成されるようになっています。

シーン上に用意されたDungeonGeneratorが迷路生成用アルゴリズムのメイン部分となっています。

• WallObject
  • 迷路の壁となるオブジェクトのPrefabを指定
• DungeonTile
  • 迷路の床となる面のPrefabを指定
• Width、Height
  • タイルの横方向、縦方向の数
• StartPoint
  • 迷路の左下の座標
• TileLength
  • WallとTileの幅と一致させます。

今回のサンプルでは、WallとTileの幅は３ｍとなっています。

壁はX軸方向正に３ｍの幅としています。

基本的に、②で解説したアルゴリズムをDungeonGenerator.csのGenerateDungeon関数で実現してます。

以下の部分はまず、すべてのエッジ部分に壁を置いている操作になるため、あまり難しい部分はありません。

        public void GenerateDungeon(int columnCount, int rowCount)
        {
            //generate tiles
            m_tiles = new List<DungeonTile>();
            for(int i= 0; i < rowCount; ++i)
            {
                for(int j=0; j < columnCount; ++j)
                {
                    Vector3 pos = new Vector3(i * m_tileLength, 0, j * m_tileLength);
                    Quaternion quat = Quaternion.identity;
                    m_tiles.Add(new DungeonTile(pos, quat));
                }
            }

            foreach(DungeonTile tile in m_tiles)
            {
                Instantiate(m_tileObject, tile.Pos, tile.Quat);
            }

            List<DungeonEdge> bounderyEdges = new List<DungeonEdge>();
            //1. generate outer bounderies
            //1-1. bottom
            for(int i = 0; i < columnCount; ++i)
            {
                Vector3 pos = m_startPoint + new Vector3(i * m_tileLength, 0, 0);
                Quaternion quat = Quaternion.Euler(0, 0, 0);
                bounderyEdges.Add(new DungeonEdge(pos, quat));
            }
            //1-2. top
            for(int i = 0; i < columnCount; ++i)
            {
                Vector3 pos = m_startPoint + new Vector3(i * m_tileLength, 0, rowCount * m_tileLength);
                Quaternion quat = Quaternion.Euler(0, 0, 0);
                bounderyEdges.Add(new DungeonEdge(pos, quat));
            }
            //1-3. left
            for(int i = 0; i < rowCount; ++i)
            {
                Vector3 pos = m_startPoint + new Vector3(0, 0, i * m_tileLength);
                Quaternion quat = Quaternion.Euler(0, -90, 0);
                bounderyEdges.Add(new DungeonEdge(pos, quat));
            }
            //1-4. right
            for(int i = 0; i < rowCount; ++i)
            {
                Vector3 pos = m_startPoint + new Vector3(columnCount * m_tileLength, 0, i * m_tileLength);
                Quaternion quat = Quaternion.Euler(0, -90, 0);
                bounderyEdges.Add(new DungeonEdge(pos, quat));
            }

            //instantiate
            foreach(DungeonEdge edge in bounderyEdges)
            {
                Instantiate(m_wallObject, edge.Pos, edge.Quat);
            }

            //2. generate inner edges
            List<DungeonEdge> innerEdges = new List<DungeonEdge>();
            //2-1. left to right edges
            int tileIndex = 0;
            for (int i = 0; i < rowCount; ++i)
            {
                for (int j = 1; j < columnCount; ++j)
                {
                    Vector3 pos = m_startPoint + new Vector3(j * m_tileLength, 0, i * m_tileLength);
                    Quaternion quat = Quaternion.Euler(0, -90, 0);
                    DungeonEdge edge = new DungeonEdge(pos, quat);
                    edge.NeigboringTileLeft  = m_tiles[tileIndex];
                    edge.NeigboringTileRight = m_tiles[tileIndex + 1];
                    innerEdges.Add(edge);
                    tileIndex += 1;
                }
                tileIndex += 1;
            }

            //2-2. bottom to top edges
            tileIndex = 0;
            for (int i = 1; i < rowCount; ++i)
            {
                for (int j = 0; j < columnCount; ++j)
                {
                    Vector3 pos = m_startPoint + new Vector3(j * m_tileLength, 0, i * m_tileLength);
                    Quaternion quat = Quaternion.Euler(0, 0, 0);
                    DungeonEdge edge = new DungeonEdge(pos, quat);
                    edge.NeigboringTileLeft  = m_tiles[tileIndex];
                    edge.NeigboringTileRight = m_tiles[tileIndex + columnCount];
                    innerEdges.Add(edge);
                    tileIndex += 1;
                }
            }

それに続く以下の部分で、削除対象のエッジをはさむタイルのグループを調べ、

1. 同一グループであれば、エッジは削除しない
2. 異なるグループであれば、エッジを削除したのち、そのタイルを同一グループにする

ということを行っています。

            //remove edges
            //generate edge
            m_edges = new List<DungeonEdge>();
            while (true)
            {
                if(innerEdges.Count == 0)
                {
                    break;
                }
                int edgeIndex = Random.Range(0, innerEdges.Count);
                var targetEdge = innerEdges[edgeIndex];
                innerEdges.RemoveAt(edgeIndex);

                var leftTile  = targetEdge.NeigboringTileLeft;
                var rightTile = targetEdge.NeigboringTileRight;
                if(leftTile.TopParent() == rightTile.TopParent())
                {
                    //keep this edge
                    m_edges.Add(targetEdge);
                }
                else
                {
                    //dose not keep this edge
                    //set parent right to left
                    rightTile.TopParent().Parent = leftTile;
                }
            }


            //instantiate
            foreach(DungeonEdge edge in m_edges)
            {
                Instantiate(m_wallObject, edge.Pos, edge.Quat);
            }

非常に簡単なアルゴリズムで、プロシージャルな迷路を作成することができました。

今後、このアルゴリズムを使用して、ゲーム作成を行っていきます。