[Rust] 四分木による経路探索

ChatGPT の勢いがすごいですね。きっと我々の仕事はなくなるのでしょう。 そんな中、空気を読まずに経路探索のアルゴリズムについて語ります。 この記事は swarm-rs というゲーム実装のノートの一部 (こちら) を翻訳し、少し肉付けしたものです。 まず前提ですが、経路探索するのは二次元の占有グリッド(Occupancy grid)の中です。 地形情報がバイナリイメージとして与えられていると考えても良いです。 経路探索のアルゴリズムとしては、ダイクストラ法とA*が有名ですが、これらについては良い教材が腐るほどあるので触れません。 ただ、どちらも探索空間をグラフとして表現することを前提とします。 占有グリッドをそのまま探索空間とすると、ゴールに至るまでのピクセルのほとんどを評価する必要があるので、探索計算が非常に長くなる傾向があります。 ここでは、バイナリイメージで与えられた探索空間をい

[biwakonbu]

最近ゲームAI系に興味がちょっと出てきてるんだよな。特にやりたい事があるわけでも無いんだけど。