閉じた区画の既知化(目指せ全面探索part1)
おはこんばんちは~、ひふみです。
当然かつ簡単なことなのかもしれない機能の追加が成功したのでめも。
閉じた区画の既知化です。僕が表現する閉じた区画とは↓の様な状態。
死ぬほど見にくくて申し訳ない。この白い部分が閉じた区画。
(恐らく)この区画、ただ探索回してるだけでは既知にならない、気がします。もしかして簡単に既知になるのだったらこの記事は未知のものとしたい。
僕が実装したこの区画を既知にする方法は至って簡単で、
1.走行中周辺に探索最大歩数区画(=迷路サイズの2乗)があるか見る。
2.その区画を既知にする(任意区画周辺壁フラグを立てる関数を用意します)。
3.その区画の周辺に探索最大歩数区画があるか見る(かつ既知区画でないこと)。
4.あったなら2に戻る。ないなら終了
と言った感じです。これを適当にキューで実装しました。すると、閉じた区画もちゃんと既知区画とすることが出来ました。これで誤って全面探索時に閉じた区画を回ろうとしないで済む。がしかしこれを書いている途中に全面探索する直前に閉じた区画を既知にすればいいんじゃないか・・・?とも思った。探索計算時間余分に増えそうだしこの機能は入れないかもなぁ。
とまぁそんな所が今日の進捗でした。
お読み頂きありがとみんと。