DATE: --/--/--(--)   CATEGORY: スポンサー広告
スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
page top
DATE: 2016/03/22(火)   CATEGORY: 未分類
遠回りな道を潰してみた(仮)


今回は最近,新作マウスの探索に導入しようとしているものについて書こうかなと思います.

今回,実装しようと考えているのは
「探索中の遠回り潰し」
です.

正直,いい案が思いつかないので誰か教えてください.
現状入り口が一つである袋小路は潰せるのですが,下のような迂回路は判定ができていません.

遠回り


来シーズンでは,この様なパターンも判定したいなと思っています.

もちろん迂回路といっても残すべき迂回路と,潰していい迂回路の2種類あります.
すべての迂回路を潰すと最短経路のみが残ります.
歩数での最短はいつかやめたいので,歩数的に可能性のある経路は残したいです.

現在考えているものは,経路Aと経路Bがあったらその差,b-aがある程度以内なら有効,
大きすぎたら潰すというものです.(図が曲がっているのは許してください)
追記:図の説明を省き過ぎたと思ったので追記。
経路Aが最短経路。経路Bが遠回りな経路。xはゴールから分岐点までの距離です。(3/24)

迂回路説明


今回のb-aの基準は,定数kを与えてやってb-a>=kaとなったら潰すことにします.
定数の値を変えれば潰す判定範囲を変えることができます.
この考え方にしたがって話をすすめていきます.(もっと簡単で賢い方法があれば紹介してください)

例として,上で上げた迂回路をを潰します.
現在(7,8)にいる設定です.ゴールは(7,7).

迂回路歩数マップ


経路Aはゴールがすぐ南にあるので距離は0.
経路Bの距離は12となります(180°超信地ターンはしないとしています).
定数k=1(bはaの2倍までなら許容),とすると,
b-a=12-0=12>=1×0=0→潰すとなります.

具体例でもわかるように,aの距離さえ分かれば判定できます.
現在悩んでいるのはこの部分です.
綺麗なaの求め方がわからないです.

今シミュレーターに実装しているアルゴリズムは,簡単に言うと
①経路Aのマスを記録.
②経路BをたどりながらAとの合流地点を探す.
③aが求まる.
です.

②のときに,1つ進める度にaの経路上にぶつかった判定の処理が重いのかなと思っています.
bで一つ進める,進んだ先がaの経路に当たっていないかaの経路上を全部確認を行っています.
シミュレーター内では動いてくれてますが,マイコンで計算が間に合うかが怖いです.
どうにか処理を軽くしたいですね..

それではこれを実装した様子を見てみましょう.定数はk=0.5(aの1.5倍まで許容)です.




基本的には上の処理を加えているだけです.
他の処理の都合上,潰す場所が推定最短経路上(現情報での最短経路)や
b-a>2を満たさない場合は上の条件でも潰していません.

ここ2日で実装したので,まだまだバグが多そうです.
いろいろな迷路で試しながら,改善策を考えます.

スポンサーサイト
Copyright © うむ夫の歩み. all rights reserved.
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。