Actualmente estoy haciendo una investigación de búsqueda de rutas y mi simulación es la siguiente: tengo una escena en 3D con un punto de inicio y final representado, soy capaz de crear mallas de navegación, puntos de referencia y polígonos para ayudar con la búsqueda de rutas.
He probado un algoritmo A * y algunas de sus variantes y funcionan perfectamente. Sin embargo, ahora estoy más interesado en la búsqueda de rutas 'dinámicas'. Por ejemplo, mientras encuentro una ruta desde el punto A hasta el punto B, si aparece un nuevo obstáculo de repente, quiero que mi algoritmo pueda volver a planificar de inmediato una ruta y no comenzar a buscar desde cero nuevamente.
He leído un poco sobre el algoritmo D * y me pregunto si esto sería apropiado para lo que necesito o si parece una exageración.
Entonces, mis preguntas son básicamente: ¿Qué algoritmo sería mejor para la búsqueda dinámica de rutas en tiempo real? ¿O qué combinación de técnicas podría utilizar en su lugar?
fuente
Respuestas:
D * está bastante involucrado, no recomiendo intentar implementarlo. Incluso cuando los proyectos están bien financiados y están siendo desarrollados por personas inteligentes / experimentadas, se utiliza D * lite, porque D * es muy difícil hacerlo bien.
Puede interesarle esta presentación, que incluye una discusión sobre la búsqueda de caminos de Left 4 Dead:
http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf
Un enfoque es utilizar una búsqueda general de nivel A * para obtener una ruta general para un agente, y luego realizar una búsqueda detallada de nivel A * para el entorno local de un agente. De esta forma, puede volver a calcular rápidamente la búsqueda A * de detalles del curso si el terreno cambia, y luego volver a calcular rápidamente la búsqueda A * de detalles finos para un pequeño segmento del entorno. Esto no es perfecto Funciona siempre y cuando tus obstáculos no puedan bloquear múltiples nodos del gráfico de detalles del curso, lo cual está bien para la mayoría de los juegos. Este es el método que recomiendo si tiene menos de 100 agentes.
Si desea apoyar a cientos o miles de agentes, puede implementar algo como multitudes continuas. Vea esta investigación: http://grail.cs.washington.edu/projects/crowd-flows/ Que analiza un método basado exclusivamente en la CPU que puede admitir a miles de actores en un entorno dinámico.
Si desea admitir decenas de miles, o cientos de miles de agentes, puede implementar algo como multitudes continuas, con asistencia de GPU. Vea aquí la investigación relevante: https://a248.e.akamai.net/f/674/9206/0/www2.ati.com/misc/siggraph_asia_08/GPUCrowdSimulation_SLIDES.pdf
Aquí hay un video que muestra las multitudes continuas en acción: http://www.youtube.com/watch?v=lGOvYyJ6r1c (Pase a 4:10 para ver grandes obstáculos dinámicos como automóviles y semáforos que afectan a cientos de personas caminando por una ciudad).
fuente
¿Has visto comportamientos de dirección simples?
http://www.red3d.com/cwr/steer/
Puede usarlos para desviarse de su camino A * para evitar obstáculos locales y luego volver a su camino una vez que haya terminado.
También es bastante fácil combinar múltiples comportamientos.
fuente
Dado que su publicación está en la parte de "Desarrollo de juegos" del intercambio de pila, esto es lo que la mayoría de los programadores de juegos le responderían: ¡No se trata de la búsqueda dinámica en tiempo real, se trata de la ruta dinámica en tiempo real * siguiente *!
Algunos casos de borde en los que un borde en su gráfico de navegación está totalmente obstruido requeriría que el buscador de ruta recalcule otra ruta, pero la mayoría de las veces simplemente puede dirigir sus entidades alrededor de los obstáculos, haciendo predicciones de posición y evitando en la dirección correcta. Para la mayoría de los juegos, sería demasiado pesado tener que predecir con el tiempo la posición de los agentes dinámicos, especialmente porque no puedes predecir con precisión las acciones de los jugadores o las decisiones de los agentes.
Entonces, mi consejo sería comenzar implementando Comportamientos de dirección (http://red3d.com/cwr/steer/), manejar los casos en los que el camino se vuelve imposible y luego agregar una capa encima para manejar los casos extremos que no t manejado por las dos soluciones anteriores.
Espero que esto ayude
fuente