Tri, balayage et élagage : algorithmes de détection de collision (2023)

Algorithmes de détection de collision

Détection de collision

• En programmation de jeux vidéo, la détection de collision est un problème très courant
• Elle est indispensable pour empêcher les personnages de se traverser ou pour implémenter un moteur physique

Approche simple 🐥

• Une méthode consiste à vérifier toutes les paires d’objets pour savoir s’il y a collision
• Exemple de code :

  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);
      }
    }
  }
  

• Cette méthode a une complexité temporelle en O(n^2)

Problèmes de performance

• Plus le nombre d’objets augmente, plus des problèmes de performance apparaissent
• Par exemple, quand n = 20, il faut vérifier 190 paires

Amélioration de la solution

• Réduire le travail inutile est essentiel
• Optimisation de la fonction intersects() :

  function intersects(object1, object2) {
    return object1.left < object2.right &&
           object1.right > object2.left &&
           object1.top < object2.bottom &&
           object1.bottom > object2.top;
  }
  

Optimisation par tri

• Trier les objets selon leur coordonnée x permet de réduire les vérifications inutiles
• Exemple de code :

  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);
      }
    }
  }
  

Analyse des performances

• Tri : O(n log n)
• Boucle interne : en moyenne O(n + m) (m est le nombre total de chevauchements sur l’axe x)
• Complexité temporelle finale : O(n log n + m)

Comparaison visuelle

• Comparaison entre la vérification globale des paires et la vérification des paires après tri
• La vérification des paires après tri effectue beaucoup moins de contrôles

Résumé de GN⁺

• Cet article explique comment optimiser les algorithmes de détection de collision dans le développement de jeux
• Il part d’un algorithme simple en O(n^2) puis améliore fortement les performances grâce au tri
• C’est une information très utile pour les développeurs de jeux ou les ingénieurs logiciel
• D’autres projets offrant des fonctionnalités similaires incluent Box2D et Bullet Physics

[GN⁺]

Commentaires sur Hacker News

• L’auteur suggère d’utiliser des algorithmes de tri « rapides » comme mergesort ou quicksort pour obtenir des performances optimales

  • Cependant, en pratique, des algorithmes de tri « moins bons » comme insertion sort peuvent offrir de meilleures performances
  • Les objets d’un système de détection de collision se déplacent par pas relativement faibles d’une frame à l’autre, ce qui permet de conserver la liste presque triée de la frame précédente
  • Lorsqu’on trie une telle liste presque triée, insertion sort est proche de O(n) tandis que Quicksort se rapproche de O(n^2)

• J’ai déjà fait un travail similaire par le passé, mais en conservant des listes d’indices pour chaque direction au lieu d’utiliser un tri

  • Par exemple, il y a 4 listes comme objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge
  • Lorsqu’un objet se déplace horizontalement, il met à jour son indice dans les tableaux leftEdge et rightEdge
  • Pendant le déplacement, il suffit au maximum d’échanger 1 ou 2 indices

• Cet article est vraiment très bien structuré

  • Je fais du développement de jeux depuis la fin des années 90, mais la plupart de ces aspects ont été abstraits par les moteurs
  • C’est essentiel pour comprendre les simulations de systèmes complexes
  • Merci à l’auteur d’avoir écrit un texte aussi accessible

• J’ai toujours aimé lire la documentation sur la détection continue de collision

  • https://github.com/bepu/bepuphysics2/blob/master/Documentation/ContinuousCollisionDetection.md
  • La bibliothèque elle-même est impressionnante du point de vue des performances
  • En revanche, elle est tellement optimisée qu’elle est un peu difficile à intégrer

• L’usage des illustrations était appréciable

  • Parfois, ce genre d’articles donne l’impression d’être un prétexte pour rassembler de jolies démos, mais ici les illustrations ne prennent pas le dessus

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

  • Je recommande aussi de consulter ses autres articles : https://leanrada.com/

• Je m’interroge sur l’affirmation selon laquelle « cet algorithme simple s’exécute en temps O(n^2) en termes de Big O »

  • La boucle externe (i) compte jusqu’à n - 1, et la boucle interne (j) commence à i + 1 en comptant de moins en moins d’éléments
  • Je n’ai pas fait d’études d’informatique, mais je me demande si, pour de grandes valeurs de n, c’est approximativement équivalent à O(n^2) ou si c’est inférieur

• Je me demandais si cette méthode est similaire à l’utilisation d’un quadtree pour réduire les collisions potentielles

• Je me demandais si une méthode de programmation linéaire avait déjà été proposée

  • https://users.encs.concordia.ca/~akgunduz/CollisionDetection.pdf

• Ce site m’a distrait, mais dans le bon sens du terme

  • C’est amusant et inspirant