Proper way to handle destruction of game entities

Question

Imagine a game world where loads and loads of entities are dynamicly loaded all the time, I would represent that as a list of entities perhaps, but what about removing them?

While when adding i could be pushing back the new entity, i could have the need to remove anywhere in the container. To avoid searching the element to find its position for removal, what choices do i have?

I tought that i could store the entity id as being its position in the container, creating a path for direct removal, but wouldnt that generate some kind of mutual dependency 'disorder' ?

I know the right way would be something like List.RemoveAt(whereToRemove); but what if only the entity knows when it should die?

Or am I just missing something and a list container would know when an object is destructed and reduce its own size?

Answer 1

Here are your conditions:

• Other objects may still be dependant on your removed entity, after it is removed.

• You want only the entity to specify it's own removal.

You can't have both. Why? Because code at a higher level than your entity itself (see examples below) decides when that entity needs to be used. Consequently, only code at that same level can determine whether your entity is fit for removal or not.

However, what can happen is that the entity can request it's own removal, by firing off an event which the higher level code is listening for. That higher level then stores this request for removal in a list.

---

Example 1: without events

You are checking collisions between entities in your world. This is handled higher up, usually in your main game loop, which checks every entity against every other. In this example specifically, when an entity collides with another, only that entity's internal logic can determine how much damage it has taken, and whether or not it has "expired". So lets follow the logic flow for collisions where you have four entities in your world, A, B, C, and D. A is our entity we are concerned with.

We check A for collision with B. There is a collision. A takes damage 50%.

We check A for collision with C. There is a collision. A takes damage 50%. Because damage reaches 0, A determines that it has "died". It removes itself from the list.

We check A for collision with D. There would have been no collision, but you'll never get that far: you get a runtime exception because your entities list has been modified in the midst of a traveral operation.

Example 2: with events

Same setup as before.

We check A for collision with B. There is a collision. A takes damage 50%.

We check A for collision with C. There is a collision. A takes damage 50%. Because damage reaches 0, A determines that it has "died". It fires an event to the entity management code to say, "Remove me ASAP". The entity management code looks at the entity reference sent as part of the event, and stores that reference in a list of entities to be removed.

We check A for collision with D. There is no collision, and the check works just fine.

Now, at the very end of the current game loop iteration, run through the list of entities to be removed, and remove every one of these from your main entities list.

---

You can see how this avoids the problem altogether. You needn't use events, you can use signals or something else, but the principle is the same -- don't remove entities until you can safely do so. The flipside to this approach, to keep things clean and orderly, is doing the same with entities to add -- make sure you keep references to them, and only add them at the start of the next game loop iteration.

Lastly, don't forget to flush both your to-remove and your to-add lists, each time you use them to perform additions / removals on your main entity list.

PS. Don't be afraid to seek through your main list to do individual removals. It's part and parcel of entity management, and even massive lists tend to be very fast to traverse -- after all, that's what they're engineered for.

Answer 2

You're definitely looking for a HashMap/HashTable. A hashtable is a map that matches a key to a specific value. The key can be anything (such as the Entity ID).

Answer 3

I Guess you could use smartpointer idea to handle deallocations for you, in that case there won't be a need to keep a list of all entities inside your code.

in some cases you need a list to iterate over all the objects in your game. this list could be simply a link list where inserting and removing objects from it will take exactly O(1) time.

even to increase your speed more you can use some static array (possibly a vector). in that case you'll need to keep track of 2 linked lists inside same vector, one will iterate over valid objects and one will iterate over free objects. whenever smartpointer marks some place to be deleted you simply remove that pointer and add it's space to free spaces list. and whenever you add some entity you only need to remove first freespace fill it with entity pointer and then add it to valid objects list.