Estructura de datos (o algoritmo) para búsquedas rápidas de entidades basadas en distancia

8

Por ejemplo, tu juego tiene 100 enemigos (en diferentes equipos) corriendo y su IA quiere inspeccionar las entidades cercanas para ver a qué debería atacar. ¿Cuál es una forma rápida de organizar esas entidades para que cada enemigo no tenga que calcular la distancia entre él y todas las demás entidades?

En resumen, ¿cuál es una forma rápida para que una entidad de IA responda la pregunta "¿Quién está cerca de mí?"

khayman218
fuente
intente usar árboles cuádruples
Ali1S232

Respuestas:

8

Desea un índice espacial como quadtree (2D) u octree (3D).

Será
fuente
1
@FxIII No estoy seguro de seguir todo lo que estás hablando. Estas estructuras de datos de árboles espaciales están específicamente diseñadas para responder a la pregunta del afiche, y se comprenden y utilizan bien.
Será
5

La solución más simple es una cuadrícula. . Coloque una cuadrícula 2D sobre su nivel. Cada celda de la cuadrícula mantiene una colección de las entidades que la ocupan actualmente. A medida que las entidades se mueven, sáquelas de la celda que están dejando y agréguelas a la que ingresan.

Luego puede encontrar entidades cercanas simplemente examinando las celdas cercanas. Un quadtree refina esto subdividiendo recursivamente la cuadrícula, pero a veces una plana es adecuada, especialmente si el tamaño de su nivel es fijo y relativamente pequeño.

munificente
fuente