CODE

【C#】簡単な迷路ゲームを作ってみた【穴掘り法】【アルゴリズム】

投稿日:

先日C#で迷路ゲームを作りました。

迷路を自動で生成して、WASDで生成した迷路内を移動できるようなプログラムです。

今回はその解説をしていきたいと思います。コードだけ見たい人は目次からまとめに飛んでください。

汚い部分もあるかと思いますが、そこは僕の実力不足ということで。

(Visual Studio 2019で作成したコンソールアプリです。)

アルゴリズム(穴掘り法)の説明

このプログラムは大きく分けて迷路を生成するプログラムプレイヤーが移動するプログラムに分けられます。

迷路を生成するアルゴリズムは何種類かあるのですが、今回は穴掘り法を採用しました。

穴掘り法のアルゴリズムをまとめると、

  1. 全てのブロックを壁に初期化する。
  2. ランダムに奇数マスの1ブロックを選ぶ。
  3. 選んだブロックから4方向のいずれかに2ブロック掘れるか判断する
  4. 2ブロック掘れるなら堀り、また方向を決めて2ブロック掘れるか判断する。これを繰り返す。
  5. 掘れない場合はすでに掘ってある奇数マスのブロックを選び3, 4を繰り返す。
  6. 掘るところが無くなれば終了。

という流れです。

迷路を囲う壁を突き抜けたり、2ブロック先がすでに通路である場合は掘れないと判断します。

注意しなければいけないのが、迷路のマップは縦横ともにブロックを5以上の奇数個にしなければならない事です。

なので7×9マスは大丈夫ですが、10×9マスにしてしまうと動きません。
これは2ブロック掘ることにしているからです。偶数だとズレが生じます。

コードの説明

コードを交えながら順に説明します。

マップの生成

            //迷路の長さ指定
            int maze_length = 31;
            int[,] wall = new int[maze_length, maze_length];

            //全て壁で埋めて周りは通路にする
           
            for (int i = 1; i < maze_length - 1; i++)
            {
                for (int j = 1; j < maze_length - 1; j++)
                {
                    wall[i, j] = 1;
                }
            }

まずは、2次元配列を使ってマップを生成します。壁は数字の1で表しています。
そして、通路は0で表します。

配列をnew intで宣言すると要素は自動で0になります。

マップの周りを0に設定しているのは、アルゴリズムで掘れるかどうかの判定をする際に楽だからです。

ちゃんと、最後は戻します。

掘り始める場所を指定して0にしておきます。上のコードでは[1, 1]です。

次は再帰的に掘ります。

再帰的な穴掘り

      //穴掘り開始
       Random cRandom = new System.Random();
            while (true)
            {
                //掘る方向を決める
                int dir = cRandom.Next(4);
                int X;
                int Y;

                //再帰的に掘る
                while (true)
                {
                    (X, Y) = Map_dig(wall, x, y, dir);
                    if (X == 0 && Y == 0)
                    {
                        break;
                    }
                    x = X;
                    y = Y;
                    dir = cRandom.Next(4);
                }

                //まだ掘れる場所が存在するか判断
                
                if (Program.cnt == (maze_length - 1)  * (maze_length - 1) / 4)
                {
                    break;
                }

                //存在すれば別の座標を決定
                do
                {
                    x = 2 * cRandom.Next((maze_length - 1) / 2) + 1;
                    y = 2 * cRandom.Next((maze_length - 1) / 2) + 1;
                } while (wall[x, y] == 1);
            }

まずは乱数で掘る方向(上下左右)を決めて、掘り始めの座標と方向をメソッドに渡してます。そのメソッドで掘れるか判断します。戻り値は掘った先の座標です。メソッドは後述。

その座標を引数に代入して掘るのを繰り返します。
もし掘れない場合はループを抜けて終了条件に当てはめます。

終了条件は掘れる場所が無くなることです。

一回掘るごとに、奇数マスが一つ通路になることを利用します。つまり奇数マスが全て通路(0)になれば終了です。

staticでcntという変数を定義して一回掘るごとにメソッド内で+1します。

まだ掘れる場所がある場合は、すでに通路の部分(配列の奇数番の要素が0)からランダムに新しい座標を決定して掘っていきます。

穴掘りのメソッド

次に上で出てきたMap_digメソッドについて解説します。

static (int a, int b) Map_dig(int[,] wall, int x, int y, int dir)
        {
            if (dir == 0 && wall[x, y + 1] == 1)
            {
                if (wall[x, y + 2] == 1)
                {
                    wall[x, y + 1] = 0;
                    wall[x, y + 2] = 0;
                    Program.cnt += 1;
                    return (x, y + 2);
                }
                else
                {
                    return (0, 0);
                }
            }
            else
            {
                if (dir == 1 && wall[x + 1, y] == 1)
                {
                    if (wall[x + 2, y] == 1)
                    {
                        wall[x + 1, y] = 0;
                        wall[x + 2, y] = 0;
                        Program.cnt += 1;
                        return (x + 2, y);
                    }
                    else
                    {
                        return (0, 0);
                    }
                }
                else
                {
                    if (dir == 2 && wall[x, y - 1] == 1)
                    {
                        if (wall[x, y - 2] == 1)
                        {
                            wall[x, y - 1] = 0;
                            wall[x, y - 2] = 0;
                            Program.cnt += 1;
                            return (x, y - 2);
                        }
                        else
                        {
                            return (0, 0);
                        }
                    }
                    if (dir == 3 && wall[x - 1, y] == 1)
                    {
                        if (wall[x - 2, y] == 1)
                        {
                            wall[x - 1, y] = 0;
                            wall[x - 2, y] = 0;
                            Program.cnt += 1;
                            return (x - 2, y);
                        }
                        else
                        {
                            return (0, 0);
                        }
                    }
                    else
                    {
                        return (0, 0);
                    }
                }
            }
        }

このメソッドの引数は、掘り始めのxy座標、掘る方向、マップの配列です。
戻り値は掘った先の座標です。

基本的には選択したマスの2マス先が通路かどうかで判断してます。

ただ、それだと2マス先が存在しない場合(マップの端に向かって進むとき)にエラーになります。黒四角が壁です。

〇→

このエラーを回避するために先にマップの周りを通路にします。

2マス先を判断する前に1マス先を判断してそこが0ならば掘れないと判断します。
1マス先が0になるのはマップの周りを越える時だけです。

2マス先が壁で掘れる場合はその2マスを通路にしてその2マス先の座標を戻り値にします。

戻れない場合は(0, 0)を返します。

プレイヤーを動かす

キーボードのWASDでプレイヤーの位置を動かします。

while (true)
            {

                //キー入力を取得
                ConsoleKeyInfo c = Console.ReadKey(true);
                string key = c.Key.ToString();

                (int X, int Y) = Move_player(key, x, y, wall);
                Console.Clear();
                Draw_map(wall, maze_length);

                //ゴール判定
                if (wall[maze_length - 2, maze_length - 2] == 2)
                {
                    Console.WriteLine("GOAL");
                    break;
                }
                x = X;
                y = Y;
            }

入力キーとプレイヤーの座標をメソッドに渡して、マップ上のプレイヤーの位置を変更します。

このキー入力はコンソールではないので、エンターを押さなくても認識されます。

Draw_mapはマップの描画のメソッドです。
あとゴールは右下に設定しています。

プレイヤーの移動メソッド

static (int a, int b) Move_player(string key, int x, int y, int[,] wall)
        {
            if (key == "A" && wall[x, y - 1] == 0)
            {
                wall[x, y] = 0;
                wall[x, y - 1] = 2;
                return (x, y - 1);
            }
            else
            {
                if (key == "W" && wall[x - 1, y] == 0)
                {
                    wall[x, y] = 0;
                    wall[x - 1, y] = 2;
                    return (x - 1, y);
                }
                else
                {
                    if (key == "D" && (wall[x, y + 1] == 0 || wall[x, y + 1] == 3))
                    {
                        wall[x, y] = 0;
                        wall[x, y + 1] = 2;
                        return (x, y + 1);
                    }
                    else
                    {
                        if (key == "S" && (wall[x + 1, y] == 0 || wall[x + 1, y] == 3))
                        {

                            wall[x, y] = 0;
                            wall[x + 1, y] = 2;
                            return (x + 1, y);
                        }
                        else
                        {
                            return (x, y);
                        }
                    }
                }
            }
        }

引数はプレイヤーの座標、入力キー、マップの配列です。

戻り値は移動後の座標です。

まとめ(全体コード)

最後に全体のコードを載せておきます。

プログラミング学習の参考になれば幸いです。

class Program
    {
        static int cnt = 1;
        static void Main(string[] args)
        {
            //迷路の長さ指定
            int maze_length = 31;
            int[,] wall = new int[maze_length, maze_length];

            //全て壁で埋めて周りは通路にする
           
            for (int i = 1; i < maze_length - 1; i++)
            {
                for (int j = 1; j < maze_length - 1; j++)
                {
                    wall[i, j] = 1;
                }
            }
            Random cRandom = new System.Random();

            //初期位置は(1, 1)
            int x = 1;
            int y = 1;
            wall[1, 1] = 0;

            //穴掘り開始
            while (true)
            {
                //掘る方向を決める
                int dir = cRandom.Next(4);
                int X;
                int Y;

                //再帰的に掘る
                while (true)
                {
                    (X, Y) = Map_dig(wall, x, y, dir);
                    if (X == 0 && Y == 0)
                    {
                        break;
                    }
                    x = X;
                    y = Y;
                    dir = cRandom.Next(4);
                }

                //まだ掘れる場所が存在するか判断
                
                if (Program.cnt == (maze_length - 1)  * (maze_length - 1) / 4)
                {
                    break;
                }

                //存在すれば別の座標を決定
                do
                {
                    x = 2 * cRandom.Next((maze_length - 1) / 2) + 1;
                    y = 2 * cRandom.Next((maze_length - 1) / 2) + 1;
                } while (wall[x, y] == 1);
            }

            //周りを壁に戻す
            for (int i = 0; i < maze_length; i++)
            {
                wall[0, i] = 1;
                wall[i, 0] = 1;
                wall[i, maze_length - 1] = 1;
                wall[maze_length - 1, i] = 1;
            }

            //プレイヤーとゴールの初期位置を決定
            x = 1;
            y = 1;
            wall[1, 1] = 2;
            wall[maze_length - 2, maze_length - 2] = 3;

            //マップを描写
            Draw_map(wall, maze_length);


            //プレイヤー位置の移動
            while (true)
            {

                //キー入力を取得
                ConsoleKeyInfo c = Console.ReadKey(true);
                string key = c.Key.ToString();

                (int X, int Y) = Move_player(key, x, y, wall);
                Console.Clear();
                Draw_map(wall, maze_length);

                //ゴール判定
                if (wall[maze_length - 2, maze_length - 2] == 2)
                {
                    Console.WriteLine("GOAL");
                    break;
                }
                x = X;
                y = Y;
            }


        }

        //2マス先まで掘れるか判断して掘る。無理なら(0, 0)を返す
        static (int a, int b) Map_dig(int[,] wall, int x, int y, int dir)
        {
            if (dir == 0 && wall[x, y + 1] == 1)
            {
                if (wall[x, y + 2] == 1)
                {
                    wall[x, y + 1] = 0;
                    wall[x, y + 2] = 0;
                    Program.cnt += 1;
                    return (x, y + 2);
                }
                else
                {
                    return (0, 0);
                }
            }
            else
            {
                if (dir == 1 && wall[x + 1, y] == 1)
                {
                    if (wall[x + 2, y] == 1)
                    {
                        wall[x + 1, y] = 0;
                        wall[x + 2, y] = 0;
                        Program.cnt += 1;
                        return (x + 2, y);
                    }
                    else
                    {
                        return (0, 0);
                    }
                }
                else
                {
                    if (dir == 2 && wall[x, y - 1] == 1)
                    {
                        if (wall[x, y - 2] == 1)
                        {
                            wall[x, y - 1] = 0;
                            wall[x, y - 2] = 0;
                            Program.cnt += 1;
                            return (x, y - 2);
                        }
                        else
                        {
                            return (0, 0);
                        }
                    }
                    if (dir == 3 && wall[x - 1, y] == 1)
                    {
                        if (wall[x - 2, y] == 1)
                        {
                            wall[x - 1, y] = 0;
                            wall[x - 2, y] = 0;
                            Program.cnt += 1;
                            return (x - 2, y);
                        }
                        else
                        {
                            return (0, 0);
                        }
                    }
                    else
                    {
                        return (0, 0);
                    }
                }
            }
        }


        //Mapの描画
        static void Draw_map(int[,] wall, int maze_length)
        {
            for (int i = 0; i < maze_length; i++)
            {
                for (int j = 0; j < maze_length; j++)
                {
                    if (wall[i, j] == 1)
                    {
                        Console.Write("■");
                    }
                    else
                    {
                        if (wall[i, j] == 0)
                        {
                            Console.Write("  ");
                        }
                        else
                        {
                            if (wall[i, j] == 2)
                            {
                                Console.Write("〇");
                            }
                            else
                            {
                                Console.Write("☆");
                            }
                        }
                    }
                }
                Console.WriteLine("");
            }
        }

        //プレイヤー位置の移動
        static (int a, int b) Move_player(string key, int x, int y, int[,] wall)
        {
            if (key == "A" && wall[x, y - 1] == 0)
            {
                wall[x, y] = 0;
                wall[x, y - 1] = 2;
                return (x, y - 1);
            }
            else
            {
                if (key == "W" && wall[x - 1, y] == 0)
                {
                    wall[x, y] = 0;
                    wall[x - 1, y] = 2;
                    return (x - 1, y);
                }
                else
                {
                    if (key == "D" && (wall[x, y + 1] == 0 || wall[x, y + 1] == 3))
                    {
                        wall[x, y] = 0;
                        wall[x, y + 1] = 2;
                        return (x, y + 1);
                    }
                    else
                    {
                        if (key == "S" && (wall[x + 1, y] == 0 || wall[x + 1, y] == 3))
                        {

                            wall[x, y] = 0;
                            wall[x + 1, y] = 2;
                            return (x + 1, y);
                        }
                        else
                        {
                            return (x, y);
                        }
                    }
                }
            }
        }
    }





-CODE

Copyright© DaigoDiary , 2020 All Rights Reserved Powered by STINGER.