歩数マップ更新
この記事を書く背景
皆さんはマイクロマウス、ひいては、他のプログラムにおいて、計算コストというのを気にしたことがありますか。
ここでは、コストが高い=時間がかかるとし、そのためには多少のメモリを使うという思想で話します。
前提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)となります。
これがハーフサイズ決勝のサイズになったときの計算時間を想定した場合、恐ろしいことになります。
まとめ
計算コストについて意識する場合、ループ数を気にする
これだけです。