algorithm - 障害物がある連続した大きな地図で道を見つける

Question

私は、いくつかの障害物（ランダムなポイントでのボックスや台無しの壁など、マップが大きい）を使用して、連続ボード（グリッドセルなし）でゲームを作成しようとしています。これを解決するためにどのアルゴリズムを使用できますか (グリッドボードの A* に似たものです)? ちょっと調べてみたのですが、ボロノイ図を使ってもいいですか？

Answer 1

Skiena のThe Algorithm Design Manualでは、「モーション プランニング」と呼ばれる計算幾何学の下にエントリがあります。そのためのいくつかの実装、Motion Planning Toolkit、SWIFT++、およびCGALがリストされています。できれば、その本を読んでみてください。読むのは非常に実用的であることがわかりました。実際には多くの解決策を提供しているわけではありませんが、それらを見つけるためのヒントが常にいくつかあります。基本的に、アプローチは、マップから適切なグラフを生成し、ダイクストラのアルゴリズム (または A*?) を使用して最短の方法を見つけることです。グラフを生成するには、障害物を越えずに移動できるポイントを分析する必要があります。