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日で実装したので,まだまだバグが多そうです.
いろいろな迷路で試しながら,改善策を考えます.

スポンサーサイト

コメントの投稿

 管理者にだけ表示を許可する

pazeshun | URL | 2016/03/23(水) 10:37 [編集]
このaっていうのは、一回でもゴールまでの経路がでないと求まらないのかな。
もしそうなら、ゴールへの経路が一つでも求まるまでは、全面探索は控えた方が効率よく探索できるかもね。
なんにせよ、素晴らしい取り組みだと思います。

umuoumu | URL | 2016/03/23(水) 15:04 [編集]
コメントありがとうございます。

経路を出さなくても求まるやり方を考えているのですが、回り道したときにどこで合流するかの判断が難しいです。

もうaを求めることをやめて、b-aと経路Aの距離の比較でもいい気がしてます。
全体に対して何%の遠回りなら許容するといったやり方でも悪くないかなと。

全面探索のような、取りこぼしを拾っていく探索では基準となる経路は欲しいと思います。
1つの経路が出れば、それと比較して可能性あるマスかどうかを判断していければなと考えています。
Copyright © うむ夫の歩み. all rights reserved.