Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I've seen great questions on similar topics, but none that addressed this particular method:

Given that I have multiple collections of game entities in my [XNA Game Studio] game, with many entities belonging to multiple lists, I'm considering ways I could keep track of whenever an entity is destroyed and remove it from the lists it belongs to.

A lot of potential methods seem sloppy/convoluted, but I'm reminded of a way I've seen before in which, instead of having multiple collections of game entities, you have collections of game entity IDs instead. These IDs map to game entities via a central "database" (perhaps just a hash table).

So, whenever any bit of code wants to access a game entity's members, it first checks to see if it's even in the database still. If not, it can react accordingly.

Is this a sound approach? It seems that it would eliminate many of the risks/hassles of storing multiple lists, with the tradeoff being the cost of the lookup every time you want to access an object.

share|improve this question
add comment

5 Answers

I often use this approach in my own C#/.NET game. Aside from the other benefits (and hazards!) described here, it can also help avoid serialization issues.

If you want to leverage the .NET Framework's built-in binary serialization facilities, then using entity IDs can help minimize the size of the object graph that gets written out. By default, .NET's binary formatter will serialize out an entire object graph at the field level. Let's say I want to serialize a Ship instance. If Ship has an _owner field referencing the Player who owns it, then that Player instance would get serialized out too. If Player contains a _ships field (of, say, ICollection<Ship>), then all of the player's ships will also get written out, along with any other objects referenced at the field level (recursively). It's easy to accidentally serialize a huge object graph when you only want serialize one small part of it.

If, instead, I have an _ownerId field, then I can use that value to resolve the Player reference on demand. My public API can even remain unchanged, with the Owner property simply performing the lookup.

While hash-based lookups are generally very fast, the added overhead could become a problem for very large entity sets with frequent lookups. If it becomes a problem for you, you can cache the reference using a field that does not get serialized. For example, you could do something like this:

public class Ship
{
    private int _ownerId;
    [NonSerialized] private Lazy<Player> _owner;

    public Player Owner
    {
        get { return _owner.Value; }
    }

    public Ship(Player owner)
    {
        _ownerId = owner.PlayerID;
        EnsureCache();
    }

    private void EnsureCache()
    {
        if (_owner == null)
            _owner = new Lazy<Player>(() => Game.Current.Players[_ownerId]);
    }

    [OnDeserialized]
    private void OnDeserialized(StreamingContext context)
    {
        EnsureCache();
    }
}

Of course, this approach can also make serialization harder when you actually want to serialize out a large object graph. In those cases, you would need devise some sort of 'container' to ensure that all the necessary objects are included.

share|improve this answer
add comment

Another way to handle your cleanup is to invert control and use a Disposable object. You probably have a factor allocating your entities, so pass the factory all lists that it should be added to. The entity keeps a reference to all lists that it is a part of, and implements IDisposable. In the dispose method, it removes itself from all the lists. Now you only have to be concerned with list management in two places: factory (creation) and dispose. Deleting in the object is as simple as entity.Dispose().

The issue of names vs references in C# is really only important for managing components or value types. If you have lists of components that are linked to one entity, using an ID field as a hashmap key can be useful. If you just have lists of entities though, just use lists with a reference. C# references are safe and simple to work with.

To remove or add items from the list, you can use a Queue or any number of other solutions to dealing with adding and deleting from lists.

share|improve this answer
add comment

This seems to just be a more specific instance of the "how to remove objects from a list, while iterating through it" problem, which is easy to solve (iterating in reverse order is probably the simplest way for a array-style list like C#'s List).

If an entity is going to be referenced from multiple places, then it should be a reference type anyway. So you don't have to go through a convoluted ID system - a class in C# already provides the necessary indirection.

And finally - why bother "checking the database"? Just give each entity an IsDead flag and check that.

share|improve this answer
    
I don't really know C#, but this architecture is often used in C and C++ where the language's normal reference type (pointers) aren't safe to use if the object was destroyed. There are several ways to deal with it, but they all involve a layer of indirection, and this is a common solution. (A list of backpointers as Kylotan suggests is another - which you pick depends on if you want to spend memory or time.) –  user744 Nov 2 '10 at 12:32
    
C# is garbage collected, so it does not matter if you abandon instances. For unmanaged (ie: by the garbage collector) resources there is the IDisposable pattern, which is very similar to marking an object as IsDead. Obviously if you need to pool instances, rather than have them GC'd, then a more complicated strategy is required. –  Andrew Russell Nov 2 '10 at 14:16
    
The IsDead flag is something I've used with success in the past; I just like the idea of the game crashing if I fail to check for a dead state rather than continuing on gleefully, with potentially bizarre and hard-to-debug results. Using a database lookup would be the former; IsDead flag the latter. –  vargonian Nov 2 '10 at 20:41
3  
@vargonian With the Disposable pattern, what usually happens is that you check IsDisposed at the top of each function and property in a class. If the instance is disposed you throw ObjectDisposedException (which will generally "crash" with an unhanded exception). By moving the check to the object itself (rather than checking the object externally), you allow the object to define its own "am I dead" behaviour and remove the burden of checking from callers. For your purposes you could implement IDisposable, or make your own IsDead flag with similar functionality. –  Andrew Russell Nov 3 '10 at 1:46
add comment

Is this a sound approach? It seems that it would eliminate many of the risks/hassles of storing multiple lists, with the tradeoff being the cost of the lookup every time you want to access an object.

All you've done is move the burden of performing the check from the time of destruction to the time of use. I wouldn't claim I've never done this before, but I don't consider it 'sound'.

I suggest using one of several more robust alternatives. If the number of lists is known, you can get away with simply removing the object from all lists. That is harmless if the object is not in a given list, and you're guaranteed to have removed it correctly.

If the number of lists is unknown or impractical then store back-references to them on the object. The typical implementation of this is the observer pattern, but you can probably achieve a similar effect with delegates, which call back to remove the item from any containing lists when necessary.

Or sometimes you don't really need multiple lists at all. Often you can keep an object in just one list and use dynamic queries to generate other transient collections when you need them. eg. Instead of having a separate list for a character's inventory, you can just pull out all objects where "carried-by" equals the current character. This might sound fairly inefficient, but it's good enough for relational databases and can be optimised by clever indexing.

share|improve this answer
    
Yeah, in my current implementation, every list or single object that wants a reference to a game entity needs to subscribe to its destroyed event and react accordingly. This might be just as good or better in some ways than the ID lookup. –  vargonian Nov 2 '10 at 20:46
1  
In my book, this is the exact opposite of a robust solution. Compared with lookup-by-id, you have MORE code, with MORE places for bugs, MORE opportunities to forget something, and a possibility to destroy object WITHOUT informing everyone to boot. With lookup-by-id, you have a little bit of code that almost never changes, a single point of destruction and a 100% guarantee that you'll never access a destroyed object. –  Nevermind Nov 3 '10 at 8:23
1  
With lookup-by-id, you have extra code in every single place you need to use the object. With an observer-based approach you have no extra code except when adding and removing items from lists, which is likely to be a handful of places in the entire program. If you reference items more than you create, destroy, or move them between lists, then the observer approach will result in less code. –  Kylotan Nov 3 '10 at 11:09
    
There probably are more places that reference objects than places that create/destroy ones. However, each reference requires only a tiny bit of code, or none at all if lookup is already wrapped by property (which should be most of the time). Besides, you CAN forget to subscribe for object destruction, but you CAN'T forget to look an object up. –  Nevermind Nov 3 '10 at 19:19
add comment

Short answer: yes.

Long answer: Actually, all games I've seen worked in this way. Hash-table lookup is fast enough; and if you don't care about actual ID values (i.e. they're not used anywhere else) you can use a vector instead of a hash-table. Which is even faster.

As an added bonus, this setup makes it possible to re-use your game objects, reducing your memory allocation rate. When a game object is destroyed, instead of "freeing" it, you just clean up its fields, and put in some "object pool". Then, when you need a new object, just take an existing one from the pool. If new objects spawn constantly, this can noticeably improve performance.

share|improve this answer
    
In general, that's accurate enough, but we need to take other things into account first. If there are a lot of objects being quickly created and destroyed, and our hash function is good, the hashtable might be a better fit than a vector. If you're in doubt, though, go with the vector. –  hokiecsgrad Nov 7 '10 at 14:11
    
Yes, I have to agree: vector is not absolutely faster than a hash-table. But it is faster 99% of the time (-8 –  Nevermind Nov 7 '10 at 14:55
    
If you want to reuse slots ( which you definitly want ), than you need to make sure that invalid IDs are recognized. ex. Object at ID 7 is in List A, B and C. Object is destroyed and in the same slot another object is created. This object registers itself to List A and C. The entry of the first object in List B now "points" to the newly created object, which is wrong in this case. This can be perfectly solved with the Handle-Manager from Scott Bilas scottbilas.com/publications/gem-resmgr. I've used this in commercial games already and it works like a charm. –  DarthCoder Jan 17 '11 at 22:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.