He estado tratando de descubrir cómo implementar algo como la búsqueda de caminos en Starcraft 2. No estoy buscando todas las características sofisticadas como el agrupamiento, las colas, etc. De hecho, me gusta cómo en Starcraft 1 las unidades interferirían con cada una otro. Pero sí quiero un buscador de ruta mejor que el utilizado en Starcraft 1.
De las búsquedas en Google que hice, las diversas respuestas tienen algo que ver con A * a través de una malla de navegación y / o con algún tipo de "gráfico de visibilidad". Pero he recibido respuestas algo conflictivas o poco claras sobre lo que debo hacer.
Una cosa sobre la que leí tiene algo que ver con hacer A * sobre los vértices de una malla triangular (la malla de navegación). Y luego de alguna manera "enderezar el camino", que no sé cómo hacer. Pero eso no garantiza la optimización, ¿verdad?
Otra pregunta que tuve fue: ¿cómo aborda la trayectoria de Starcraft 2 el hecho de que las unidades son discos con un radio finito y no puntos cuando se trata de esquinas? Y cómo lidiar con obstáculos dinámicos como unidades inactivas o incluso otras unidades móviles.
Estoy buscando una explicación detallada y arenosa y no las descripciones genéricas de nivel súper alto que son típicas en los resultados de búsqueda.
Si es importante, ya he visto las notas de Amit sobre la búsqueda de caminos . He oído hablar de Geometría Computacional: Algoritmos y Aplicaciones, pero no la he leído . Y una publicación de blog sobre una presentación de navegación de AI en GDC 2011 mencionó que Starcraft 2 usa una triangulación de delaunay restringida para una malla de navegación. Aunque la publicación del blog menciona la dirección de Boids y el "análisis del horizonte", no menciona exactamente cómo se realiza la búsqueda de ruta central en la malla de navegación.
fuente
Respuestas:
Si tienes instalado Starcraft 2, abre el editor de mapas y alterna la búsqueda de ruta . Podrá ver cómo se construye la malla de navegación a medida que coloca edificios y otros obstáculos.
No debería ser un problema: la búsqueda de caminos de Starcraft 1 fue una tontería. Esta publicación de blog de uno de los programadores habla sobre ello.
Se trata de hacer que la IA no sea más tonta que óptima. Sus unidades terminan con movimientos en zig-zag entre nodos si no aplica un poco de suavizado.
Al planificar la ruta, tendrá una etapa de refinamiento en la que verá los nodos por los que su unidad necesita caminar para llegar a su objetivo, y luego comenzará a eliminar los nodos en exceso en el medio de la ruta que no necesitamos. seguir, es decir, podemos ir directamente del nodo A al nodo C a través de B sin colisiones estáticas, así que ignore B por completo.
Esto termina enderezando el camino.
Si quieres una explicación sólida, esto ya está bien cubierto en los libros (incluso con un código de juego que funcione). Entonces, si tiene algo de dinero para gastar, eche un vistazo a Programming Game AI By Example y / o Artificial Intelligence for Games . Ambos discuten estos temas en gran profundidad.
fuente