Discussion :

[mazertys17]

Bonjour,

je cherche a faire un algo qui permet a des objets de se déplacer en faisant en sorte qu'ils respectent une distence entre eux.
Donc si par exemple, un objet se déplace vers la droite et qu'il rencontre un autre objet, sa trajectoire doit automatiquement dévier et si elle ne peut pas alors il s'arrête.

Cela pose un problème simple que je n'arrive pas a résoudre, étant véritablement nul en math...

Avez vous une idée de comment résoudre ce problème ?

Voici à quoi cela peut ressembler:



Merci si vous pouvez m'aider!

[anapurna]

salut

tout ceci ressemble a un exercice
qu'as tu essayer comme solution pour que l'on puisse t'aider il faut que tu nous prouve que tu as un tans soit peu fait quelque essai

sinon un indice essai de déterminé les triangles coché dans ton exercice

[tbc92]

Que sais-tu de la distance (C1,C3), elle vaut ?
Et la distance (C2,C3), elle vaut ?
Donc C3 est à l'intersection de ... et de ...

[mazertys17]

Merci pour vos réponses.

J'ai essayé plein de trucs, je me suis cassé la tête de tous les côté...

Un moment donné je me suis dit qu'avec cos sin tan je pourrais trouver mais sans succès.

J'ai vraiment l'impression d'avoir une malédiction des maths car en plus je suis convaincu que c'est super simple!

tbc92 la distance C1/C3 comme la distance C2/C3, on la connait, puisque C3 est sur le cercle C1 dont on connait les coordonnées du centre et le rayon, et que C3 touche C2 dont on connait les rayons (donc cette distance équivaut au rayon C2 + le rayon C3).

anapurna un triangle coché ?
Désolé je ne vois pas ce que tu veux dire, j'ai cherché sans trouvé de définition ?

Je vais continuer de chercher si vous avez la solution ou des indices c'est bienvenue .

[tbc92]

C3 est donc à l'intersection de 2 cercles.

Ca donne 2 équations :

(x3-x1)²+(y3-y1)² = R1²
(x3-x2)²+(y3-y2)² = (R2+R3)²

Si tu développes tout ça, tu vas arriver normalement à 2 solutions (Le point C3 peut être en haut du cercle C1 comme sur ton dessin, ou en bas)

[mazertys17]

tbc92 Hum...désolé mais soit j'ai rien compris soit je me suis mal fait comprendre.

On ne connait pas les coordonnées de C3, c'est justement celles qu'on cherche, en sachant seulement qu'il se trouve sur le cercle de centre C1 et a une distance connue de C2 dont on connait les coordonnées.

Donc dans ton équation,

(x3-x1)²+(y3-y1)² = R1²
(x3-x2)²+(y3-y2)² = (R2+R3)²

Il me semble qu'on a pas assez d'éléments pour la résoudre..?

à partir du moment ou il faut le carré d'une partie de l'équation entre parenthèse dont on ne connait qu'une variable sur deux, comment faire ?
Désolé, je suis vraiment archi nul en math.

[anapurna]

salut

caché pas coché

il y a bien des angle a trouvé et de triangles
il est meme possible que tu doivent chercher un point intermédiaire
je verrais bien un truc dans se sens

[mazertys17]

anapurna ah oui, ok.

J'ai bien sur déjà cherché tous les triangles cachés possibles...
Mais à chaque fois ça se mord la queue.

EX : je peux connaître l'angle I/C1/C2 mais c'est l'angle I/C1/C3 qui m'intéresse.
On peut constater que le triangle CI/C3/C2 est isocel en C1...ok c'est bien donc l'angle C1/I/C3 = C1/C3/I...
J'ai l'impression que ça me fait une belle jambe...mais guerre plus.

Je tourne le pb dans tous les sens...a chaque fois j'ai l'impression qu'il me manque une donnée.

[wiwaxia]

Bonjour,

... Je cherche à faire un algo qui permette à des objets de se déplacer en faisant en sorte qu'ils respectent une distance entre eux.
Donc si par exemple, un objet se déplace vers la droite et qu'il rencontre un autre objet, sa trajectoire doit automatiquement dévier et si elle ne peut pas alors il s'arrête.

Cela pose un problème simple que je n'arrive pas à résoudre, étant véritablement nul en maths ... Avez vous une idée de comment résoudre ce problème ?

Voici à quoi cela peut ressembler: ...

Une petite question: si l'objet à localiser est la boule de centre (C3), il doit plutôt se déplacer vers la gauche et vers le bas pour venir en contact avec les deux autres; dans une autre direction, aucun obstacle ne vient limiter son mouvement.
Les équations proposées sont bien résolubles, mais il s'agit d'une réponse statique, qui n'indique rien sur la restriction du mouvement.

L'énoncé apparaît incohérent; le point mobile ne serait-il pas (C1) ? Le dessin semble lui attribuer un mouvement migratoire vers la droite ...

[wiwaxia]

Exemple d'algorithme de choix.

Supposons (C2, C3) immobiles, et (C1) animé d'un mouvement uniforme horizontal dont les positions successives sont données (en l'absence de toute contrainte) par la relation: OC1_j+1 = OC1_j + U .
Chaque déplacement est alors représenté par le vecteur horizontal U = h.u_x = (h, 0)
de longueur U = h .

On peut, à partir de la position actuelle C1_k, envisager 3 déplacements de même longueur:
# un déplacement horizontal de même sens U = C1_kI = h.u_x = (h, 0) ;
# un déplacement vertical ascendant V = C1_kJ = h.u_y = (0, h) , normal au précédent;
# un déplacement vertical descendant W = C1_kK = -h.u_y = (0, -h) , opposé à (V) ,
comme il est indiqué ci-dessous:

Le choix découlera de la comparaison des distances observées entre les 3 nouveaux points et les centres (C2) et C3); l'incompressibilité des boules impose en effet une valeur minimale aux carrés des distances séparant leurs centres.

Soit donc M12 = Min(C1C2²) = (R1 + R2)² , et M13 = Min(C1C3²) = (R1 + R3)² , en supposant chacune des boules caractérisée par un rayon donné (R1, R2 ou R3).
Le choix du déplacement (T) - ou son absence - sera effectué par un algorithme du type suivant ^(*):

Code :

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

1
2
3
4
5
6
7
8
9
10
 
TestI:= ((IC2<sup>2</sup>>M12) AND (IC3<sup>2</sup>>M13));
TestJ:= ((JC2<sup>2</sup>>M12) AND (JC3<sup>2</sup>>M13));
TestK:= ((KC2<sup>2</sup>>M12) AND (KC3<sup>2</sup>>M13));
IF TestI THEN T:= U
         ELSE IF TestJ THEN T:= V
                       ELSE IF TestK THEN T:= W
                                     ELSE T:= Vzero;          // Vecteur nul: Vzero = (0, 0)
 
OC1[k+1]:= OC1[k] + T;

^(*)Désolé pour cette notation abominable

Le point mobile (C1) contournera ainsi les obstacles en se déplaçant globalement vers la droite., à moins d'un blocage auquel il faudra trouver une échappatoire.

Le code s'adapte sans difficulté à un mouvement migratoire d'orientation quelconque, de déplacement élémentaire

U = a.u_x + b.u_y = (a, b) ;

il suffit d'associer à ce vecteur deux autres qui lui sont perpendiculaires:

V = (-b, a) et W = (b, -a) = -V .

Leur norme commune (h) est liée à leurs composantes par la relation de Pythagore:

h² = a² + b² .

[mazertys17]

Merci à tous pour vos réponses !

Mais je dois avouer que pour moi ça ressemble à du chinois ou de l’hébreu...
Cependant j'ai essayé de me casser la tête a décortiquer ces équations pour moi complexes mais déjà je vais essayer de clarifier les choses :

En fait j'ai plein de personnages qui vont se déplacer de gauche à droite et s'arrêter à une ligne verticale.
Et dans leur déplacement il faut éviter qu'ils se touchent et se retrouvent les uns sur les autres.
Je vais donc calculer leur déplacement en fonction de la position des autres.

Donc mon algo à ce stade ressemble à ça :
(l'opération qui suit va être effectuée par chaque personnage en déplacement.

Code Java :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
                float avance = speed*Surface.elapsedTime ;//c'est la distance que le personnage va parcourir
                float MOVEX = avance ;//au début elle est sur un axe horizontal uniquement, donc MOVEX représente le déplacement sur l'axe X
                float MOVEY = 0 ;//MOVEY représente le déplacement sur l'axe Y
                for ( int i = 0 ; i < persos.length ; i ++ ){//chaque personnage va vérifier la position de tous les autres personnages avant d'avancer
                    if ( !persos[i].equals(this) ){//donc il va faire la calcul avec tous les autres sauf lui même.
 
                        double dist = Math.sqrt(Math.pow(persos[i].x-(x+MOVEX),2) + Math.pow(persos[i].y-(y+MOVEY),2) );// là il calculer la distance entre la position de destination après son déplacement et celle du personnage ciblé
                        if ( dist <= distance ){//si la destination rentre dans le cercle de distance d'un des personnage alors il faut que sa trajectoire soit déviée.
                            //calcul que j'arrive pas a mettre en place correctement
                            break ;//ici dans un premier temps je break mais quand l'algo sera plus au point il faudra que je vérifie si cette nouvelle position se trouve dans un cercle d'un autre personnage en ce cas il faudra recalculer la position en prenant en compte tous les personnages qui sont gênant. et s'il ne peut pas se déplacer alors je mettrais MOVEX et MOVEY à 0 et il ne bougera pas.
                        }
 
                    }
                }
                x += MOVEX;
                y += MOVEY;

J'ai essayé la proposition de Flodelara

Vas-y comme un gros bourrin :

x3 = sqrt( R1² - ( y3 - y2 )² ) ± x1

Donc
y3 = sqrt( ( R2 + R3 )² - ( sqrt( R1² - ( y3 - y2 )² ) ± x1 - x2 )² ) ± y2

Tout est connu.

Par suite,
x3 = sqrt( R1² - ( sqrt( ( R2 + R3 )² - ( sqrt( R1² - ( y3 - y2 )² ) ± x1 - x2 )² ) ± y2 - y2 )² ) ± x1

et cela donne à peu près ceci :
Si j'ai bien compris, x1 et y1 sont les coordonnées du centre du cercle C1 soit la position au début du personnage, (donc ici x et y )
x2 et y2 sont les coordonnées du centre du cercle du personnage gênant. (donc ici perso[i].x/y )
x3 et y3 sont les coordonnées à déterminer qui seront la nouvelle position du personnage qui avance. (MOVEX et MOVEY)

Code Java :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
                float avance = speed*Surface.elapsedTime ;
                float MOVEX = x + avance ;
                float MOVEY = y + 0 ;
                for ( int i = 0 ; i < persos.length ; i ++ ){
                    if ( !persos[i].equals(this) ){
 
                        double dist = Math.sqrt(Math.pow(persos[i].x-(x+MOVEX),2) + Math.pow(persos[i].y-(y+MOVEY),2) );
                        if ( dist <= distance ){
                            MOVEX = (float) (Math.sqrt( Math.pow(avance,2) - Math.pow( MOVEY - persos[i].y,2 ) ) + x);
                            MOVEY = (float) (Math.sqrt( Math.pow( distance*2,2 ) - Math.pow( Math.sqrt( avance*avance - Math.pow( MOVEY - persos[i].y,2 ) ) + x - persos[i].x,2 ) ) + persos[i].y);
                            MOVEX = (float) (Math.sqrt( avance*avance - Math.pow( Math.sqrt( Math.pow( distance*2,2 ) - Math.pow( Math.sqrt( avance*avance -Math.pow ( MOVEY - persos[i].y ,2) ) + x - persos[i].x,2) ) + persos[i].y - persos[i].y,2 ) ) + x);
                            break ;
                        }
 
                    }
                }
                x = MOVEX;
                y = MOVEY;

Evidemment, ce serait trop beau...ça ne marche pas.
Ce que j'ai pas compris c'est comment peut ont calculer MOVEX par ex, en prenant la position MOVEY qu'on ne connaît pas encore ?

Quand à la proposition de wiwaxia, j'ai encore moins compris...ou j'ai l'impression que j'ai moi même pas été assez clair j'espère l'être un peu plus avec ce message...

Bref je vais continuer d'essayer de décortiquer la chose mais c'est pas gagné !
Donc tout aide/conseils est toujours bienvenue!

[Flodelarab]

Tu te tortures. Pour rien.

Tu as une situation initiale jugée valide.
Un personnage est déplacé si sa nouvelle position laisse la situation valide.
Sinon, le personnage reste immobile et passe la main.

Pourquoi ne pas juste faire une fonction qui calcule la distance entre le personnage principal et les autres personnages ?
Puis tester si cette distance est suffisamment grande.

La question initiale qui veut calculer C3 n'a pas lieu d'être.
Et les formules qui en découlent sont inutiles.

[mazertys17]

Sinon, le personnage reste immobile et passe la main.

Le problème c'est que les personnages vont rester bloqués en laissant un grand vide devant eux or le but est qu'ils se rangent le plus densément possible près de la ligne.

J'ai déjà testé cette solution qui marche mais elle ne convient pas au but recherché.
J'ai pensé aussi, utiliser une solution de collision basique ex le personnage avance peu importe s'il rentre dans un autre ensuite je calcule les position et si un personnage est dans un autre alors je le fais expulser en prenant simplement en compte les coordonnées de ces 2 persos.
Mais ça risque d'être bordélique mon but est que les personnages se rangent correctement en respectant une vitesse stable.