How to build a game entity list custom data structure

Question

I'm writing a game in Flash (player 10) and need to come up with a good way to manage the list of objects/entities/actors in the game (player character, obstacles, enemies, etc.). It has these requirements:

• Iterable
• Objects addable and removable while iterating.
  • Argument to remove() function would be the object to remove, not an index.
• [optional] Objects can be assigned a name, and retrieved using that.
• [optional] Sortable, so some objects get updated earlier than others.

How would I implement this?

---

I was thinking along the lines of an in-memory database table which would contain:

• An array with the objects (records).
• A hashmap (index) which links names to array indices.
• Another hashmap to link objects to their indices (for removing by passing the object to remove).

Removing an entity would make the corresponding record null. Once in a while the array needs to be compacted (empty spaces removed) or it will grow too big. This requires rebuilding the hashmap to point to the correct records (but can that be done efficiently).

Thoughts? Would it perform well? And how to make the sortable and add/remove while iterating parts?

Answer 1

It sounds like this is what you're looking for:

http://gamedev.michaeljameswilliams.com/2008/09/20/actionscript-3-collection-class/

It's a Collection Class for AS3, which extends Array and adds functions like add() and remove(), as well as some really useful sorting functions. I've used it and it performs nicely, didn't have any gripes. Hope that's what you're looking for, and it's useful to you.

Answer 2

Consider this: Will Array or Dictionary fit your needs? Yes, they aren't blazing fast, but they are simple to use (and fit your requirements).

If you properly segregate your objects according to the code paths they take (i.e. static objects, entities, projectiles), you'll usually end up with fairly small lists of dynamic objects, and large lists of static objects.

The static objects don't need fancy data structures, because you can make lots of assumptions about them (or do the heavy lifting at load time), and the dynamic objects don't need fancy data structures because there aren't many of them. Don't optimize this kind of thing unless: you have a significant architecture issues, or, you have an actual bottleneck here.

Because ultimately, this is what matters: Spend your time making a game, not a data structure. :)

Or perhaps I'm misreading the situation?

Answer 3

If you are looking for some different (and performant) datastructures for AS3, I've found these ones quite comfortable in the past:

DataStructures by polygonal

Answer 4

My current solution is to use an EntityManager class that maintains a dictionary of all entities, as well as an array of actives. The former is used for retrieving entities by id. The latter is used for the update loop, which looks like this:

var len:int = actives.length;
for(var i:int = 0; i < len; i++)
{
    var entity:Entity = actives[i];
    if(!entity.isActive)
    {
        actives.splice(i,1);
        --len;
    }
    else
    {
        entity.update();    
    }
}

I would suggest creating an interface for your entity manager, implementing something that works, then go back and fix it later if you find you need to boost performance or add features.

Answer 5

It sounds to me like you want a Linked list.

• You can enumerate the list from start to finish, or finish to start
• To add to the collection, simply append to the start or the end (simply by changing 2 pointers, really fast!)
• If the objects themselves act as linked list nodes, then you can remove an object directly (simply by swapping four pointers, really fast!)
• A linked list can be sorted in O(nlongn) using merge sort