この目的を明確にするために、プレーヤーが任意の速度を与えることができる小さなスプライトを制御する 2 次元ゲームを想像してください。重力のみが作用します。最初は、画面の下部の大部分にまたがる大きなプラットフォーム上にあり、その上に少し離れたところに別のはるかに小さなプラットフォームがあります。スプライトがまっすぐ上にジャンプすると、プラットフォームの下部を通り抜け、その上を少し移動した後、降りて上部のプラットフォームの上に着地できます。下から上へは通過できますが、上からは下ることができません。
これを行うには、画面上のオブジェクトのソリッド エッジのそれぞれを、右、左、またはその両方から通過できるベクトルとして表示します。この例では、メイン ベース プラットフォームの上部にエッジが 1 つ必要です (右隅から左隅に向けられている場合、右からは透過できません)。小さなプラットフォームの上部には別のエッジが必要で、さらにいくつかのエッジが必要です。スプライトの場合 (小さな長方形の場合は 4 つ)。ポイントが間違った方向からエッジを通過すると、衝突解決アルゴリズムに信号が送信され、ポイントがそれを行わないようにします。
それはすべて素晴らしく機能しますが、唯一の問題はあまり効率的ではないということです。従来の衝突検出メカニズムを使用すると、正方形が 1 つのオブジェクトになります。衝突をテストするためのn個の正方形のリストがある場合は、実行する必要があります。ほとんどの方法では、この数が縮小されます。つまり、 n乗の衝突テストです。ポイントエッジ法を使用すると、各正方形には約 4 つのエッジがあり、各エッジにはテスト対象の 2 つの端点があります。これは、n個の正方形に対して、約 (8 n ) 個の正方形の衝突テストを実行することを意味します。64 倍の衝突テスト。それはひどい。
では、ポイントエッジ法と同じことを達成するが、コンピューターの処理能力に過度の負担をかけない、広く使用されている、またはより受け入れられている衝突検出方法はありますか? これは実際には 2D でのみ適用されることに注意してください。3D は空間の 3 次元すべてを完全に表現することができ、拡張する必要はありません。