Gestion efficace de collision

Version imprimable

12/10/2011, 12h36
Glycol

Gestion efficace de collision

Bonjours à tous ;),
Je suis à la recherche de bonne idée pour résoudre un problème algorithmique qui me sèche depuis une dizaines de jours...

Alors je pose le contexte:
- J'ai un plan quasi-infini (quasi = limité par la taille d'un flottant 64bit),
- J'ai une grande quantité d'objet mouvant sur ce plan (entre 10k et 100k), ils ne sont pas repartie aléatoirement et ont tendance à se regrouper.
- J'ai un process pour représenter un objet (le process gére cet objet, le déplace, ...)(ce ne sont pas des proccess système, ils sont extrement léger, des process Erlang pour les intimes :D),
- J'ai pour chaque process la possibilité de communiquer avec un autre de manière asynchrone (par envoie de message).

Maintenant le problème:
Comment gérer de manière efficace une gestion des collisions entre les différents objets (et ceux de manière de maniere fluide) ? :mrgreen:

Donc je galère, non pas que je ne sache pas faire, mais d'habitude je travail dans un environnement clos avec beaucoup moin d'objet. J'ai deja envisager plusieurs solutions mais sont pas top top...

La première c'est une approche naive, mon objet envoie un message aux autres avec sa position et sa géométrie, et les autres lui reponde si il y a collision. Problème: Ca marche trés bien avec peu d'objet, mais le temps de propagation est trop long pour une grande quantité d'objet (sans parler des ressources machines necessaire).
La seconde c'est d'utiliser ca mais après un partionnement spatial avec un Quadtree ou un R-tree, le problème c'est que je ne sais pas comment partionner un environnement infinie, et surtout comment le mettre à jours en temps reel...

J'espère avoir été clair et surtout j'espere que l'un de vous va pouvoir m'aider...

Merci :P
13/10/2011, 16h39
Graffito

Première éventuelle optimisation : pour chaque objet définir son centre et les rayon externes et internes (rayon de la sphère la plus petite contenant l'objet et de la sphère la plus grande contenue dans l'objet). Si il y a pas de collision entre les sphères externes, pas de traitement. Si il y a collision des sphères internes, on est sur de devoir traiter une collision, Sinon, il faut déterminer précisément si il y a collision en fonction de la géométrie des 2 objets.

Comment traites-tu globalement les déplacements ?
- Est-ce un recalcul à intervalles réguliers des vitesses, positions géométires orientation ?
- Est-ce seulement recalculé à des instants obtenus via un calcul prédictif (exemple 2 trains circulants vitesse constante sur la même voie vont entrer en collision à 12:48) ?
- Les vitesses de déplacement d'un objet sont-elles significativement bornées? Connaissant la position P d'un objet à un instant, cela permettrait de déterminer la valeur max de PP' (même en cas de collision), P' étant la position à l'instant t'.

Comment doits-tu gérer les collisions multiples (3 objets se trouvant au même point , au meme moment) ?
13/10/2011, 16h58
Mat.M

Citation:

Envoyé par Graffito

Première éventuelle optimisation : pour chaque objet définir son centre et les rayon externes et internes (rayon de la sphère la plus petite contenant l'objet et de la sphère la plus grande contenue dans l'objet). Si il y a pas de collision entre les sphères externes, pas de traitement. Si il y a collision des sphères internes, on est sur de devoir traiter une collision, Sinon, il faut déterminer précisément si il y a collision en fonction de la géométrie des 2 objets.

oui mais lorsqu'on veut déterminer s'il y a des collisions entre une entité et une liste d'autres entités on est obligé de faire une boucle ce qui prend du temps comme l'indique Glycol

Une première astuce simple c'est de calculer d'abord la distance entre les centres de chaque entité; si la distance est inférieure à un certain seuil, une certaine valeur alors on calcule plus en détail s'il y a collision réelle, ça permet d'économiser des calculs.
C'est comme cela que j'ai procédé dans le jeu que j'ai développé :mouarf:

Citation:

Envoyé par Glycol

La seconde c'est d'utiliser ca mais après un partionnement spatial avec un Quadtree ou un R-tree, le problème c'est que je ne sais pas comment partionner un environnement infinie,

oui c'est comme cela qu'on procéde dans l'IA des jeux vidéos
13/10/2011, 19h49
Glycol

Citation:

Première éventuelle optimisation : pour chaque objet définir son centre et les rayon externes et internes (rayon de la sphère la plus petite contenant l'objet et de la sphère la plus grande contenue dans l'objet). Si il y a pas de collision entre les sphères externes, pas de traitement. Si il y a collision des sphères internes, on est sur de devoir traiter une collision, Sinon, il faut déterminer précisément si il y a collision en fonction de la géométrie des 2 objets

Pour le moment je n'utilise que des cercles englobant (je travail en 2D) pour approximer mes collisions. Rajouter un test avec un cercle interne est une bonne idée, surtout que ça ne coute pas bien cher en calcul ^^.

Citation:

Comment traites-tu globalement les déplacements ?
- Est-ce un recalcul à intervalles réguliers des vitesses, positions géométires orientation ?
- Est-ce seulement recalculé à des instants obtenus via un calcul prédictif (exemple 2 trains circulants vitesse constante sur la même voie vont entrer en collision à 12:48) ?
- Les vitesses de déplacement d'un objet sont-elles significativement bornées? Connaissant la position P d'un objet à un instant, cela permettrait de déterminer la valeur max de PP' (même en cas de collision), P' étant la position à l'instant t'.

Mes positions sont calculées plusieurs fois par seconde, mais tous les objets ne sont pas mis à jours simultanément (car chaque objet est géré par un thread). Je ne peux pas prédire mes futures positions (en tous cas je ne sais pas faire :) ). Par contre mes vitesses sont bornées mais variables.

Citation:

oui mais lorsqu'on veut déterminer s'il y a des collisions entre une entité et une liste d'autres entités on est obligé de faire une boucle ce qui prend du temps

C'est bien la tout le problème... Pour le moment je m'oriente vers un pavage statique de l'espace. Et les collisions sont calculées entre les objets dans chaque case...

Citation:

Citation:

La seconde c'est d'utiliser ca mais après un partionnement spatial avec un Quadtree ou un R-tree, le problème c'est que je ne sais pas comment partionner un environnement infinie,

oui c'est comme cela qu'on procéde dans l'IA des jeux vidéos

Ils travaillent en espace finie ou infini ? Parce que en faite je le sens pas trop de tenter de découper un flottant 64bit en petit carré, j'ai peur d'exploser en mémoire surtout que si mes souvenirs sont bons, une fois le quadtree construit il ne me reste que 1 objet par feuille ? Donc si j'ai 100k objets j'ai besoin d'un arbre de 100k + (100k - 1) nœuds ? non ?
14/10/2011, 01h54
Mat.M

Salut Glycol dans les jeux vidéos c'est plutôt dans des espaces finis donc ta problèmatique n'est pas simple :D
14/10/2011, 11h07
Graffito
Citation:

donc ta problèmatique n'est pas simple

+1,

J'aurais tendance à utiliser les Quad-tree gérant des portions d'espace fini et à ajouter une couche dynamique encapsulant ces portions d'espace.

Exemple :
Code:

1 2 3 4 5 6 7 8 +-+ +-+ |Q| |Q| +-+ +-+-+ |Q|Q| +-+-+-+ +-+ |Q| |Q| +-+ +-+
14/10/2011, 16h56
Glycol
Citation:
Envoyé par Graffito

+1,

J'aurais tendance à utiliser les Quad-tree gérant des portions d'espace fini et à ajouter une couche dynamique encapsulant ces portions d'espace.

Exemple :

Code:

1 2 3 4 5 6 7 8 +-+ +-+ |Q| |Q| +-+ +-+-+ |Q|Q| +-+-+-+ +-+ |Q| |Q| +-+ +-+
Merci, c'est en cours d'implémentation :mrgreen:
14/10/2011, 22h51
pseudocode

Citation:

Envoyé par Graffito

J'aurais tendance à utiliser les Quad-tree gérant des portions d'espace fini et à ajouter une couche dynamique encapsulant ces portions d'espace.

+1. C'est le principe des "Bounding Volume Hierarchies".

Une autre méthode, c'est de faire du "spatial hashing". C'est très efficace quand on a peu d'objet par rapport a l'espace, ca a l'air d'être ton cas (100k objets vs (2^64)^2 cases :P).
15/10/2011, 11h50
edfed

effectivement, la pixelisation de l'espace permet de representer notre plan quasi infini avec une succession de bitmaps.

premier bitmap, 256*256 points( c'est deja enorme je trouve), chaque point represente l'occupation d'un carré de taille float64/256.

le principe serait d'ecrire le bitmap avec les objets.
une seule passe sur tout les objets permettant de savoir s'ils vont se poser sur une case déjà occupée.
si la case est occupée au moment de poser l'objet, il faudra alors passer au bitmap de deuxieme niveau, qui est un carré de 256 points de cotés, mesurant float64/256.

en construisant une suite de bitmaps, ça permet de hierarchiser les espaces.

avec des entiers 32 bits par exemple et des bitmaps de 256*256, il sera possible d'avoir une detection de collisions sur 4 niveaux, un niveau par tranche de 8 bits.
avec des float64, ça sera plus grand.

serait-ce une bonne manière pour implementer la detection de collisions?

sachant qu'une comparaison de 2 coordonnées mange plus de ressources temps que le test d'un point. mais que l'occupation memoire des bitmaps serait non negligeable en cas de reparatition très homogène des points. pouvant demander un enormement de bitmaps à chaque niveau de hierarchie.
avec 65536 repartis dans exactement 65536 cases differentes, on aurait besoin d'un bitmap principal de 256*256, mais lorsqu'on ajouterais 65536 objets, eux aussi repartis sur la grille de manière homogène, il faudrait generer autant de de bitmaps qu'il y a partage du meme point sur le bitmap, soit jusqu'à 65536^2 bitmaps de 256^2 points. ça fait beaucoup.

peut etre que le bitmap peut faire un degrossissage de premier niveau, et passer en listes de bounding box sur les niveaux en dessous.
18/10/2011, 11h15
Glycol

Je vous remerci pour toutes ces reponses :ccool:

Alors pour le moment j'ai un "manager" qui joue le role d'un HUB dans un carré de taille fixe. Les "managers" sont des thread qui s'occupe de faire tourner les messages. Je les lance dynamiquement si j'ai la présence d'un objet dans un carré. J'ai un super manager qui permet de créer les autres managers.
Les objets communiquent avec ce super manager pour savoir a quel manager se rattacher...

Pour le moment pas de spacial hashing mais je pense utiliser cette technique plus tard pour optimiser les echanges de messages. J'ai deux trois autres optimisation en tete mais que je n'ai pas le temps d'implémenter pour le moment... Je vais attendre les testes pour voir ce que ca donne :?