歩数map [Mice Wiki]

現在位置: IndexPage » 歩数map

技術資料

このWikiについて

この文書は読取専用です。文書のソースを閲覧することは可能ですが、変更はできません。もし変更したい場合は管理者に連絡してください。

====== 歩数マップ ======
足立法や最短経路の導出には必須だと思います。

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

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

===== 簡単な歩数マップの作り方 =====
①歩数マップ用に、16×16（迷路区画分）のunsigned char型配列を用意します。

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

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

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

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

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

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

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

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

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

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

{{:wall_map:歩数マップa.png?150|}}　→　{{:wall_map:歩数マップb.png?150|}}　→ {{:wall_map:歩数マップc.png?150|}} …　{{:wall_map:歩数マップd.png?150|}} 

===== 高速な歩数マップの作り方 =====
上記方法でも問題なく走れますが、迷路が複雑になるほど計算に時間がかかってしまいます。

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

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

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

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

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

/home/users/2/deca.jp-mice/web/cgi/dokuwiki/data/pages/歩数map.txt · 最終更新: 2011/08/05 03:13 by member

文書の表示以前のリビジョン

[unknown link type]文書の先頭へ

Menu

このWikiについて