探索アルゴリズム完成
探索アルゴリズムが完成したようです。(まだハマるパターンがあるかも?)
直線優先型足立法みたいな感じになりました。
基本は
- とりあえず壁(or仮想壁)に行き当たるまで直進
- 曲がり角の候補を列挙する
- この中で一番ゴールまでの歩数が少ない物を選択
- 一番上に戻る
の繰り返しです。
これに、
- 未踏区域優先
- 過去通った直線では1の行程を省略
- 袋小路の入り口には仮想壁を作成
等細々としたルールを追加すると、それなりに探索できるようです(?)
- 曲がる直前で通る道は必ず通った事のある道
という性質があるので、
高速なスラロームを探索の時から活かせるかもしれません。
また、必ず行き止まりまで行くので処理が遅くても目立たないかもしれません。
結論:劣化足立法
ですが、大会はこれで出ようと思います。