Je travaille sur un moteur physique purement continu , et je dois choisir des algorithmes pour la détection de collision de phase large et étroite. "Purement continu" signifie que je ne fais jamais de tests d'intersection, mais que je veux plutôt trouver des moyens d'attraper chaque collision avant qu'elle ne se produise, et de les placer dans une pile de "collisions planifiées" commandée par TOI.

Phase large La seule méthode continue à phase large à laquelle je peux penser consiste à enfermer chaque corps dans un cercle et à tester si chaque cercle se chevauchera jamais. Cependant, cela semble horriblement inefficace et ne fait l'objet d'aucune élimination.

Je n'ai aucune idée des analogies continues qui pourraient exister pour les méthodes d'élimination des collisions discrètes d'aujourd'hui telles que les quadruples. Comment pourrais-je éviter les tests larges inappropriés et inutiles comme le fait un moteur discret? J'aimerais également pouvoir voir les collisions à plus d'une image.

Phase étroite
J'ai réussi à adapter le SAT étroit à une vérification continue plutôt que discrète, mais je suis sûr qu'il existe d'autres meilleurs algorithmes dans les documents ou les sites que vous avez pu rencontrer.
Quels différents algorithmes rapides ou précis proposez-vous que j'utilise et quels sont les avantages / inconvénients de chacun?

Note finale:
je dis des techniques et non algorithmes car je n'ai pas encore décidé comment je vais stocker différents polygones qui pourraient être concaves, convexes, ronds ou même avoir des trous. Je prévois de prendre une décision à ce sujet en fonction de ce que l'algorithme nécessite (par exemple, si je choisis un algorithme qui décompose un polygone en triangles ou en formes convexes, je vais simplement stocker les données du polygone sous cette forme).

Je lance vraiment des idées ici. En supposant que vous ayez (au moins) la currentposition etnext position; pour chaque image.

Vous auriez besoin de deux grandes phases distinctes, suivies de votre phase étroite:

• Celui qui comprend qu'une collision va se produire.
• Celui qui indique approximativement où la collision se produit réellement (par exemple, une phase large / SAT imprécis)
• Enfin, votre phase étroite améliorerait le résultat de la deuxième phase large.

Phase large initiale

Vous pouvez examiner le hachage spatial (en utilisant la nextposition, non current) pour la phase large initiale. Cela partitionnerait bien votre espace de problème en groupes de candidats à la collision.

Deuxième grande phase

Faites un multi-échantillon binaire en utilisant la méthode d'intersection de cercle que vous avez décrite. En d'autres termes:

left = current
right = next
midpoint = (left + right) / 2
loop a desired amount of times tweaked to the accuracy you want:
  is a collision occuring at midpoint?
    right = midpoint
  else?
    left = midpoint
  midpoint = (left + right) / 2
pointOfCollision = midpoint

Ce réglage de précision pourrait également prendre en compte la distance - je pense que l' utilisation de la `` longueur au carré '' next - currentdonnerait un résultat parfait en pixels.

Phase étroite

Faites un multi-échantillon binaire en utilisant quelque chose comme PMask - la logique sera exactement la même que ci-dessus; en utilisant simplement une routine de collision différente.

finalement

Vous serez en mesure de déterminer le moment de l'intersection de pointOfCollision, currentet votre courant speedet acceleration(en supposant que vous avez un intégrateur raisonnable).

D'accord, j'ai vu que vous avez mis à jour votre question afin d'être plus précis. Je vais essayer de vous aider un peu plus.

Pour votre première vérification en phase large, je recommanderais fortement le hachage spatial .

Essentiellement, vous divisez votre écran en grilles de taille égale. Ensuite, si un objet se trouve dans une grille, vous l'ajoutez à un "compartiment" dans une table de hachage 1D.

C'est votre premier contrôle effectué. Si les objets ne sont pas dans le même seau, il leur serait impossible de se croiser.

Pour continuer, vous avez maintenant une liste de compartiments contenant (potentiellement) des objets. Vous pouvez effectuer une autre vérification à large phase ici:

A.) Diviser ce compartiment en 4 autres compartiments et vérifier la table de hachage 1D résultante. S'ils ne sont pas dans le même seau, pas de collision.

Ou:

B.) Faire un simple contrôle de distance et garder à l'esprit la largeur et / ou la hauteur de l'objet pour garantir la précision.

Mais qu'en est-il lorsque vous avez potentiellement une collision?

Ensuite, je recommanderais quelque chose dans le sens de cela . C'est essentiellement une sorte de mélange entre collision polygonale (pour les formes complexes) ou rectangle / cercle pour les formes moins complexes.

De plus, si vous voulez vraiment "attraper les collisions avant qu'elles ne se produisent et les stocker", vous pouvez toujours faire quelque chose comme ceci:

Si deux objets se trouvent dans le même compartiment, ils peuvent entrer en collision.

De plus, les objets sont-ils suffisamment proches pour qu'ils puissent entrer en collision bientôt? (En tenant compte de la vitesse, de la taille de l'objet et de la distance)

Si la réponse aux deux est oui, alors allez-y et stockez-la pour faire un test d'intersection plus tard.

" Ancienne réponse

Eh bien, malheureusement, j'ai perdu la trace de mon manuel "Tous les types de collision et à quoi ils servent". :)

Cependant, même s'il s'agit d'un queston extrêmement large, je vais commencer.

Il y a une bonne (réponse) question concernant quelque chose comme ça ici .

Ainsi qu'un article par les gens qui ont fait N et N + ici .

Sans oublier, vous avez la bonne vieille collision par pixel de secours .

Je doute sincèrement que quiconque disposera d'une liste à portée de main pour chaque type de collision, mais cela devrait vous aider à démarrer.

Cependant, je dois mentionner que le type de collision dont vous avez besoin (et que vous finirez par utiliser) dépend en grande partie du type de jeu que vous créez. C'est pourquoi vous trouvez des tutoriels - la plupart des gens supposent que vous avez une idée de ce que vous voulez, ils vous aident donc dans ce domaine spécifique. Je me rends compte que la plupart de mes liens sont des tutoriels sur un sujet spécifique, mais je pense qu'un tutoriel vous aidera honnêtement plus. Une liste est une chose, mais si vous lisez vous-même chaque puce, vous pouvez prendre une décision plus instruite qui répondra probablement à vos besoins plus spécifiquement.