ソート、スイープ、枝刈り: Collision Detection Algorithms (2023)

 (leanrada.com)
3 ポイント 投稿者 GN⁺ 2024-08-15 | 1件のコメント | WhatsAppで共有

衝突検出アルゴリズム

衝突検出

  • ビデオゲームプログラミングでは、衝突検出は非常によくある問題
  • キャラクター同士がすり抜けないようにしたり、物理エンジンを実装したりするうえで不可欠

単純なアプローチ 🐥

  • すべてのオブジェクトの組を調べて、衝突しているかどうかを確認する方法
  • コード例: 
    for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}
  • この方法の時間計算量は O(n^2)

パフォーマンスの問題

  • オブジェクト数が増えるほどパフォーマンス上の問題が発生する
  • たとえば n = 20 のとき、190 組を検査する必要がある

解決策の改善

  • 不要な処理を減らすことが重要
  • intersects() 関数の最適化: 
    function intersects(object1, object2) {
  return object1.left < object2.right &&
         object1.right > object2.left &&
         object1.top < object2.bottom &&
         object1.bottom > object2.top;
}

ソートによる最適化

  • オブジェクトを x 座標に従ってソートすると、不要な検査を減らせる
  • コード例: 
    sortByLeft(balls);
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];
    if (ball2.left > ball1.right) break;
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}

パフォーマンス分析

  • ソート: O(n log n)
  • 内側のループ: 平均して O(n + m)（m は x 軸上で重なっている総数）
  • 最終的な時間計算量: O(n log n + m)

視覚的な比較

  • 全ペア検査と、ソート済みペア検査の比較
  • ソート済みペア検査のほうが、はるかに少ない検査で済む

GN⁺のまとめ

  • この記事は、ゲーム開発における衝突検出アルゴリズムを最適化する方法を扱っている
  • 単純な O(n^2) アルゴリズムから始めて、ソートによって性能を大きく向上させる
  • ゲーム開発者やソフトウェアエンジニアにとって非常に有用な情報
  • 類似機能を持つ他のプロジェクトとしては、Box2D、Bullet Physics などがある

関連記事

1件のコメント

 
GN⁺ 2024-08-15
Hacker Newsのコメント

  • 著者は最適なパフォーマンスのために、mergesort や quicksort のような「高速」なソートアルゴリズムを使うことを提案している

    • しかし実際には、insertion sort のような「劣る」ソートアルゴリズムのほうがより良い性能を示すことがある
    • 衝突検知システムのオブジェクトはフレーム間で比較的小さなステップで移動するため、前のフレームのほぼ整列済みのリストを維持できる
    • このようなほぼ整列済みのリストを並べ替える場合、insertion sort は O(n) に近く、Quicksort は O(n^2) に近い

  • 過去に似たような作業をしたことがあるが、ソートの代わりに各方向ごとのインデックスリストを維持していた

    • たとえば、objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge のような 4 つのリストがある
    • オブジェクトが水平方向に移動すると、leftEdge と rightEdge 配列内で自分のインデックスを更新する
    • 移動時には最大でも 1〜2 個のインデックスを入れ替えるだけで済む

  • この記事は本当によく整理されている

    • 90年代後半からゲーム開発をしてきたが、ほとんどの作業はエンジンによって抽象化されている
    • 複雑なシステムシミュレーションを理解するうえで不可欠だ
    • 著者が非常に取っつきやすい記事を書いてくれたことに感謝している

  • 連続衝突検知に関する文書はいつも楽しく読んでいる

  • イラストの使い方が良かった

    • ときどきこうした記事は、見栄えの良いデモを集めるための口実のように感じられることがあるが、今回の記事はイラストが主役になりすぎていない

  • Part 2: https://leanrada.com/notes/sweep-and-prune-2/

  • 「この単純なアルゴリズムは Big O の用語では O(n^2) 時間で実行される」という主張に疑問を呈している

    • 外側のループ (i) は n - 1 まで数え、内側のループ (j) は i + 1 から始まって徐々に少ない回数だけ数える
    • CS 専攻ではないが、大きな n の値に対して O(n^2) と大まかに同じなのか、それとももっと少ないのか気になっている

  • この方法が、潜在的な衝突候補を減らすためにクワッドツリーを使うのと似ているのか気になった

  • 線形計画法が提案されたことがあるのか気になった

  • このウェブサイトには良い意味で気を取られた

    • 面白くて刺激を受ける