ダイクストラ法とA*アルゴリズムをMaya上でビジュアライズする+おまけ
この記事はMaya Python Advent Calender 19日目の記事です。
ダイクストラ？A*？
聞きなれない方もいらっしゃるかもしれませんが、いわゆる最短経路長問題を解決するアルゴリズムです。
迷路、経路探索というとわかりやすいかもしれません。
このアルゴリズムでは単なる経路探索ではなく距離や移動時間といった重みをつけて探索できます。カーナビなどもこのアルゴリズムが利用されているそうです。
ダイクストラ法
対象の全ノードに対する最短経路を計算し始点と終点を結ぶ最短経路を求めます。
全ノード探索するので処理コストはかかりますが、始点からの最短重みが計算されるのでMayaでいうところのメッシュ形状を考慮したソフト選択とか実装できたりします。
A*（エースター）
ダイクストラ法の発展形。予想される最短ノードから順番に探索し、経路が見つかった処理終了するので計算量が少なく済み圧倒的に早いです。今回の例ではユークリッド距離でヒューリスティック関数を実装しています。
詳しくはググってね☆
実装コードご紹介
例題としてMaya上で選択したメッシュの2頂点感を結ぶ最短経路をもとめるスクリプトを作成してみました。
サンプルとしてXSI男さん（ややHighMesh化）にご協力いただきます。
総頂点数4795となっています。
ダイクストラ法
細かいことは置いといてコードがこちら
任意の2点を選択して実行するとこんな感じで最短経路が求められます。
ログで計算回数と実行時間を確認します。
探索回数28664回、総実行時間2.93sec
といった結果になりました。
念のため両胸ポッチの最短経路も求めておきます。
ははあ、距離2.29ね。
※あくまで念のためです。
A*アルゴリズム
お次はA*で実装した例です。
処理の流れはほぼ同じですが、事前に終点からの直線距離を計算しておき、一番最短である可能性の高いノードから探索していきます。
実行結果は同じ、正しく最短経路が求まっています。
ログを確認してみましょう。
実行時間が0.43sec、計算回数は2456回
約7倍ほど早いですね。
計算量と時間比較
このメッシュ数なので7倍程度の差になっていますが、ダイクストラ法はO(n²)で計算量が増加するのでハイメッシュになればなるほど差が大きくなります。
試しに33458頂点に割りなおして実行すると・・・
総実行時間で17倍程度に差が開きます。
ノード探索の様子をビジュアライズ
ダイクストラとA*、同じようなアルゴリズムなのにどうして大きく差がつくのでしょうか？実際にノード探索がどのように進んでいくのかわかりやすいようにビジュアライズしてみましょう。
題材はXSI男さん(さらにハイメッシュ顔半分)のUV。
この2点間の探索を行います。
ダイクストラをビジュアライズ
始点から周囲に対して均一に探索範囲が広がっていきます。
全ノード探索後に最短ルートが確定しています。
A*をビジュアライズ
終点からのユークリッド距離を基準に探索ノードを決定しながら進んでいきます。
終点付近に近づくにつれ、迷わずノード探索するようになります。
用途に応じて使い分けたいですね。
念のため両胸ポッチの探索もビジュアライズしておきます。
ははあ、こう進んでるんですね。
※あくまで念の(ry
おまけ
以前TKCMさんの記事で紹介されていたメッシュ形状を考慮したソフト選択のFablic_Engenでの実装、どうしてもやってみたくなったので作ってみました。
ソフト選択反映にラグがあるあたりはちょっと劣化版ですが、、
コードはこちら。
実行するとスフィアとUIが取り出されます。
コンポーネントを選択してComputeすると頂点の重みが計算されてソフト選択状態になります。
ノードのエッジ間の距離で重みづけされるので分断されている箇所の距離も正確に考慮されます。
最後に
こちらのサンプルはアルゴリズム初心者がなんとなーく実装したゆるいコードとなっております。
実装面での間違いや速度面の改善案などあればご指摘いただけるとうれしいです。
