2D pathfinding - encontrar caminos suaves

10

Estaba tratando de implementar una ruta simple, pero el resultado es menos satisfactorio de lo que pretendía lograr. La cosa es que las unidades en juegos como Starcraft 2 se mueven en todas las direcciones, mientras que las unidades en mi caso solo se mueven en la mayoría de las 8 direcciones (estilo Warcraft 1) ya que estas 8 direcciones dirigen a los siguientes nodos disponibles (se mueven de una ficha a la siguiente ficha adyacente) . ¿Qué debo hacer para lograr el resultado como en Starcraft 2? ¿Reducir el tamaño del azulejo?

http://i.stack.imgur.com/lr19c.jpg

En la imagen, puede ver una línea horizontal de mosaicos de roca que son obstáculos, y el camino encontrado marcado como mosaicos verdes. La línea roja es el camino que quiero lograr.

game-design game-mechanics path-finding Kooi Nam Ng
fuente
Soy un gran admirador de la búsqueda de puntos de salto, aunque todavía no he encontrado el tiempo para implementarla. Pero la documentación fue interesante y tiene un buen rendimiento.
2
¿Estás seguro de que ese es tu camino deseado? Las unidades que lo usen atravesarán parcialmente las paredes. Lo hice más visible en otro ejemplo: i.imgur.com/eh4ZR.png Y esto es lo que probablemente realmente quieras lograr: i.imgur.com/vFQg4.png
Markus von Broady
Tienes razón. Mi camino tenía fallas, pero era más para fines ilustrativos. Gracias por señalar la mejor manera de mirar.
Kooi Nam el
Tendrás que tener coordenadas fraccionarias dentro de un mosaico para obtener lo que deseas. Ningún camino posible sin esto funcionaría: transportar las fracciones pero no mostrarlas haría que su unidad se mueva en línea recta / diagonal / recta / diagonal.
Loren Pechtel el
@LorenPechtel estás equivocado, puedes suavizar el camino después de encontrar uno. Es bastante fácil ya que crea dos líneas basadas en las dimensiones de la unidad y comprueba si se cruzan con los mosaicos entre tile0 y tileN, donde tile1-tile (N-1) son mosaicos que desea eliminar de la ruta.
Markus von Broady

Respuestas:

8

Para un buen algoritmo de búsqueda de rutas, usar A * probablemente sería una buena idea, sin embargo, para un juego simple que no requiere una búsqueda de rutas sofisticada, eficiente ni efectiva, simplemente hacer que los personajes se muevan hacia un objetivo descubriendo la dirección de El objetivo debe ser suficiente.

Lo que puede hacer es generar un 'gráfico de visibilidad' (qué otros puntos son visibles desde cada punto) desde los vértices y luego realizar A * en el gráfico. Esto funciona porque el camino más corto siempre estará en el gráfico de visibilidad.

Reducir el tamaño del azulejo puede ayudarlo.

Recursos

Otras lecturas

EDITAR: Me gusta el comentario de @ MarkusvonBroady.

"en realidad se trata de suavizar el camino, no encontrarlo. El camino que se encuentra en la imagen se ve bien".

Recursos

De @MarkusvonBroady

Hice una búsqueda, encuentre los siguientes (eso puede ayudarlo)

Md Mahbubur Rahman
fuente
1
excelentes enlaces, +1 de mi parte
lhk
2
@ MarkusvonBroady, gracias por -1. He aprendido de ti. No quiero un punto, sino que estoy dispuesto a aprender y compartir el correcto. Creo que al discutir podemos encontrar el correcto. :)
Md Mahbubur Rahman
@ MarkusvonBroady, ¿podría compartir varios recursos del algoritmo de suavizado de ruta?
Md Mahbubur Rahman
En realidad, creo que esta respuesta ayuda al OP. No creo que el OP estuviera pidiendo un suavizado real (interpolación de splines o similar), sino que su algoritmo actualmente está encontrando un camino horriblemente no óptimo y necesita ser "suavizado" en una línea más recta. Que A * habría encontrado naturalmente para él sin ningún suavizado adicional.
Sean Middleditch el
Había estado usando A * y creo que había encontrado el camino óptimo.
Kooi Nam el
0

Comenzando desde un extremo de la ruta sin procesar, por ejemplo path[0], puede eliminar path[1]si el segmento se formó uniendo los puntos de path[0]y path[2]NO intersecta ninguna pared. Ir más allá hasta el último segmento proporcionará un camino más simple.

Esto no solo suavizará el camino sino que también eliminará algunos puntos inútiles, como el ejemplo de fuego, 3 segmentos consecutivos de una línea recta.

arainone
fuente