Discussion :

[shaiHulud]

Bonjour,

J'ai un ensemble de rectangles (all_rects) que je cherche à partitionner de la manière suivante:
- deux rectangles qui s'intersectent doivent appartenir à la même classe
- 2 rect. de 2 classes distinctes ne doivent pas s'intersecter.

Le but de cette partition est, plutôt que de dessiner tous mes sprites d'un coup, de pouvoir redessiner uniquement des groupes de sprites qui s'intersectent (et qui doivent donc être dessinés ensemble, de manière 'atomique').

Commencons par une version simple: calculer la classe d'un rectangle (un_rect) donné. J'imagine le pseudo code suivant (en python/pygame):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
classe = []
new_elems= [un_rect]
while new_elems:
    all_rects.remove(new_elems) # epure la liste des candidats
    intersecting= [s for s in all_rects if s.collideany(new_elems) ]
    classe.extend(new_elems)
    new_elems= intersecting # epure la classe des éléments déja vérifiés

La complexité (O(N^3) au pire) de ce code me laisse perplexe, d'autant plus qu'il faudrait y rajouter des infos sur quels sprites ont été dessinés (car entre deux appels à paint(), les classes ont pu évoluer).

Existe-t'il un algo rapide pour faire cela ?

Je pense aux pistes suivantes:
- Une classification descendante (plutot qu'ascendante dans le pseudo code précédent)
- Mettre à jour à chaque update de rectangle la liste des rect intersectant, plutot que le calcul collideany() à chaque fois que je calcule une classe.

Merci d'avance pour vos idées / commentaires.

[Nyarlathotep]

J'ai un ensemble de rectangles (all_rects) que je cherche à partitionner de la manière suivante:
- deux rectangles qui s'intersectent doivent appartenir à la même classe
- 2 rect. de 2 classes distinctes ne doivent pas s'intersecter.

Si j'ai bien compris, tu veux isoler des sortes "d’ilots" de collision : des groupes de rectangles en collision.

Tout d'abord, mon approche serait de construire une fois pour toutes les paires d'objets en collision. Une méthode efficace est le Sort And Sweep (aussi connu sous le nom de Sweep And Prune, http://www.codercorner.com/SAP.pdf). La complexité de cet algorithme est de l'ordre de O(n) dans le meilleurs des cas (avec cohérence temporelle, c'est à dire si les rectangles ne bougent pas trop).

Une fois ces paires déterminées, un algorithme très basique en O(n^2) suffit à déterminer les ilots de collision.

[shaiHulud]

Merci Nyarlathotep,

Si j'ai bien compris, tu veux isoler des sortes "d’ilots" de collision : des groupes de rectangles en collision.

C'est ca, mais il faut que deux ilots distincts n'aient aucune intersections

La complexité de cet algorithme est de l'ordre de O(n)

Pour trouver toutes les paires en collision parmi n objets ?

si les rectangles ne bougent pas trop

Mon probleme porte sur 'un jeu vidéo en temps continu. La majorité de mes rectangles ne bougent pas, mais certains (creature,joueurs...) bougent plutot rapidement.

je vais essayer d'implémenter le SAP, mais j'ai quand même l'impression que le temps de calcul risque de rendre le résultat (une fontion draw() plus atomique) mitigé.

Merci

[Nyarlathotep]

La complexité de cet algorithme est de l'ordre de O(n)

Pour trouver toutes les paires en collision parmi n objets ?

En fait, elle est en O(n+k) où k est est le nombre d'échanges lors du tri sur l'axe et ce n'est valable que dans le cas unidimensionnel. Mais en pratique, les résultats sont très bons, aussi biens voir meilleurs que l'utilisation d'un quadtree.

J'ai une autre référence pour le Sweep And Prune : http://graphics.cs.cmu.edu/courses/1.../14/notesg.pdf (Voir la section 7.2.1).

Si tu t’intéresses au quadtrees, il suffit de taper dans google "quadtrees" pour tomber sur des articles interessants.

Évidemment, tout cela ne te donnera que les paires d'objets en collision, pas les ilots. Il faut implémenter un algorithme qui répond à la question "quelles sont les paires qui contiennent cet objet".

Après avoir réfléchi à la question, j'ai trouvé une idée : il s'agit de modifier les paires d'indices d'objets (a, b) de telle sorte que a < b, et de construire un arbre binaire avec l'ordre partiel sur le premier éléments avec celles-ci. Un algorithme de parcours de l'arbre en O(ln (p)) donne alors les paires qui contiennent un objet donné (p désigne le nombre de paires).