Ruta de "línea de visión" a través de la malla de navegación

Quiero calcular la línea de visión en una malla de navegación.

Considere la imagen a continuación, la línea amarilla es el resultado de solo A * y la línea roja es el resultado de un algoritmo de "línea de visión" que utiliza la línea amarilla como entrada. Ahora la unidad puede moverse directamente sin "zigzag".

¿Qué es un algoritmo para calcular esa "línea de visión"?

Estás buscando un algoritmo de embudo.

Aquí tienes una simple

http://digestingduck.blogspot.com.es/2010/03/simple-stupid-funnel-algorithm.html

Básicamente, el algoritmo identifica los bordes como portales y construye un embudo que se prueba contra el vértice de los bordes para verificar si están dentro del embudo o no.

En el paso A, el embudo se construye con la posición de inicio y el portal cruzado por una línea amarilla.

En el paso B, se verifica el siguiente portal, el vértice superior está dentro del embudo, por lo que la línea superior del embudo ahora lo atraviesa. Pero el vértice inferior está fuera del embudo porque la línea roja se encuentra debajo de la línea verde, por lo que la línea inferior no pasará, sino que continuará pasando por el vértice inferior del portal anterior.

Como puede comprobar, el embudo será más pequeño, y más pequeño, hasta el paso F, donde no se puede construir el embudo, porque la línea roja hace un embudo malo, por lo que el vértice superior se elige como un nuevo punto de inicio y un nuevo embudo se construirá si el punto final no está en esa malla.

Tenga en cuenta que este tipo de algoritmo también permite una solución simple al problema del tamaño del modelo, ya que puede considerar que los portales son más pequeños en el radio de 2x de su modelo.

Hay una técnica simple que se puede usar con rutas generadas usando esta idea de línea de visión. Básicamente, desea recorrer el camino, y en cada nodo, "mirar hacia atrás" dos antes del último nodo para ver si es visible. Si el nodo anterior al último es visible, puede eliminar el último nodo (dado que tiene una línea de visión entre su nodo actual y el nodo anterior al último, el último nodo, que es un nodo intermedio, no es obligatorio).

Un artículo de Gamasutra tiene el siguiente ejemplo de pseudocódigo:

checkPoint = starting point of path
currentPoint = next point in path
while (currentPoint->next != NULL)
if Walkable(checkPoint, currentPoint->next)
// Make a straight path between those points:
temp = currentPoint
currentPoint = currentPoint->next
delete temp from the path
else
checkPoint = currentPoint
currentPoint = currentPoint->next

Este algoritmo hace lo que desea, donde la Walkablefunción es esencialmente una función de línea de visión, pero ligeramente mejorada para incluir también situaciones en las que el camino es visible, pero no transitable (es decir, hoyos, trampas, zonas restringidas).