Algoritmo rápido para calcular la línea de vista en un juego de RTS

Question

Estoy haciendo un juego de estrategia en tiempo real simple. Quiero que funcione muy rápido porque debería funcionar con miles de unidades y 8 jugadores.

Todo parece funcionar sin problemas, pero parece que el cálculo de la línea de visión es un cuello de botella. Es simple: si una unidad enemiga está más cerca que cualquier rango LOS de mi unidad, estará visible.

Actualmente uso un algoritmo bastante ingenuo: para cada unidad enemiga comprobo si alguna de mis unidades lo está viendo. Es O (n^2)

Entonces, si hay 8 jugadores y tienen 3000 unidades cada uno, eso significaría 3000 * 21000 = 63000000 pruebas por jugador en el peor de los casos. Que es bastante lento

Más detalles: es un espacio 2D simple y estúpido RTS: sin rejilla, las unidades se mueven a lo largo de líneas rectas en todas partes y no hay colisión para que puedan moverse entre sí. Entonces, incluso cientos de unidades pueden estar en el mismo lugar.

Quiero acelerar este algoritmo LOS de alguna manera. ¿Algunas ideas?

EDIT:

detalles adicionales: Así

• que significó un jugador puede tener incluso 3.000 unidades.
• mis unidades tienen radares por lo que todas las direcciones son iguales.

Answer 1

Utilice un spatial data structure para buscar eficientemente unidades por ubicación.

Además, si sólo se preocupan si una unidad es visible, pero no el que la unidad lo descubrió, se puede hacer

for each unit 
    mark the regions this unit sees in your spatial data structure 

y tienen:

isVisible(unit) = isVisible(region(unit)) 

Una estructura de datos espacial muy simple es la grilla: superpone una grilla gruesa sobre el campo de juego. Las regiones son las celdas de esta cuadrícula. Usted asigna una matriz de regiones, y para cada región mantiene una lista de unidades actualmente en esta región.

También puede encontrar Muki Haklay's demonstration of spatial indexes útil.

Answer 2

Una de las reglas más importantes en gamedev es optimizar los juegos de tus algoritmos explotando todas las restricciones posibles que tu juego define: esta es la razón principal por la que no ves juegos tremendamente diferentes construidos encima de cualquier motor de juegos de las empresas, han explotado sus limitaciones de manera tan eficiente que no pueden hacer frente a nada que no esté dentro de estas limitaciones.

Dicho esto, dijiste que las unidades se mueven en línea recta - y dices que los jugadores pueden 3000 unidades - incluso si supongo que son 3000 unidades para ocho jugadores, eso es 375 unidades por jugador, entonces creo que estoy a salvo en asumiendo que en cada paso del juego (y supongo que cada paso involucra el cálculo que describes arriba) que más unidades no cambiarán su dirección que las unidades que cambiarán de dirección.

Por lo tanto, si esto es cierto, entonces quiere dividir todas sus piezas en dos grupos: las que cambiaron de dirección en el último paso y las que no lo hicieron.

Para los que sí lo hicieron, necesita un poco de calibración: para unidades de dos fuerzas opuestas, querrá preguntar: ¿cuándo verá la unidad A la unidad B, dado que ni la unidad A ni la unidad B cambian de dirección o velocidad? ? (puede tratar con aceleración/desaceleración, pero luego se vuelve más complicado) - para calcular esto, primero debe determinar si los vectores que la unidad A y la unidad B están viajando intersectarán (cálculo de intersección de línea 2D simple, combinado con un cálculo que le dice cuándo cada unidad llega a esta intersección) - si no lo hacen, y no pueden verse ahora, entonces nunca se verán a menos que al menos uno de ellos cambie de dirección. Si se cruzan, entonces necesitas calcular la diferencia de tiempo entre cuando la primera y la segunda unidad pasan por el punto de intersección; si esta distancia es mayor que el rango LOS, entonces estas unidades nunca se verán a menos que uno cambie de dirección. si este diferencial es menor que el rango LOS, entonces unos pocos cálculos más (agite las manos vigorosamente) le indicarán cuando tenga lugar este evento bendecido.

Ahora, lo que tiene es una colección de información bifurcada en elementos que nunca se verán y elementos que se verán en algún momento t en el futuro - cada paso, simplemente trata con las unidades que han cambiado dirección y calcular sus interacciones con el resto de las unidades. (Ah, y trate con esas unidades que los cálculos previos le dijeron que se verían entre sí, recuerde mantenerlas en una estructura ordenada insertable) Lo que ha hecho efectivamente es explotar el comportamiento lineal del sistema para cambiar su pregunta de 'no unidad de ver la unidad B' a 'Cuando la unidad voluntad a ver la unidad B'

Ahora, todo esto dicho, esto no es para descontar el espacio respuesta estructura de datos - es una buena respuesta - sin embargo, también es capaz de tratar con unidades en movimiento aleatorio, por lo que debe considerar cómo optimizar aún más este proceso; también debe tener cuidado al tratar con la visibilidad entre regiones, es decir, las unidades en los bordes de dos regiones diferentes pueden ser capaz de verse, si tienes piezas que tienden a agruparse, cantar una estructura de datos espaciales con dimensiones variables podría ser la respuesta, donde las piezas que no están en la misma región tienen la garantía de no poder verse entre sí.

Answer 3

Haría esto con una cuadrícula. Creo que así es como los juegos comerciales de RTS resuelven el problema.

• Discretize the game world for the visibility tracker. (Cuadrícula cuadrada es más fácil. Experimente con la tosquedad para ver qué valor funciona mejor.)
• Registre las unidades actuales en cada área. (Actualice cada vez que una unidad se mueva)
• Registre las áreas que ve cada jugador. (Esto tiene que actualizarse a medida que las unidades se mueven. La unidad podría simplemente sondear para determinar sus fichas visibles. O podrías analizar el mapa antes de que comience el juego ...)
• Haz una lista (o la estructura que corresponda) para el enemigo unidades vistas por cada jugador.

Ahora cada vez que una unidad va de una zona de visibilidad a otro, realizar una comprobación:

• pasó de un invisible a un área visto - añadir a la unidad de seguimiento de la visibilidad del jugador.
• Se movió de un área vista a otra no visible: quite la unidad del rastreador de visibilidad del reproductor.
• En los otros dos casos, no se produjo ningún cambio en la visibilidad.

Esto es rápido pero requiere algo de memoria. Sin embargo, con BitArrays y listas de punteros, el uso de la memoria no debería ser tan malo.

Había un artículo sobre esto en uno de los libros Gems programación de juegos (uno de los tres primeros, creo.)