マイクロマウスのアルゴリズムについて④

佐倉です。

今回はマイクロマウスのアルゴリズムにについて書きます。
足立法を少しだけ拡張して迷路を完全に探索し切る、全面探索を行う方法をご紹介します。

まず、全面探索をするために何をすれば良いかを考えましょう。
効率を考慮に入れなければ簡単で、全てのマスを踏むようなアルゴリズムを組めば全面探索をしたことになります。

今回ご紹介するのは、全てのマスを踏むように探索するアルゴリズムです。

単純な方法なので、足立法がわかっている方には、一言で説明できます。
全てのマスをゴールに設定して、足立法を行う
と全面探索になります。

※ここで言うゴールは、競技として定められたゴールではなく、歩数マップを生成する時に目指すマスの事です。

より具体的には、
初期化処理として、スタート地点以外の全てのマスをゴールに設定し、

新たなマスに侵入する
壁情報を更新する
入ったマスがゴールであれば、ゴールから除外する
足立法で次に行く方向を定める

という処理を繰り返します。
入ることができる全てのマスに入ると、
ゴールがない＝歩数マップを作った時にスタート地点の歩数が更新されなくなる
ため、これを検知して全面探索終了と判定します。

これだけで全面探索を行う事ができます。
ただし効率が悪いアルゴリズムなので、スラローム走行で探索ができるマイクロマウスでないと時間内に探索し切るのは難しいでしょう。

ゴールを複数持つというのが感覚的にわかりづらい方に向けて、私の実装はこんな感じというコードを載せておきます。

//マスごとの属性を保持するビットフィールド構造体
typedef struct
{
    unsigned char isUnknown:1;    //未知か否か(今回は不使用)
    unsigned char isGoal:1;       //ゴールか否か
    unsigned char padding:6;      //予備の領域
}t_mapFlag;

//全てのマスの属性を保持する配列
t_mapFlag mapFlag[MAPSIZE_X][MAP_SIZE_Y];

//歩数マップ用の配列
uint_16 map[MAPSIZE_X][MAPSIZE_Y];

//歩数マップを作る関数
void makeMap(void)
{
    initMap();    //歩数マップの初期化

    /*
    このあたりに足立法用の歩数マップを作成するルーチン
    */
}

//今回のキー、複数のゴールを目指すための歩数マップの初期化
void initMap(void)
{
    int x,y;

    for(x = 0; x < MAPSIZE_X; x++)
    {
        for(y = 0; y < MAPSIZE_Y; y++)
        {
            if(mapFlag[x][y].isGoal == 1)
            {
                map[x][y] = 0;                //ゴールなら、目指すべきマスに初期化
            }
            else
            {
                map[x][y] = MAP_INIT_NUM;     //ゴールでなければ目指さなくていいマスに初期化
            }
        }
    }
}

これは効率の悪いアルゴリズムですが、足立法の必ずゴールに辿り着く性質と、ゴールを複数持つという発想をあわせると、簡単にいろいろなアルゴリズムを作る事ができます。
次回からはまた、私の個人のマウスを設計する過程をご紹介します。
(アルゴリズムについてもまた思いついたタイミングでご紹介します。)