De quelle manière présenteriez-vous un algorithme pour détecter les collisions entre différents objets?

Question

En travaillant sur un projet vraiment seulement pour le plaisir j'ai rencontré un problème.

Il existe un monde en 2D peuplé de balles rondes, de triangles pointus et de lignes fines (et d'autres animaux sauvages, peut-être). Ils sont tous des sous-classes de WorldCreatures. Ils peuvent se déplacer dans ce monde. Quand ils se rencontrent, une collision se produit.

La chose que je voudrais faire est de trouver un moyen de détecter la collision entre eux. Voici ce que je suis debout en ce moment:

• Pour moi Ball-Ball est facile, je calcule juste leur distance de leurs positions et le compare à la somme de leurs «tailles».
• La collision entre la balle et le bord du monde est aussi simple - je vérifie simplement la distance qui le sépare, ce qui, en coordonnées cartésiennes, est simple.
• Plus de problèmes génériques sont - comment détecter une collision entre la ligne (début et fin à certains points) ou d'autres objets que je pourrais avoir là? Distance entre une ligne et un point peut être calculé facilement aussi, mais ce que je voudrais est d'avoir

Une sorte de manière générique pour dire si l'objet A entre en collision avec l'objet B. Le code tel qu'il est semble maintenant un peu comme:

class WorldCreature: 
    def detectCollision(self, otherObject): 
     # do something 
     if collision: 
      self.onCollision(otherObject) 
      otherObject.onCollision(self) 
class Ball(WorldCreature): 
    # someing here 
class Line(WorldCreature): 
    # someing here 

Maintenant, la détection de collision mechanizm devrait dépendre de ce que les objets peuvent entrer en collision. Donc, l'effet sera.

Devrais-je simplement garder une liste de tous les objets en mémoire et les parcourir tous en à chaque étape? Ou, y a-t-il une meilleure façon d'améliorer les performances de cette tâche?

Answer 1

Utilisez un quadtree. Ils sont utilisés pour éliminer les grandes régions que vous connaissez en dehors d'un rayon de collision, et ils vous permettent de rechercher rapidement le point le plus proche.

En ce qui concerne la détection de collisions, puisque vous n'utilisez que des objets convexes, jetez un oeil à Metanet Software's tutorial sur the separating axis theorem. Dans leur jeu phare, ils utilisent en fait une grille pour trouver tous les objets à vérifier, mais il ne devrait pas être trop difficile d'utiliser un quadtree à la place.

(Je me souviens avoir lu un article sur quadtrees qui ont utilisé des cercles dans une grille pour illustrer la façon dont vous pouvez trouver les points dans un rayon. Je ne peux pas sembler trouver cependant.)

Answer 2

La réponse dépend sur un certain nombre de facteurs, tels que le nombre d'objets, le nombre de mouvements par rapport au déplacement, la vitesse à laquelle ils bougent, etc. Je pense que le bon endroit pour commencer est d'obtenir la détection de collision et le code de comportement corrects en ignorant les optimisations que vous pouvez effectuer pour élaguer les vérifications de collision, etc.

Une fois que le code de base est correct, vous pouvez commencer à exécuter des tests pour voir ce qui fonctionnera bien pour vous. Je recommanderais une sorte de technique de subdivision spatiale, comme kd-trees (bien que dans 2d, vous pouvez aussi utiliser quadtrees). Fondamentalement, cependant, il n'y a probablement pas de bonne réponse, sauf ce que vous pouvez déterminer en codant votre jeu et en l'expérimentant.

Answer 3

Je pense que Hough Transform devrait aider d'une manière ou d'une autre.

Answer 4

Python. Kinda étrange bête pour moi 8)

J'ai une expérience C++ en créant des jeux - donc je parle de ce point de vue. Tout d'abord (vous pouvez ignorer cela si vous avez peu d'objets) vous avez besoin d'une détection de collision à grande échelle. Quadtree déjà mentionné est juste une implémentation possible. Une phase large est nécessaire pour trouver des paires d'objets pouvant entrer en collision.

Ensuite, passe la phase étroite - lorsque les paires sont vérifiées.

J'ai utilisé le schéma suivant (note - ceci a été créé avec des primitives à l'esprit, si vous avez besoin de collisions polyèdres - il suffit d'utiliser GJK et sphères, plus les rayons, segments):

Tout ce qui a besoin de collisions ont CollisionObject qui gère les transformer et stocker CollisionPrimitive (boîte, sphère, etc.)

chaque CollisionPrimitive a type_id - lorsque vous écrivez A_B_CheckIntersection - le premier objet ont toujours inférieur type_id

Pour chaque paire dans la liste que vous obtenez de large phase - vous permutez des objets si nécessaire et indexez un arra y où des pointeurs vers des fonctions de collision spécifiques sont stockés. Bien sûr - pour que vous devriez avoir les ont des interfaces identiques (C++), mais il est facile 8)

En ce qui concerne les routines de collision spécifiques: visite http://realtimerendering.com/intersections.html Il est bon endroit pour commencer