今回はポリゴン上の2頂点間における最短経路探索について。
標準関数でありそうな機能ですが、意外にも見つからなかったので自前で実装してみました。
ゲームキャラのルーティングや、カーナビのルート探査などでよく使われているらしいA*(Aスター)アルゴリズムを使用しています。
本当は2時間くらいかけて書いた詳細なアルゴリズムの説明があったのですが、Wordpressの設定ミスで消滅してしまったので気力が尽きました。
A*アルゴリズムについて
A*は最短経路問題解決アルゴリズムの一種で、ダイクストラ法の派生アルゴリズムです。
標準的なダイクストラ法では、スタート地点から放射状に周辺ノードを探査していくのに対し、A*法では出来るだけゴールに近いルートを優先的に探査する事によって、処理コストを低減しています。
詳細についてはA*のWikiを参照してください。(丸投げ)
MaxScriptへの最適化
基本的にWikiのアルゴリズムを流用していますが、MaxScript用にいくつか最適化しています。
- 頂点IDを2つ渡し、それぞれをスタート地点とゴール地点とする。
- 2頂点間を最小距離で移動するルートを探索する。(ステップ数は考えない)
- CLOSEリストを使用せず、代わりにノードにisClosedプロパティを持たせる。
- 作成済みノードを頂点IDで索引する為に、頂点数と同じ大きさのプール配列を使用する。
- 経路は頂点IDのみを記憶し、エッジIDは保持しない。(理由後述)
コード (Editable_Poly版)
ダウンロードリンク
TRLib_PolyAStar.ms (5.1 KB)
テストコード
編集可能ポリゴン上で2頂点を選択し以下を実行します。
-- 編集可能ポリゴンから選択頂点を取得
local epoly = $.baseObject
local selVerts = for v in polyop.getVertSelection epoly collect v
-- オペレーション構造体を作成
local op = PolyAStarOp()
-- 2頂点間の経路頂点を取得
local resVerts = op.getVertsBetweenTwoVerts epoly selVerts[1] selVerts[2]
polyop.setVertSelection epoly resVerts
-- 2頂点間の経路エッジを取得
local resEdges = op.getEdgesBetweenTwoVerts epoly selVerts[1] selVerts[2]
polyop.setEdgeSelection epoly resEdges
経路上の頂点が選択された状態になります。
また、エッジモードに変更すればエッジが選択されているのを確認出来ます。
ただし頂点間に経路が存在しない(2頂点が別の要素上にある)場合、戻り値配列が空のため選択は解除されます。
エッジ取得について
エッジ取得を別関数にしたのは、隣接要素の取得関数(polyop.getVertsUsingEdge等)の処理コストが大きく、毎回取得していると遅くなってしまうからです。
探査コードの以下の部分はエッジを個別に処理せず、直接頂点IDへ再変換しています。
そこからノード自身の頂点IDを引く事によって、隣接頂点のみを取得しています。
-- 頂点に隣接する頂点リストを取得
local verts = getVUE epoly (getEUV epoly theNode.id)
verts[theNode.id] = false
移動コストの計算
移動コストの計算は_openNodeの先頭で行っています。ここの計算式を変更すれば、探査条件を変更する事が出来ます。
-- 頂点座標を取得しコストを計算する
local pos = polyop.getVert this._epoly vertId
local cost = (length (pos - parentNode.pos)) + parentNode.cost
例えば、実距離ではなく経由したノード数をコストにすれば、極力ステップ数を減らすような経路を選択させる事もできます。ただし、単純に定数を加算しただけだと、ゴールまでの距離によって相対的なコストの重さが変化してしまいます。
オブジェクトを拡大しただけで経路が変わってしまうので注意が必要です。
コード (Mesh版)
Editable_Polyではなく、Meshを処理したい場合はこちらを使用してください。
例えばモディファイヤのビューポートメッシュで処理したい場合など、ノードの.meshプロパティからTriMeshを取得して処理する事が出来ます。
コードはほぼ同じなのでDLリンクだけを置いておきます。
TRLib_MeshAStar.ms (5.6 KB)
不可視エッジ
基本的な内容はEPoly版と同じですが、Meshでは不可視エッジの概念がある為、表示されているエッジだけを辿る必要があります。
以下のコードはmeshop.getEdgesUsingVertで取得したエッジリストから、不可視エッジを取り除いています。
-- vertIdを使用する全てのエッジを取得する
local edges = meshop.getEdgesUsingVert theMesh vertId
-- 不可視エッジをフィルタリング
for ei in edges do
edges[ei] = getEdgeVis theMesh ((ei - 1) / 3 + 1) ((mod (ei - 1) 3) + 1)
getEdgeVisはフェースIDとフェース内でのインデックス(1~3)を指定する必要がありますが、Meshの場合、エッジIDからこの2つを逆算する事が出来ます。
隣り合うフェースに挟まれたエッジ
Meshの場合、1つのフェースが常に3つのエッジを専有しており、隣り合うフェースの間にあるエッジは2つのエッジが重なっています。つまり、2つの頂点間にあるエッジは、常に1つか2つ存在する事になります。
結果として、Mesh版のgetEdgesBetweenTwoVertsの戻り値はBitArrayの配列になっています。
EPoly版と違い、戻り値を直接setEdgeSelection等に食わせるとエラーになるので注意が必要です。
Mesh版の処理速度
残念な事に、Mesh版はPoly版に比べて大分処理速度が遅いです。
正確には計測していませんが、おおよそ2~10倍程度速度差が出ます。
上記のエッジフィルタリングも1つの原因ですが、どうもTriMeshそのものが若干遅いみたいです。
Editable_Meshであればもう少し速度が出るみたいなのですが、snapshotを作成するコストを考えると、TriMeshをそのまま使うかEditable_Meshに変換するかは、今回に限らず問題になりそうです。
最後に
自分なりにコードを最適化したつもりですが、経路探索の仕組み上それなりに重いです。
特にポリゴン数が多いモデルで、非常に遠い距離で実行するとかなり時間がかかるはずです。(仕組み上、処理時間が無限大になる事はありませんが…。)
ここはこうした方がもっと早くなる等ありましたら、教えて頂けると大変有り難いです。
najx60