Miceで主流な壁情報の記録方法

壁情報の記録方法の記事が少ないということで書きます．

以下の記事の方法の話です．
壁情報の記録 - hantas's blog

マイクロマウスを完走させるうえで一番初めにビット演算などが関わってくるのが壁情報です．ビット演算と聞いて機械工でプログラム初心者の僕はすごく嫌な気分になりました．同じような人に少しでも助けになればと思います．お酒入れているので間違ってたらすいません....

壁の数

クラシック競技の迷路は16×16区画で，壁は2×16×17枚あります．すべての壁の有無を記憶するためには，bit必要です．

4×4の迷路を考えると，水平(Horizontal)な壁が4枚×5行分，垂直(Vertical)な壁が4枚×5行分，計2×4×5枚分あるのがわかる思います．

縦壁と横壁で記録する

言葉で説明するのもつらいので，図を見てください．垂直な壁と水平な壁に分けて考えて，壁がないことを0，壁があることを1と表し，各ビットを一枚の壁に対応させます．

任意の座標の任意の方向の壁はどこの配列のどこのビットに対応するのか考える

まず注意として，以下では最上位ビットから数えて何bit目かという表現をします．2進数で1000という数があったとすると，1は最上位ビットから数えて0bit目，0100という数があったとすると，1は最上位ビットから数えて1bit目という調子です．上図を見てください．座標(3,2)の東西南北の壁はどの配列の何bit目に対応しているでしょうか．．．北壁はwallH[3]上位から3bit目，西壁はwallV[3]上位から2bit目，南壁はwallH[2]上位から3bit目，東壁wallV[4]上位から2bit目に対応してますね？(間違えてたらすみません...お酒のせいです)

さてこれを一般化して，座標(x,y)であったら，どうでしょうか．

少し考えると上図のようになりますね？(間違えてたらすみません...お酒のせいです)

ということで，任意の座標の任意の方向の壁はどこの配列のどこのビットに対応するのかわかりました．あとは実装するのみです．頑張って．

16×16区画だと必要な配列数は？

4×4の迷路であれば，wallHとwallVという2進数4桁の配列は[0]から[4]の5個必要でした．ということは16×16の迷路なら17個の2進数16桁の配列があればよさそうです．まずはそのようにして実装すればよいと思います．マイクロマウスの競技の規定上一番外の壁は必ずあります．そのように事前にあることが確定している壁については壁情報用の配列を用意しなくてよいので，本当は垂直と水平それぞれで15個の配列があれば十分かもしれません．しかし，今後，(x,y)座標における北壁があるのか確かめる関数等を実装する必要があります．そのような関数を作る際，例外処理が必要になるので，まずは17個の配列を用意して壁情報に関わる関数の動作を一通り確認し終えたら，不必要な情報は持たないようにしていけばいいんじゃないかと個人的には思います．(僕はいまだに未実装...)

実装の方法

16×16マスであれば，17個の2進数16桁の配列があればよさそうなので，uint16_tの配列を垂直と水平方向で2つ用意します．最上位ビットだけが1で他が0の16桁の2進数を16進数で表すと0x80です．南壁を例にとると，wallH[y]上位からxbit目の数を1としたいです．uint 16_t one=0x80;として，このoneを右にxだけビットシフトして，0で初期化したwallH[y]と(one>>x)をor演算すればいいんじゃないでしょうか．それでは，壁を入れることしかできませんが，その辺は自分の宗教によるところだと思います．(僕は壁を入れることしかできません．入れ間違えたら終わりです．)

完走に必要な壁情報に関わる関数

⓪ 壁の初期化関数(外壁とスタートの横の壁は1,他は0に初期化)
① 座標と方位を与えたらその場の壁の配列に壁を入れる関数
② ある座標と向きにおいて左と前と右センサの値が閾値を超えていたら，その方向の壁に壁を入れる関数
③ 座標と向きを与えたらその場の壁があるかどうか判定する関数
④ すべての壁情報を吐き出す関数

...ここまでが足立法実装に必要な関数だと思います．この後は，完走から先に必要になるもの．
⑤ 既知壁の記録，判定，出力の関数→最短走行，既知区間加速，未知区間優先探索に
⑥ 未知壁をすべてあるものとして壁を入れる関数→最短走行に
⑦ 入れた未知壁を取り除く関数→最短走行後の探索に

いっぱいありますね...一発ですべてを理解して，実装するのは厳しいので，一つ一つ作っていきましょう．．．
お酒もまわってきたので，この辺で...