Fichier de rejeu Close

Indication Close

A propos de... Close

Commentaire Close

Téléchargements

Crédits

© Your Copyright

Aide

Détection et gestion des collisions

Objectif :

L’objectif de ce cours est de vous permettre de concevoir un algorithme de gestion des collisions entre les objets que vous animerez dans votre jeu. Trois stratégie vous sont proposées. Vous devez être capable de les intégrer dans un projet au besoin.

Principe

L’objectif précédent vous a appris à déplacer des objets dans un espace en 2 dimensions au moyen d’intégration de lois plus ou moins physiques avec la méthode d’Euler. Maintenant, il s’agit de stopper la trajectoire de ces objets lorsqu’ils rencontrent un obstacle... voire même de pouvoir rebondir sur ces obstacles. Pour cela il faut détecter et gérer les collisions.

Définition :

Détection des collisions

La détection des collisions est un mécanisme permettant de repérer des déplacements interdits ou nécessitant un traitement particulier, au cours de la simulation d’objets en mouvement.

Quand mettre en œuvre la gestion des collisions?
  • ”...la balle rebondit sur les murs...”
  • ”...le joueur se déplace dans un labyrinthe. Il doit éviter les monstres qui s’y promènent...”
La détection des collisions intervient dans la partie “simulation” de la boucle de simulation:
  • Avant le déplacement: pour interdire un déplacement qui provoquerait une collision.
  • Après: pour détecter puis gérer les objets en collisions pour laisser le système dans un état valide.

On peut effectuer la détection et le traitement des collisions à chaque petit déplacement des éléments à déplacer ou une seule fois par pas de simulation.

Pour réaliser la détection de collisions, il faut concevoir une ou plusieurs fonctions de détections de collisions. Un algorithme de détection des collisions s’appuie sur des données qui décrivent les éléments pouvant entrer en collision. Il faut donc représenter (ou modéliser) les “obstacles” et les objets en mouvement.

Trois méthodes de représentation des obstacles vous sont proposées dans ce cours:
  1. Mise en équations de l’environnement
  2. Collection d’éléments mis en équations
  3. Utilisation d’une grille
Le problème de la gestion des collisions est une affaire de compromis et d’optimisation. Il n’y a pas de solution universelle mais une solution adaptée à chaque cas particulier. Vous devrez probablement vous inspirer des méthodes proposées pour inventer la votre en évitant les écueils récurrents de la gestion des collisions:
  • La complexité algorithmique : les calculs peuvent devenir extrêmement complexe quand plusieurs éléments entre en collision. Typiquement, les calculs de physique à mettre en œuvre pour réaliser un jeu de billard sont très complexes dans le cas ou plusieurs billes sont en contact lors d’un choc.
  • Le manque de robustesse : Un système de détection des collision trop “perméable” peut provoquer les états incohérent du jeu et donc des risque de plantage.
  • Le manque de réalisme : Si il y a une incohérence entre les positions et formes affichées et les calculs menés; ou si la gestion des collision n’a aucun sens physique.
  • Le compromis entre le temps de calcul et la précision : parfois il faut accepter de perdre en précision ou en réalisme pour permettre une fréquence de simulation adaptée à la réactivité souhaitée pour le jeu.

Soyez astucieux! La barrière d’abstraction peut vous aider.

Pour vous aider à concevoir la gestion des collisions, 3 méthodes vous sont proposées:
  • La mise en équations de l’environnement.
  • L’utilisation de liste d’obstacles simples
  • L’utilisation d’une grille

Mise en équations

Vos connaissances mathématiques vous permettent de mettre en équations un certain nombre de formes géométriques. Vous pouvez par exemple mettre en équation des demi-plans dans un espace en 2D et délimiter des zones par intersection de ces demi plan grâce à un système d’inéquations :

Exemple :

Mise en équation d’un triangle isocèle rectangle

Voici la mise en équation d’un triangle isocèle rectangle:

\(\left\{\begin{array}{l}\displaystyle x > 0 \\ \displaystyle y > 0 \\ \displaystyle y < -x+1 \\ \end{array} \right.\)

Exemple :

Mise en équation d’un disque

Voici la mise en équation d’un disque:

\((x-x_{centre})^2+(y-y_{centre})^2 < rayon^2\)

Exemple :

Gestion des collisions dans un rectangle

  1. Pour gérer les collision d’un balle en mouvement dans un environnement rectangulaire, on commence par mettre en équation le rectangle.
\(\left\{\begin{array}{l}\displaystyle 0 > x > x_{max} \\ \displaystyle 0 >y > y{max} \\ \end{array} \right.\)
  1. Ensuite, on ajoute à la fonction qui réalise l’intégration du ddans une détection
def move(dt,balle,xMax,yMax):
    x0,y0=balle.position
    vx,vy=balle.vitesse
    x1=x0+dt*vx
    y1=y0+dt*vy
    balle.position = x1,y1
    collide(balle,xMax,yMax)

def collide(balle,xMax,yMax):
    x,y=balle.position
    vx,vy=balle.vitesse
    if(x<0):
        x=0
        vx=-vx
    if(y<0):
        y=0
        vy=-vy
    if(x>xMax):
        x=xMax
        vx=-vx
    if(y>yMax):
        y=yMax
        vy=-vy
    balle.position=x,y
    balle.vitesse=vx,vy

La mise en équation se limite à des environnements assez simples pour que vous puissiez les mettre en équations. Cette méthodes est souvent la plus efficace en terme de temps de calcul mais elle s’adapte difficilement aux environnements dynamique dont la forme évolue au cours du temps.

  1. Carré dans le carré

    Une balle se déplace dans une pièce carré. Au centre de la pièce un mur carré bloque la pièce. Faites rebondir la balle sur les murs en complétant la fonction move()

    Votre réponse :
    python : code_run242.py
    Sorties 
    
            
    
            
    
            
    
            
        
     
    
    
    
        
        
        
        
    
    

    







    

    Commentaires
    
    
    
    

    Tester la si la futur position occupée correspond à une case vide dans la grille.
    

    
    

    



    


    
    
    Une solution possible :
    

    def move(ball,dt,c1,c2):
    #c1=cote carre interieur
    #c2=cote carre exterieur
    #coin inferieur gauche de c1 en 1,1

    x=ball.p[0]+ball.v[0]*dt
    y=ball.p[1]+ball.v[1]*dt
    dontmove=False

    #carre interieur
    xmini=c1/2.0-c2/2.0
    xmaxi=c1/2.0+c2/2.0
    ymini=c1/2.0-c2/2.0
    ymaxi=c1/2.0+c2/2.0

    #position future dans le carre?
    if x>xmini and x<xmaxi and y>ymini and y<ymaxi:
        #si la position futur est dans le carre central
        dontmove=True

        #gestion collision
        if ball.p[0]<xmini or ball.p[0]>xmaxi:
            ball.v[0]=-ball.v[0]
        else:
            ball.v[1]=-ball.v[1]
    else:
        #carre exterieur
        if x<0 or x>c1:
            dontmove=True
            ball.v[0] = -ball.v[0]
        if (y<0 or y>c1):
            dontmove=True
            ball.v[1] = - ball.v[1]
    if dontmove==False:
        ball.p=[x,y]

    

    


    

    
    
    

    


    2. 







Collection d’obstacles


Cette méthode s’appuie sur la précédente. Il s’agit en fait de composer un environnement d’éléments pour lesquels on sait détecter les collisions et d’appliquer la gestion des collisions pour chacun de ces élément.


Par exemple, il peut paraître difficile de mettre en équations un labyrinthe. Mais, il est facile de gérer les collisions entre un rectangle et un personnage qui se déplace en 2D. Si on construit le labyrinthe comme un somme de rectangles placés dans l’espace, pour gérer les collisions personnage/environnement, il suffit de répéter le calcul élémentaire de gestion de collisions personnage/rectangle pour chaque rectangle composant le labyrinthe.




    

        
        Exemple :  
        
    

    

        


fireZones


On imagine qu’il y a un type abstrait FireZone qui définit une zone enflammée qui fait perdre des point de vie au joueur s’il s’y trouve. La forme de cette zone est élémentaire, par exemple un carré.
La fonction FireZone.isInside() effectue un calcul pour indiquer si une position se trouve ou non dans le carré.


def move(dt, player, fireZones):
   x0,y0=player.position
   vx,vy=player.vitesse
   x1=x0+dt*vx
   y1=y0+dt*vy
   player.position = x1,y1
   collide(player, fireZones)

def collide(player, fireZones):
    x,y=player.position
    for f in fireZones:
        #detection
        if fireZone.isInside(f,x,y):
            #gestion
            player.health=player.health-1





Pour gérer les collision Joueur/zones enflammé on a donc tester successivement la collision avec chaque zone.


        

    





La limite de cette méthode est qu’elle peut amener à réaliser un grand nombre de calculs inutiles. En effet si les collections d’obstacles à gérer son très importantes, il faudra probablement tester les collisions sur l’ensemble des obstacles...


Plus que pour gérer des collision entre personnage et environnement, cette méthode est intéressante pour gérer des collisions entre objets mobiles ou personnages mobiles.


    

  1.  

    
     
    Collision liste de segments (EN CONSTRUCTION)

    

    
    
    
        
    
    
    
    

    Une balle se déplace dans un triangle.
Faites rebondir la balle sur les murs en complétant la fonction move()
    


    
    
    Votre réponse :
    



    
    
    python : 
    code_run247.py

    

    
    
    
        
            
                
                
                
                
            
            
                
                
                
                
            
            
                
                
            
        
    
    
    
    
        
        
        
    
    
    
    
    
    
    
    
    
        Sorties
        
    
            
    
            
    
            
    
            
    
            
        
     
    
    
    
        
        
        
        
    
    

    







    

    Commentaires
    
    
    
    

    Tester la si la futur position occupée correspond à une case vide dans la grille.
    

    
    

    



    


    
    
    Une solution possible :
    

    

    

    


    

    
    
    

    


    2. 







Utilisation d’une grille


La limite de la méthode précédente est qu’on est amené à tester des collisions entre des objets pouvant être très éloignés et n’avoir aucune chance d’entrer en collision dans l’état actuel du jeu.
Il est possible de considérablement optimiser les recherches de collisions en utilisant un maillage de l’espace.


Principe: L’affichage et la simulation se basent sur une représentation partagée du “monde” simulé.
Cette représentation peut être une grille dans laquelle on insère les différents éléments du monde.


world=[]
world.append(['+','-','-','-','-','-','+'])
world.append(['|',' ',' ',' ',' ',' ','|'])
world.append(['+','-','+',' ',' ',' ','|'])
world.append([' ',' ','|',' ',' ',' ','|'])
world.append([' ',' ','+','-','-','-','+'])

#player.py
def move(dx,dy,player,w):
    x,y=player.position
    x=x+dt
    y=y+dy
    if (world.isValide(w,x,y)):
        player.position=x,y

#world.py
def isValid(w,x,y):
    if (w[int(y)][int(x)]==' '):
        return True
    else:
        return False





    

  1.  

    
     
    Marche aléatoire

    

    
    
    
        
    
    
    
    

    Un personnage sur déplace aléatoirement dans une pièce.
Empêchez le de traverser les murs.
    


    
    
    Votre réponse :
    



    
    
    python : 
    code_run251.py

    

    
    
    
        
            
                
                
                
                
            
            
                
                
                
                
            
            
                
                
            
        
    
    
    
    
        
        
        
    
    
    
    
    
    
    
    
    
        Sorties
        
    
            
    
            
    
            
    
            
    
            
        
     
    
    
    
        
        
        
        
    
    

    







    

    Commentaires
    
    
    
    

    Tester la si la futur position occupée correspond à une case vide dans la grille.
    

    
    

    



    


    
    
    Une solution possible :
    

    grid=["***********","*     *   *","*     *   *","*         *","*   *     *","*   *     *","*   *     *","*   *     *","***********"]
class Player: pass
player=Player()
player.x=1
player.y=1

def move(player,grid):
    x=playe.x+random.randint(0,2)-1
    y=player.y+random.randint(0,2)-1

    if (grid[y][x])==" ":
        player.x=x
        player.y=y


drawBg(grid)
i=1000
#boucle de simulation
while(i):
    i=i-1
    move(player,grid)
    show(player)

    

    


    

    
    
    

    


    2. 

  2.  

    
     
    Animat

    

    
    
    
        
    
    
    
    

    Reprenez l’exemple de base animat en utilisant le fond d’écran pour les collisions.
    

    
    
    

    


    3.