Collision par la méthode de l'axe séparateur

comtois · Message par **comtois** » mar. 24/avr./2007 10:10

Voici une première version, j'espère que j'aurai le temps d'en faire d'autres d'ici quelques années

Fichier Include "polygones.pb"

;J'ai largement utilisé le tutoriel d'Olivier renault pour construire ce code.
;Je ne retrouve plus l'adresse dans mes favoris, mais c'était sur gamedev je crois ?
;D'autres sites utiles
;http://www.limsi.fr/Individu/jacquemi/IG-TR-4-5-6/coll-inters-th-sep-axes1.html
;http://www.harveycartel.org/metanet/tutorials/tutorialA.html
;http://www.flashxpress.net/wikimedia/index.php/D%C3%A9tection_De_Collision

;faut que j'étudie ça de près !!
;http://gregory.corgie.free.fr/dotclear/index.php?2007/03/26/30--physic-engine-gestion-d-une-box-partie-2-2

;Principe de la méthode générale (pour n'importe quel polygone convexe)
; 1 - Calcule de chaque segment du polygone
; 2 - Calcule de la normale de ce segment
; 3 - Projection des polygones A et B sur cette normale (projection des sommets)
; 4 - Test du chevauchement des projections A et B
; 5 - Si pas de chevauchement , c'est qu'on a trouvé un plan de séparation, pas de collision. 
; 6 - Calcule du déplacement mini à effectuer pour séparer les deux polygones en cours de test.

; Il s'agit ici d'une version simplifiée, Il manque la gestion de la vitesse et des matrices des polygones.
; il faut tenir compte de la vitesse pour éviter de traverser un polygone.
; C'est à dire qu'il faut projeter la vitesse et en déduire à quel moment aura lieu l'impact.
; Il manque aussi la gestion du point d'impact, je suis en train de bosser le sujet.

; En guise d'exercice il serait intéressant de faire une version qui ne gère que des box.
; Voir aussi pour structurer le code comme la gestion des collision3D que j'avais fait.
; C'est à dire calculer tous les polygones pour retenir la collision la plus proche et 
; gérer la réponse d'une façon récursive. 


Declare CalculeIntersection(*A.s_Polygone, *B.s_Polygone, *Axe.s_Vecteur2D, *Distance.s_Vecteur2D, *Chevauchement.Float)
Declare ChercheDeplacementMini(Axe.s_Vecteur2D(1), Chevauchement.f(1), NbAxes.l, *Collision.s_Collision)

 Macro PRODUIT_SCALAIRE(V1, V2)
  (V1\x * V2\x + V1\y * V2\y) 
EndMacro

Procedure ConstructionPolygone(*Polygone.s_Polygone, Rayon.f)
  ;Permet de calculer un polygone convexe 
  Define.l i
	Define.f Angle, Rayon 
	For i = 0 To *Polygone\NbSommet-1
    *Polygone\Sommet[i]\x = Cos(Angle) * Rayon
    *Polygone\Sommet[i]\y = Sin(Angle) * Rayon
    Angle + 2.0 * #PI / *Polygone\NbSommet  
	Next i
EndProcedure

Procedure ConstructionMur(*Polygone.s_Polygone)
  Define.l i
	Define.f Angle, Rayon 
  Rayon = 22.63
	Angle = #PI/4
	For i = 0 To *Polygone\NbSommet-1
    *Polygone\Sommet[i]\x = Cos(Angle) * Rayon
    *Polygone\Sommet[i]\y = Sin(Angle) * Rayon
    Angle + 2.0 * #PI / *Polygone\NbSommet  
	Next i
EndProcedure

Procedure ConstructionVoiture(*Polygone.s_Polygone)
  Define.f Rayon 
  Rayon = 65
  *Polygone\Sommet[0]\x = Cos(#PI/6)     * Rayon
  *Polygone\Sommet[0]\y = Sin(#PI/6)     * Rayon
  *Polygone\Sommet[1]\x = Cos(#PI-#PI/9) * Rayon
  *Polygone\Sommet[1]\y = Sin(#PI-#PI/9) * Rayon
  *Polygone\Sommet[2]\x = Cos(#PI+#PI/9) * Rayon
  *Polygone\Sommet[2]\y = Sin(#PI+#PI/9) * Rayon
  *Polygone\Sommet[3]\x = Cos(-#PI/6)    * Rayon
  *Polygone\Sommet[3]\y = Sin(-#PI/6)    * Rayon
  
EndProcedure

Procedure AffichePolygone(*Voiture.s_Polygone, Mur.s_Polygone())
  StartDrawing(ScreenOutput())
  ;Affiche les murs	
  Couleur = #Red
  With Mur()
  ForEach  Mur()
    For i = 0 To \NbSommet-2
      LineXY(\Position\x + \Sommet[i]\x, \Position\y + \Sommet[i]\y, \Position\x + \Sommet[i+1]\x, \Position\y + \Sommet[i+1]\y, Couleur)
    Next i
    LineXY(\Position\x + \Sommet[\NbSommet-1]\x, \Position\y + \Sommet[\NbSommet-1]\y, \Position\x + \Sommet[0]\x, \Position\y + \Sommet[0]\y, Couleur)
	Next 
	EndWith
  ;Affiche la voiture
  Couleur = #White
  With *Voiture
  For i = 0 To \NbSommet-2
    LineXY(\Position\x + \Sommet[i]\x, \Position\y + \Sommet[i]\y, \Position\x + \Sommet[i+1]\x, \Position\y + \Sommet[i+1]\y, Couleur)
  Next i
  LineXY(\Position\x + \Sommet[\NbSommet-1]\x, \Position\y + \Sommet[\NbSommet-1]\y, \Position\x + \Sommet[0]\x, \Position\y + \Sommet[0]\y, Couleur)
  If Fun=0
    Circle(\Position\x + \Sommet[1]\x,\Position\y + \Sommet[1]\y,4,#Green)
    Circle(\Position\x + \Sommet[2]\x,\Position\y + \Sommet[2]\y,4,#Green)
  EndIf 
  EndWith
	StopDrawing()
 
EndProcedure	

 Procedure CollisionPolygone(*A.s_Polygone, *B.s_Polygone, *Distance.s_Vecteur2D, *Collision.s_Collision)
  Define.l j, i
  Define.s_Vecteur2D Segment
  If *A=0  Or *B=0 : ProcedureReturn #False : EndIf
	
	; Tous les axes de séparation
	Dim Axe.s_Vecteur2D(#NbPlan) 
	Dim Chevauchement.f(#NbPlan)
	Define.l NoAxe

	;Utilisation de la méthode générale, 
	;pour un rectangle on pourrait se contenter de tester 2 segments(largeur et longueur)
	;Une autre méthode projette le centre et le rayon du rectangle(à tester).
	
	; test séparation des axes du polygone A
	j = *A\NbSommet-1
	For i = O To *A\NbSommet-1 
	  ;Calcule chaque segment du polygone
		Segment\x  = *A\Sommet[i]\x - *A\Sommet[j]\x
		Segment\y  = *A\Sommet[i]\y - *A\Sommet[j]\y
		;Calcul la normale pour chaque segment du polygone
		Axe(NoAxe)\x = -Segment\y
		Axe(NoAxe)\y =  Segment\x
		If CalculeIntersection(*A, *B, Axe(NoAxe), *Distance, @Chevauchement(NoAxe)) = #False
			ProcedureReturn #False ; dès qu'on trouve un axe de séparation on peut sortir
		EndIf
		NoAxe + 1
		j = i 
	Next i
	; test séparation des axes du polygone B
	j = *B\NbSommet-1
	For i = O To *B\NbSommet-1 
	  ;Calcule chaque segment du polygone		
		Segment\x  = *B\Sommet[i]\x - *B\Sommet[j]\x ; Le polygone pourrait être stocké avec cette valeur
		Segment\y  = *B\Sommet[i]\y - *B\Sommet[j]\y ; ça éviterait de la calculer à chaque fois
		;Calcul la normale pour chaque segment du polygone
		Axe(NoAxe)\x = -Segment\y
		Axe(NoAxe)\y =  Segment\x
		If CalculeIntersection(*A, *B, Axe(NoAxe), *Distance, @Chevauchement(NoAxe)) = #False
			ProcedureReturn #False ; dès qu'on trouve un axe de séparation on peut sortir
		EndIf
		NoAxe + 1
		j = i
	Next i
	
	;Il faudra chercher le point d'impact !
	If ChercheDeplacementMini(Axe(), Chevauchement(), NoAxe, *Collision) = #False
		ProcedureReturn #False
	EndIf	

	; Inverse la normale si nécessaire pour être sûr que les polygones seront bien séparés.
	If PRODUIT_SCALAIRE(*Collision\Normale, *Distance) < 0.0
		*Collision\Normale\x = -*Collision\Normale\x
		*Collision\Normale\y = -*Collision\Normale\y
		Debug "correction"
		Debug *Collision\Normale\x
		Debug *Collision\Normale\y
		Debug "fin correction"
	EndIf	

	ProcedureReturn #True
	
EndProcedure

; calcule la projection du polygone sur l'axe en cours de test
Procedure CalculeProjection(*Polygone.s_Polygone, *Axe.s_Vecteur2D, *Projection.s_Intervalle)
  Define.l i
  Define.f Projection
  ;Calcul la projection du Sommet[0] sur la normale du plan en cours de test
	*Projection\mini = *Polygone\Sommet[0]\x * *Axe\x + *Polygone\Sommet[0]\y * *Axe\y
	*Projection\maxi = *Projection\mini 

  ;Recherche les projections mini et maxi en testant tous les sommets du polygone
	For i = 1 To *Polygone\NbSommet-1 
	  Projection = *Polygone\Sommet[i]\x * *Axe\x + *Polygone\Sommet[i]\y * *Axe\y
		If (Projection < *Projection\mini)
		  *Projection\mini = Projection
		ElseIf (Projection > *Projection\maxi)
		   *Projection\maxi = Projection
		EndIf   
	Next i
EndProcedure

Procedure CalculeIntersection(*A.s_Polygone, *B.s_Polygone, *Axe.s_Vecteur2D, *Distance.s_Vecteur2D, *Chevauchement.Float)
  Define.f h, dist0, dist1
  Define.s_Intervalle A, B
  ;Calcul la projection des sommets du polygone A sur la normale du plan en cours de test 
	CalculeProjection(*A, *Axe, @A)
	;Calcul la projection des sommets du polygone B sur la normale du plan en cours de test 
	CalculeProjection(*B, *Axe, @B)

  ;Calcul la projection de l'offset entre les polygones
	h = *Distance\x *  *Axe\x + *Distance\y * *Axe\y
	
	;Ajoute la projection de l'offset à la projection du polygone A
	A\mini + h
	A\maxi + h
  
  ;Calcul le chevauchement entre les projections de A et B
	dist0 = A\mini - B\maxi
	dist1 = B\mini - A\maxi
  
  
  ;Test le chevauchement 
	If dist0 > 0.0 Or dist1 > 0.0 
		ProcedureReturn #False
	Else
	  If dist0 > dist1
	    *Chevauchement\f = dist0
	  Else 
	    *Chevauchement\f = dist1
    EndIf
		ProcedureReturn #True
	EndIf
EndProcedure

Procedure.f Normalise(*V.s_Vecteur2D) 
  Define.f 	Longueur
	Longueur = Sqr(*V\x * *V\x + *V\y * *V\y)	
	If Longueur <> 0.0 
	  *V\x / Longueur 
    *V\y / Longueur 
  EndIf
	ProcedureReturn Longueur	
EndProcedure

Procedure ChercheDeplacementMini(Axe.s_Vecteur2D(1), Chevauchement.f(1), NbAxes.l, *Collision.s_Collision)
	Define.l mini, i
	Define.f n 
	
	;Initialise les données collision
	mini = -1
	*Collision\distance = 0
	*Collision\Normale\x = 0
	*Collision\Normale\y = 0
 
  ;On cherche parmi tous les axes de séparation le chevauchement le plus petit
	For i = 0 To NbAxes-1 
		n = Normalise(@Axe(i)) ; Normalise l'axe et récupère sa longueur
		Chevauchement(i) / n
	
    ;On retient le plus petit chevauchement pour se dégager de l'autre polygone
		;les valeurs de chevauchement sont négatives d'où le test > ci dessous
		;Par la suite il faudra aussi tenir compte du point d'impact !!
		If (Chevauchement(i) > *Collision\distance) Or (mini = -1)
			mini = i
			*Collision\distance  = Chevauchement(i)
			*Collision\Normale\x = Axe(i)\x
			*Collision\Normale\y = Axe(i)\y
		EndIf
	Next i

 ProcedureReturn (mini <> -1)
EndProcedure

Programme principal

Code : Tout sélectionner

;Comtois le 29/04/07 - Avec l'aide du tutoriel d'Olivier Renault (gamedev)
; PureBasic 4.02
 
If InitSprite()=0 Or InitMouse()=0 Or InitKeyboard()=0
  MessageRequester("Erreur","Initialisation impossible",0)
  End
EndIf
If OpenScreen(800, 600, 32,"Collision par la méthode de séparation des axes")=0
  MessageRequester("Erreur","Ouverture d'un écran 800x600x32 impossible",0)
  End
EndIf
  
#Epsilon = 0.00001
#NbSommet = 32              ;Nombre de Sommet maxi pour un polygone
#NbPlan = (#NbSommet*2)-1   ;Un plan par Sommet pour deux polygones
#DeltaAngle = 0.09/#PI
#NbPolygones = 25*18

Enumeration 
  #A
  #B
EndEnumeration
Structure s_Vecteur2D
  x.f
  y.f
EndStructure

Structure s_Intervalle
  Mini.f
  Maxi.f
EndStructure

Structure s_Polygone
  Position.s_Vecteur2D          
  Vitesse.f
  Angle.f
  NbSommet.l
  Sommet.s_Vecteur2D[#NbSommet]
EndStructure

Structure s_Collision
  Detectee.l
  Normale.s_Vecteur2D
  Distance.f
EndStructure

Define.s_Polygone Voiture
NewList Mur.s_Polygone()  
Global Fun = 1 ; Changez cette valeur à #True pour tester avec des polygones quelconques(convexes)

XIncludeFile "Polygones.pb"

Procedure InitialiseJeu(*Voiture.s_Polygone, Mur.s_Polygone())
  ;Création du jeu
	Define.l i, x, y
  Restore Niveau
  ClearList(Mur())
	For i = 0 To #NbPolygones-1
	  Read Poly 
	  x = 16 + (i % 25) * 32
	  y = 16 + (i / 25) * 32
	  If Fun 
  	 	If poly = 2
    	  *Voiture\Position\x = x  
    	  *Voiture\Position\y = y
        *Voiture\NbSommet = Random(5)+3 
        *Voiture\Vitesse = 5
        *Voiture\Angle = 0
        ConstructionPolygone(*Voiture, Random(32)+16)
      ElseIf Poly = 3
        AddElement(Mur())
  	    Mur()\Position\x = x 
  		  Mur()\Position\y = y
        Mur()\NbSommet = Random(10)+3    
        ConstructionPolygone(Mur(),Random(32)+16)
      EndIf
	  Else
  	 	If poly = 2
    	  *Voiture\Position\x = x  
    	  *Voiture\Position\y = y
        *Voiture\NbSommet = 4 
        *Voiture\Vitesse = 5
        *Voiture\Angle = 0
        ConstructionVoiture(*Voiture)
      ElseIf Poly = 1
        AddElement(Mur())
  	    Mur()\Position\x = x 
  		  Mur()\Position\y = y
        Mur()\NbSommet = 4   
        ConstructionMur(Mur())
      EndIf
    EndIf  
  Next i
EndProcedure

Procedure CollisionReponse(*Voiture.s_Polygone, Mur.s_Polygone())
  ;A reprendre
  ; Il faudrait d'abord chercher le point d'impact le plus proche en testant tous les polygones
  ; Puis calculer la réponse d'une façon récursive, en prenant un vecteur vitesse en compte.
  Define.s_Vecteur2D Distance
  Define.s_Collision Collision
  
  ForEach Mur()
    Distance\x = *Voiture\Position\x - Mur()\Position\x
    Distance\y = *Voiture\Position\y - Mur()\Position\y
	  Collision\Detectee = CollisionPolygone(*Voiture, Mur(), @Distance, @Collision)
    ;Séparation des polygones	
    If Collision\Detectee
	    *Voiture\Position\x - (Collision\Normale\x * (Collision\Distance * 1.0)) ; ou un peu moins que 1.5
		  *Voiture\Position\y - (Collision\Normale\y * (Collision\Distance * 1.0)) ; ou un peu moins que 1.5
	    If fun 
	      MouseLocate(*Voiture\Position\x, *Voiture\Position\y)
	    EndIf  
	  EndIf  
	Next 
EndProcedure

Macro ROTATION(Angle)
  CosAngle.f = Cos(Angle)
  SinAngle.f = Sin(Angle)
  
  x0.f = 0 ; Mettre 0 pour placer l'axe de rotation au centre
  y0.f = 0
  
  For i = 0 To *Voiture\NbSommet-1
    x1.f = *Voiture\Sommet[i]\x - x0
    y1.f = *Voiture\Sommet[i]\y - y0
    *Voiture\Sommet[i]\x = x0 + x1 * CosAngle + y1 * SinAngle
    *Voiture\Sommet[i]\y = y0 - x1 * SinAngle + y1 * CosAngle
  Next i
EndMacro

  
Procedure GestionClavier(*Voiture.s_Polygone, Mur.s_Polygone())
  If ExamineKeyboard()
      If KeyboardReleased(#PB_Key_F1) 
        Fun = 1 - Fun
        InitialiseJeu(*Voiture, Mur())
      ElseIf KeyboardReleased(#PB_Key_Space) 
        InitialiseJeu(*Voiture, Mur())
      EndIf
      
    If Fun = 0
      If  KeyboardPushed(#PB_Key_Left)  
        *Voiture\Angle + #DeltaAngle
        ROTATION(#DeltaAngle)
       ElseIf  KeyboardPushed(#PB_Key_Right)  
        *Voiture\Angle - #DeltaAngle
        ROTATION(-#DeltaAngle)
      EndIf 
   
      If  KeyboardPushed(#PB_Key_Down)  
        *Voiture\Position\x + Cos(*Voiture\Angle) * *Voiture\Vitesse 
        *Voiture\Position\y - Sin(*Voiture\Angle) * *Voiture\Vitesse 
      ElseIf  KeyboardPushed(#PB_Key_Up)  
        *Voiture\Position\x - Cos(*Voiture\Angle) * *Voiture\Vitesse 
        *Voiture\Position\y + Sin(*Voiture\Angle) * *Voiture\Vitesse 
      EndIf
    ElseIf ExamineMouse()
      *Voiture\Position\x = MouseX()
      *Voiture\Position\y = MouseY()   
    EndIf   
  EndIf               
EndProcedure
InitialiseJeu(@Voiture, Mur())
Repeat
 	ClearScreen(#Black)
 	GestionClavier(@Voiture, Mur())
	CollisionReponse(@Voiture, Mur())
	AffichePolygone(@Voiture, Mur())
	FlipBuffers()
Until KeyboardPushed(#PB_Key_Escape) 

DataSection
Niveau:
Data.l 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
Data.l 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1
Data.l 1,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1
Data.l 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1
Data.l 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1
Data.l 1,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,3,0,0,0,1
Data.l 1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,0,1,0,0,0,0,0,1,3,0,0,0,0,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,1,1,1
Data.l 1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,0,1,1,0,0,0,1,1,0,0,0,0,1,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,1,0,0,0,3,0,0,0,1
Data.l 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1
Data.l 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
EndDataSection

Thyphoon · Message par **Thyphoon** » mar. 24/avr./2007 10:16

Merci comtois tes codes sont toujours tres interessant

Frenchy Pilou · Message par **Frenchy Pilou** » mar. 24/avr./2007 11:39

Le compilateur ne touve pas les structures déclarées en ligne 27 ???
J'ai la 4.00
(et j'ai bien copier coller tout le listing

comtois · Message par **comtois** » mar. 24/avr./2007 11:41

Frenchy Pilou a écrit :Le compilateur ne touve pas les structures déclarées en ligne 27 ???
J'ai la 4.00

Il y a deux fichiers, le premier code (fichier polygones.pb" est appelé par le second code

Frenchy Pilou · Message par **Frenchy Pilou** » mar. 24/avr./2007 11:42

Ah désolé, j'avais pas épluché tout le bazar

comtois · Message par **comtois** » dim. 29/avr./2007 0:11

J'ai modifié les codes dans le premier post, histoire de montrer la collision entre des polygones quelconques.

Utilisez la barre espace à tout moment pour changer les polygones (taille et nombre de segments calculés de façon aléatoire)
Utilisez la touche [F1] pour passer d'un mode à l'autre, c'est à dire, collision avec des polygones quelconques, ou uniquement des boites.

dans un mode il faut utiliser le curseur (les boites), dans l'autre mode la souris (polygones quelconques).