He estado leyendo esto: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
Pero hay algunas cosas que no entiendo, por ejemplo, el artículo dice que use algo como esto para encontrar caminos con movimiento diagonal:
function heuristic(node) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
return D * max(dx, dy)
No sé cómo configurar D para obtener un camino de aspecto natural como en el artículo, configuré D al costo más bajo entre cuadrados adyacentes como decía, y no sé qué querían decir con las cosas sobre la heurística debería ser 4 * D, eso no parece cambiar nada.
Esta es mi función heurística y función de movimiento:
def heuristic(self, node, goal):
D = 5
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
return D * max(dx, dy)
def move_cost(self, current, node):
cross = abs(current.x - node.x) == 1 and abs(current.y - node.y) == 1
return 7 if cross else 5
Resultado:
El camino de navegación suave que queremos que suceda:
El resto de mi código: http://pastebin.com/TL2cEkeX
Actualizar
Esta es la mejor solución que he encontrado hasta ahora:
def heuristic(node, start, goal):
dx1 = node.x - goal.x
dy1 = node.y - goal.y
dx2 = start.x - goal.x
dy2 = start.y - goal.y
cross = abs(dx1*dy2 - dx2*dy1)
dx3 = abs(dx1)
dy3 = abs(dy1)
return 5 + (cross*0.01) * (dx3+dy3) + (sqrt(2)-2) * min(dx3, dy3)
def move_cost(current, node):
cross = abs(current.x - node.x) == 1 and abs(current.y - node.y) == 1
return 7 if cross else 5
Produce el camino deseado a partir de la segunda imagen, pero no maneja muy bien los obstáculos (tiende a arrastrarse por las paredes) y no produce caminos óptimos a veces en distancias más largas.
¿Cuáles son algunos ajustes y optimizaciones que puedo aplicar para mejorarlo?
fuente
Respuestas:
A * te da la ruta más corta en el gráfico. Cuando se usa una cuadrícula como gráfico, a menudo hay múltiples rutas más cortas. En su primer diagrama, ese es uno de los caminos más cortos. Pone todos los movimientos axiales primero y todos los movimientos diagonales después. Pero esa es la misma ruta de longitud que si coloca todas las diagonales primero, o si combina movimientos axiales y diagonales. Todos estos son equivalentemente cortos, y cuál elige A * depende de cómo se escribe el código y cómo se representa el gráfico.
Creo que lo que quieres es:
fuente
El algoritmo A * le permite asignar diferentes costos a los bordes de la ruta. También puede asignar costos según las circunstancias. Esta es su herramienta principal para dar forma a las rutas A * para que se vean como usted quiere que se vean.
Cuando quieras desalentar las diagonales largas, puedes penalizarlas. Agregue un poco de costo por cada vez que el camino vaya en la misma dirección. Cuando haga esto, el algoritmo intentará distribuir automáticamente los pasos diagonales de la manera más uniforme posible en toda la ruta. Solo asegúrese de que este costo adicional nunca sea más el costo de tomar una ventaja adicional, o el algoritmo comenzará a realizar desvíos completamente innecesarios solo para evitar líneas rectas.
Una buena fórmula podría ser:
cost = normal_cost * (1.1 - 0.1 / num_of_steps_in_the_same_direction
)Tenga en cuenta que esto requiere que el costo de la ruta se rastree como valores de punto flotante, no como enteros.
fuente
Adaptando A *
Como dijo Philipp, debe agregar costos cuando la dirección no cambia durante mucho tiempo. Pero, la función de Philipp puede llevar rápidamente a sumar costos adicionales, que son más altos que el costo de atravesar un mosaico adicional. ¡Pero su idea clave es correcta!
Parece fácil adaptar A * para calcular "todos" los caminos óptimos (con la longitud más corta) y luego seleccionar uno de ellos por otra heurística. Pero hay un problema. Si tiene un camino largo, puede haber muchas soluciones con una longitud óptima. Esto hace que el algoritmo A * tarde mucho más en calcular todas estas otras soluciones también. Esto se debe a la cuadrícula. No puede caminar 80 grados en lugar de 90 grados, lo que conduce a múltiples soluciones subóptimas en lugar de una solución óptima. Para la imaginación, imagina un mapa sin obstáculos. La distancia x es 2, la distancia y es 3. Esto significa que todos los caminos más cortos tienen 2 movimientos diagonales y 1 movimiento recto. Hay 3 combinaciones válidas: SDD, DSD, DDS (donde D = diagonal, S = recta) para esta ruta simple. La verdadera "diversión" ya comienza cuando tienes caminos con, por ejemplo, 3 movimientos rectos y 2 diagonales: SSSDD, SSDSD, SSDDS, SDSSD, SDSDS, SDDSS, DSSSD, DSSDS, DSDSS, DDSSS (10 variaciones del camino más corto, si no me perdí ninguna). Creo que deberías haber tenido la idea ...
Por lo tanto, debemos solucionar esto adaptando la función de costo de manera que menos soluciones (o incluso una sola solución) sean "óptimas".
Adaptando la función de costo
Hacer la adaptación como Philipp sugiere en su fórmula de ejemplo le dará resultados mucho mejores, pero aún tiene algunos problemas. No distribuirá uniformemente las "partes" más cortas / más largas a lo largo del camino, lo que significa que los cambios de dirección serán más frecuentes al comienzo del camino o viceversa.
Además, un camino en el que el actor tiene que "girar" sin parar parece ser subóptimo cuando lo observa un humano. Como lleva tiempo (mostrar la animación de giro) y, por lo tanto, debe ser más lento.
Sin embargo, en lugar de utilizar flotantes para los costos, puede implementar un "costo secundario" o criterios de clasificación secundarios. Si los costos primarios son los mismos, el costo secundario se usa para estimar qué solución se prefiere. Esto no hará que aumenten accidentalmente los costos primarios (longitud de la ruta en la medida de la cuadrícula).
fuente