Mapeo eficiente de posiciones de entidades de juego en Java

Question

En Java (Swing), supongo que tengo un juego en 2D en el que tengo varios tipos de entidades en la pantalla, como un jugador, tipos malos, mejoras, etc. Cuando el El jugador se mueve a través de la pantalla, para hacer un control eficiente de lo que está en las inmediaciones del jugador, creo que me gustaría tener acceso indexado a las cosas que están cerca del personaje en función de su posición.

Por ejemplo, si los pasos jugador 'P' sobre el elemento 'E' en el siguiente ejemplo ...

| | | | | | 
| | | |P| | 
| | |E| | | 
| | | | | | 

... sería hacer algo como:

if(player.getPosition().x == entity.getPosition().x && 
       entity.getPosition.y == thing.getPosition().y) 
{ 
    //do something 
} 

Y eso está bien, pero eso implica que las entidades mantienen sus posiciones, y por lo tanto, si tuviera MUCHAS entidades en la pantalla, tendría que recorrer todas las posibles entidades disponibles y verificar la posición de cada una de ellas frente a la posición del jugador. Esto parece realmente ineficiente, especialmente si comienzas a recibir toneladas de entidades.

Así, sospecharía que me gustaría algún tipo de mapa como

Map<Point, Entity> map = new HashMap<Point, Entity>(); 

y almacenar la información de mi punto de allí, para que pudiera acceder a estas entidades en un tiempo constante. El único problema con ese enfoque es que, si quiero mover una entidad a un punto diferente en la pantalla, tendría que buscar a través de los valores de HashMap para la entidad que quiero mover (ineficiente ya que no sé su Point position before time), y luego una vez que lo encuentre, quítelo de HashMap y vuelva a insertarlo con la nueva información de posición.

¿Alguna sugerencia o consejo sobre qué tipo de estructura de datos/formato de almacenamiento debería utilizar aquí para tener un acceso eficiente a las entidades en función de su posición, así como las posiciones basadas en la entidad?

Answer 1

La partición de espacio podría ser efectiva.

Puede hacer divisiones fijas, como una cuadrícula uniforme, o una cuadrícula ponderada si exceptúa que existen puntos calientes en su mapa donde las cosas se agrupan inusualmente. Para cada partición ocupada, cree un contenedor de todas las entidades que contiene.

La inserción es a tiempo constante. La eliminación es una fracción prácticamente infinitesimal de n (su número total de entidades) asumiendo n es muy grande y ha configurado sus particiones de manera eficiente. Las búsquedas de proximidad comparten el mismo tiempo de ejecución que las eliminaciones. Todavía técnicamente O ( n) sin embargo, la fracción es pequeña. Esto se haría evidente si una partición alguna vez se llenara de gente.

Para obtener una lista de todas las entidades dentro x unidades de una entidad, primero debe obtener una lista de todas las particiones atravesado por una amplia plaza cuadrada de 2 x centrada en su entidad. Si usa una partición de cuadrícula, esto es bastante trivial.A continuación, recorre todas las entidades en esas particiones y devuelve cada una con una distancia de x o menos a la entidad en cuestión.

Un método más complicado de partición es particionar dinámicamente el espacio en un árbol, asegurando que ninguna partición pueda contener más de un número dado de entidades. Si una partición se llena, la divide a lo largo de la media espacial y crea dos particiones espaciales, de modo que cada una contiene la mitad de las entidades de la partición original. Esto hace que las inserciones y búsquedas tengan un tiempo de ejecución logarítmico ya que ya no puede descubrir las particiones deseadas en tiempo constante, pero las eliminaciones se convierten en tiempo constante dadas las poblaciones de particiones limitadas.

Answer 2

ineficaz puesto que no sé su posición de punto antes de tiempo
Estoy en lo cierto, que el objeto de entidad no tiene información de posición en ella? Sugeriría agregarlo. O bien, de lo contrario, puede tener un mapa de las posiciones de entidades actuales Map<EntityIdType, Point> y buscar la posición primero. Nada sofisticado.

Answer 3

Si hay un mapeo uno a uno entre Entity y Point, y desea poder mapear en ambas direcciones, entonces un bimap es la estructura de datos más natural.

Guava tiene una implementación BiMap<K,V>, que admite una operación de vista BiMap<V,K> inverse(). Es solo una vista, por lo que no es costoso en absoluto.

O bien puede administrar su propio Map<Entity,Point> y Map<Point,Entity>, pero eso sería reinventar la rueda.