歩数マップ更新

この記事を書く背景

皆さんはマイクロマウス、ひいては、他のプログラムにおいて、計算コストというのを気にしたことがありますか。
ここでは、コストが高い=時間がかかるとし、そのためには多少のメモリを使うという思想で話します。

前提1:速い処理と遅い処理について

処理の速さとは、今回注目する、歩数マップ更新の更新においては、
ループの回数が少ない=速い処理であること意味します。
厳密には、加減乗除もコストに入るわけですが、今回に限っては、四則演算は求められないので、関係ありません。
その他、CPUの性能やメモリ等のリソースに関して、ここでは触れません。

前提2:必要な知識

この記事では以下の知識を要求します。

  • 基礎的な歩数マップ更新のプログラムが理解できること。
  • ビット演算を理解していること。

実装例

  
void updateDist(int x, int y, int mode) { //(x,y)ゴール座標
    unsigned char distPositionList[257];
    char head=0, tail=1;
    distPositionList[0] = x * 16 + y;
    clearMap(x, y); //歩数マップ初期化
    while (head != tail) { //head = tail なら更新する区画がない
        char Y = distPositionList[head] & 0x0f;
        char X = (distPositionList[head] & 0xf0) >> 4;
        head++;
        int distPoint= dist[X][Y] + 1;//歩数値
        char D = 1;//方向用の変数
        while (D <= 8) {
            char i = 0, j = 0;
            if (D == North) {//North=1
                j = 1;
            } else if (D == East) {//East=2
                i = 1;
            } else if (D == West) {//West=4
                i = -1;
            } else if (D == South) {//South=8
                j = -1;
            }
            //更新対象か確認 mode = 1(最短)のとき、既探索かを内部でチェック
            char isUpdateTarget = (mode==1) ? proceedEnable(X, Y, D) : !existWall(X, Y, D);
            if (isUpdateTarget  && getDistance(X + i, Y + j) == ILLEGAL_ARGUMENT) {
                if (X + i < 0 || X + i >= MAZE_SIZE || Y + j < 0
                        || Y + j >= MAZE_SIZE) {
                } else {
                    dist[X + i][Y + j] = distPoint;
                    distPositionList[tail] = ((X + i) << 4) | (Y + j);
                    tail++;
                }
            }
            D *= 2;
        }
    }
}

説明・解説

アルゴリズム解説

更新座標格納用配列qに初期値として、ゴール座標を格納、
隣接する座標に歩数を割り振り、
その座標を配列に格納、次の隣接する座標を探します。
無理やり1次元配列としている理由は、データ節約のためです。
ハーフでは2次元配列としてもよいと思います。
while(D<=8)としているのは、ソースの再利用性を考慮した結果です。

更新する座標情報の格納について

更新座標格納用配列qの各値には以下の法則で値を格納します。

  • 上位4ビットをX座標
  • 下位4ビットをY座標

headがインクリメントされ、値を参照したとき、上記のソースコードのようにX,Yに複合化します。

32*32の場合でも、同様の手法が使えます。

計算コストについて

今回紹介したアルゴリズムは、最大O(n)です。
ちなみに簡単に思いつく手法として

  
char looping = true;
while(looping){
    looping = false; //全座標を参照後更新がなければ、breakする仕掛け。
    for(int i=0;i<16;i++){
        for(int j=0;j<16;j++){
            if(dist[i][j]==targetDist){
                if((map[i][j+1]&0x11)==0x10){ 
                    dist[i][j+1]=dist[i][j]+1;
                    looping = true; //更新が続く可能性があるのでフラグをtrueにする
                }
                // 以下略
            }
        }
    }
}

上記のような感じになりますが、for文が3段階にネストしています。
この場合、計算コストはO(n^3)となります。
これがハーフサイズ決勝のサイズになったときの計算時間を想定した場合、恐ろしいことになります。

まとめ

計算コストについて意識する場合、ループ数を気にする
これだけです。