¿Cómo elimino mejor una entidad de mi bucle de juego cuando está muerta?

16

Ok, entonces tengo una gran lista de todas mis entidades que reviso y actualizo. En AS3 puedo almacenar esto como una matriz (longitud dinámica, sin tipo), un vector (con tipo) o una lista vinculada (no nativa). En este momento estoy usando Array pero planeo cambiar a Vector o lista vinculada si es más rápido.

De todos modos, mi pregunta, cuando se destruye una Entidad, ¿cómo debo eliminarla de la lista? Podría anular su posición, empalmarlo o simplemente ponerle una bandera para decir "salta sobre mí, estoy muerto". Estoy agrupando mis entidades, por lo que es muy probable que una entidad que está muerta vuelva a estar viva en algún momento. Para cada tipo de colección, ¿cuál es mi mejor estrategia y qué combinación de tipo de colección y método de eliminación funcionará mejor?

Iain
fuente
La longitud de un Vector no es fija, pero está escrita, y eso la hace superior a la Matriz. El inconveniente es que no hay una sintaxis rápida para definir una lista precargada, pero creo que no es necesario.
Bart van Heukelom el

Respuestas:

13

Almacenaría todas las adiciones / eliminaciones en listas separadas y realizaría esas operaciones después de iterar a través del ciclo de actualización.

Simón
fuente
10

El marco Flixel usa el indicador muerto (en realidad, varios indicadores que determinan si se debe dibujar, actualizar, etc.). Diría que si va a revivir entidades, y si el rendimiento es un problema, use la bandera muerta. En mi experiencia, crear instancias de entidades nuevas es la operación más costosa en el caso de uso que usted describe, y el empalme o la anulación de elementos pueden llevar a la acumulación de memoria dada la recolección de basura a veces arduamente de Flash.

Gregory Avery-Weir
fuente
1
+1 para flixel. Reciclar deadrealmente ayuda con el rendimiento.
Snow Blind el
3

Si bien algunas técnicas son inherentemente más eficientes que otras, solo importará si se está quedando sin ciclos en su plataforma de destino. Usa cualquier técnica que te permita terminar tu juego más rápido. Mientras tanto, trate de no confiar en la implementación específica de sus estructuras de datos de contenedor y le ayudará a optimizar después si lo necesita.

Solo para abordar algunas de las técnicas ya discutidas por otros aquí. Si el orden de las entidades es importante, entonces una bandera muerta puede permitirle empalmar durante su ciclo de actualización en el siguiente cuadro. p.ej. pseudocódigo muy simple:

void updateGame()
{
  // updateEntities()
  Entity* pSrcEntity = &mEntities[0];
  Entity* pDstEntity = &mEntities[0];
  newNumEntities = 0;
  for (int i = 0; i < numEntities; i++)
  {
    if (!pSrcEntity->isDead)
    {
       // could be inline but whatever.
       updateEntity(pDstEntity, pSrcEntity);
       // if entity just died, don't update the pDstEntity pointer, 
       // and just let the next entity updated overwrite it.
       if (!pDstEntity->isDead)
       {
          pDstEntity++;
          newNumEntities++;
       }
    }
    pSrcEntity++;
  }
}
numEntities = newNumEntities;

Estas son las características de este esquema:

  • compacidad natural de las entidades (aunque posiblemente con 1 latencia de trama antes de que se pueda reclamar un espacio de entidad).
  • sin problemas de reordenamiento aleatorio.
  • mientras que las listas doblemente vinculadas tienen O (1) inserción / eliminación, pero son muy difíciles de obtener previamente para ocultar la latencia de caché óptima. Mantenerlos en una matriz compacta permite que las técnicas de captación previa de bloques funcionen bien.
  • En el caso de la destrucción de múltiples objetos, no tiene que hacer copias de turnos redundantes para mantener el orden y la compacidad (todo se hace una vez durante la actualización)
  • Aproveche la posibilidad de tocar datos que ya deberán estar en caché durante la actualización.
  • Funciona bien si los punteros de la entidad de origen y de destino deben separar las matrices. A continuación, puede hacer doble búfer en sus matrices de entidades para aprovechar multinúcleo / por ejemplo. un hilo actualiza / escribe las entidades para el cuadro N, mientras que otro hilo representa las entidades del cuadro anterior para el cuadro N-1.
  • La compacidad significa que es más fácil DMA todo a un procesador heterogéneo para una mayor descarga de trabajo de la CPU, por ejemplo. SPU o GPU.
jpaver
fuente
+1. Me gusta esto. Aunque casi nunca necesito actualizaciones ordenadas dentro de un grupo, lo agregaré a la bolsa de cosas para recordar si me encuentro con la situación: o)
Kaj
2

Hablando en términos de mi experiencia de programación general, el empalme suele ser una operación lenta, que implica cambiar todos los elementos existentes hacia arriba. Creo que establecerlo en nulo sería la mejor solución aquí ; una bandera muerta funcionaría, pero debe tener cuidado de no dejar que su código se vea desordenado.

Sin embargo, en realidad solo estábamos hablando de la agrupación de recursos en la sala de chat. Es una muy buena práctica, y es bueno saber que lo estás haciendo. :)

Ricket
fuente
1
Si el orden de actualización no es importante, el empalme debería ser tan simple como mover la última entidad al índice actual y disminuir el recuento de grupos y el índice de iterador.
Kaj
Wow, muy buen punto Kaj! :)
Ricket
2

Personalmente, usaría una lista vinculada. Iterar sobre una lista de Me gusta es rápido, así como agregar y eliminar elementos. Usar una matriz o un vector sería una buena opción si necesita acceso directo a elementos en la estructura (por ejemplo, acceso a un índice), pero no parece que lo necesite.

Siempre que elimine un elemento de la lista vinculada, puede agregarlo a un grupo de objetos que luego se pueden reciclar para guardar en la asignación de memoria.

He utilizado las estructuras de datos poligonales en varios proyectos y he estado muy contento con ellas.

Editar: Lo siento, creo que la respuesta no fue muy clara en términos de estrategia de eliminación: sugeriría eliminar el elemento de la lista, tan pronto como esté muerto y agregarlo directamente a la estructura de agrupación (reciclaje). Dado que eliminar un elemento de una lista vinculada es muy eficaz, no veo ningún problema al hacerlo.

bummzack
fuente
1
¿Supongo que sugiere una lista de doble enlace aquí? (adelante / atrás)? Además: ¿Está sugiriendo algún tipo de grupo sobre los elementos de enlace o está asignando dinámicamente cada titular de puntero en la lista vinculada?
Simon
Sí, tendría que ser una lista de doble enlace que sea más adecuada para esa tarea. ¡Gracias por señalar eso! Con respecto a la reutilización de elementos: estaba pensando en una clase / estructura de datos de agrupación especializada, una que crea nuevos objetos a pedido o utiliza instancias existentes si hay algunas en la agrupación. Por lo tanto, sería bueno eliminar realmente los elementos "muertos" de la lista y agregarlos al grupo para su uso posterior.
bummzack
Una lista vinculada individualmente estará bien. Las listas doblemente enlazadas solo dan la ventaja de iterar en ambas direcciones. Para recorrer una lista enlazada individualmente con la opción de eliminar el elemento actual, deberá realizar un seguimiento de la entrada anterior.
deft_code el
@caspin sí exactamente. Si está utilizando una lista de enlaces únicos, entonces necesita hacer un seguimiento de los nodos anteriores y vincular su nextpuntero al nodo después de uno eliminado. Si no quiere la molestia de hacer esto usted mismo, una lista de doble enlace sería la estructura de datos de elección.
bummzack
1

"solo ponle una bandera que diga" salta sobre mí, estoy muerto ". Estoy agrupando mis entidades, por lo que es muy probable que una entidad que está muerta vuelva a estar viva en algún momento"

Creo que respondió su propia pregunta con respecto a esta aplicación específica. Me alejaría de las matrices si alguna vez planea trabajar en ellas además de push y pop. Las listas vinculadas serían una forma más inteligente de hacerlo si planea realizar operaciones pesadas. Dicho todo esto, si planeas volver a integrar la misma entidad en el juego, entonces tiene sentido establecer solo una variable booleana y verificarla durante los bucles de operación del juego.

bohordo
fuente
0

Una solución limpia y general que encontré en una biblioteca que usé fue usar un mapa bloqueable.

tienes 2 operaciones lock()y unlock(), mientras iteras sobre el mapa lock(), ahora, a partir de este punto, cada operación que cambie el mapa no tiene efecto, solo se inserta en una CommandQueueque se ejecutará una vez que llames unlock().

Entonces, eliminar una entidad tendría el siguiente pseudocódigo:

void lockableMap::remove(std::string id) {
   if(isLocked) {
       commandQueue.add(new RemoveCommand(id));
   } else {
       //remove element from map
   }

y cuando tu unlock()

isLocked = false
commandQueue.execute(this);

Lo único que debe tener en cuenta es que solo eliminará la entidad después del ciclo.

EDITAR: esta es la solución propuesta por Simon.

GriffinHeart
fuente
0

Tengo dos métodos

Cuando llama a un objeto para que se elimine, realmente establece dos banderas:

1. Uno para decirle al contenedor que un objeto ha sido eliminado

2. Uno para decirle al contenedor qué objetos se han solicitado que se eliminen

void object::deleteObject()
{
    container->objectHasBeenDeleted = true;
    isToDelete = true;
}

Uno usando un vector de objetos

std::vector<object*> objects;

Luego, en la función de actualización, verifique si se ha eliminado un objeto y, en caso afirmativo, repita todos los objetos y elimine los que tienen un indicador de eliminación.

void container::update()
{
    if (objectHasBeenDeleted)
    {
        std::vector<object*>::iterator ListIterator;
        for(ListIterator=objects.begin(); ListIterator!=objects.end();)
        {
            if( (*ListIterator)->isToDelete )
            {
                ListIterator = objects.erase(ListIterator);
                delete *ListIterator;
            }
            else {
                ++ListIterator;
            }
        }
    objectHasBeenDeleted = false;
    }
}

Dos Usando un (puntero a) un vector de objetos.

std::vector<object*> *objects;

En la función de actualización, si se va a eliminar un objeto, repita los objetos y agregue los que no se van a eliminar a un nuevo vector. eliminar el vector de objetos y establecer el puntero en el nuevo vector

void container::update()
{
    if (objectHasBeenDeleted)
    {
        std::vector<object*> *newVector;
        unsigned long i;
        for (i = 0; i < objects->size(); i++)
        {
            if (!objects->at(i)->isToDelete)
            {
                newVector->push_back(objects->at(i));
            }
        }
        delete objects;
        objects = newVector;
        objectHasBeenDeleted = false;
    }
}

fuente