Comment rendre mes personnages fluides en marchant sur un chemin (liste de coordonnées)?

J'ai une liste de coordonnées - sortie de l'algorithme A * - et je voudrais que mes personnages suivent en douceur ce chemin avec des rotations.

J'ai donc quelque chose comme A et je veux obtenir C

Comment puis-je faire ceci ?

ÉDITER

Pour être un peu plus clair:

Je suis plus intéressé par un virage en douceur car je sais déjà comment marcher d'un nœud à un autre.

ÉDITER

Comme beaucoup de gens trouvent cela utile (moi aussi), je poste un lien vers la "Nature du code" de Daniel Shiffman où il discute de nombreux problèmes d'IA (et de physique) du jeu, par exemple les comportements de pilotage http://natureofcode.com/book/chapter- 6-agents-autonomes / # chapter06_section8

Si vous voulez des chemins lisses dans un environnement basé sur des tuiles, il n'y a aucun moyen d'appliquer un lissage de chemin sur vos waypoints A *. Dans son livre sur la programmation du jeu AI, Matt Buckland décrit un algorithme simple et rapide pour lisser un chemin (essentiellement supprimer tous les bords qui peuvent être supprimés sans provoquer une intersection avec vos obstacles).

Une fois que vous avez supprimé les bords inutiles comme celui-ci, votre premier cas ( A -> B ) est résolu. Le lissage des bords de votre graphique peut être accompli de plusieurs manières. Très probablement, les splines Hermite fonctionneraient (en fonction un peu de la densité de votre obstacle et de la taille des carreaux). Une autre option pourrait être des comportements de pilotage, où vous commencez à vous diriger vers le prochain waypoint, dès que vous êtes à une demi-tuile de la cible actuelle (cela dépend vraiment de la vitesse à laquelle votre "agent" se déplace / tourne).

Comme d'autres l'ont mentionné, pour le deuxième cas, vous devrez implémenter une sorte de spline ou (en fait, un meilleur ajustement pour votre exemple) donner à l'unité une sorte de comportement de direction.

Cependant, pour le premier cas, il existe une solution qui est à la fois plus simple et donne de meilleurs résultats que le lissage de trajectoire. Il s'appelle Theta * , et est une extension simple (et relativement nouvelle) de A * sur les grilles qui permet aux unités de se déplacer dans n'importe quelle direction entre les points de grille.

Il y a un bel article expliquant Theta * (dont j'ai volé l'image ci-dessus) ici

Pour un mouvement plus humain et réaliste, essayez de vous intégrer aux comportements de pilotage. (Version C # de l'OpenSteer classique http://sharpsteer.codeplex.com/ ) Vous obtenez la sortie d'AStar et laissez le comportement de direction se soucier de la mobilité (l'un des exemples montre exactement comment procéder, naviguez en suivant un chemin)

En cas de navigation d'un point à un autre, j'ai utilisé la différence d'angles (direction actuelle du joueur par rapport à la direction du point actuel au point suivant), puis j'ai progressivement changé l'angle en angle final au fur et à mesure du mouvement. Vérifiez ce jeu ici où les avions se déplacent d'un point à un autre mais le virage n'est pas brusque mais en observant attentivement on peut identifier les points du chemin. (le jeu ne fonctionne que sur mobile mais de préférence sur iPhone / iPad).

J'ai eu de la chance avec les splines Catmull-Rom (un type de spline cubique également recommandé par @bummzack). La bonne partie de ceux-ci est que la spline passera toujours par les points de contrôle, beaucoup d'autres non. Implémentez quelque chose comme ceci:

t    = <time*>
t12  = t + 1.0
t23  = t
t34  = t - 1.0
t123 = (t + 1.0) / 2.0
t234 = t / 2

c1 = controlpoint[0];
c2 = controlpoint[1];
c3 = controlpoint[2];
c4 = controlpoint[3];

l12 = lerp(c1, c2, t12);
l23 = lerp(c2, c3, t23);
l34 = lerp(c3, c4, t34);
position = lerp(lerp(l12, l23, t123), lerp(l23, l34, t234), t);

* le temps est une valeur [0,1] entre les points de contrôle 1 et 2.

A-> B peut être résolu en utilisant des maillages de navigation au lieu d'une grille. Cela implique un grand changement dans la génération de données d'orientation.

Des cas comme C et D ne sont que des coins: si le personnage se déplace dans un chemin et à l'intérieur d'un "coin" (cellule où les cellules précédentes, actuelles et suivantes ne sont pas sur une ligne droite), poussez-le dans le sens de la cellule précédente et suivante . Le seul problème est de déterminer la distance par rapport à la position réelle (la distance de poussée). Cela nécessiterait probablement la distance de la cellule actuelle en entrée. Quelque chose comme ça:

push_dir = average( prevcell.pos, nextcell.pos ) - curcell.pos;
push_dist = cell_half_width - distance( char.pos, curcell.pos );
char.pos += push_dir * push_dist;