こんにちは、Web担のソノベです。
月一更新がWeb担の務めと言うことで、
今月は、Basic Mouseの迷路探索の足立法で使う、
等高線マップ作成関数の高速バージョンについて書きます。
等高線マップは、目的地点からのステップ数を、16×16迷路の区画すべてに割り当てたものですが、
Basic Mouse在中のmake_smap関数は、各区画にステップ数を振る時に、1つ前のステップ数がある区画をfor文を使って探し出します。
16×16区画を1つずつ調べて行くので、とても時間が掛かります。
しかし、1つ前のステップ数がある区画の場所は、その区画にステップ数を入れた時に分かっているわけです。
つまり、あるステップ数をある区画に割り当てた時に、その区画の座標を記憶しておけば、
その次のステップ数を割り当てる時に、1つ前のステップ数の区画を探す必要が無くなり、高速化が図れます。
この時、区画の座標を記憶する方法が重要となるのですが、
ここでは”キュー”を使います。
キューは、情報の記憶に使われるデータ構造で、情報を入れる配列と、情報の先頭位置を指す変数と、末尾位置を指す変数の3つで構成されます。
キューに情報を入れる時は配列の末尾に順に入れて行き、
情報を取り出す時は先頭から順に取り出します。
イメージとしては、飲食店などの順番待ちの行列と同じで、
キューに入れる情報を人間、情報を入れる配列を行列とすると、
先に列に並んでいたお客さんから順に入店し、あとから来た人は列の最後に並ぶ、という具合です。
こんな感じで区画の座標情報を記憶します。
実際にプログラムを組んだのが下です。
make_smap2(int gx, int gy, int mode){
unsigned char pt1;
short x, y, z;
unsigned char wdata;
unsigned q[257]; /* 区画の座標(0~255)を入れる配列
左下0、右下15、左上240、右上255 */
short head, tail; /* 先頭位置, 末尾位置 */ for (z=0;z<256;z++){ /* 等高線マップを初期化する */
smap[z/16][z & 15] = 255;
}
smap[gy][gx] = 0; /* 目標地点に距離0を書き込む */
q[0] = gy*16 + gx; /* 目標地点の座標を記憶 */
head = 0; /* 先頭位置を初期化 */
tail = 1; /* 末尾位置は、最後の情報位置+1 */
while(head != tail){ /* 配列の中身が空ならループを抜ける */
x = q[head] & 15; /* 配列から区画の座標を取り出す */
y = q[head] / 16;
head++; /* 情報を取り出したので先頭位置をずらす */
pt1 = smap[y][x] + 1; /* 新しいステップ数 */
wdata = map[y][x];
if(mode==T_MODE){
if (((wdata & 0x11)==0x10)&&(y!=15)){
if(smap[y+1][x]==255){
smap[y+1][x] = pt1;
q[tail] = (y+1)*16 + x; /* 次の区画の座標を記憶 */
tail++; /* 情報を入れたので末尾位置をずらす */
}
}
if (((wdata & 0x22)==0x20)&&(x!=15)){
if(smap[y][x+1]==255){
smap[y][x+1] = pt1;
q[tail] = y*16 + x+1;
tail++;
}
}
if (((wdata & 0x44)==0x40)&&(y!=0)){
if(smap[y-1][x]==255){
smap[y-1][x] = pt1;
q[tail] = (y-1)*16 + x;
tail++;
}
}
if (((wdata & 0x88)==0x80)&&(x!=0)){
if(smap[y][x-1]==255){
smap[y][x-1] = pt1;
q[tail] = y*16 + x-1;
tail++;
}
}
}else{/*S_MODEは省略*/}
}
}
探索モード(S_MODE)の記述は割愛します。
マウスに組み込む時は、忘れずに書いて下さい。
と言いますか、このプログラムを実際に動かしたことがないので、
大変なことが起こったらごめんなさい。
マウス作ります。