Dividir A * ruta de muchas unidades en marcos de juegos separados

Question

Así que mi problema es que, para grandes grupos de unidades, intentar encontrar todas ellas en el mismo marco está causando una desaceleración bastante notable. Cuando se navega por 1 o 2 unidades, la desaceleración generalmente no se nota, pero para muchos más que eso, dependiendo de la complejidad de la ruta, puede ser muy lenta.

Mientras que mi A * probablemente podría permitirse un poco de puesta a punto, también sé que otra forma de acelerar la ruta es simplemente dividir el pathfinding en varios marcos de juego. ¿Cuál es un buen método para lograr esto?

Disculpe si esta es una pregunta obvia o fácil de buscar, realmente no podría pensar en cómo ponerla en una cadena de búsqueda.

Más información: Esta es A * en una cuadrícula rectilínea, y se programó utilizando C# y el marco XNA. Planeo tener potencialmente entre 50 y 75 unidades que necesiten rutas.

Gracias.

Answer 1

Escalabilidad

Hay varias formas de optimizar de esta situación. Por un lado, es posible que no tenga que dividirse en varios marcos de juego. Hasta cierto punto, parece que la escalabilidad es el problema. 100 unidades es al menos 100 veces más caro que 1 unidad.

Entonces, ¿cómo podemos hacer que la ruta esté más optimizada para la escalabilidad? Bueno, eso depende del diseño de tu juego. Voy a (quizás erróneamente) asumir un escenario RTS típico. Varios grupos de unidades, con cada grupo relativamente cerca en la proximidad. La solución de ruta para muchas unidades en las proximidades será bastante similar. Las unidades podrían solicitar rutas desde algún tipo de solucionador de rutas. Este solucionador de rutas podría mantener una tabla de solicitudes de itinerarios recientes y sus soluciones y evitar calcular la misma salida de la misma entrada varias veces. Esto se llama memoization.

Otra adición a esto podría implicar hacer una jerarquía fuera de su cuadrícula o gráfico. Primero resuelve el gráfico más simple, luego cambia a un gráfico más detallado. Las unidades múltiples podrían usar la misma ruta de baja resolución, aprovechando la memorización, pero cada una calcula su propia ruta de alta resolución individualmente si las rutas de alta resolución son demasiado numerosas para memorizar de forma razonable.

Cálculos de fotogramas múltiples

cuanto a tratar de dividir los cálculos entre los marcos, hay algunos enfoques que se me ocurre de la mano fuera.

Si desea tomar la ruta de subprocesos múltiples, puede utilizar un modelo de agrupación de subprocesos de trabajador. Cada vez que una unidad solicita una ruta, se pone en cola para una solución. Cuando un hilo de trabajo es libre, se le asigna una tarea para resolver. Cuando el hilo resuelve la tarea, puede tener una devolución de llamada para informar a la unidad o puede hacer que la unidad pregunte si la tarea está completa de alguna manera, lo más probable es que haya consultado cada cuadro.

Si no hay obstáculos dinámicos o se manejan por separado, puede tener un estado constante que utiliza el solucionador de ruta. Si no es así, habrá una cantidad no despreciable de complejidad y quizás incluso se escuche que estos hilos bloqueen la información del estado del juego mutable. Las rutas se pueden volver inválidas de un cuadro al siguiente y requieren una nueva validación de cada cuadro. Multi-threading puede terminar siendo un extra-overhead sin sentido donde, debido al bloqueo y la sincronización, los hilos rara vez se ejecutan en paralelo. Es solo una posibilidad.

Como alternativa, puede diseñar sus algoritmos de búsqueda de ruta para ejecutar en pasos discretos. Después de n cantidad de pasos, verifique la cantidad de tiempo transcurrido desde el inicio del algoritmo. Si excede una cierta cantidad de tiempo, el algoritmo de ruta guarda su progreso y regresa. El código de llamada podría verificar si el algoritmo se completó o no. En el siguiente cuadro, reanudar el algoritmo de ruta desde donde estaba. Repita hasta que se resuelva.

Incluso con el enfoque voluntario de un solo subproceso para resolver rutas, si los cambios en el estado del juego afectan la validez de las rutas de cuadro a cuadro, tendrá que volver a validar las soluciones actuales en un marco para enmarcar la base.

utilizar soluciones parciales

Con cualquiera de los métodos anteriores, puede encontrarse con el problema de las unidades mandó ir a algún lugar al ralentí durante varios fotogramas antes de tener una solución completa encauzamiento. Esto puede ser aceptable y prácticamente indetectable en circunstancias típicas. Si no es así, podría intentar usar la solución incompleta tal como está. Si cada solución incompleta difiere demasiado, las unidades se comportarán de forma indecisa sin embargo. En la práctica, esta "indecisión" tampoco puede ocurrir con la suficiente frecuencia como para causar preocupación.

Answer 2

Si sus unidades están viajando al mismo destino, esta respuesta puede ser aplicable, de lo contrario, será solo de reflexión.

Utilizo un algoritmo de distancia de amplitud para las unidades de ruta. Comience en su destino y marque la distancia desde 0. Todas las celdas adyacentes son 1, las celdas adyacentes a ellas son 2, etc. No atraviese obstáculos y recorra todo el tablero. Usualmente la complejidad del tiempo O (A) donde A es el área de las juntas.

Luego, cuando quiera determinar a qué dirección debe ir una unidad, simplemente encuentra la casilla con la distancia mínima al destino. O (1) complejidad del tiempo. Utilizaré este algoritmo de ruta para juegos de defensa de torre con bastante frecuencia porque su complejidad de tiempo depende completamente del tamaño del tablero (generalmente bastante pequeño en juegos TD) en vez del número de unidades (generalmente bastante grandes). Le permite al jugador definir su propio camino (una buena característica), y solo necesito ejecutarlo una vez por ronda debido a la naturaleza del juego.