【Unity】3次元でのFunnelアルゴリズム - Qiita

Funnelアルゴリズムとは Funnel(ファンネル)アルゴリズムとは1辺を共有する三角形リストの始点から終点までの最短経路を求めるアルゴリズムです。 ダイクストラ法やA*から得られた経路を平滑化する方法として使用されています。 Funnelは日本語で漏斗の意味です。 言葉通り漏斗をイメージしながら解いていくアルゴリズムです。 実装、記事にした理由 ここ を参考にして実装したが動作しないパターンがあった Unityで使いたい 3次元に適用したい 日本語で詳説しているサイトが見つからなかった 大まかな流れ 与えられた三角形リストから3次元における左右の頂点配列を作成する 1で作成した配列をコピーしたものをXY平面の2次元に変換する 先端、左側の頂点リスト、右側の頂点リスト から形成されるFunnelを更新しながら経路を求める 求めた経路と三角形リストの連結部分(共有辺)の交点を挿入する 経