¿Cuál es el contenedor más eficiente para almacenar objetos dinámicos del juego? [cerrado]

20

Estoy haciendo un juego de disparos en primera persona y conozco muchos tipos diferentes de contenedores, pero me gustaría encontrar el contenedor más eficiente para almacenar objetos dinámicos que se agregarán y eliminarán del juego con bastante frecuencia. Balas EX.

Creo que, en ese caso, sería una lista para que la memoria no sea contigua y nunca haya ningún cambio de tamaño. Pero también estoy contemplando el uso de un mapa o conjunto. Si alguien tiene alguna información útil, lo agradecería.

Estoy escribiendo esto en c ++ por cierto.

También se me ocurrió una solución que creo que funcionará.

Para comenzar, voy a asignar un vector de gran tamaño ... digamos 1000 objetos. Voy a realizar un seguimiento del último índice agregado en este vector para saber dónde está el final de los objetos. Luego, también crearé una cola que contendrá los índices de todos los objetos que se "eliminan" del vector. (No se realizará una eliminación real, solo sabré que esa ranura está libre). Entonces, si la cola está vacía, agregaré al último índice agregado en el vector + 1, de lo contrario, agregaré al índice del vector que estaba al frente de la cola.

msawayda
fuente
¿Algún idioma específico al que se dirige?
Phill.Zitt
Esta pregunta es demasiado difícil de responder sin muchos más detalles, incluida la plataforma de hardware, el lenguaje / marcos, etc.
PlayDeezGames
1
Consejo profesional, puede almacenar la lista gratuita en la memoria de los elementos eliminados (por lo que no necesita la cola adicional).
Jeff Gates
2
¿Hay alguna pregunta en esta pregunta?
Trevor Powell
Tenga en cuenta que no tiene que hacer un seguimiento del índice más grande ni tener que preasignar una serie de elementos. std :: vector se encarga de todo eso por ti.
API-Beast

Respuestas:

33

La respuesta siempre es usar una matriz o std :: vector. Los tipos como una lista vinculada o un std :: map suelen ser absolutamente horrendos en los juegos, y eso definitivamente incluye casos como colecciones de objetos de juego.

Debe almacenar los objetos mismos (no punteros) en la matriz / vector.

Usted desea memoria contigua. Realmente realmente lo quieres. La iteración sobre cualquier dato en memoria no contigua impone una gran cantidad de errores de caché en general y elimina la capacidad del compilador y la CPU para realizar una captación previa efectiva de caché. Esto solo puede matar el rendimiento.

También desea evitar asignaciones de memoria y desasignaciones. Son muy lentos, incluso con un asignador de memoria rápido. He visto que los juegos obtienen un aumento de FPS de 10x simplemente eliminando unos cientos de asignaciones de memoria en cada cuadro. No parece que deba ser tan malo, pero puede serlo.

Por último, la mayoría de las estructuras de datos que le interesan para administrar objetos de juego pueden implementarse de manera mucho más eficiente en una matriz o un vector que en un árbol o una lista.

Por ejemplo, para eliminar objetos del juego, puedes usar swap-and-pop. Implementado fácilmente con algo como:

std::swap(objects[index], objects.back());
objects.pop_back();

También puede marcar los objetos como eliminados y poner su índice en una lista gratuita para la próxima vez que necesite crear un nuevo objeto, pero hacer el intercambio y el pop es mejor. Le permite hacer un bucle for simple sobre todos los objetos vivos sin ramificación aparte del bucle en sí. Para la integración física de balas y similares, esto puede ser un aumento significativo del rendimiento.

Más importante aún, puede encontrar objetos con un simple par de búsquedas de tabla desde un único estable utilizando la estructura del mapa de ranuras.

Sus objetos de juego tienen un índice en su matriz principal. Se pueden buscar de manera muy eficiente con solo este índice (mucho más rápido que un mapa o incluso una tabla hash). Sin embargo, el índice no es estable debido al intercambio y pop al eliminar objetos.

Un mapa de tragamonedas requiere dos capas de indirección, pero ambas son simples búsquedas de matriz con índices constantes. Son rápida . Realmente rápido.

La idea básica es que tiene tres matrices: su lista de objetos principal, su lista de indirección y una lista libre para la lista de indirección. Su lista principal de objetos contiene sus objetos reales, donde cada objeto conoce su propia identificación única. La identificación única se compone de un índice y una etiqueta de versión. La lista de indirección es simplemente una matriz de índices para la lista de objetos principal. La lista gratuita es una pila de índices en la lista de indirección.

Cuando crea un objeto en la lista principal, encuentra una entrada no utilizada en la lista de indirección (usando la lista libre). La entrada en la lista de indirección apunta a una entrada no utilizada en la lista principal. Inicializa su objeto en esa ubicación y establece su ID única en el índice de la entrada de la lista de indirección que eligió y la etiqueta de versión existente en el elemento de la lista principal, más uno.

Cuando destruye un objeto, realiza el intercambio y despliegue de forma normal, pero también incrementa el número de versión. Luego también agrega el índice de la lista de indirección (parte de la ID única del objeto) a la lista libre. Al mover un objeto como parte del intercambio y pop, también actualiza su entrada en la lista de indirección a su nueva ubicación.

Pseudocódigo de ejemplo:

Object:
  int index
  int version
  other data

SlotMap:
  Object objects[]
  int slots[]
  int freelist[]
  int count

  Get(id):
    index = indirection[id.index]
    if objects[index].version = id.version:
      return &objects[index]
    else:
      return null

  CreateObject():
    index = freelist.pop()

    objects[count].index = id
    objects[count].version += 1

    indirection[index] = count

    Object* object = &objects[count].object
    object.initialize()

    count += 1

    return object

  Remove(id):
    index = indirection[id.index]
    if objects[index].version = id.version:
      objects[index].version += 1
      objects[count - 1].version += 1

      swap(objects[index].data, objects[count - 1].data)

La capa de indirección le permite tener un identificador estable (el índice en la capa de indirección, donde las entradas no se mueven) para un recurso que se puede mover durante la compactación (la lista de objetos principal).

La etiqueta de versión le permite almacenar una ID en un objeto que podría eliminarse. Por ejemplo, tiene la identificación (10,1). El objeto con el índice 10 se elimina (por ejemplo, su bala golpea un objeto y se destruye). El objeto en esa ubicación de memoria en la lista de objetos principal tiene su número de versión eliminado, dándole (10,2). Si intenta buscar (10,1) nuevamente desde una ID obsoleta, la búsqueda devuelve ese objeto a través del índice 10, pero puede ver que el número de versión ha cambiado, por lo que la ID ya no es válida.

Esta es la estructura de datos más rápida que puede tener con una ID estable que permite que los objetos se muevan en la memoria, lo cual es importante para la localidad de datos y la coherencia de la memoria caché. Esto es más rápido que cualquier implementación de una tabla hash posible; una tabla hash, como mínimo, necesita calcular un hash (más instrucciones que una búsqueda de tabla) y luego debe seguir la cadena hash (ya sea una lista vinculada en el horrible caso de std :: unordered_map o una lista de direcciones abiertas en cualquier implementación no estúpida de una tabla hash), y luego tiene que hacer una comparación de valores en cada clave (no más costosa, pero posiblemente menos costosa, que la verificación de la etiqueta de versión). Una tabla hash muy buena (no la que se encuentra en ninguna implementación de la STL, ya que la STL exige una tabla hash que se optimice para diferentes casos de uso de los que se usa para una lista de objetos del juego) podría ahorrar en una dirección indirecta,

Hay varias mejoras que puede hacer al algoritmo base. Usando algo como std :: deque para la lista de objetos principal, por ejemplo; una capa adicional de indirección, pero permite que los objetos se inserten en una lista completa sin invalidar ningún puntero temporal que haya adquirido del mapa de ranuras.

También puede evitar almacenar el índice dentro del objeto, ya que el índice se puede calcular a partir de la dirección de memoria del objeto (esto - objetos), y aún mejor solo es necesario cuando se elimina el objeto, en cuyo caso ya tiene la identificación del objeto (y por lo tanto índice) como parámetro.

Disculpas por la redacción; No creo que sea la descripción más clara que podría ser. Es tarde y es difícil de explicar sin pasar más tiempo del que tengo en ejemplos de código.

Sean Middleditch
fuente
1
Está intercambiando un derecho adicional adicional y un alto costo de asignación / libre (intercambio) por cada acceso por almacenamiento 'compacto'. En mi experiencia con los videojuegos, eso es un mal negocio :) YMMV, por supuesto.
Jeff Gates
1
En realidad, no se hace la desreferencia tan a menudo en escenarios del mundo real. Cuando lo haga, puede almacenar el puntero devuelto localmente, especialmente si usa la variante deque o sabe que no creará nuevos objetos mientras tenga el puntero. Iterar sobre las colecciones es una operación muy costosa y frecuente, necesita la identificación estable, desea compactación de memoria para objetos volátiles (como balas, partículas, etc.), y la indirección es muy eficiente en el hardware del módem. Esta técnica se utiliza en más de unos pocos motores comerciales de muy alto rendimiento. :)
Sean Middleditch
1
En mi experiencia: (1) Los videojuegos se juzgan por el peor rendimiento del caso, no por el rendimiento promedio del caso. (2) Normalmente tiene 1 iteración sobre una colección por cuadro, por lo que la compactación simplemente 'hace que su peor caso sea menos frecuente'. (3) A menudo tiene muchas asignaciones / liberaciones en un solo cuadro, un alto costo significa que limita esa capacidad. (4) Tienes derefs ilimitados por cuadro (en los juegos en los que he trabajado, incluido Diablo 3, a menudo el deref fue el costo de operación más alto después de una optimización moderada,> 5% de la carga del servidor). ¡No pretendo descartar otras soluciones, solo señalar mis experiencias y razonamientos!
Jeff Gates
3
Me encanta esta estructura de datos. Me sorprende que no sea más conocido. Es simple y resuelve todos los problemas que me han estado golpeando la cabeza durante meses. Gracias por compartir.
Jo Bates el
2
Cualquier novato que lea esto debe tener mucho cuidado con este consejo. Esta es una respuesta muy engañosa. "La respuesta siempre es usar una matriz o std :: vector. Los tipos como una lista vinculada o un std :: map suelen ser absolutamente horrendos en los juegos, y eso definitivamente incluye casos como colecciones de objetos de juego". Es muy exagerado. No hay una respuesta "SIEMPRE", de lo contrario, estos otros contenedores no se habrían creado. Decir que los mapas / listas son "horrendos" también es una hipérbole. Hay MUCHOS videojuegos que los usan. "Más eficiente" no es "Más práctico" y puede interpretarse erróneamente como un "Mejor" subjetivo.
user50286
12

matriz de tamaño fijo (memoria lineal)
con lista libre interna (O (1) alloc / free, indicaciones estables)
con claves de referencia débiles (reutilización de la ranura invalida la clave)
cero desreferencias generales (cuando se conoce como válido)

struct DataArray<T>
{
  void Init(int count); // allocs items (max 64k), then Clear()
  void Dispose();       // frees items
  void Clear();         // resets data members, (runs destructors* on outstanding items, *optional)

  T &Alloc();           // alloc (memclear* and/or construct*, *optional) an item from freeList or items[maxUsed++], sets id to (nextKey++ << 16) | index
  void Free(T &);       // puts entry on free list (uses id to store next)

  int GetID(T &);       // accessor to the id part if Item

  T &Get(id)            // return item[id & 0xFFFF]; 
  T *TryToGet(id);      // validates id, then returns item, returns null if invalid.  for cases like AI references and others where 'the thing might have been deleted out from under me'

  bool Next(T *&);      // return next item where id & 0xFFFF0000 != 0 (ie items not on free list)

  struct Item {
    T item;
    int id;             // (key << 16 | index) for alloced entries, (0 | nextFreeIndex) for free list entries
  };

  Item *items;
  int maxSize;          // total size
  int maxUsed;          // highest index ever alloced
  int count;            // num alloced items
  int nextKey;          // [1..2^16] (don't let == 0)
  int freeHead;         // index of first free entry
};

Maneja todo, desde balas hasta monstruos, desde texturas hasta partículas, etc. Esta es la mejor estructura de datos para videojuegos. Creo que vino de Bungie (en los días de la maratón / mito), lo aprendí en Blizzard, y creo que fue en un juego de programación de gemas en el día. Probablemente esté en toda la industria de los juegos en este momento.

P: "¿Por qué no usar una matriz dinámica?" R: Las matrices dinámicas provocan bloqueos. Ejemplo simple:

foreach(Foo *foo in array)
  if (ShouldSpawnBaby(*foo))
    Foo &baby = array.Alloc();
    foo->numBabies++; // crash!

Puedes imaginar casos con más complicaciones (como callstacks profundos). Esto es cierto para todos los contenedores tipo array. Al hacer juegos, tenemos suficiente comprensión de nuestro problema para forzar tamaños y presupuestos en todo a cambio de rendimiento.

Y no puedo decirlo lo suficiente: Realmente, esto es lo mejor de la historia. (¡Si no está de acuerdo, publique su mejor solución! Advertencia: debe abordar los problemas enumerados en la parte superior de esta publicación: memoria lineal / iteración, O (1) asignación / libre, índices estables, referencias débiles, cero derechos indirectos o tiene una razón increíble por la que no necesita uno de esos;)

Jeff Gates
fuente
¿Qué quieres decir con matriz dinámica ? Estoy preguntando esto porque DataArrayparece que también asigna una matriz dinámicamente en ctor. Por lo tanto, podría tener un significado diferente con mi comprensión.
Eonil
Me refiero a una matriz que cambia el tamaño / memmoves durante su uso (a diferencia de su construcción). Un vector stl es un ejemplo de lo que yo llamaría una matriz dinámica.
Jeff Gates
@JeffGates Realmente me gusta esta respuesta. Totalmente de acuerdo en aceptar el peor de los casos como costo estándar de tiempo de ejecución del caso. Respaldar la lista enlazada gratuita usando la matriz existente es muy elegante. Preguntas Q1: Propósito de maxUsed? P2: ¿Cuál es el propósito de almacenar el índice en los bits de ID de orden inferior para las entradas asignadas? ¿Por qué no 0? P3: ¿Cómo maneja esto las generaciones de entidades? Si no es así, sugeriría usar los bits de orden inferior de Q2 para el recuento de generación breve. - Gracias.
Ingeniero
1
A1: Max utilizado le permite limitar su iteración. También amortizas cualquier costo de construcción. A2: 1) A menudo vas del elemento -> id. 2) Hace que la comparación sea barata / obvia. A3: No estoy seguro de lo que significa 'generaciones'. Interpretaré esto como '¿cómo diferencia el quinto elemento asignado en la ranura 7 del sexto elemento?' donde 5 y 6 son las generaciones. El esquema propuesto utiliza un contador global para todos los espacios. (De hecho, comenzamos este contador en un número diferente para cada instancia de DataArray para diferenciar más fácilmente los identificadores). Estoy seguro de que podría reajustar los bits por seguimiento de elemento era importante.
Jeff Gates
1
@JeffGates - Sé que este es un tema antiguo, pero realmente me gusta esta idea, ¿podría darme información sobre el funcionamiento interno de void Free (T &) sobre void Free (id)?
TheStatehz
1

No hay una respuesta correcta para esto. Todo depende de la implementación de sus algoritmos. Solo ve con uno que creas que es mejor. No intentes optimizar en esta etapa temprana.

Si a menudo elimina objetos y los vuelve a crear, le sugiero que observe cómo se implementan los grupos de objetos.

Editar: ¿Por qué complicar las cosas con las máquinas tragamonedas y qué no? ¿Por qué no usar una pila y sacar el último elemento y reutilizarlo? Entonces, cuando agregue uno, hará ++, cuando haga estallar uno, para hacer un seguimiento de su índice final.

Sidar
fuente
Una pila simple no maneja el caso en que los elementos se eliminan en orden arbitrario.
Jeff Gates
Para ser justos, su objetivo no era exactamente claro. Al menos no para mí.
Sidar
1

Depende de tu juego. Los contenedores son diferentes en cuanto a qué tan rápido es el acceso a un elemento específico, qué tan rápido se elimina un elemento y qué tan rápido se agrega un elemento.


  • std :: vector - El acceso rápido y la eliminación y adición al final es rápido. Eliminar desde el principio y el medio es lento.
  • std :: list : iterar sobre la lista no es mucho más lento que un vector, pero acceder a un punto específico de la lista es lento (porque iterar es básicamente lo único que puede hacer con una lista). Agregar y quitar elementos en cualquier lugar es rápido. La mayoría de la memoria sobrecarga. No continuo.
  • std :: deque - El acceso rápido y la eliminación / adición al final y al comienzo es rápido pero lento en el medio.

Por lo general, desea usar una lista si desea que su lista de objetos se ordene de una manera diferente a la cronocial y, por lo tanto, tenga que insertar nuevos objetos en lugar de agregarlos, de lo contrario, una deque. Una reducción ha aumentado la flexibilidad sobre un vector, pero en realidad no tiene muchos inconvenientes.

Si realmente tienes muchas entidades, deberías echar un vistazo a Particionamiento espacial.

API-Bestia
fuente
No es cierto re: list. El asesoramiento de Deque depende completamente de las implementaciones de Deque, que varían enormemente en velocidad y ejecución.
metamorfosis