情報学的バナナの皮

だらだらと自作プログラムについての備忘録

Unityでローグライク的ダンジョン自動生成

みんな大好き自動生成アルゴリズムのお時間です。

何を隠そう私ゲームボーイカラーシレンGB2から始まりローグライクゲームが大好きでして、ダンジョン生成はいつかやってみたいと思ってたんです。

苦戦しつつもおおむね形になったのでコード載せつつ解説していこうかなーと。

先に参考になった文献をば

oyasen.exblog.jp

SFCシレンを解析してくれているブログ様で、ダンジョン生成についての手順が書いてます。

ダンジョン生成アルゴリズム古今東西様々な方法があるようでネットで記事を調べると結構部屋作り→通路作りの順のものが多いようですが、この記事によるとSFCシレンでは通路作り→部屋作りの順でやっている模様。

今回はこれを踏襲してやっていきたいと思います。

0.下準備

とりあえず下準備としてマス目の定義を行っておきます。

各マス目の床定義として

//床のタイプ
    public enum Tile_Type {
        //壊れない壁
        Unbreakable_Wall,
        //壊れる(普通の)壁
        Wall,
        //廊下の床
        Hall_Floor,
        //部屋の床
        Room_Floor,
        //デバッグ用
        Debbug
    }

こんな感じのenumを用意します。
壁を2種類用意しているのはそれ以上移動できない枠とゲーム内の仕様で壊せる壁で分けたいからですね、床も2種類ありますがこれは自分の書いた処理上部屋のマスと廊下のマスを区別するのがめんどくさかったからです。
あとはこのenumを二重配列で宣言してあげつつ、その他使いそうな変数の宣言もしておきます。(これがすべてじゃないけど)
下ででてくる「ブロック」はマス目全体を縦横で区切る概念です。16*16のマス目を縦2ブロック横2ブロックで区切ったら1ブロック8*8のblockが4つできるよねって感じですね。
最終的には各ブロックに最大1つの部屋をつくってあげることになります。

    private Map_Tile[,] stage;//マス目の配列

    public int add_way_limit=4;//部屋から生える廊下の最大本数

    private int Width_Max;//横方向の全マス数
    private int Height_Max;//縦方向の全マス数

 private int Block_All_num;//ブロック数

    private int Block_X_num;//横方向の全ブロック数
    private int Block_Y_num;//縦方向の全ブロック数

    private int Block_Width;//1ブロックの横マス数
    private int Block_Height;//1ブロックの縦マス数

1.通路作り

SFCシレンのダンジョン生成では通路作りに3つのステップがあります。
まずランダムに決めた1つのブロックから4方向にランダムにブロックを選んで進ませていき一筆書きで通路を伸ばしていきます。
次に一筆書きの都合上、通路がたどり着かなかったブロックができてしまうので現在ある通路からそのようなブロックに向けて枝分かれして通路を伸ばします。
最後にランダムに通路をいくつか増やして通路作りは終わりです。

1.一筆書き通路

リストなり配列なりで各ブロックに通路を引いたかどうかを保存しつつ次の4方向、次の4方向と進んであげるだけです。
ここで重要なのは、行き止まりの点と枝分かれの点をリストで保存しておくことです。後々使います。
ここでの枝分かれ点には曲がり角も含まれます、ならなんで”枝分かれ”って言葉にするのかって?それは…うん…プログラム書いてた時の言葉選びが悪かっただけです。
コードはこんな感じです。

        //通路を一筆書きで伸ばしていく
        void Aisle_One_Stroke() {
            //始まりとなるブロックを選択
            int now_block = Random.Range(0, Block_All_num);
            //そのブロックに通路が存在するか否かのフラグをtrueに
            block_aisle[now_block] = true;
            //始点を決定
            int[] now_point = Block_To_Random_Point(now_block, 2);
            //始点は行き止まりになるはずなので、行き止まり点にする
             deadend_point.Add(Stage_Manager.Return_int2(now_point));
            //終点を宣言
            int[] next_point;
            //道の方向
            XY vector = XY.Not;
            {
                //一筆書きのルーチン
                for (int i = 0; i < Block_All_num; i++) {
                    //周囲4方向でまだ通路ができていないブロックを受け取る
                    int[] empty_blocks = Enable_Aisle_Block(now_block, false);
                    //もし4方向全て通路ができていれば終了
                    if (empty_blocks.Length == 0) {
                        //branch_point.RemoveAt(i-1);
                        break;
                    }
                    //通路ができていないブロックがあればその中からランダムで1つブロックを選ぶ
                    else {
                        //新たなブロックを選出
                        int next_block = empty_blocks[Random.Range(0, empty_blocks.Length)];
                        if (i == 0) { vector = Block_XY(now_block, next_block); }
                        next_point = Block_To_Random_Point(next_block, 2);
                        //通路を床で埋める
                        Fill_Foor(Fill_List(now_point, next_point, Block_XY(now_block, next_block), false), false);
                        //方向ベクトルが変化したら枝分かれした点を保存
                        if (vector != Block_XY(now_block, next_block) && !(i == (Block_All_num - 1) || i == 0)) {
                            branch_point.Add(Stage_Manager.Return_int2(now_point[(int)XY.X], now_point[(int)XY.Y]));
                        }
                        //次の始点を現在の終点で更新
                        now_point[(int)Block_XY(now_block, next_block)] = next_point[(int)Block_XY(now_block, next_block)];
                        //引いた道の方向を保存
                        vector = Block_XY(now_block, next_block);
                        //ブロックを更新
                        now_block = next_block;
                        //現在のブロックに通路を引いたことを記録
                        block_aisle[now_block] = true;
                    }
                }
                //行き止まりになった点の保存
                deadend_point.Add(Stage_Manager.Return_int2(now_point));
            }

2.枝分かれ通路

まず先ほどの一筆書きのところで作ったブロックに通路があるかどうかのリストから、まだ通路が存在しないブロックを探します。
そしてその通路のないブロックの上下左右のブロックに通路が存在するかをチェック、存在しなければ一度そのブロックは飛ばし、存在すればその通路のどこかから道を引いて通路があるかどうかの情報を更新。
これをループで通路のないブロックが存在しなくなるまで繰り返します。ただしフリーズ防止に最大のトライ回数は決めておいた方が吉です。whileを使うときはなんでもそうですけど。

注意するところは先ほど同様枝分かれした点を保存しておきたいんですけど、下の画像の赤線が通路だったとして
f:id:tkg_lag:20211025114608p:plain
下のように軸が変わるように通路が伸びたらその始点をただ単に枝分かれ点にすればいいんですが
f:id:tkg_lag:20211025114611p:plain
下のように同じ軸で通路が伸びた場合、始点を枝分かれ点にしたら別に枝分かれしていないのに~~ってなってしまいます。
f:id:tkg_lag:20211025114613p:plain
これを解決するにはまぁ色々方法がありますが、簡単なのは通路の方向を計算して同じ軸方向には進まないようにすることかなと思います。
自分の場合は先に通路のないブロック側で始点を決めておいて、周囲のブロックと垂直方向な通路が生成できるようなマスだけを選んで道を伸ばしました。

3.ランダム通路

これは簡単。ただ単に現在すでに通路になっている点とそれからランダムな点を選んできて繋げるだけ。
ただし突き抜けには注意です。
f:id:tkg_lag:20211025115323p:plain
紫の点から青の点にかけて道を繋げたいときに
f:id:tkg_lag:20211025115325p:plain
このように繋げると、枝分かれ点の計算がまためんどくさくなってしまうので
f:id:tkg_lag:20211025115328p:plain
こんな感じに止めてあげるのが吉です。
あとこの方法だと通路の長さが1マスとか2マスみたいな変な通路になりがちなので何マス分未満の通路は計算して引かない、とかしてあげるとよりそれらしくなると思います。

ここまでの進捗を見てみましょう。
一筆書きして、
f:id:tkg_lag:20211025121825p:plain
道のないブロックに道を伸ばして
f:id:tkg_lag:20211025121828p:plain
ランダムに道を作る。
f:id:tkg_lag:20211025121822p:plain

2.部屋作り

部屋を作るのに必要なのは部屋の大きさと部屋の中心です、矩形作りなので。これをどう決めるのかが問題ですね。
ここでは先ほどから記録し続けてきた行き止まり点と枝分かれ点が効いてきます。
行き止まりの点の上に部屋を作れば行き止まりに部屋ができるし、枝分かれの点の上に部屋を作れば複数の出入口がある部屋を作ることができますからね。
ということで部屋を作るブロックをランダムに決めたら、そのブロック内にある行き止まり点、枝分かれ点の平均を取ってその真ん中らへんに部屋の中心を持ってきます。
さらに部屋のサイズはそれらの点の絶対値から決めてやることできれいに行き止まりの点や枝分かれの点の周辺に部屋を持ってくることができます。
行き止まりとか枝分かれがないブロックならまぁ乱数のままに作ってあげればOKです。
部屋で塗りつぶされた枝分かれ、行き止まり点はきちんとリストから外してあげましょう。まだ使います。
ということで部屋を作ってあげるとこんな感じに。
f:id:tkg_lag:20211025122807p:plain
先ほどの通路のみの画像と比べたらなんとなく行き止まり点とか枝分かれ点の上に部屋ができているのがわかりますかね。

3.最後に整理整頓

さて、繋がった廊下にいくつかの部屋というローグライクのダンジョンの基本構造は完成しましたが、まーだ不満点があります。
それはやけに行き止まりが多いことと、部屋と部屋の間の通路が少ないこと。
これは通路→部屋の順番で作っている弊害ですね。部屋→廊下の順で作れば確実に部屋と部屋の間に繋がる通路を作れるので行き止まりはわざとつくらないと生まれないし部屋と部屋の間に通路がいっぱい作れるのです。

1.行き止まり

/与えられた座標の周囲4マスを、分岐がなければ壁にしていく再帰、startがtrueであれば再帰の開始である
            bool Point_Recursion(int[] center) {
                //周囲4マスのリスト
                List<int[]> nei_point = Nei_4dir_point(center);
                //もし周囲4マスのうち2マス以上が床なら(つまり現在のマスが分岐点なら分岐点は)再帰せずに帰す
                if (nei_point.Count >= 2) { return false; }
                else {
                    //もしただの通路であればその点を壁にして、次の点に再帰で進む
                    stage[center[(int)XY.Y], center[(int)XY.X]].tile = Tile_Type.Wall;
                    //すでに上で弾いているので2個以上要素が来るはずはないけど一応ループに
                    for (int i = 0; i < nei_point.Count; i++) {
        //再帰
                        Point_Recursion(nei_point[i]);
                    }
                }
                //再帰が終了したらtrue
                return true;
            }

これは引数の点が分岐の点でなければ廊下を潰していく関数になっています。
この関数の引数に各行き止まり点を与えてあげると気持ちいいくらいに行き止まりの道が無くなっていきます。

2.廊下増やし

これは普通に2つの部屋の端と端の点をランダムに選んで繋げてあげるだけ。
注意するところはすでにある通路の横1マスには作らないことですかね。太さ2マスの廊下は見栄えが悪いですから。
ということでこれが
f:id:tkg_lag:20211025121825p:plain
こうなる
f:id:tkg_lag:20211025123922p:plain

完成

ここまでできたらあとはもうボタン1つでバンバン生成できます。
f:id:tkg_lag:20211025131724p:plainf:id:tkg_lag:20211025131727p:plain
f:id:tkg_lag:20211025131731p:plainf:id:tkg_lag:20211025131734p:plain
なかなか時間かかって難しかったですがこう結果が視覚的に出るのはゲーム作りの楽しいところですよね~ということで書きたいもの書けたのでまた今度。