Comment adapter les algorithmes de pathfinding aux déplacements restreints?

Imaginez un mouvement semblable à une voiture où les entités ne peuvent pas allumer un sou. Disons, pour les besoins de la discussion, que lorsqu'ils sont à grande vitesse, ils peuvent tourner à 90 degrés par seconde. Dans de nombreux cas, cela modifierait le chemin optimal et donc la recherche de chemin. Cela peut même rendre les chemins «habituels» entièrement impossibles à parcourir.

Existe-t-il des algorithmes d'orientation de cheminement ou des algorithmes de planification de mouvement qui peuvent garder cela à l'esprit, ou existe-t-il des moyens simples d'adapter les plus populaires?

Bienvenue dans le monde merveilleux de la planification de mouvements non holonomiques . Je recommande de le faire en utilisant un planificateur de chemin de grille en treillis . D'autres alternatives incluent le RRT cinodynamique et l' optimisation de la trajectoire . Les systèmes non holonomiques incluent les voitures, les bateaux, les monocycles ou tout ce qui ne permet pas au véhicule de se déplacer dans la direction souhaitée. La planification de ces systèmes est beaucoup plus difficile que les systèmes holonomiques et jusqu'en 2000 était à la pointe de la recherche universitaire. De nos jours, il existe de nombreux algorithmes à choisir, qui fonctionnent décemment.

Voici comment ça fonctionne.

Etat

La configuration q de votre voiture est en fait un état 3D contenant la position x, y de la voiture et son orientation t . Les nœuds de votre algorithme A * sont en fait des vecteurs 3D.

class Node
{
    // The position and orientation of the car.
    float x, y, theta;
}

Actions

Et les bords?

C'est un peu plus difficile, car votre voiture pourrait en fait choisir un nombre infini de façons de tourner la roue. Ainsi , nous pouvons la rendre accessible à un planificateur de réseau de réseau en limitant le nombre d'actions que la voiture peut prendre pour un ensemble discret, A . Par souci de simplicité, supposons que la voiture n'accélère pas, mais qu'elle peut plutôt changer sa vitesse instantanément. Dans notre cas, A peut être comme suit:

class Action
{
    // The direction of the steering wheel.
    float wheelDirection;

    // The speed to go at in m/s.
    float speed;

    // The time that it takes to complete an action in seconds.
    float dt;
}

Maintenant, nous pouvons créer un ensemble discret d'actions que la voiture peut entreprendre à tout moment. Par exemple, une droite dure tout en appuyant à fond sur le gaz pendant 0,5 seconde ressemblerait à ceci:

Action turnRight;
turnRight.speed = 1;
turnRight.wheelDirection = 1;
turnRight.dt = 0.5;

Mettre la voiture en marche arrière et reculer ressemblerait à ceci:

Action reverse;
reverse.speed = -1;
reverse.wheelDirection = 0;
reverse.dt = 0.5;

Et votre liste d'actions ressemblerait à ceci:

List<Action> actions = { turnRight, turnLeft, goStraight, reverse ...}

Vous avez également besoin d'un moyen de définir comment une action effectuée sur un nœud entraîne un nouveau nœud. C'est ce qu'on appelle la dynamique vers l' avant du système.

// These forward dynamics are for a dubin's car that can change its
// course instantaneously.
Node forwardIntegrate(Node start, Action action) 
{
    // the speed of the car in theta, x and y.
    float thetaDot = action.wheelDirection * TURNING_RADIUS;

    // the discrete timestep in seconds that we integrate at.
    float timestep = 0.001;

    float x = start.x;
    float y = start.y;
    float theta = start.theta;

    // Discrete Euler integration over the length of the action.
    for (float t = 0; t < action.dt; t += timestep)
    {
       theta += timestep * thetaDot;
       float xDot = action.speed * cos(theta);
       float yDot = action.speed * sin(theta);
       x += timestep * xDot;
       y += timestep * yDot;
    }

    return Node(x, y, theta);
}

Cellules de grille discrètes

Maintenant, pour construire la grille en treillis, tout ce que nous devons faire est de hacher les états de la voiture en cellules de grille discrètes. Cela les transforme en nœuds discrets qui peuvent être suivis de A *. Ceci est super important car sinon A * n'aurait aucun moyen de savoir si deux états de voiture sont réellement les mêmes pour les comparer. En hachant des valeurs de cellules de grille entières, cela devient trivial.

GridCell hashNode(Node node)
{
    GridCell cell;
    cell.x = round(node.x / X_RESOLUTION);
    cell.y = round(node.y / Y_RESOLUTION);
    cell.theta = round(node.theta / THETA_RESOLUTION);
    return cell; 
}

Maintenant, nous pouvons faire un plan A * où les GridCells sont les nœuds, les Actions sont les bords entre les nœuds et le Début et le But sont exprimés en termes de GridCells. L'heuristique entre deux GridCells est la distance en x et y plus la distance angulaire en thêta.

Suivre le chemin

Maintenant que nous avons un chemin en termes de GridCells et d'actions entre eux, nous pouvons écrire un suiveur de chemin pour la voiture. Étant donné que les cellules de la grille sont discrètes, la voiture sauterait entre les cellules. Nous devrons donc lisser le mouvement de la voiture le long du chemin. Si votre jeu utilise un moteur physique, cela peut être accompli en écrivant un contrôleur de direction qui essaie de garder la voiture aussi près que possible du chemin. Sinon, vous pouvez animer le chemin à l'aide de courbes de Bézier ou simplement en faisant la moyenne des quelques points les plus proches du chemin.

La plupart des algorithmes de recherche de chemin fonctionnent sur un graphe arbitraire sans restriction de géométrie.

Donc, ce que vous devez faire est d'ajouter l'orientation de la voiture à chaque nœud exploré et de restreindre les nœuds réellement connectés.

Mes pensées, je ne les ai pas testées!

1. Exécutez A * du début à la destination, retournez le chemin.
2. Boucle à travers le chemin, lorsque vous détectez un virage, utilisez un algorithme de Bézier (ou tout autre modèle similaire) qui utilise la vitesse actuelle du demandeur pour prédire les nœuds qui créeront un virage en douceur. Assurez-vous qu'il essaie de revenir au nœud de chemin le plus proche.
3. Si le virage peut être fait, super, sinon, répétez avec une vitesse plus lente, ce qui rend le virage plus net.
4. Une fois que le chemin correct est créé, revenez sur le chemin en ajustant la vitesse du chercheur avant que le virage ne soit fait afin qu'il ralentisse à la bonne vitesse avant qu'il n'initie le virage.
5. Si le tour ne peut pas être fait du tout, recommencez le tout. Assurez-vous simplement que tous les nœuds traités du tour qui ne peuvent pas être effectués sont dans la liste fermée, afin qu'ils soient ignorés. Et vous pouvez commencer par le point où le virage est initié afin que vous puissiez sauter la partie réussie du chemin, cependant, dans certains cas, cela pourrait éventuellement entraîner un chemin moins qu'optimal.

Vous devriez également pouvoir le faire sans avoir à terminer d'abord le chemin, ergo: gérer les virages pendant A *, qui sera probablement beaucoup mieux optimisé, mais cela pourrait également s'avérer problématique et glitchy, je ne le saurais vraiment pas et malheureusement je je n'ai pas le temps de le tester moi-même.

Si votre agent a le plein contrôle de la voiture, faites-le dans l'autre sens. Connectez une ligne du début à la fin en premier, puis déterminez à quelle vitesse vous pouvez naviguer à chaque tour, similaire à la réponse de Dennis.

Ne dessinez pas les courbes de Bézier à partir de points fixes. Pour minimiser la perte de vitesse, vous devez déplacer toute la ligne, alors commencez par insérer des nœuds supplémentaires à une distance plus ou moins égale, puis déplacez-vous ensuite pour minimiser l'énergie ou des stratégies similaires. Pour plus de détails, vous devez vous pencher sur la génération de lignes AI dans (de préférence sur sim ou semi-sim) les jeux de course.

Une fois que le système de ligne AI est en cours d'exécution, lancez votre recherche A * et pour chaque chemin, avancez d'au moins un coin, puis calculez la ligne AI qui vous donne une estimation du temps. Ce serait votre fonction de coût.