IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Calculer une position


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2014
    Messages
    521
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2014
    Messages : 521
    Par défaut Calculer une position
    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:

    Nom : probleme_de_math.png
Affichages : 1642
Taille : 114,3 Ko

    Merci si vous pouvez m'aider!

  2. #2
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 489
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 489
    Par défaut
    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

  3. #3
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 215
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 215
    Par défaut
    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 ...

  4. #4
    Membre éclairé
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2014
    Messages
    521
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2014
    Messages : 521
    Par défaut
    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 .

  5. #5
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 215
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 215
    Par défaut
    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)

  6. #6
    Membre éclairé
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2014
    Messages
    521
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2014
    Messages : 521
    Par défaut
    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.

  7. #7
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 489
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 489
    Par défaut
    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
    Nom : Sans titre.png
Affichages : 1298
Taille : 77,9 Ko

  8. #8
    Membre éclairé
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2014
    Messages
    521
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2014
    Messages : 521
    Par défaut
    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.

  9. #9
    Membre Expert

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 78
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Billets dans le blog
    9
    Par défaut Calculer une position
    Bonjour,

    Citation Envoyé par mazertys17 Voir le message
    ... 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: Nom : Cercles_C1C2C3.png
Affichages : 1300
Taille : 27,5 Ko ...
    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 ...

  10. #10
    Membre Expert

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 78
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Billets dans le blog
    9
    Par défaut Calculer une position
    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: OC1j+1 = OC1j + U .
    Chaque déplacement est alors représenté par le vecteur horizontal U = h.ux = (h, 0)
    de longueur U = h .

    On peut, à partir de la position actuelle C1k, envisager 3 déplacements de même longueur:
    # un déplacement horizontal de même sens U = C1kI = h.ux = (h, 0) ;
    # un déplacement vertical ascendant V = C1kJ = h.uy = (0, h) , normal au précédent;
    # un déplacement vertical descendant W = C1kK = -h.uy = (0, -h) , opposé à (V) ,
    comme il est indiqué ci-dessous:
    Nom : 3_Cercles.png
Affichages : 1212
Taille : 6,4 Ko
    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(C1C22) = (R1 + R2)2 , et M13 = Min(C1C32) = (R1 + R3)2 , 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.ux + b.uy = (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:
    h2 = a2 + b2 .

  11. #11
    Membre éclairé
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2014
    Messages
    521
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2014
    Messages : 521
    Par défaut
    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!

  12. #12
    Expert confirmé Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 288
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 288
    Par défaut
    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.

  13. #13
    Membre éclairé
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2014
    Messages
    521
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2014
    Messages : 521
    Par défaut
    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.

Discussions similaires

  1. Réponses: 0
    Dernier message: 21/01/2016, 18h31
  2. Réponses: 0
    Dernier message: 21/01/2016, 10h27
  3. Calcul d'une position à partir d'une accéleration
    Par YohDono dans le forum Physique
    Réponses: 0
    Dernier message: 01/01/2013, 17h07
  4. Réponses: 0
    Dernier message: 28/07/2011, 07h46
  5. Réponses: 2
    Dernier message: 26/05/2004, 17h53

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo