rand関数で迷路をランダム生成させてみた


みなさんはじめまして。Rivièreです。
ブログ初投稿につき、ご不便がありましたら申し訳ありません。

この記事は
WMMC Advent Calendar 2020 - Adventar
の6日目の記事です。

昨日は、まんぼーさんによる
2020年に勉強した本の紹介 - まんぼーの技術記
でした。

制御からプログラミング、また私のような諸学者向けの本まで紹介してくれています。勉強しなきゃ...!
特にいつも雰囲気でプログラムを書いてしまう自分には、リーダブルコードが気になります。
そんな私の書く今回のブログは、プログラミングがテーマなのですが...

目次

はじめに

まず、今回の内容なのですが、初心者が好き勝手弄った結果、なんかうまくいったものを紹介するというものになります。
理論的に本当に問題が解決できたのかは定かではないのですが、とりあえずrand関数をそのまま使うよりはよい結果になった気がします。(小並感)

今回のテーマ

さて、今回のテーマですが、
rand関数を使って迷路をランダム生成させてみる
というものになります。

これは、マウスともっとお話しできるようにしたいというのがモチベーションです。
あと、二次走行の調整をしてるときに何度も一次走行させるのが面倒だったので、ならば最初から迷路情報を与えられるようにしておきたいという思いもありました。

rand関数について

今回はC言語を用い、乱数の生成に stdlib.h で用意されているrand関数を使っていきます。
Excel内の関数としても採用されているrand関数は、機械に精通していない人でも一度は目にしたことがあるのではないでしょうか。

このrand関数は乱数の種と呼ばれる値を与えることによって、0からRAND_MAX(stdlib.hで定義)の値をとる疑似乱数を生成してくれます。
具体的には次のアルゴリズムに従って疑似乱数が生成されます。

 X_n + 1 = (A \times X_n + B)modM

ここで、A、B、Mはコンパイラごとに設定された定数であり、乱数の種は X_0にあたります。
このアルゴリズム線形合同法と呼ばれるものです。
参考: 計算研究会 - C言語のrand関数について
参考: 乱数の仕組み - Qiita

重要なのは、

  • このようにして生成される疑似乱数列には周期があり、rand関数の周期は比較的短いこと
  • 同じコンパイラを使用して同じ乱数の値を与えると、同じ疑似乱数列が得られること

です。

より周期が長く、品質の良い乱数アルゴリズムとしてメルセンヌ・ツイスタ等が知られています。

メルセンヌ・ツイスタの使用法については、

等を参照してください。

全体の構成

見通しをよくするために、プログラムの概要を説明します。

主要な構成は、

  • 迷路をランダム生成させる関数

void make_map (int goal_x, int goal_y)

  • 作成した迷路を検証する(歩数マップを作成する)関数

int step_map (int goal_x, int goal_y)

  • main関数

となっています。

流れとしては、壁をランダム生成させて、それが迷路の形を成しているかを検証し、もしうまくいってなければ再生成させるというものになります。

ここでは説明しませんが、ゴール座標(goal_x, goal_y)の設定などもしておき、main関数内で引数として渡します。

とりあえず作ってみる

それでは作ってみます。
発生させた乱数の値によって壁を配置するか否かを決定します。

グローバル変数

    #define SIZE 16 
    int rand_coeff = 10;

基礎設定

今回はmap[SIZE][SIZE]のような二重配列を用いて座標を指定し、その座標ごとに周囲を囲む壁の情報を与えていきます。
この情報を与えるために、map[SIZE][SIZE]は、

struct NEWS{
    int n;
    int e;
    int w;
    int s;
    int step;
};

struct NEWS map[SIZE][SIZE];

という構造体配列として宣言しておきます。

ただし、以下の点に注意が必要です。

  1. 迷路の外周には壁がある。
  2. 迷路という特性上、隣同士の壁情報は連続している必要がある。(一つ右の位置において西壁があるのならば、現在地には東壁がある)
  3. スタートからゴールまでつながっている必要がある。

迷路ランダム生成関数の作成(make_map)

使用する変数

    float n_temp, e_temp, w_temp, s_temp;
    int x,y;
    int i;

実装

まず、壁情報を-1で初期化します。
以降

  • 壁があるときは1
  • 壁がないときは0
  • 未設定のときは-1

を格納することにします。

    for(x=0; x<SIZE; x++){
        for(y=0; y<SIZE; y++){
            map[x][y].n=-1;
            map[x][y].e=-1;
            map[x][y].w=-1;
            map[x][y].s=-1;
        }
    }

つぎに、外周に壁を配置します。

    for(i=0; i<SIZE; i++){
        map[i][0].s = 1;
        map[0][i].w = 1;
        map[i][SIZE-1].n = 1;
        map[SIZE-1][i].e =1;
    }

また、マイクロマウスではスタート地点では北壁のみ壁がないという設定になっていますので、これに準拠します。

    map[0][0].n = 0;
    map[0][0].e = 1;
    map[0][0].w = 1;
    map[0][0].s = 1;

壁のランダム配置(make_map)

壁をランダムに配置していきます。
ここで慣例では、乱数の種はtime(NULL)で与えます。

しかし、失敗した場合には再び迷路を作成するためにmake_mapを実行しなければなりません。
この間、システム上の時間経過は1秒に満たず、乱数の種は同一のものが与えられるために同一の乱数が生成され、その結果全く同じ壁の配置がなされてしまいます。

これを避けるために、座標(x,y)やら係数(rand_coeff)やらをかけて無理やり変化させます。

また、各n_tempe_tempw_temps_tempには0から1未満の値をとるように規格化した乱数値を格納します。

            switch(x*y){
                case 0:
                    if(x == 0 && y != 0){
                        srand(y*rand_coeff*((unsigned)time(NULL)));
                    }else if(x != 0 && y == 0){
                        srand(x*rand_coeff*((unsigned)time(NULL)));
                    }else{
                        srand(rand_coeff*((unsigned)time(NULL)));
                    }
                break;

                default:
                    srand(x*y*rand_coeff*((unsigned)time(NULL)));
                break;
            }

            n_temp = rand()/ (RAND_MAX + 1.0);
            e_temp = rand()/ (RAND_MAX + 1.0);
            w_temp = rand()/ (RAND_MAX + 1.0);
            s_temp = rand()/ (RAND_MAX + 1.0);

ここで先ほどの注意に従って壁を配置していきます。以下for文継続です。

  • すでに壁が挿入されているときは何もしない
  • 配置する方向の1マス隣の逆方向の壁(東壁の設定をするときは右隣りのマスの西壁)があるときは、壁を配置
  • 上記以外のときランダム生成

いま、乱数値を規格化しているので、だいたい50%の確率で配置したいとすると、
n_temp等が0.5より大きいときには配置することにすれば実装できます。


以下は北壁の設定についてです。

            /*Decide the state of north for each area.*/
            if(map[x][y].n != -1){
                //if Wall info is already installed.(pass)
            }else if(map[x][y+1].s != -1){
                map[x][y].n = map[x][y+1].s;
            }else if(n_temp < 0.5){
                map[x][y].n = 0;
            }else{
                map[x][y].n = 1;
            }

上記を東壁、西壁、南壁についても実行します。

その後、

            rand_coeff+=100;

とsrandの引数にかかるrand_coeffの値も増やしておきます。
これはグローバル変数として宣言したので、値は関数を出ても保持されます。

for文はここで閉じます。

ここまでで一応壁の設定はできました。迷路を作成する関数はここまでになります。

作成した迷路の確認(step_map

壁の設定が終わったものの、迷路になっているかは別問題です。
迷路はスタートからゴールまでつながっていないといけないからです。

使用する変数

    int x, y;
    int min_step =0;

以下では迷路を確認する関数step_mapを作っていきます。

確認方法はいくつかあると思うのですが、ここでは歩数マップを展開することで確認します。

歩数マップの値はmap[SIZE][SIZE].stepに格納します。

まずは、-2で初期化します。

    for(x=0; x<SIZE; x++){
        for(y=0; y<SIZE; y++){
            map[x][y].step = -2;
        }
    }

歩数マップの作成

次に歩数マップを作成していきます。

各座標について0から順に、歩数値が入るかどうかを検証(つまり歩数値がnとなる場所がどこかを検証)しますが、先ほど述べたのように解けない場合というものが存在します。

終了条件をスタート地点の歩数値が記入されることとしているので、解けていれば総座標数よりも大きい歩数値の検証は行われないはずです。

したがって、総座標数よりも大きい歩数値の検証を始めた段階でどこかで迷路が閉じてしまっていると考えられます。

このような考えのもとに実装したのが以下のコードです。

    /*Set the goal step*/
    map[goal_x][goal_y].step = 0;

    /*Set the steps from goal until the start step is determined.*/
    while(map[0][0].step == -2){
        for(x=0; x<SIZE; x++){
            for(y=0; y<SIZE; y++){

                //check only for minimum step areas
                if(map[x][y].step == min_step){

                    //check north area
                    if(map[x][y].n == 0 && map[x][y+1].step == -2 ){
                        map[x][y+1].step = min_step + 1;
                    }

                    //check east area
                    if(map[x][y].e == 0 && map[x+1][y].step == -2){
                        map[x+1][y].step = min_step + 1;
                    }

                    //check west area
                    if(map[x][y].w == 0 && map[x-1][y].step == -2){
                        map[x-1][y].step = min_step + 1;
                    }

                    //check south area
                    if(map[x][y].s == 0 && map[x][y-1].step == -2){
                        map[x][y-1].step = min_step + 1;
                    }
                }

            }
        }

        /*if the start is not connected from start to goal*/
        if(min_step>SIZE*SIZE){
            // the maze is not solved
            return -2;
        }
        min_step++;
    }

main関数

使用する変数

    int goal_x, goal_y;
    int status = -1;

main関数内では、上記で作成した関数を

    while(status != 0){
    make_map(goal_x, goal_y);
    status = step_map(goal_x, goal_y);
    }

のように回します。

以上で主要なプログラムの完成です。

作成した迷路

このようにして作成した迷路の例を張っておきます。
f:id:argoship25:20201205204006p:plain
f:id:argoship25:20201205204345p:plain

おわりに

いかがだったでしょうか。
今回はrand関数を用いてランダムな迷路を作成するという内容でした。
かなりやっつけでしたが、無事にrand関数でもランダムに見える迷路を作成できたように思います。

ここまで書いてから気づいたのですが、マイクロマウスでは4マスゴールかつ柱に最低一つの壁を設置する必要がありましたね...
それはまた後日ということで...

WMMC Advent Calendar 2020 - Adventar 7日目は
aluminum君による BOOX Note2のレビュー です。

昨今需要が高まっているタブレット端末の記事とあって、個人的に非常に楽しみです。

それでは。