2013-12-08 47 views
5

私は、ゲームのグリッドからナビゲーションメッシュを構築しているRTSゲームのパス検索に取り組んでいます。穴を持つ最も速い三角形分割アルゴリズム?

私は、地図の歩行可能領域と歩行不能領域の間の境界線を作成し単純化するマーチング・スクエアに似たアルゴリズムを書いています。今私は唯一のエッジで構成される "メッシュ"を持っています。最後の三角形分割に最初の辺が含まれるように、このメッシュを三角形分割してから、ナビゲーションできない領域を削除してナビゲーションメッシュに穴を作成する必要があります。例えば、私は

enter image description here

三角形がマップの歩きやすい領域を表す...これを実行する必要があります。穴は、山や建物などの不安定な地域を表します。高さは無関係なので、メッシュは2Dと見なすことができます。これは明らかに非常に単純化されたケースです。ゲーム内のナビゲーションメッシュは、何千もの頂点と多数の穴から構成されますが、動的な更新のために小さな小塊に分解することがあります。

私は拘束されたDelaunay三角測量アルゴリズムを見てきました。まず、Delaunay三角測量を作成し、拘束された辺を交差する三角形を取り除き、次に削除した三角形を再三角形分割します。

これは私の目的にとって少し冗長なようです。私のメッシュはDelaunayである必要はなく、拘束された辺から完全に構成されているので、できるだけ余分な三角形分割をスキップしたいと思います。これにはより良いアルゴリズムがありますか?私は見て、見て、拘束Delaunayアルゴリズムを見つけることができただけです。または、私は間違っているかもしれません。制約付きDelaunayアルゴリズムが最適でしょうか?

以前はナビゲーションメッシュパスの検索を行っていましたが、ナビゲーションメッシュを自分で生成する必要はありませんでした。三角測量アルゴリズムは私にとって初めてのものです。どんな洞察?

+0

三角に関する特別なリクエストがないので、[ポリゴン三角形分割](http://en.wikipedia.org/wiki/Polygon_triangulation)のような簡単な方法がDelaunayより使いやすいです。 – Ante

+0

私は、Delaunay三角測量よりもわずかに遅いと思われるEar-Clippingメソッドを見ましたが、ループオーダーで頂点をソートする必要があります。 –

+0

今私はあなたがエッジだけを持っていることを認識します。いずれの場合も、エッジを接続して向きを合わせる必要があります。穴のあるポリゴンを三角形分割して、他の部分(穴があるかどうかを知る)の内側にある部分を探します。穴は、穴からポリゴンの境界線または他の穴まで2つの同じ辺を追加することで削除できます。耳のクリッピングは単純な方法で、空間分割(BSPツリー、クワッドツリー、...)ではO(n^2)よりも速いです。 – Ante

答えて

0

Fernandez et al 2008は、複雑なドメインを分解する問題については、最先端に近いと思われます。もしあなたが(もっと単純な)代替案を探しているならば、著者はp370の第2段落に他の可能なアルゴリズムを列挙します。

関連する問題