Calculer point d'interception de deux objets en mouvement

Version imprimable

22/07/2008, 11h14
Zarr.be

Calculer point d'interception de deux objets en mouvement

j'ai deux objets qui ont la propriété suivante:
une coordonnée: point (x,y)
une vitesse: float v
une direction: float d
une masse:float m
une force de propulsion: float p

Question: comment calculer le point de rencontre? : (x,y)
et comment savoir s'il n'y aura pas de rencontre??

plus difficile: auriez-vous une solution pour calculer le point de rencontre malgré l'inertie
c'est mon plus gros problème, car actuellement les prédateurs loupent régulièrement les cibles et tournant en rond autour...

j'ai d'abord essayé simplement de viser la position de la cible, mais à cause de l'inertie, c'était peu concluant

Ensuite j'ai essayé d'ajouter une correction à l'angle de poursuite, ça marche dans certains cas mais pas dans tous

il me faudrait un calcul qui me donne l'angle idéal de poursuite en tenant compte des différents paramètres (inertie, vitesse, direction etc...)
je ne suis pas très doué en maths ni en algèbre :aie: désolé
D'avance merci:)
PS: je programme en C#
22/07/2008, 11h56
PRomu@ld

Normalement tes deux objets ont des mouvements qui peuvent être mis en équation. Le tout est d'écrire l'équation (plus ou moins complexe en fonction des phénomènes que tu souhaites prendre en compte), ensuite pour savoir s'il y a intersection, il suffit de savoir si f(t) = g(t) pour un t positif. Si ça n'est pas le cas, tu n'as pas d'intersection, sinon, tu as la ou les valeurs de t pour lesquels il y a intersection.
22/07/2008, 12h17
Zarr.be

déjà, merci pour ta réponse ;-)
mais , je suis désolé mais je ne comprends pas le plus important "f(t) = g(t) pour un t positif."
dans mes données je n'ai ni de f ni de t et encore moins de g
Je vous avais dit que j'étais nul en algèbre :aie:

je me doute bien, qu'il y a une équation pour résoudre mon problème ;-)
si je poste, c'est bien pour la trouver...
22/07/2008, 12h29
PRomu@ld

En fait f(t) c'était l'équation de ton objet 1 g(t) l'équation de ton objet 2. Ici t c'est le temps. Tu peux avoir d'autres formulations de tes équations (en fonction d'autres choses), mais c'est assez pratique d'avoir le temps comme paramètre.

Pour ce qui est de l'équation, quels sont les paramètres à prendre en compte ?

-> pesanteur ?
-> frottement ?
-> force magnétique ?

Je pense que pour t'aider le mieux est de trouver un cours de mécanique du solide, tu peux en trouver un peu partout sur le net.
22/07/2008, 13h07
phryte
Salut.

Citation:

Question: comment calculer le point de rencontre? : (x,y)
et comment savoir s'il n'y aura pas de rencontre??

Il faut faire de la physique avec les vitesses et les positions :
Soit B et C les deux objets.
Tu calcules :
- le vecteur BC
- la dérivée de BC
- l'intervalle de temps qui annule cette vitesse
- tu extrapoles les deux objets à leur vitesse pendant ce temps
- la différence te donne les coordonnées du passage minimal
(connaissant les dimensions des objets tu peux savoir s'il y a collision.
Sous Matlab :
Code:

1 2 3 4 5 6 BC = C(x,y,z)-B(x,y,z); dt = dot(BC,(VB-VC))/((VB-VC)*(VB-VC)'); Bf = B+VB*dt;% B futur Cf = C+VC*dt;% C futur md = Cf-Bf;%Miss distance md = sqrt(md*md');%Miss distance
22/07/2008, 13h46
pseudocode

Citation:

Envoyé par Zarr.be

il me faudrait un calcul qui me donne l'angle idéal de poursuite en tenant compte des différents paramètres (inertie, vitesse, direction etc...)

Hum... Ca ressemble fort a un problème d'optimisation. Cependant la résolution analytique de "alpha(t)" (le meilleur angle de poursuite au cours du temps) ne va pas être facile, meme si ca reste faisable.

Comment as-tu caculé ta trajectoire pour l'instant ? (asservissement PID ?)
22/07/2008, 14h09
ToTo13

Bonjour,

tout d'abord, quelles sont les différentes forces qui interviennent dans ton problème ? Frotements, inertie, propulsion de tes objets, ...

Ensuite je pense que la première chose à faire, c'est d'écrire une équation générique pour ton objet loup. Il faut calculer l'équation de la trajectoire du loup lorsqu'il souhaite atteindre un point quelconque de coordonnées (x,y). Dans un premier temps, tu peux le faire en orientant uniquement le vecteur directeur sur le point (x,y). Une fois que tu as l'équation, tu dérives par rapport à l'angle du vecteur afin de trouver l'angle qui minimise le temps de rencontre.
Une fois que tu en es là, tu sais comment se comportera ton objet Loup pour atteindre une cible fixe.

Pour une cible en mouvement (rectiligne dans un premier temps), tu dois résoudre un système qui pour avoir le point d'intersection théorique entre les deux trajectoire. Une fois que tu as le point, tu ajustes pour le Loup.

petite correction: pour la vitesse et la direction, des objets, j'utilise un vecteur2d(que j'ai créé)
voila en détail les opérations que j'effectue:
Code:

1 2 3 4 5 6 7 public float Accélération { get { return ForcePropulsion/Masse; } }
pour la propulsion:
Code:

1 2 3 4 5 6 public void Propulser (Vecteur2d VectPropulsion, float DuréeCycle) { Vitesse += (VectPropulsion * (Accélération * DuréeCycle)); }
et voilà pour effectuées le mouvement
Code:

1 2 3 4 public void Move (float DuréeCycle) { coordonnées = coordonnées + (vitesse * DuréeCycle); }
duréecycle= 1sec/nombre de frames par seconde

donc pour accélérer, je trouve un angle je convertis en vecteur avec lequel j'envoie la durée de pousser, dans je modifie le vecteur vitesse de mon objet

Et autre part dans le code(car il y a une gestion de collision avec les bords) j'effectue le mouvement

j'ai aussi une fonction de frottement(pour limiter la vitesse maximale de mes objets)
Code:

1 2 // Aplication du frottement EnCour.Vitesse -= (EnCour.Vitesse * ZI.CoefficientFrottement);

22/07/2008, 14h40
Zavonen

Citation:

j'ai deux objets qui ont la propriété suivante:
une coordonnée: point (x,y)
une vitesse: float v
une direction: float d
une masse:float m
une force de propulsion: float p

Il y a des choses Be.zarr
Une vitesse c'est un vecteur donc pas un float mais deux ou trois dans l'espace.
La direction est donnée par le vecteur vitesse (inutile)
Une force c'est encore un vecteur pas un nombre.
Pour ce qui concerne la collision les seules choses qui importent sont les positions et les vitesses (les trajectoires s'en déduisent par intégration), éventuellement aussi les formes géométriques des objets (les grosses boules se rencontrent plus facilement que les petites, non?).
Donc a priori ta masse et ta force de propulsion ne pourraient servir qu'à calculer l'accélération par la formule de ce bon vieil Isaac (l'homme à la pomme) F=mG (il s'agit d'une identité vectorielle encore...)
Dans ce cas, partant de l'accélération tu intègres pour avoir la vitesse.
Par contre il te faut pour une intégration complète:
La position à l'instant 0
La vitesse à l'instant 0.
Après ça tu intègres et tu as pour chaque objet n une trajectoire fn(t).
Les collisions sont alors des inéquations du type
d(fn(t),fm(t))< delta où en gros delta est le diamètre des objets.
En résumé il y a beaucoup de choses qui ne collent pas. Il faut être plus précis dans la définition du problème.

voici les deux fonctions que j'ai essayé pour trouver l'angle de poursuite
mais elle ne marche pas très bien et sont très approximatives

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
        void PourSuivrexx (IVectPropulsable Poursuivant, IVectMobile Cible)
        {
            float distanceBrute,dist1s, distanceEstimee, tempParcour;
            Vecteur2d posPoursuivantEstimer, posCibleEstimer;
            AngleRadian angleCorrigé;
 
            distanceBrute = Vecteur2d.Distance(Poursuivant.Coordonnées, Cible.Coordonnées);
            //if(Vecteur2d.Distance(Poursuivant.Vitesse) < Poursuivant.Accélération )
            //{
            //    dist1s = Poursuivant.Accélération ;
            //}
            //else
            //{
                dist1s = Vecteur2d.Distance(Poursuivant.Vitesse);
           // }
            tempParcour = (distanceBrute / dist1s);
            posPoursuivantEstimer = Poursuivant.Coordonnées + (Poursuivant.Vitesse * tempParcour);
 
            //dist1s = Vecteur2d.Distance(Cible.Vitesse);
            //tempParcour = (distanceBrute / dist1s);
            posCibleEstimer = Cible.Coordonnées + (Cible.Vitesse * tempParcour);
 
            distanceEstimee = Vecteur2d.Distance(posPoursuivantEstimer, posCibleEstimer);
            angleCorrigé = (AngleRadian)Vecteur2d.Delta(Poursuivant.Coordonnées, posCibleEstimer);
 
            Poursuivant.Propulser((Vecteur2d)angleCorrigé, ZI.DuréeCycle);
        }
 
        private void Poursuivre (EvolAnimal EnCour, Evol proie)
        {
 
            float aCorrection;
 
            AngleRadian angleVersCible, aCorriger, aPoussee, aPropul;
            Vecteur2d vectPropulsion, vDelta;
 
            vDelta = Vecteur2d.Delta(EnCour.Coordonnées, proie.Coordonnées);
            angleVersCible = (AngleRadian)Vecteur2d.Delta(EnCour.Coordonnées, proie.Coordonnées);
                angleVersCible = AngleRadian.Normalize(angleVersCible);
                aPoussee = (AngleRadian)EnCour.Vitesse;
 
               /* Prédator.Vitesse = Prédator.Vitesse+ ((vecteurDirection * Prédator.Accélération) * zi.DuréeCycle));
                 * Non non ce n'est pas juste, je dois calculer la différence d'angle entre l'angle actuel du prédateur et l'angle de propulsion
                 * et l'ajouté à l'angle de propulsion  
                 * À VÉRIFIER
                 */
 
                aCorrection = AngleRadian.Différence(angleVersCible, (AngleRadian)EnCour.Vitesse);
                float aTest;
 
                aTest = (float)(Math.PI / 2);
                    // sup 45°
                if(aCorrection > aTest)
                {                 // = (-180 + diff)/3
                    aCorrection = (-(float)Math.PI + aCorrection) / 3;
                }
                    // inf -45°
                else if(aCorrection < -aTest)
                {
                    aCorrection = ((float)Math.PI + aCorrection) / 3;
                }
                      // inf - 120°                           sup 120°
                else if(aCorrection < -Math.PI / 3 * 2 || aCorrection > Math.PI / 3 * 2)
                {
                    aCorrection = 0 - ((aCorrection / 3) * 2);
                }
 
                else
                {
                    aCorrection = 0 - aCorrection;
                }
                aCorriger = angleVersCible + aCorrection;
                //aCorriger = angleVersCible;//  +aCorrection;
                /*
                Console.WriteLine(angleVersCible.Degrés+"; - " +  
                 ((AngleRadian)Prédator.Vitesse).Degrés+
                    ((AngleRadian)aCorrection).Degrés+ " = "+ aCorriger.Degrés);
                */
 
                vectPropulsion = (Vecteur2d)aCorriger;
 
                EnCour.Propulser( vectPropulsion, ZI.DuréeCycle);
                   }

22/07/2008, 19h28
Zavonen

Il s'agissait donc d'un problème de poursuite !
Voici l'algo très simple de poursuite du lièvre par le renard.
Le lièvre se déplace sur l'axe y'Oy et sa position à l'instant t est repérée par l'ordonnée z.
Le renard se déplace dans le plan ses coordonnées sont x et y.
Le lièvre se déplace à vitesse constante p, le renard à vitesse constante q (il s'agit de la vitesse absolue, pas du vecteur vitesse)
Voici la boucle à parcourir pour chaque intervalle de temps:

d <-- racine(x^2+(y-z)^2
x <-- x-qx/d
y <-- y+q(z-y)/d
z<--z+p

Maintenant à partir de ce schéma très simple tu peux faire accélérer le lièvre.
il suffit de prévoir une ligne
p<--ap avant z<--z+p
Tu peux faire accélerer le renard avec
q<--bq avant la ligne x<---x-qx/d
Tu peut introduire un frottement etc..
23/07/2008, 03h20
Zarr.be

je crois vous oublier tous la masse donc l'inertie du poursuivant

Aussi, dans le calcul simple de point de rencontre il y a un problème:
si le poursuivant à une vitesse très lente et que la cible se dirige vers le poursuivant, le point de rencontre se situera derrière le poursuivant(il se mettra alors à reculer face la cible ... tout en accélérant ce qui aura pour effet de diminuer le point de rencontre virtuelle, donc il refera demi-tour (en ralentissant de nouveaux) ce qui fait que le point de rencontre se retrouvera de nouveau derrière)
ça aura pour effet d'avoir un mouvement synchrone sans jamais se rencontrer...

Et ça je ne vous parle que sur une cible à mouvement linéaire
comme dans mon cas des prédateurs qui chassent d'autres prédateurs cela ne va pas du tout...

Je vais essayer de faire un mixte des deux méthodes approximative que je vous ai montré plus haut...
en affinant à chaque itération la direction vers la cible, je dois arriver à les faire se rencontrer...

Quand même merci pour votre patience et vos réponses, je vous tiens au courant des développements futurs
amicalement Zarr.be ;)