Estructura de datos bidireccionales para esta situación

Question

Estoy estudiando una pequeña parte de mi motor de juego y preguntándome cómo optimizar algunas partes.

La situación es bastante simple y es la siguiente:

• Tengo un mapa de Tile s (almacenados en una matriz bidimensional) (~ azulejos 260k, pero supongo que muchos más)
• tengo una lista de Item s que siempre están en al menos ya lo sumo un azulejo
• un Tile puede contener lógicamente cantidad infinita de Item s
• Durante la ejecución del juego muchos Item s son continuas Ly creado y comienzan a partir de su propia Tile
• Cada Item cambia continuamente su Tile a uno de los vecinos (arriba, derecha, abajo, izquierda)

Hasta ahora cada Item tiene una referencia a su real Tile y solo guardo una lista de artículos. Cada vez que un Item se mueve a un mosaico adyacente, simplemente actualizo item->tile = .. y estoy bien. Esto funciona bien, pero es unidireccional.

Al extender el motor me di cuenta de que tenía que encontrar todos los elementos contenidos en un mosaico muchas veces y esto degradaba el rendimiento (especialmente en algunas situaciones en las que tengo que encontrar todos los elementos para un rango de mosaicos, uno a uno).

Esto significa Me gustaría encontrar una estructura de datos adecuada para encontrar todos los elementos de una específica Tile mejor que en O (n), pero me gustaría evitar gran parte de arriba en el "pasar de una baldosa para otra "fase (ahora solo asigna un puntero, me gustaría evitar hacer muchas operaciones allí, ya que es bastante frecuente).

Estoy pensando en una estructura de datos personalizada para explotar el hecho de que los elementos siempre se mueven a la celda vecina, pero actualmente estoy buscando a tientas en la oscuridad. Cualquier consejo sería apreciado, incluso enfoques engañosos o crípticos. Lamentablemente, no puedo simplemente desperdiciar memoria, por lo que es necesario un buen intercambio.

Lo estoy desarrollando en C++ con STL pero sin Boost. (Sí, lo sé sobre multimap, no me satisface, pero lo intentaré si no encuentro nada mejor)

Answer 1

struct Coordinate { int x, y; }; 
map<Coordinate, set<Item*>> tile_items; 

Este mapas de coordenadas en el mapa azulejo para conjuntos de punteros artículo que indican los elementos que se encuentran en esa ficha. No necesitaría una entrada para cada coordenada, solo las que realmente tienen elementos en ellas. Ahora, sé que usted ha dicho esto:

pero me gustaría evitar muchos gastos en el "pasar de una baldosa a otro" fase

Y este método implicaría la adición de más sobrecarga en ese fase. Pero, ¿realmente has intentado algo así todavía y has determinado que es un problema?

Answer 2

Para mí, envolvería un std::vector en un tipo de matriz (IE impone acceso 2d en una matriz 1d) esto le da acceso rápido y aleatorio a cualquiera de sus teselas (la implementación de la matriz es trivial).

uso

vector_index=y_pos*y_size+x_pos; 

al índice de un vector de tamaño

vector_size=y_size*x_size; 

A continuación, cada elemento puede tener un std :: vector de elementos (si la cantidad de artículos tiene un azulejo es muy dinámico tal vez a deque) de nuevo, estos son de acceso aleatorio y contienen una sobrecarga mínima.

Me mantendría alejado de contenedores indirectos para su caso de uso.

PD: si lo desea, puede tener mi plantilla de matriz.

Answer 3

Si realmente piensas que tener cada tienda de azulejos sus artículos te costará demasiado espacio, considera usar un quadtree para almacenar los artículos. Esto le permite obtener de manera eficiente todos los elementos en un mosaico, pero deja su cuadrícula de mosaico en su lugar para el movimiento del artículo.