encontrar caminos con obstáculos en un juego de Warcraft 3

Considere A * buscando en un mapa basado en mosaicos. Un código directo sería: si hay una unidad dentro de esa celda, entonces es inalcanzable, está bien.

Pero hay un problema de resolución de mapas. Cuando miro a Warcraft 3, los monstruos y las estructuras tienen un radio diferente, y puedes caminar muy cerca, que es más como un vector, ¿cómo se implementó?

Además, ¿cuál es la solución estándar para incorporar la detección de colisión de obstáculos en movimiento con un algoritmo de búsqueda de ruta, como Warcraft 3?

No puedo decir con certeza qué tipo de enfoque fue utilizado por los desarrolladores de WC3, pero se parece bastante a Hierarchical Annotated A *. El radio de la unidad definido en el WC3Editor se usó tal cual para la escala del modelo 3D, pero el tamaño real de la unidad para la búsqueda de ruta fue discreto, tal vez algo así como unitSize = (int) (unitRadius / 10). No estaba basado en vectores, eso es seguro.

Digamos que hay muchos nodos de ruta que forman una cuadrícula de nodos de alta resolución. La unidad simple como un necrófago tiene un tamaño de 2, por lo que para colocarla en algún lugar de una cuadrícula necesitamos 4 nodos de camino libre cerca uno del otro. Un héroe caballero de la muerte es un poco más grande con un tamaño de 3, ocupando 9 nodos de ruta en total. Ahora colocamos 2 zigurats juntos dejando un espacio de 2 nodos en todo el medio, y enviamos un ghoul y un caballero de la muerte al otro lado. Ghoul podrá pasar entre dos zigurats, mientras que el caballero de la muerte tendrá que moverse. ¿Cómo se puede determinar?

Para ver si un nodo puede acomodar una unidad de tamaño específico, asignemos un valor de autorización especial a cada nodo que defina un tamaño de unidad máximo permitido. Básicamente, significa que se realizaron varias verificaciones de límite para un nodo, y los límites más grandes posibles se recordaron como la autorización del nodo. Entonces, cuando queremos colocar un caballero de la muerte en algún nodo, se vuelve tan simple como comparar la separación del nodo con el tamaño del caballero de la muerte. Por supuesto, las cosas se volverán mucho más complejas cuando haya varias unidades saltando compitiendo por nodos, pero esa es otra historia.

Para más detalles, puede consultar este artículo:

http://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/

Usaría el mosaico para crear mallas de navegación de regiones AKA. Este artículo explica el concepto con diagramas completos.

Todavía puede mantener A * como su enfoque de búsqueda de ruta, sin embargo, su red ya no es una cuadrícula (gráfico conectado a 4), sino un gráfico que representa la conectividad arbitraria entre sus regiones poligonales. Por lo tanto, tendrá que adaptar su algoritmo a su gusto.