¿Cómo hacer que mis personajes se vuelvan suaves mientras camino por un camino (lista de coordenadas)?

Tengo una lista con coordenadas, salida del algoritmo A *, y me gustaría hacer que mis personajes sigan sin problemas este camino con rotaciones.

Entonces tengo algo como A y quiero obtener C

Cómo puedo hacer esto ?

EDITAR

Para aclararme un poco más:

Estoy más interesado en un giro suave , ya que sé cómo caminar de un nodo a otro.

EDITAR

Como mucha gente encuentra esto útil (yo también), estoy publicando un enlace a la "Naturaleza del código" de Daniel Shiffman donde discute muchos problemas de IA (y física) del juego, por ejemplo, comportamientos de dirección http://natureofcode.com/book/chapter- 6-autónomos-agentes / # chapter06_section8

Si desea rutas suaves en un entorno basado en mosaicos, no hay forma de aplicar un poco de suavizado de ruta en sus puntos de ruta A *. En su libro sobre la programación de IA de juegos, Matt Buckland describe un algoritmo simple y rápido para suavizar un camino (básicamente, eliminar todos los bordes que se pueden eliminar sin causar una intersección con sus obstáculos).

Una vez que haya eliminado los bordes innecesarios como este, se resuelve su primer caso ( A -> B ). Alisar los bordes en su gráfico se podría lograr de varias maneras. Lo más probable es que las estrías de Hermite funcionen (dependiendo un poco de la densidad de su obstáculo y el tamaño del azulejo). Otra opción podrían ser los comportamientos de dirección, en los que comienzas a dirigirte hacia el siguiente punto de referencia, tan pronto como estés a media casilla de distancia del objetivo actual (esto realmente depende de qué tan rápido se mueva / gire tu "agente").

Como otros han mencionado, para el segundo caso necesitará implementar algún tipo de spline o (en realidad un mejor ajuste para su ejemplo) darle a la unidad algún tipo de comportamiento de dirección.

Sin embargo, para el primer caso, hay una solución que es más simple y ofrece mejores resultados que el suavizado de rutas. Se llama Theta * , y es una extensión simple (y relativamente nueva) de A * en cuadrículas que permite que las unidades se muevan en cualquier dirección entre los puntos de la cuadrícula.

Hay un buen artículo que explica Theta * (del que robé la imagen de arriba) aquí

Para un movimiento más humano realista, intente integrarse con Steering Behaviors. (Versión C # del clásico OpenSteer http://sharpsteer.codeplex.com/ ) Obtiene la salida de AStar y deja que el comportamiento de la dirección se preocupe por el movimiento (uno de los ejemplos muestra exactamente cómo hacer esto, navegue siguiendo un camino)

En el caso de la navegación de un punto a otro, utilicé la diferencia en los ángulos (dirección actual del jugador vs. dirección del punto actual al siguiente punto) y luego cambié gradualmente el ángulo al ángulo final a medida que ocurre el movimiento. Mira este juego aquí donde los aviones se mueven de 1 punto a otro, pero el giro no es abrupto, pero al observar con cuidado uno puede identificar los puntos del camino. (el juego solo funciona en dispositivos móviles, aunque preferiblemente iPhone / iPad).

He tenido buena suerte con las splines Catmull-Rom (un tipo de spline cúbico como también lo recomienda @bummzack). Lo bueno de eso es que la spline siempre pasará por los puntos de control, muchos otros no. Implemente algo como esto:

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);

* el tiempo es un valor [0,1] entre los puntos de control 1 y 2.

A-> B se puede resolver utilizando mallas de navegación en lugar de una cuadrícula. Esto implica un gran cambio en la generación de datos de búsqueda de caminos.

Casos como C y D son solo cortes de esquinas: si el personaje se mueve en una ruta y dentro de una "esquina" (celda donde las celdas anteriores, actuales y siguientes no están en línea recta), empújela en la dirección de la celda anterior y siguiente . El único problema es determinar la distancia desde la posición real (la distancia de empuje). Eso probablemente requeriría la distancia desde la celda actual como entrada. Algo como esto:

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;