Fornax 迷路探索アルゴリズム解説
こんにちは。Fornaxのハード&迷路探索担当のさばみそです。
この記事ではRCJ2024 名古屋オープンで使う迷路探索アルゴリズムの解説をしていきます。
どんなアルゴリズム？
一言でいうと、「直進優先の探索」です。
ほとんどのチームでは、拡張左手（もしくは右手）法を採用していると思います。しかし、それだと曲がる回数が増えて、その分時間がかかると考えて別のアルゴリズムを考案、実装しました。
（拡張）左手法は、進む方向の優先順位は（左,前,右）になっていますが、私が作ったアルゴリズムでは（前,左,右）という順番になっています。
直進優先の探索にすることで発生する問題を都度解決していったという感じです。深さ優先探索でよくね
主軸について
基本的な部分は非常にシンプルです。それぞれのマスで通った回数を記録し、一番通った回数が小さい方向に向かっています。
通った回数が同じ場合には、直進を優先し、次に左、右、最後に後ろ、という順番になっています。
(雑ですごめんなさい)
上のようなマップになっていた場合は、前に向かいます。
問題点 1
上のような迷路を考えます。実際に上記のアルゴリズムで試してみると、左の腕部分を意味もなく2往復します。
下の画像のような状態になった後、前のマスは2回、後ろのマスは1回通ったことがある状態になるので、ここでUターンし、効率が悪くなります。
解決策 1
上のような迷路をいい感じに探索する方法：
3方向が壁に囲まれたマスを壁だと見なします。また、壁だと見なされたマスで囲まれたマスも同様です。
実装としては、上記の条件のマスを100(※任意の大きな数)回通ったことにしています。-1などにして if 書いてもいいですが、100などの大きい数字の方が楽できる部分がありました。
図のように、行き止まりになる部分を埋めていきます。
リニアウォール制覇
これでフローティングウォールのない、リニアウォールだけの迷路で全対応できるようになりました。（多分）
フローティングウォール対応
今までのプログラムでも、通った回数を数えていることにより、ほとんどのコートで効率的な対応が可能です。
しかし、いろいろ試しているうちに非効率な動きをするマップを見つけたので、それにも対応していきます。
問題点2
この迷路で変な挙動をします。具体的には
このように、前も右も1回通ったことがある状態となり、遠回りになる、前方向に向かいます。
解決策2
上の図の状態で、絶対に通らなくていいところを壁だと見なしましょう。
具体的には、上の図の、水色の四角で囲ったところです。
さあ、ではどうやってここを通らなくていいと判断するかです。
もちろん、脳筋ですね。いいアイデアです。
具体的な手順は
・分かれ道で、行かなかった方向のマスを記録する
・記録されている、行かなかった方向のマスすべての間で最短経路を計算する(※)
・最短経路が1回も通らなかったマスを通らなくていいと判断する
というようになります。
わかりにくいと思うので、実際にその方法で探索するとどうなるかお見せします。
最短経路で使わなかったマス(のうち今までで通ったマス)を壁とみなす
今回は壁とみなすマスはなし
はい、これで無事に行かなくていい判定ができました。
これで、フローティングウォールがある迷路でも高効率の探索ができるようになりました。
(※)実際には、行かなかったマスと現在いるマスの間でも最短経路を計算します。帰り道が封鎖されてしまう可能性があるので…
おわりに
最後まで読んでいただき、本当にありがとうございます。
こんな長々と書いといてなんなんだって感じですが、迷路探索アルゴリズムをぐちゃぐちゃ考えるよりも、機体がなくても迷路探索のプログラムが書けるということが大事だと思います。仮想迷路みたいなのを作れるようにして、その中で疑似的に動かす、という環境があれば迷路探索はまず大丈夫なんじゃないでしょうか。
質問などがあればX(旧Twitter)のDM(@sabamiso_RRSC)までどうぞ！
この記事が気に入ったらサポートをしてみませんか？