迷路を自動生成してみる(後編)

こんにちは、きうちです。

今回は、前回の 迷路を自動生成してみる(前編) の続きをお送りしたいと思います。

あれからいろいろいじっていて、もうちょっとチューニングしたらさらに良くなる・・・

とか続けていたら、なかなかブラッシュアップポイントが多かったです。

いつまで経っても後編が書けないと思ったのと、そのまま書くとだらだら長くなりすぎて読みづらくなりそうだったので

「ブラッシュアップしすぎず、必要な分だけ」

載せようと思います。

気が済むまでいじったバージョンは後日GitHubで公開しようかなと。

★ ★ ★

前回は「大地を作って幹を伸ばす」というのをやりました。

今回は「枝を伸ばす」ですね。

やることは幹の時と似ているんですけど・・・今度は、起点が「幹のどこかの点」になります。

Makeメソッドに枝を作るメソッドの呼び出しを追加します。

        private void Make() // 迷路を作る
        {
            // セルをクリアする
            ClearCells();

            // 大地を作る
            MakeGround();

            // 幹を作る
            MakeStem();

            // 枝を作る (追加)
            MakeBranch();
        }

枝を作るメソッド MakeBranch と、そこから利用する「開始位置を決める」メソッド MakeBranchStartPosition はこんな感じ。

        private void MakeBranch() // 枝を作る
        {
            for (int i = 0; i < 10000; i++)
            {
                int sx = 0;
                int sy = 0;
                if (MakeBranchStartPosition(ref sx, ref sy))
                {
                    int direction = MakeBranchGrowDirection(ref sx, ref sy);
                    if (direction > -1)
                    {
                        Grow(sx, sy, direction, GetGrowLength(50, 10), 50, CELL_BRANCH);
                    }
                }
            }
        }

        private bool MakeBranchStartPosition(ref int sx, ref int sy) // 枝の開始位置を決める
        {
            sx = -1;

            for (int i = 0; i < 100; i++)
            {
                int x = random.Next(1, cells.GetLength(0) - 2);
                int y = random.Next(1, cells.GetLength(1) - 2);
                if ((cells[x, y] == 2 || cells[x, y] == 3) && CountNeighbor(x, y) <= 2)
                {
                    sx = x;
                    sy = y;
                    break;
                }
            }

            return sx != -1;
        }

先に MakeBranchStartPosition について。

枝は幹から伸ばすわけですが、ここでは枝から枝を伸ばすことも可能としました。

開始地点をランダムに仮決定した後、その座標に対応するセルの値が「2または3」と判定しているのはそのためです。

2が幹で3が枝です。

また、開始地点は近傍の壁の数が2以下、としました(本当はこのあたり、もっと工夫できるのですが、とりあえず)。

100回やってダメだったらあきらめるようにしました。

MakeBranch について、枝の作成試行回数は10000回としました。

MakeBranchStartPosition を呼んで開始地点を決めたら、今度は伸ばす方向を決めます。

この伸ばす方向を決めるメソッドとして後述の MakeBranchGrowDirection を呼んでいます。

決定した方向は番号で direction 変数に入ります。

0:右方向、1:下方向、2:左方向、3:上方向

です。

後は幹のときと同様、GrowLength と Grow メソッドを呼んでいます。

なお、今作成している迷路の作成方法は、「なるべくまっすぐ伸ばす」「突き当たったら曲げる」というような仕組みですが、

「『ランダムに伸ばしたら曲げる』を繰り返す」という風にも作ることができます。

MakeBranchGrowDirection メソッドと、そこから使用する CountForward メソッドは以下の通りです。

        private int MakeBranchGrowDirection(ref int x, ref int y) // 枝を伸ばす方向を決める
        {
            int direction = -1;

            for (int i = 0; i < VXVY.GetLength(0); i++) // 4方向それぞれ調べる
            {
                int vx = VXVY[i, 0];
                int vy = VXVY[i, 1];
                int x1 = x + vx;
                int y1 = y + vy;
                if (cells[x1, y1] == 0 && CountForward(x1, y1, vx, vy) == 0) // 何もない場所かつ進む方向の壁がない
                {
                    direction = i;
                    x = x1;
                    y = y1;
                    break;
                }
            }

            return direction;
        }

        private int CountForward(int x, int y, int vx, int vy) // 前方(進む方向)の3近傍に壁がいくつあるか調べる)
        {
            int ct = 0;

            if (vy == 0)
            {
                for (vy = -1; vy <= 1; vy++)
                {
                    if (cells[x + vx, y + vy] > 0) ct++;
                }
            }
            else
            {
                for (vx = -1; vx <= 1; vx++)
                {
                    if (cells[x + vx, y + vy] > 0) ct++;
                }
            }

            return ct;
        }

MakeBranchGrowDirection について、コメントにある通り「4方向それぞれ順番に調べる」ことをしています。

調べる内容は「進んだ先のセルに何もない、かつそのさらに前方の壁がない」ことです。

これが当てはまっていればその方向で決定します。

で、これ・・・順番に調べるということは、0、つまり右方向が一番採用されやすいということです。その次が1の下方向。

これだと偏っちゃいますね。

本当はここ、ランダムに決定したほうがいいですね。

さて、ここまでやって実行させてみますと・・・

やりました!だいぶ迷路っぽくなりました!

ちゃんと迷路として、解けもしますよね。

★ ★ ★

最後に、入口と出口を作りましょう。Make メソッドの最後にそのための処理を足します。

        private void Make() // 迷路を作る
        {
            // セルをクリアする
            ClearCells();

            // 大地を作る
            MakeGround();

            // 幹を作る
            MakeStem();

            // 枝を作る
            MakeBranch();

            // スタートとゴールを作る (追加)
            cells[0, 1] = CELL_EMPTY;
            cells[cells.GetLength(0) - 1, cells.GetLength(1) - 2] = CELL_EMPTY;
        }

色も、わかりやすくするために色を変えていましたけど、単一色にしてみようかな。

private static readonly Brush[] CELL_COLORS = { Brushes.Green, Brushes.Green, Brushes.Green }; // 壁の色

背景も黒くしましょう。

実行すると・・・

うん、これは「迷路」と言ってもよさそうな仕上がりになりましたね。

↑ちゃんと解けますよね?^^

★ ★ ★

といったところで今回はここまでです。

先にも少しお伝えしました通り、やればもうちょっときれいな迷路作れます。

今のだと、ちょびちょびした壁が結構多いし、もうちょっと詰められそうな隙間がどうしても残る生成になります。

そのあたりは、「気が済むまでいじったバージョン」ができたらそのリンクをこのブログでお伝えしようかなー・・・と思っています。

それではまた次回!