This explanation is currently available in Japanese.
ひとことで
ナビメッシュの探索で見つかった「通る多角形の列（回廊）」の中で、角をかすめて進む最短の折れ線を求める方法です。回廊の入口と出口の間に糸を張って、両端を引っ張ったときにできる形なので、ストリングプリング（糸を引く）とも呼ばれます。多角形の中心や辺の中点を結ぶだけのジグザグの経路に比べて、短く、人が歩きそうな自然な経路になります。
ゲームでの使いどころ
- ナビメッシュの経路の仕上げ：Recast/Detour などのナビメッシュのライブラリは、A* で回廊を求めたあと、ほぼ必ずこの処理で経路を引く。
- 曲がり角の数を減らす：曲がり角が少ないほど、キャラクターの向きの変化が少なく、自然に見える。
- 次の曲がり角だけを求める：毎フレーム全体の経路を作り直さず、「今いる位置から見た次の曲がり角」だけを求めて、そこへ向かって歩く（シーク）。
しくみ
回廊の境目の辺（ポータル）を、進む向きに対して左端と右端をそろえて並べます。始点を「頂点（apex）」として、頂点からポータルの左端・右端へ 2 本の線を張ります。これが漏斗（ファネル）です。
ポータルを 1 つずつ進めながら、次のように漏斗を狭めていきます（Mononen の Simple Stupid Funnel Algorithm）。
- 狭める：次のポータルの右端が、今の右の線より内側にあれば、右の線をそこまで動かします（左も同様）。
- 越えたら曲がる：右の線を動かそうとして、それが左の線を越えてしまう場合は、左の線の端が「どうしても回り込まなければならない角」です。そこを曲がり角として経路に加え、新しい頂点にして、その角の次のポータルからやり直します（左右逆も同様）。
- 最後のポータル（ゴール）まで進んだら、ゴールを経路に加えて終わりです。
内側か外側かの判定は、2 次元の外積の符号で行います。頂点 から見て点 が線 の左にあるかは
でわかります。平方根も三角関数も使わないので、とても速く動きます。
実装のポイント
- ポータルの左右：回廊の多角形の中から辺を見て、左手にある端を left にそろえます。そろっていないと漏斗がすぐ裏返って、おかしな経路になります。
- 最初と最後：始点とゴールを、左右の端が同じ「長さ 0 のポータル」として、列の最初と最後に足しておくと、処理を分けずに済みます。
- 角から少し離す：ナビメッシュをキャラクターの半径で縮めていれば、角をかすめてもめり込みません。縮めていない場合は、曲がり角を外へ少しずらします。
- なめらかにする：折れ線の角を、キャットマル・ロム曲線や円弧でならすと、さらに自然な歩き方になります。
つまずきやすい点
- 同じ点の扱い：頂点と端が同じ位置にあるとき（直前に曲がった角など）は外積が 0 になります。この場合も狭めてよいことにしないと、処理が進まなくなります。
- やり直しの位置：曲がり角を見つけたら、その角があったポータルの次から調べ直します。今のポータルから続けると、角を 1 つ見落とします。
- 回廊が最短とは限らない：ファネル法は、与えられた回廊の中での最短を求めます。A* が遠回りの回廊を選んでいれば、経路もそれに従います。
デモで試すこと
- 白い点が頂点、青い線と黄色い線が漏斗の左右の線、太い白線が今見ているポータルです。ポータルが進むにつれて漏斗が狭まっていく様子を見てください。
- 片側の線が反対側を越えたところで、その角が曲がり角として赤い経路に加わり、頂点が移ります。
- 「ポータルの中点を結んだ経路と比べる」で、紫の点線（ジグザグの経路）との長さの違いを、左下の数値で確かめてください。
- 「1 手順の時間」を長くすると、1 つずつ追えます。床をクリックすると、別の目的地で最初から始まります。