Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 4 sur 4

Discussion: Classes de collision

  1. #1
    Membre Expert
    Inscrit en
    août 2010
    Messages
    950
    Détails du profil
    Informations forums :
    Inscription : août 2010
    Messages : 950
    Points : 1 004
    Points
    1 004

    Par défaut Classes de collision

    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 :
    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.

  2. #2
    Membre actif Avatar de Nyarlathotep
    Étudiant
    Inscrit en
    juin 2005
    Messages
    174
    Détails du profil
    Informations personnelles :
    Âge : 23

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juin 2005
    Messages : 174
    Points : 185
    Points
    185

    Par défaut

    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.
    "That is not dead which can eternal lie
    And with strange aeons even death may die"

    The Call of Cthulhu

  3. #3
    Membre Expert
    Inscrit en
    août 2010
    Messages
    950
    Détails du profil
    Informations forums :
    Inscription : août 2010
    Messages : 950
    Points : 1 004
    Points
    1 004

    Par défaut

    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

  4. #4
    Membre actif Avatar de Nyarlathotep
    Étudiant
    Inscrit en
    juin 2005
    Messages
    174
    Détails du profil
    Informations personnelles :
    Âge : 23

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juin 2005
    Messages : 174
    Points : 185
    Points
    185

    Par défaut

    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).
    "That is not dead which can eternal lie
    And with strange aeons even death may die"

    The Call of Cthulhu

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •