木構造で探索済み迷路を表現してみる?
マイクロマウスの最短経路導出を目標に、
木構造を使って迷路のゴールとスタートを結ぶ経路を導き出す事を考えてみます。
まず、木構造を作るにはノードを定義する必要があります。
マイクロマウスで最短経路を導出する時、
「カーブで減速する事や直線で加速できる事を盛り込んだ上で最短な経路」
を導く必要があるので、
ノードは「各動作の基点となる場所」ということになりそうです。
斜め走行をしないマウスでは、曲がり角または分岐点ということになるでしょう。
斜め走行に関しては自分のマウスではできないので置いておきます。
ノードの持つ情報ですが、座標と次のノードに対するポインタで良さそうです。
ポインタは、北東南西それぞれに向けて、ノードが存在すればアドレスを入れ、
(絶対座標での方向を示すのに北東南西を使っています)
対象となるようなノードが存在しなければNULLで良いでしょう。
何かすごくムダな気がしますが・・・。
それから、ノードとノードを繋ぐルールの定義です。
これが結構難題で、
うまくやらないとループにはまってしまうのが恐ろしい所です。
ゴールを起点とした歩数Mapが存在すると仮定して話を進めます。
大きな袋小路(3×3が無意味な囲いになっている等)を検出できるのならば、
- 元に戻らない
- 自分より大きい値が存在すればそちらに、なければ自分より小さな値にであっても枝を張る
というルールだけで行けそうです。
大きな袋小路が検出できない場合、
自分の枝から起点までに通ったノードと今のノードが被っているか否かを調べながらやる必要がありそうです。
こんな感じで、迷路を木構造で表せば
真の最短経路を容易に見つける事ができそうかな?と思いました。
・・・が、これ16×16迷路とかで木構造作ったらハンパじゃないデータ容量になりそうだ。
ところで歩数マップの作成もそうですが、マイコンでこの手の
再帰呼び出しで書きたくなる処理をどうやって書けば良いんでしょうか。
歩数map作成を再帰呼び出しで書いたら、
スタックオーバーフローで目も当てられない状態になってしまいました。