Comment calculer les trajectoires des objets à accélération limitée?

Par exemple, disons que j'ai une voiture et qu'une voiture a un rayon de braquage minimum spécifique et que je veux conduire cette voiture du point a au point b, mais la voiture n'est pas face au point b. Comment calculer un chemin vers le point b? Pouvoir spécifier l'orientation au point b serait également bon (disons que vous voulez conduire jusqu'à votre entrée et ensuite vous garer dans votre garage - cela ne fait pas grand chose si vous arrivez dans votre entrée en conduisant sur votre pelouse et sont face à côté :)

Un pointeur vers la documentation (ou même juste un nom) conviendrait parfaitement - j'ai du mal à trouver quoi que ce soit.

Dans mes tentatives, ils fonctionnent dans des cas simples, mais échouent misérablement dans des situations telles que lorsque le point b est plus proche de a que le rayon de braquage minimum.

Par exemple, comment détermineriez-vous un chemin similaire à celui-ci (le chemin en gras):

edit: Dans mon problème actuel, il y a quelques contraintes de cheminement simples, mais j'ai déjà un algorithme A * en place qui fonctionne, mais il permet aux choses de faire des changements de cap instantanés, donc ça a l'air idiot de voir une voiture faire soudainement un virage de 90 ° sur un sou quand ils arrivent à un tournant.

Je n'ai pas encore parcouru les équations complètes pour cela, mais voici quelques visuels pour nous aider à comprendre ce problème. Cela se résume à une certaine géométrie:

( Icônes de voiture via Kenney )

À partir de n'importe quel point de départ et orientation, nous pouvons dessiner deux cercles avec notre rayon de braquage minimum - un à gauche, un à droite. Ceux-ci décrivent les points sur le début le plus serré possible de notre chemin.

Nous pouvons faire de même pour n'importe quelle position finale et orientation souhaitées. Ces cercles décrivent la fin la plus étroite possible de notre chemin.

Maintenant, le problème se résume à trouver un chemin qui relie l'un des cercles de départ à l'un des cercles de fin, en embrassant chacun le long de sa tangente.

(Cela suppose que nous n'avons pas besoin de rechercher des obstacles entre les deux, ce qui n'était pas mentionné dans la question. La réponse de Stormwind explique comment utiliser les informations du graphique de navigation pour ces types de problèmes. Une fois que nous avons la séquence de nœuds pour passer, nous pouvons appliquer la méthode ci-dessous à chaque segment du plan.)

Si, pour plus de simplicité, nous utilisons des lignes droites, nous obtenons quelque chose comme ceci:

Cela nous donne le cas limite. Une fois que vous avez trouvé un chemin par cette méthode, vous pouvez gonfler artificiellement un ou les deux cercles de début et de fin pour obtenir un chemin moins direct mais plus lisse, jusqu'au point où les deux cercles s'embrassent.

Calcul de ces chemins

Étudions les cas pour un sens de rotation - disons que nous commençons notre chemin en tournant à droite.

Le centre de notre cercle de braquage à droite est:

startRightCenter = carStart.position + carStart.right * minRadius

Appelons l'angle de la section droite de notre chemin (mesuré à partir de l'axe x positif) pathAngle

Si nous dessinons un vecteur du rightCenterpoint où nous quittons le cercle de rotation (auquel point nous devons faire face à pathAngle), alors ce vecteur est ...

startOffset = minRadius * (-cos(pathAngle), sin(pathAngle))

Cela signifie que le point où nous quittons le cercle doit être ...

departure = startRightCenter + startOffset

Le point où nous rentrons dans un cercle de virage dépend de si nous visons à terminer par un virage à gauche ou à droite:

// To end with a right turn:
reentry = endRightCenter + startOffset

// To end with a left turn: (crossover)
reentry = endLeftCenter - startOffset

Maintenant, si nous avons bien fait notre travail, la ligne se joignant departureà reentrydoit être perpendiculaire à startOffset:

dot(reentry - departure,  startOffset) = 0

Et la résolution de cette équation nous donnera l'angle (s) auquel cela est vrai. (J'utilise un pluriel ici parce que techniquement il y a deux de ces angles, mais l'un d'eux implique de conduire en marche arrière, ce qui n'est généralement pas ce que nous voulons)

Remplaçons le virage à droite par un virage à droite comme exemple:

dot(endRightCenter + startOffset - startRightCenter - startOffset, startOffset) = 0
dot(endRightCenter - startRightCenter, startOffset) = 0
pathAngle = atan2(endRightCenter - startRightCenter)

Le cas du crossover est plus compliqué - c'est celui pour lequel je n'ai pas encore calculé tous les calculs. Je posterai la réponse sans pour l'instant, au cas où cela vous serait utile pendant que je travaille sur les détails restants.

Modifier: destination à l'intérieur du rayon de braquage minimum

Il s'avère que cette méthode fonctionne souvent prête à l'emploi même lorsque la destination est plus proche que notre distance de virage minimale. Au moins une partie de l'un des cercles de rentrée se retrouve en dehors du rayon de virage, ce qui nous permet de trouver un chemin viable tant que cela ne nous dérange pas de devenir un peu bretzel ...

Si nous n'aimons pas le chemin que nous obtenons de cette façon (ou si un n'est pas faisable - je n'ai pas vérifié tous les cas de manière exhaustive - peut-être qu'il y en a des impossibles), nous pouvons toujours continuer tout droit ou en arrière jusqu'à ce que nous obtenions un véhicule approprié baiser le contact entre un cercle de début et de fin, comme illustré ci-dessus.

Cela dépend beaucoup du reste de votre modèle de données pour la navigation. C'est à dire. quelles données vous avez à portée de main, ce que vous pouvez facilement ajouter des données et comment vous les consommez.

En prenant un scénario similaire à partir d'un système de circulation sur l'eau, et en supposant que

• vous êtes dans une boucle de jeu
• vous avez un système de chemin de nœud
• vos voitures se comportent comme des objets autonomes qui se contrôlent "de l'intérieur", en utilisant leur propre force et direction
• vos voitures ne bougent pas comme sur des rails

vous pourriez avoir quelque chose comme ci-dessous (pardonnez-moi pour l'apparence enfantine des images)

(Les carrés rouges sont les nœuds, les lignes rouges sont les interconnexions de nœuds. Supposons que vous avez utilisé un solveur de recherche de chemin qui a donné aux nœuds 1-9 de passer; les nœuds 4-9 vus sur l'image et que vous souhaitez parcourir les nœuds indiqués par la ligne verte , au garage au nœud n ° 9; cependant vous ne voulez pas aller précisément à la ligne verte, restez plutôt naturellement sur la voie de droite et faites des manœuvres lisses).

Chaque nœud aurait des métadonnées qui contiennent par exemple un rayon, ou plusieurs, à des fins diverses. L'un d'eux est le cercle bleu, qui fournit des conseils de visée pour les voitures .

À tout moment , le véhicule doit être conscient des deux points nodaux suivants P (suivant) et P (suivant + 1), et de leurs positions. Naturellement, la voiture a également une position. Une voiture vise la tangente droite du cercle de métadonnées bleu de P (suivant). Il en va de même pour les voitures qui vont dans la direction opposée, donc elles n'entreront pas en collision. Viser la tangente signifie que la voiture peut approcher le cercle de n'importe quelle direction et toujours rester à droite. Il s'agit d'un principe de base approximatif, qui peut être amélioré de nombreuses façons.

P (suivant + 1) est nécessaire pour déterminer une distance - lorsque la voiture atteint P (suivante), ou pénètre dans un rayon de ses métadonnées, elle peut ajuster son angle de braquage en fonction de l'éloignement de P (suivant + 1). C'est à dire. si c'est proche, tournez beaucoup, si c'est loin, tournez peu. Apparemment, il doit également y avoir d'autres règles et conditions de bord, par exemple le calcul d'une distance entre la voiture et une ligne d'aide basée sur les tangentes du côté droit de P (suivant) et P (suivant +1), et une correction par cela - une volonté de rester sur la ligne pointillée (au-dessus de la photo) et en pointillé (sous la photo).

Dans tous les cas, lorsque la voiture passe un nœud , elle l' oublie et commence à regarder les deux suivants .

À votre question. Apparemment, en atteignant le nœud 7 (sur la photo ci-dessus, vu comme le nœud 2 dans l'image ci-dessous), il ne peut pas tourner suffisamment .

Une solution possible consiste à construire des lignes d'aide et à maintenir un objectif à tout moment , puis à faire bouger la voiture selon ses propres paramètres physiques (accélérer à une vitesse spécifiée, reculer plus lentement, prendre en compte les limites de vitesse des métadonnées de nœud, freiner à une valeur donnée ou calculée) G, etc.). Comme dit précédemment, la voiture est un objet autonome, auto-descriptif et autoportant dans ce scénario.

Ayez les lignes d'aide vertes 1,2,3 . Lorsque la voiture atteint le cercle magenta , elle commence à tourner à droite. À ce stade, vous pouvez déjà calculer qu'il ne réussira pas (vous connaissez la vitesse de rotation maximale et pouvez calculer la courbe, et pouvez voir qu'il traversera les deux lignes d'assistance 2 et 3). Tournez la direction complètement à droite et laissez-la avancer (par incréments physiques) et ralentissez-la lorsqu'elle atteint la ligne d'aide 3 (se rapproche des seuils d'utilisation, f (distance de la ligne d'assistance), etc.). Quand il est sur la ligne d'aide 3, passez en mode marche arrière , tournez la direction à fond en face . Laissez-le s'inverser jusqu'à ce qu'il atteigne la ligne d'aide 4(la ligne de connexion entre les nœuds 1 et 2 - google pour "l'algorithme de point à côté de la ligne"). Ralentissez, quand il l'atteint, passez à nouveau en mode de marche avant , tournez la roue. Répétez jusqu'à ce que la route soit dégagée - apparemment c'était suffisant avec 1 manœuvre supplémentaire cette fois.

Voici l'idée générale: pendant la boucle du jeu, ou lors de la vérification du système de tâche des jeux:

• Vérifiez la position, la vitesse, l'angle, etc. de la voiture par rapport aux limites de bord et au but actuels ,
• Si ce n'est pas encore fait , continuez ce que vous faisiez (laissez la physique bouger; la voiture a un régime et un rapport). Insérez un nouveau chèque dans votre système que, pour arriver dans par exemple 0,1 s.
• S'il est atteint , calculez de nouvelles conditions, définissez les données et commencez . Insérez une nouvelle vérification pour arriver dans le système que dans par exemple 0,1 s.
• Terminez le cycle de boucle - continuez, répétez.

En donnant aux nœuds et aux voitures des données suffisantes, il y aura mouvement et poursuite.

Edit: Et en ajoutant: Cela nécessite naturellement un réglage fin. Le comportement de votre simulation peut nécessiter différentes lignes d'aide, métadonnées, cercles, etc. Cela donnerait cependant une idée d'une solution possible.

J'ai fini par faire ce que DMGregory a suggéré et cela fonctionne bien. Voici un code pertinent (mais pas autonome) qui peut être utilisé pour calculer les deux styles de tangentes. Je suis sûr que ce code n'est pas efficace, et il n'est probablement même pas correct dans toutes les situations, mais il fonctionne pour moi jusqu'à présent:

bool Circle::outer_tangent_to(const Circle & c2, LineSegment & shared_tangent) const {
    if (this->direction != c2.direction) {
        return false;
    }
    if (this->radius != c2.radius) {
        // how to add it: http://mathworld.wolfram.com/Circle-CircleTangents.html
        // just subtract smaller circle radius from larger circle radius and find path to center
        //  then add back in the rest of the larger circle radius
        throw ApbException("circles with different length radius not supported");
    }

    auto vector_to_c2 = c2.center - this->center;
    glm::vec2 normal_to_c2;
    if (this->direction == Circle::CW) {
        normal_to_c2 = glm::normalize(glm::vec2(-vector_to_c2.y, vector_to_c2.x));
    } else {
        normal_to_c2 = glm::normalize(glm::vec2(vector_to_c2.y, -vector_to_c2.x));
    }

    shared_tangent = LineSegment(this->center + (normal_to_c2 * this->radius),
                                 c2.center + (normal_to_c2 * this->radius));
    return true;
}


bool Circle::inner_tangent_to(const Circle & c2, LineSegment & tangent) const {

    if (this->radius != c2.radius) {
        // http://mathworld.wolfram.com/Circle-CircleTangents.html
        // adding this is non-trivial
        throw ApbException("inner_tangents doesn't support circles with different radiuses");
    }

    if (this->direction == c2.direction) {
        // inner tangents require opposing direction circles
        return false;
    }

    auto vector_to_c2 = c2.center - this->center;
    auto distance_between_circles = glm::length(vector_to_c2);

    if ( distance_between_circles < 2 * this->radius) {
//      throw ApbException("Circles are too close and don't have inner tangents");
        return false;
    } else {
        auto normalized_to_c2 = glm::normalize(vector_to_c2);
        auto distance_to_midpoint = glm::length(vector_to_c2) / 2;
        auto midpoint = this->center + (vector_to_c2 / 2.0f);

        // if hypotenuse is oo then cos_angle = 0 and angle = 90˚
        // if hypotenuse is radius then cos_angle = r/r = 1 and angle = 0
        auto cos_angle = radius / distance_to_midpoint;
        auto angle = acosf(cos_angle);

        // now find the angle between the circles
        auto midpoint_angle = glm::orientedAngle(glm::vec2(1, 0), normalized_to_c2);

        glm::vec2 p1;
        if (this->direction == Circle::CW) {
            p1 = this->center + (glm::vec2{cos(midpoint_angle + angle), sin(midpoint_angle + angle)} * this->radius);
        } else {
            p1 = this->center + (glm::vec2{cos(midpoint_angle - angle), sin(midpoint_angle - angle)} * this->radius);
        }

        auto tangent_to_midpoint = midpoint - p1;
        auto p2 = p1 + (2.0f * tangent_to_midpoint);
        tangent = {p1, p2};

        return true;
    }
};

Voici deux films du code ci-dessus en action:

Voici un chemin "externe": http://youtube.com/watch?v=99e5Wm8OKb0 et voici un chemin "de croisement": http://youtube.com/watch?v=iEMt8mBheZU

Si ce code aide mais que vous avez des questions sur certaines parties qui ne sont pas présentées ici, postez simplement un commentaire et je devrais le voir dans un jour ou deux.