点 A にオブジェクトがあるとします。オブジェクトは点 B に移動できるかどうかを調べたいと考えています。速度が制限されているため、段階的にしか移動できません。移動している方向に光線を放ちます。レイが物体に衝突し、それを検出します。光線を安全に通過させる方法を取得する方法 (衝突を回避する方法) は?
ところで、オブジェクトキャストの場合にそのようなことを機能させる方法はありますか?それは単純なレイキャストと同じくらい/ほぼ高速ですか?
いくつかのvayパスで最適なものを見つける方法はありますか?
あなたが求めているのは、実際には経路探索の質問です。より具体的には、「あらゆる角度の経路探索問題」です。
障害物のエッジをグリッドに制限できる場合、一般的な解決策は、そのグリッドで A* を使用してから、パス スムージングを適用することです。ただし、実装/理解が簡単で、パススムージングよりも優れた結果が得られる(かなり最近の)アルゴリズムがあります。それはTheta*と呼ばれます。
Theta* を説明する素敵な記事があります (上の画像はここから盗みました)。
障害物をグリッドに制限できない場合は、マップのナビゲーション メッシュを生成する必要があります。
これを行うには、さまざまな複雑さのさまざまな方法があります。たとえば、ここ、ここ、またはここを参照してください。簡単なグーグル検索でも、これを行うために利用できるライブラリがたくさん見つかります。
1 つの方法として、1 本のロープまたは複数のロープを使用する方法があります。この場合、ロープは直線的に接続されたいくつかのポイントで構成されます。空間内のランダムな場所で点を初期化できますが、最初の点はAの初期位置であり、最後の点はAの最終位置です。
最初は、ロープは非常に悪いルートになります。最適化するには、エネルギー勾配に沿ってポイントを移動します。あなたの場合、エネルギー関数は非常に単純です。つまり、ロープの全長です。
これは新しいアイデアではありませんが、コンピューター ビジョンでオブジェクトの境界を検出するために使用されますが、エネルギー関数ははるかに複雑です。それでも、「ヘビ」を見て、2 つの隣接点を考慮して各点を移動する方法を理解してください: http://en.wikipedia.org/wiki/Snake_(computer_vision )
ただし、あなたの場合は、各ポイントの方向をその隣接ポイントによって加えられる力から導き出すだけで十分です。
あなたの問題は、衝突を考慮する制約付きの問題です。ここで@paddyのアイデアを実際に使用して、各オブジェクトに凸包、または単に球を使用します。後者の場合、ポイントの数が無限ではないことを考慮して、Bまでの距離がAの半径にBの半径を加えたものにファッジ ファクターを加えた値よりも小さい場所にポイントを移動しないでください。
有効なソリューションでは、任意の隣接点間の最長距離がしきい値よりも小さいことが必要です。そうでない場合、2 点間の接続線が障害物と交差します。
まずは簡単な方法から…。
これが 1 つのオブジェクトにすぎない場合は、障害物のすべての頂点と始点と終点の凸包を計算できます。次に、船体を時計回りと反時計回りに移動して、A から B に到達する 2 つの方向を調べます。最短経路を選択します。
動かしている形状は単なる点ではないため、もう少し複雑です。その中心をやみくもに移動することはできません。そうしないと衝突します。障害物の頂点に対してオブジェクトのエッジをかすめる必要があるため、頂点を通過するにつれてさらに複雑になります。
しかし、うまくいけば、熟考するためのアイデアが得られることを願っています。概念的に理解するのは難しくありません.
これを見る1つの方法は、シャドウキャスティングの問題です。「光源A」を作成してから、シーンの各ポイントが影の中にあるか影の外にあるかを判断します。影になっていないものには、からの光線でアクセスできますA。他のエリアはそうではありません。影になっていることがわかった場合Bは、シーン内で光が当たっている最も近いポイントを見つけるだけで済みます。
この問題を「ピクセル」に分解すると、上記のアプローチは、シャドウレンダリングに関する膨大なコンピュータグラフィックスの文献で非常によく知られている解決策になります。たとえば、シャドウマップを使用して、各ピクセルをシャドウ内にあるかどうかを示すブールフラグでペイントできます。最も近い点灯ピクセルを見つけることは、周りに成長する同心円を検索するだけBです。GPUハードウェアを活用することで、これらの操作を両方とも非常に高速に行うことができます。
もう1つの注意：一般的なオブジェクトパスファインディングの問題をポイントパスの問題として扱うことができます。秘訣は、ミンコフスキー差を使用して適切な量だけ障害物を「成長」させることです。たとえば、ロボットの経路計画に関するこの作業を参照してください。
この画像は、オブジェクトを点 B に到達させるためのアイデアを伝えるために作成しました。画像内のオブジェクト:- 濃い青色の点はオブジェクトを表します。赤い線が障害物です。灰色の点と線は到達可能な領域です。紫色の矢印は点 B の方向です。オブジェクトの灰色の線は視野です。画像を理解する :- オブジェクトには特定の可視領域があります。これは 2D の状況なので、視野角は 180 度と仮定しています。(可視性の人間のフィールドについては、http://en.wikipedia.org/wiki/Human_eye#Field_of_viewを参照してください) オブジェクトはSONARの考え方を利用して距離を測定します。SONAR の助けを借りて、オブジェクトは到達できる領域を見つけることができます。BACKTRACKING を使用すると、オブジェクトはオブジェクトへの道を見つけることができます。行く方法がない場合、オブジェクトは可視領域を変更する必要があります