今回からはフレッシュマン詐欺になりかけのフレッシュマンたちのために，
自分がフレッシュマンのときに実装した，
ちょっとした小技を紹介していけたらなと思います．


今回は壁の入れ方編にしようかなと思います．

フレッシュマン詐欺になりかけのフレッシュマンたちは，
最短パスを終えてそろそろ自分の好きなことを探求し始めるときだと思います．


探索アルゴリズムの改良に手を出そうとしている人のために壁の入れ方の応用を紹介します．


足立法では物足りない，もっとたくさん探索したい！と思っているあなた！
よりよく迷路を探索するにはよりよい回り方だけではなく，壁情報の集め方も大切です．

今回は壁情報の集め方の応用を紹介しようと思います．


まずは，壁の入れ方についておさらいしましょう．
普通壁情報を入れる場合は以下の2パターンなのではと思います．
① 初期情報

壁の初期情報により入れることができる壁を入れる場合です．
具体的には迷路の外周，(0,0)，ゴール区画ですね．
これは当たり前のようにやっていると思います．


② 壁センサによる壁の取得
探索をしながら壁を入れていく場合はこれがメインですね．


実はこれ以外にも壁を入れられる条件が存在するんです．
今回紹介するのはこちら．


③ 柱の3辺に壁が入ってない場合，残りの1辺の壁入れ

です．これはマイクロマウスのルールの裏をついた条件です．
初めて先輩に教えてもらったときには感動しました笑．
これが一番力を発揮するのは
みんな大好き櫛のときですね()．この条件は難しい迷路でより効果を発揮します．

実際の実装例を示します(うむ夫。での実装です)．

この条件で入れられる壁は，自分の現在の座標を中心とした場合4つの柱の周りの8個所です．
②の条件で壁を入れた後に，この8個所を条件判定し壁を加えているだけです．



試しに，上の画像での(A)と(B)に壁を加えるか加えないかの判断を示します．
柱の周りの壁を考える影響で(A)と(B)はセットになります．



手順1
まずマウス居る区画の北壁と東壁が入っていないことを確認します．

手順2
(B)が"探索済みで壁が無い"ことを確認します．

手順3
無いなら，(A)に壁を加えて，(A)を探索済みの壁とします．

手順4
(A)が"探索済みで壁が無い"ことを確認します．

手順5
無いなら，(B)に壁を加えて，(B)探索済みの壁とします．



これだけです．これを今いる区画の他の3つ柱の周りに適応してあげるだけです．
実装は非常に簡単です．


上でも言いましたが，この条件は難しい迷路でより効果を発揮します．
しかし，足立法では効果は見えにくいのも事実です．
足立法以外の探索をする際にはぜひ試してみてください．


最後に自分の目でどのくらい差があるのかを確かめてください．
探索方法は足立法です．

③なし足立法
[広告] VPS


③あり足立法
[広告] VPS


③なし足立法結果


③あり足立法結果




自分はこれに歩数マップ展開時の袋小路潰しと大きな袋小路潰しも実装しています．


ではでは