迷路情報の考え方～WMMC秘伝のタレ 前編～
初めましての方は初めまして。
そうでない方はお疲れ様です。
今回はマイクロマウス（クラシックマウス）に必須の迷路情報の考え方です。
今まで秘伝のタレに頼りきり、かつその一部を流用してただけなので、改めて解読しまとめました。
＊この考え方はあくまでWMMCの標準マウス用プログラムの考え方であり、2018年現在として相応しくないであろう部分があることを前提としてください。＊
概要
迷路の最大の大きさは
クラシックマウスで16×16（画像）, マイクロマウスで32×32
となっています。
この一区画あたりに格子点でxy座標を与えれば二重配列map[y][x]でマップにおける位置情報が示せます。また、この配列の中身には壁情報が入っています。1つの二重配列で現実のマップ情報を全て表せるわけですね。
次に歩数マップと呼ばれる二重配列smap[y][x]。マップの一区画ずつに「重みづけ」を行った後の配列で、経路作成時に優先区画を定めるために使われます。重みの値はゴール座標が0, 遠ければ遠いほど大きくなる。書き換えていない区画はMaxの256.(8bit用、32×32に対応できない？)
続いて進路配列と呼ばれる一次元配列route[i]。現在地、歩数マップを元にしてマウスの進むべき道…経路を記録するための配列です。探索中でも用いられていますがある程度の探索が済むと、疑似的に最短経路配列になります。（エセ最短？）
グローバル変数としては
PRELOC.AXIS.Y…機体の現在y座標
PRELOC.AXIS.X…機体の現在x座標
m_step…歩数カウンタ、route[i]の中身をいじる用
m_dir…機体の向いている方向を示す
wall_info…現在の機体向きから見た壁情報
これらを用いて求心法＋足立法でやっている（と推測される）。
具体的には歩数マップの製作条件が求心法、探索時に仮最短経路生成 ⇒ 実走行 ⇒ 最短経路修正 の流れがそうなのだろうか？
概要はこんな感じでした。
迷路情報（壁情報）の管理
マウスの世界では一般的に、スタート位置から見て地図と同様に北、東、南、西が定められています。この方角は絶対的な基準です。つまり壁情報配列には「(x,y)区画での北壁、東壁、南壁、西壁それぞれの有無」が記載されているわけです。
具体的には2進数を用いて保存しています。北壁を4bit目、東を3bit目、南を2bit目、西を1bit目に割り振っていますね。
標準プログラムでは、現在の機体が取得した壁情報は前壁、左壁、右壁と判断しています。しかし！これを壁情報配列に直接書き込むのはいけません。
機体の向き次第で、前壁は北壁にもなるし、東壁や他方向の壁にもなりえます。だからこそ機体の向きを表すm_dirを用いて、取得した壁情報wall_infoを補正する必要があるんですね。
ちなみにwall_infoだけ上位bitに全く同じデータがあるのは処理の都合の為です。
忘れていましたが、m_dirでは、北向きを0, 東向きを1,南向きを2, 西向きを3と定義しています。
秘伝のタレではビットシフトを用いて補正を行っています。
具体的な事例の処理を見ながら行きます。
Ex.の状況では機体から見て、前壁（F）と右壁（R）があるのでwall_infoでは1100のように表せます。しかし、機体は東を向いているので、この区画の壁情報としては東壁（E）と南壁（S）がある、つまり0110と表せなくてはいけないんですね。ここでビットシフトによる補正を行います。
m_dirの部分だけビットシフトすると下位4bitのうち消失するデータがありますが、消えた部分は上位4bitから降ってくるんですね。このためにwall_infoには同じ情報が二つ入力されています。（頭いいなぁ）
そして処理後には上位bitは不要なデータなのでクリアしちゃいます。
また1つの区画で壁が見えると隣の区画から見た壁の有無が分かるのでその処理もしていますね。
ここまでで得られた値を現在地の座標で配列の中に格納すれば終わり。
実は格納するデータに対しては、クリアした上位４bitに下位のデータをコピーしていたりするんですが何のための処理なのかよく分からないんですよね…最短経路導出に使うとかコメントアウトしてあるけどどうして下位bitではだめなのか…
＊コード製作者からご指摘があり、上位4bitにコピーをするのは最短経路作成の際に既知区間の壁のみを考慮するためだそうです。最短経路の際は、上位4bitのデータのみで経路計算を行います。初期化の時点で上位４ｂｉｔを全て1にすれば、未知区間はデッドスペース扱いになるので通過したことがある経路のみ考えて経路作成ができるそうです。＊
とりあえず今回はここまで。
次回は（余裕があれば）歩数マップ生成と経路導出の解読回です。
マウス合宿…合宿先で徹夜レポートならワンチャン…
