ファンネルアルゴリズム

　「経路探索≒A*」と思っていると損をするなぁ（したなぁ）と感じたのでファンネルアルゴリズムの記事を翻訳してみました．元の記事はこちら↓
http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html

シンプルで高速な”ファンネルアルゴリズム

　パス検索に関する質の良いマスタークラス(Alexander Kringによる階層的なパス検索の秘訣や技巧)がAIGameDev.com にある．Left４Deadで採用したパス平滑化に関するスライドは私の不満を解消した．未だパス平滑化の基準アルゴリズムを基に「各ポリゴンの境界の点を辿ろう」なんていってる人がいるかと思うと寂しくなる．本当に寂しくなる．

　ファンネルアルゴリズムはポータルに沿って直線的なパスを探すシンプルなアルゴリズムだ．詳しい記述は”Efficient Triangulation-Based Pathfinding.”で見ることができる．

　以下がその実装だ．キューや架空の物を使わない．その代わりに、新しいコーナーが見つかった時に繰り返し実行したり、以前の場所から反復を再開したりする．つまりは、一部のポータルは必要な分より少しばかり多く計算される代わりに、全体の実装がかなりシンプルになる．

＜ここで図＞

上の図は、アルゴリズムのステップを説明するものである．

• まずは現在見ている地点（黄色い円）からみて左側と右側の角に線を引く（水色とオレンジの線）を考える．

• この三角形の中にステージ外の部分が出ない限り順角を順番にずらしていく（A〜D）

• もし、左側の点が外に図形の外に出たら更新しない（E〜F）

• もし、左側の点が右側の点を超えたら、右側に繋がる線を経路として採用する．

• 繰り返す．

上の例でも見られるように、一部の辺において再計算される事はあるが、計算がとてもシンプルなために、この普通ではない方法は実装を簡潔で、素早く動くものにする．

＜ここでソースコード＞

　　配列”portals”は経路上の全ポータル（図で言う黄色の円）を持っている．最初のポータルからみて左右に位置するポータルが開始位置として設定され、ゴールとなるポータルからみ手左右に位置するポータルが終了地点として設定される．大体こんな風に<ソースコード>

素晴らしいことに、このアルゴリズムは様々なマップ表現の探索で使う事ができる．グリッド、四分木、、ウェイポイントにナビゲーションメッシュ、どれでも大丈夫だ．経路が一つのノードから他のノードへ移動するという形で表現されているありとあらゆる形式で使用することができる．

また、このアルゴリズムは移動部分とうまくかみ合わさった時に更なる真価を発揮する．たった数回分先の計算をする事で、望ましい移動速度で次のコーナーへ動かす事ができる．この処理はすごく速くて、毎ループ移動部分の前に行うことができる．

■□■感想■□■
　　FPSのAIで「最も近い武器との距離」をA*で実装した結果、武器を取得する場所の上で止まってしまって苦戦したのはなんだったんだ^^；　あの時は前もって武器同士の距離を計算したりで誤魔化そうとしたけど、「遅いなぁ」とか思ったら他のアルゴリズムがあるかどうかを調べたり、聞いたりした方がいいなぁ、マジで損した