歩数マップ

足立法や最短経路の導出には必須だと思います。

目標位置から何マス離れているかを表すマップです。

歩数マップを作って、数字の少ない方へたどっていけばゴールまでいけます。

簡単な歩数マップの作り方

①歩数マップ用に、16×16(迷路区画分)のunsigned char型配列を用意します。

②歩数マップを255で初期化し、目標座標(ゴール位置)の歩数を0にします。

③for文とif文を使って、歩数マップが0の所を探します。

④0の所を見つけたら、その周囲4マスのうち、壁がなく歩数が255の所を1に変えます。

⑤全部探したら、今度は1の所を探します。

⑥1の所を見つけたら、その周囲4マスのうち、壁がなく歩数が255の所を2に変えます。

⑦全部探したら、今度は2…

これを歩数マップが更新できなくなるまで繰り返します。

最初のうちは、紙に書いてイメージを掴んでから作ってみるといいかもしれません。

ちなみに未探壁には注意が必要です。

足立法と最短経路導出で扱い方が変わるので注意してください。

 →  → … 

高速な歩数マップの作り方

上記方法でも問題なく走れますが、迷路が複雑になるほど計算に時間がかかってしまいます。

まだ絶対に更新しない部分や、更新済みの部分も調べてしまうため、非常に効率が悪いです。

そこで、更新した座標を覚えさせ、その部分だけ順番に調べていくのが今回の方法です。

詳しくは気が向いたら書きます。

電通大ロボメカ工房マイクロマウス部門さんのブログに書いてた方法なので、そちらを参照して下さい。

うまくいけば桁違いに速くなります。

/home/users/2/deca.jp-mice/web/cgi/dokuwiki/data/pages/歩数map.txt · 最終更新: 2011/08/05 03:13 by member
CC Attribution-Noncommercial-Share Alike 3.0 Unported
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0