+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : Calcul du chemin optimal pour un changement de direction (/showthread.php?tid=6661)
Pages :
1
2
Calcul du chemin optimal pour un changement de direction - niahoo - 22-02-2013
Hello, vu qu'on a des matheux en ce moment sur le forum on va pouvoir en profiter
Je cherche à modéliser le déplacement d'un bateau, et notamment le changement de cap.
Premièrement mon beateau est à un point A et il se dirige vers un point B. Je lui donne l'ordre de changer de cap et de se diriger vers un point C.
Il faut donc que je calcule l'angle entre la droites A->B et celle définie par le segment (0:0, 1:0) qui est l'axe des abscisses, choisi arbitrairement.
Ensuite, je calcule l'angle entre l'axe abscisses et la droite A->C pour, grâce à une soustraction, savoir de quel angle je dois virer.
ça, c'est pas trop chaud je pense.
J'ai décidé arbitrairement pour la modélisation que pour pouvoir virer d'un angle inférieur à X degrés il fallait descendre à une vitesse inférieure à Y m/s, sinon on chavire. Cette donnée n'est pas utile pour le moment, disons que c'est une fonction qui donne la vitesse maxi en fonction de l'angle, max_vire(angle) -> vitesse_max.
Donc, au départ, sans aucune connaissance en navigation, voilà ce qu'on fait : On calcule l'angle comme précédemment, on calcule la vitesse maxi. On calcule le temps de décélération pour descendre à cette vitesse en fonction de la masse du véhicule et de la puissance d'éventuels freins, on calcule le temps d'alignement en fonction de la masse et de la vitesse actuelle, et voilà, on est aligné, on peut calculer le temps d'accélération pour venir à la vitesse maxi.
Vous avez suivi ? ou plus personne ne lis ce post ?
Bon mais ça c'était la méthode facile. Parce qu'un navigateur expérimenté saura qu'on peut gagner du temps en tournant plus lentement mais en freinant beaucoup moins, c'est à dire en définissant Z cap intermédiaires et en répétant le processus décrit ci dessus pour chacun de ces cap.
Donc, pour les matheux, comment calculer ces caps intermédiaires ? Je voudrais en bonus pouvoir choisir le nombre de ces caps afin de refléter la compétence en navigation d'un personnage. (en gros par défaut on mets deux caps intermédiaires, et selon le level du perso on en calcule juqu'à 10 par exemple)
Merci si vous pouvez au moins me donner une piste
RE: Calcul du chemin optimal pour un changement de direction - Xenos - 22-02-2013
Formulé ainsi, c'est... complexe !
Tu veux changer de cap, ou tu veux aller au point C le plus vite possible? Le problème ne serait pas tout à fait le même...
RE: Calcul du chemin optimal pour un changement de direction - niahoo - 22-02-2013
Je vous ferai un schéma ce soir. Je veux aller au point C le plus vite possible.
RE: Calcul du chemin optimal pour un changement de direction - Xenos - 22-02-2013
Donc, on peut considérer:
- Je suis en A à la date t
- Je veux être en C le plus tôt possible
- J'ai une vitesse vectorielle 2D v à la date t
- J'ai une fonction de freinage (sous la forme d'une accélération opposée à la vitesse)
- J'ai une vitesse angulaire maximale dépendante de la vitesse
C'est ca?
RE: Calcul du chemin optimal pour un changement de direction - Myrina - 22-02-2013
Sans trop cherché, si tu considères ton cap au point A et le cap final au point C comme étant deux droites tangentes au même cercle, alors le cercle semble être la meilleure trajectoire
Voici un dessin trouvé sur le net correspondant à mon idée:
![[Image: forum_433505_2.PNG]](http://www.ilemaths.net/img/forum_img/0433/forum_433505_2.PNG)
T1 correspondrait au point A
T2 correspondrait au point C
B serait sur la droite (T1A)
RE: Calcul du chemin optimal pour un changement de direction - niahoo - 22-02-2013
(22-02-2013, 04:59 PM)Xenos a écrit : Donc, on peut considérer:
- Je suis en A à la date t
- Je veux être en C le plus tôt possible
- J'ai une vitesse vectorielle 2D v à la date t
- J'ai une fonction de freinage (sous la forme d'une accélération opposée à la vitesse)
- J'ai une vitesse angulaire maximale dépendante de la vitesse
C'est ca?
Ouaip ça m'a l'air d'être bien résumé
(22-02-2013, 05:00 PM)Myrina a écrit : Sans trop cherché, si tu considères ton cap au point A et le cap final au point C comme étant deux droites tangentes au même cercle, alors le cercle semble être la meilleure trajectoire
T1 correspondrait au point A
T2 correspondrait au point C
B serait sur la droite (T1A)
Oui je vois. effectivement le cercle pourrait être le mouvement parfait, ou bien une approximation suffisante. Mais n'oublie pas que T2 (mon nouveau cap) peut être très très loin, pas forcément sur le cercle. Il me faudrait donc calculer l'arc de cercle à suivre jusqu'à me retrouver dans la direction du nouveau cap.
ça me paraît être une composante utile mais pas suffisante : comment calculer le rayon optimal du cercle ?
RE: Calcul du chemin optimal pour un changement de direction - niahoo - 22-02-2013
Citation :- J'ai une vitesse angulaire maximale dépendante de la vitesse
J'ajouterais que nous ne sommes pas sur la route, donc il n'y a pas d'accélération perpendiculaire, pas d'effet d'adhérence. donc au lieu de pencher vers l'intérieur du virage, le véhicule "verse" côté extérieur. Mais on s'en fout car ça complique trop. La fonction vitesse angulaire <=> vitesse sera calculée arbitrairement.
RE: Calcul du chemin optimal pour un changement de direction - Xenos - 22-02-2013
Bien vu le cercle ! Mais on simplifie un peut car on considère une accélération angulaire infinie (ca sera suffisant dans un jeu): en effet, en A, on a une direction donnée, et l'instant d'après, même s'il est petit, on tourne déjà, d'un angle constant... Si on était en voiture, cela reviendrait à braquer les roues d'un coup sec en espérant que la voiture ne dérape pas :p
Si on garde l'idée du cercle (elle me semble être quand même une excellente simplification):
On est en A, avec une vitesse vectorielle 2D v.
On a donc définit une droite d, la droite de trajectoire inertielle (si on fait rien, on avance sur cette droite).
On a un point B (car "C" m'embête comme nom) ailleurs dans le plan. On sait que le cercle C (voilà pourquoi j'ai appeler ton point-cible "B") est de centre O et de rayon r, on cherche O et r tels que C tangente d en A et que B appartienne à C:
r = OB = OA
(d) _|_ (OA) (lire "perpendiculaire" pour _|_)
Brutalement:
{O[x] = (1/2)*(-2*v[x]*A[x]*A[y]+2*v[x]*A[x]*B[y]+A[x]^2*v[y]-v[y]*A[y]^2+2*v[y]*A[y]*B[y]-v[y]*B[x]^2-v[y]*B[y]^2)/(-v[x]*A[y]+v[x]*B[y]+A[x]*v[y]-B[x]*v[y]),
O[y] = (1/2)*(v[x]*A[x]^2+v[x]*B[x]^2-v[x]*A[y]^2+v[x]*B[y]^2-2*B[x]*v[x]*A[x]-2*B[x]*v[y]*A[y]+2*A[x]*v[y]*A[y])/(-v[x]*A[y]+v[x]*B[y]+A[x]*v[y]-B[x]*v[y])}
(Merci maple pour cette splendide mise en forme)
En calant l'origine du repère sur A, on simplifie les choses:
O[x] = k*v[y]
O[y] = k*v[x]
Avec k = AB²/(2*(AB^v)[z])
ou ^ est le produit vectoriel 3D, autrement dit, (u^v)[z] = u[x]*v[y]-u[y]*v[x]
Connaissant O, on en déduit r:
r = OA, O et A sont connus
Ensuite, on cherche le rayon de courbure R maximal de la trajectoire (ce rayon dépend de la vitesse du bateau, c'est toi qui l'a fixé). Si r<R alors on ne pourra pas tourner: il faudra freiner, sinon, on peut tourner, et on tourne, en suivant la trajectoire de r (la plus large courbe)...
RE: Calcul du chemin optimal pour un changement de direction - Myrina - 22-02-2013
Oui, le cercle est une simplification car il suppose un angle de braquage constant et une vitesse constante.
Par contre, il permet facilement de trouver la vitesse idéale car proportionnelle au rayon; le rayon idéal étant le plus court donc c'est la distance entre le point d'arrivée et la perpendiculaire au cap (droite OA).
RE: Calcul du chemin optimal pour un changement de direction - Xenos - 22-02-2013
Eyuup.
Et pour le calcul du rayon maximum, R dans le post précédent, c'est assez simple:
v = R*w où w est la vitesse angulaire (formule de mécanique)
D'où R = v/w
Si w, la vitesse angulaire maximale, est une fonction de la vitesse, cela donne:
R = v/f(v)
Ce qui se simplifiera probablement si tu as choisit un polynôme pour f(v).