DATE: 2017/11/01(水)   CATEGORY: 未分類
秘伝のタレからの脱却~探索用歩数マップ~Part4

久しぶりの更新です。

正直申し上げますとそこまで面白いお話にならないなとなったので今回は短めにまとめます。
記事を分けるのも面倒なので②、③まとめちゃいます。


まず、計算時間短縮のため自分の現在位置に到達で展開を中止についてです。
探索用に歩数マップを展開する場合展開が必要な歩数マップの範囲というのは
(自分の現在地の歩数-1)の歩数となる展開までです。
ここまで展開できてしまえば移動する方向を決めることが可能です。
ですので、自分の現在位置になったら歩数マップの展開を終了→計算時間を短縮できるってことですね。

こちら参考画像です。

・全面展開
歩数マップ全面

・(9,6)にて展開中止
歩数マップ打ち切り


今のマイコンは優秀なので16×16程度ではほとんど変わりませんが、
32×32になったときは結構効いてきますね。
他にも計算時間を短縮するアイデアの実装を考えていまますが
デバッグが追い付いていないので省略します。



次に展開時に袋小路を潰していく話ですがこれは非常に簡単です。

袋小路に対する歩数マップの展開を考えて見てください。
袋小路に歩数を振ったはいいがそこから先の展開は無い…
歩数を振る必要ないよね??ってことです。
なので袋小路に歩数を振るのをやめちゃいましょう。

歩数を振る瞬間は一度の展開に二度あります。
歩数マップの初期化(ゴールに0代入とその他に最大値代入)のときと
queueに従って展開を行うときです。

このタイミングで区画の壁の枚数を数えて3枚以上ある区画なら
歩数を振る代わりに壁を入れるだったり、展開をスキップしてあげればいですね。

壁を入れる処理をする場合は1マスゴールやスタート区画は例外であることに注意してくださいね。
悲しいことが起きます。
気をつけてください。


以上で自分が用いている探索用歩数マップについての紹介は終わりです。
誰かの参考になる話になってくれたら嬉しく思います。


ではでは
スポンサーサイト

コメントの投稿

 管理者にだけ表示を許可する
Copyright © うむ夫の歩み. all rights reserved.