math - 任意の非長方形ボディのパスファインディング

Question

球体、ピラミッド、メッシュで表されるその他のさまざまなオブジェクトなど、サーフェスが 3D で非長方形のさまざまなオブジェクトがあります。メッシュは、オブジェクトの表面全体に同じサイズと分布のポリゴンで構成されているわけではなく、円柱、球、円錐の理想的な形状のようなすべての半対称オブジェクトでもありません。

したがって、任意のメッシュを取り、さまざまな方法で自分自身をラップできるノードを生成する経路探索アルゴリズムを設計または改造するにはどうすればよいでしょうか?

Answer 1

1 つの (おそらく最も単純な) オプションは、グリッド ベースの検索手法を使用することです。マルチ解像度のグリッド分解を生成し、セルに「フリー」または「衝突」のラベルを付け、A* などを使用して結果のグリッドを検索する非常に簡単な方法がいくつかあります。 （セランが言及しているように）。

一般に、確率的ロードマップ(PRM) や高速探索ランダム ツリー(RRT)など、より強力なモーション プランニング手法を使用する必要がある場合があります。これらの分野には非常に多くの学術研究があります。

はじめに、このような調査用紙(PDF) を確認することをお勧めします。

Answer 2

このアプリケーションでは、* 検索は問題なく機能するはずです。2 点間の距離を過大評価しない関数が必要ですが、直線距離がサーフェスに沿った距離を過大評価することは決してありません。

Answer 3

おそらくここで全体像を伝えておらず、問題を3Dシーン=>有向グラフ=> ???に要約しようとしていることに気づきました。=> pathfind ですが、別の方向からこれにアプローチすることを検討しましたか?

有向グラフを事前に作成する方法はありませんか? ほとんどのゲーム (これはゲーム用だと思います) は、検索パスを構築するときに、シーン内のすべてのオブジェクトの完全なジオメトリを考慮しません。たぶん別の方法がありますか？

とにかく、このリンクはあなたの研究に役立つかもしれません。