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 haven't actually implemented this system yet. I'm trying to work through the major conceptual hurdles before I actually start writing code, and the proper way to generate IDs is a little confusing to me. Should I just give each entity an integer ID in the order that it's created? Use the C# guid? What is the proper way to assign IDs in such a way that there won't be issues later on?

share|improve this question
2  
I have entity component systems without entity IDs and it works fine. –  Kikaimaru Jan 20 '13 at 12:02
1  
There is nothing wrong with just increasing integer ids. By the way in SQL databases auto increment primary keys are very common which is the same thing. I did this in my game and it works fine. Your entity manager would provide a function for creating a new entity (which basically simply increases the last id variable by one) and a function for assigning properties to an id (where you first check if the passed id is less then the last id variable). –  danijar Jan 20 '13 at 16:15
    
@Kikaimaru what is the "size" of your project? This kind of stuff could be useful for MMORPGs, or something like patching saved games. –  Den Jan 21 '13 at 20:06
    
@Den: Its small mmorpg, and second one was small 3d engine. And in mmorpg i have component that holds id, because not every entity is on server (like particle effects on hit, test showing damage, etc). I think that main benefit of using entity ids (or numbers instead of entity classes) is optimalization, and in most cases its not nescessary. –  Kikaimaru Jan 23 '13 at 10:17

5 Answers 5

up vote 9 down vote accepted

The sole constraint of an identifier in an entity component system is that the generated identifier be unique. That's the only criteria. If it's unique, it's good.

Any method which satisfies this one constraint is a proper way to assign IDs.

  • guid? Fine.
  • integer from an incrementing counter? Provided the counter isn't going to overflow during play, that's fine too.
  • random integer? Provided the integer is big enough, this is the same as a guid, so is fine. If you're generating smaller random numbers, you'll probably eventually randomly generate a duplicate ID, so that wouldn't be ideal.
  • current time as returned by a high-resolution timer? Sure, if you're certain that you're not going to generate more than one id per whatever resolution the timer's using.
  • hashed string? See the comment above about random integers; same deal here.

Doesn't matter. Do any of the above, or do some other method that I haven't thought of. As long as whatever method you pick generates unique identifiers, that's all that matters.

Ignore folks who argue about which method is faster. This is just generating unique identifiers; it will almost definitely not be a factor in your game's execution time. Trying to optimise this sort of thing for speed is a total waste of effort until you have profiler results which prove otherwise. And in that case, the only thing you'd have to change is this one function which generates the identifier. It wouldn't be a major change to switch from one mechanism to another.

So do whatever you're comfortable with, and don't stress about it.

share|improve this answer
2  
Random? Unless you want random heisenbugs to happen with entities later, randomly. Stick with dependable, guaranteed generators just to be sure. The advice at the end, priceless! –  Patrick Hughes Oct 7 at 2:39
    
@PatrickHughes I agree; now, two years later, I have a better understanding of why guids work, and disagree with my quip that a large random number "is the same as a guid". Guids give you a lot more reliable uniqueness than a mere random number does. But at the same time, they use a lot of their space for uniqueness that we don't care about in this context (It's not useful that guids generated by my computer are different than those generated by your computer, for this scenario). Guids do tend to be more CPU-intensive to generate, but probably not enough so to matter. –  Trevor Powell Oct 7 at 5:24

I don't think there is a proper way. You might want to let the user assign his own identificators on creation, if he wants, it's what Ember does, it then lets you retrieve entities by it. Artemis probably uses consecutive integers, reusing them if they're freed when an entity is destroyed, because it uses an array implementation.

Personally i use the consecutive integer approach, because inside of the manager i store entities in an array and i want to be able to quickly access an entity by its index. Reusing identificators means that you don't have to use lists because you don't shift the array when removing an entity. Also, for me in code identifying entities comes down to entity1.id() != entity2.id(), not entity1.id() == 'player'.

It depends on your needs. If you're using an array approach, then the algorithm is simple, pop an id from the id stack, or if the stack is empty, assign the next integer. When destroying an entity, push the id to the stack. If you're using lists and just want a unique identifier then you don't even need this, unless you're worried that somebody might create four billion entities.

share|improve this answer
1  
Good article which goes into a bit of detail on why using strings for ids is usually a bad idea, particularly if that string might need to change later : altdevblogaday.com/2012/12/11/… –  Darcy Rayner Jan 20 '13 at 9:47
    
Doesn't reusing ids basically remove protection against stale references? I thought part of the use of ids instead of pointers is to give that level of safe indirection. –  david van brink Oct 7 at 14:37

Our ES implementation basically uses an unsigned integer to assign a unique ID to each entity that gets created. The entity ID is essentially an index offset to various subsystem vectors where component data is stored. When an entity is destroyed at the end of the frame, those IDs are placed into a free list and simply reused later.

In other simulations & in networked games, I've often resorted to some 64-bit ID which we referred to internally as a GUID that identified a few characteristics about the entity by simply doing some bitwise math.

As for editor friendly names or possibly encounter-specific names that make scripting easy, we generally associate a TagComponent to those entities. It allows us to query entities by some human readable name such as "General of Death" or some system-defined name such as "Target", "Player", "TargetTarget", "Leader", etc.

share|improve this answer

You could also use a dictionary (map, hasmap, etc).

It would be just as easy as using an array approach, but more flexible since shifting and all that is handled for you.

You just need an IdManager class, an instance of which would be a member of your EntityManager class. The IdManager should have a public method called GetId(), which would always return a unique string of n characters. You would also need a private method NextId(), which would be called from GetId() to compute the new unique ID.

GetId()
{
    old_id = current_id_; //Store the current id so it doesn't get changed.
    NextId(); //Advance to the next ID, just like counting.

    return old_id;
}

Now, when you're adding an entity just do entities[idm.GetId()] = some_entity;.

Most of the problems raised in that AltDevBlog article Darcy posted don't really apply here: we're not letting anyone name entities, strings are just numbers here.

If you're using C++ you might not need strings at all, as integers work as keys too.

share|improve this answer
    
TBH i don't see a point to this, you're introducing a lot of overhead for nothing. Hashing is an expensive operation, dictionaries are expensive data structures, strings are as well compared to integers. If you don't want to use arrays, it's better to just use a list. –  dreta Jan 20 '13 at 14:07
    
Not really that expensive at all. They're pretty standard for a lot of languages, and greatly optimized. Besides, you don't actually need to use strings (at least not in C++), as you could get the benefits of maps by using integer keys. The benefit of this is that it's easier to implement session-persistent IDs. –  jco Jan 20 '13 at 14:13
    
It's expensive enough though. CBES shouldn't introduce overhead, this is why Artemis does all the tricks it does. If you're only going to use CBES for something like the player or a monster in an MMO, then sure it's probably fine to use a dictionary, but usually CBES is used for everything from a few massive buildings to lots of tiny particles. These things matter. –  dreta Jan 20 '13 at 14:49

A little late to the party here but thought I'd add a few suggestions and reasoning behind each which should be considered when considering these or other suggested answers mentioned in this thread. I've faced the same question and the answer always seems to be to decide which trade-offs best suit my particular situation. My suggestions are based on c# design choices, however the reasoning is pretty much transferable to any language you'll be developing games in.


1. 32-bit Signed Integer IDs

By far the most lightweight ID type. Comparisons are fast and are easily orderable (if required). They're light enough for being passed around in function calls when needed without taking a noticeable performance hit.

Signed 32-bit integers provide a wide enough range of possible values for most gaming needs. If used for static (unchanging) IDs, this should be fine as I cant think of a single game that uses anywhere near 2.1 billion different types of entities!

If using for instance IDs, again you should be fine as 2.1 billion+ possible ID values is an enormous amount. The only time this may become a consideration is if you are talking about an online game and the game server stays up without restarts for a very very long time, in which case you'll have to monitor this and see how long you can go without needing to reset the count (by restarting the server) to avoid overflowing.

The one thing to be cautious of if using 32-bit signed integers is thread-safety. Do not assume that just because a type is static that it's threadsafe or you will be bound for problems. To successfully use an incremental 32-bit integer design, you must also implement a properly designed locking system to ensure thread safety. Due to this, you also have to be aware of any overhead involved in repeated locking as if designed poorly, this cause a big performance hit.


2. 32-bit Unsigned Integer IDs

Very similar to the above but with a few gotchas. In .NET, unsigned integers are not CLS compliant and needs to be considered if planning to allow/use libraries from other .net languages.

In some databases unsigned integers are not supported at all (strange but true). This is something to consider if these are static id's that need to be stored in a database.

The odds of needing 4.2 billion+ range in possible ID values is incredibly rare even for the largest of games but still a viable consideration for IDs.


3. GUID IDs

GUID values are 128-bit so they're a bit larger than 32-bit integers so their memory footprint is a bit bigger in comparison.

As for uniqueness, this will give you complete and utter uniqueness for each ID created. Someones bound to chime in that GUIDs are not guaranteed to be unique as per definition, but this is only true over the context of an insanely huge timeframe, well beyond the lifetime of anygame, or developer for that matter. Plain and simple, these will be unique for your requirements, even across machines.

Another benefit to GUID IDs is that you will not have to worry about thread safety during creation. Yet another bonus of GUID IDs is that they can be created in-place within the constructor of the type if desired. Doing this means that the Entity Manager is not burdened with managing ID generation and no unnecessary overhead is incurred during from locking, etc.

Performing comparison of GUID values is obviously slower than comparing integer values but it's still surprisingly fast and shouldn't be an issue in most, if any systems. Ordering these may be a major burden however but there shouldn't be any need for ordering if being used for the proper purpose (i.e.: Instance IDs). On that note though, I would suggest that anywhere you need to store these outside of the object themselves where searching must be performed against other IDs (object maps, etc) they should be stored in a dictionary. Storing in an array or a list will be absolutely horrible performance do to the search algorithm used where as in a dictionary, due to the internal structuring and search algorithm used, will be blazing fast regardless of the 128-bit size.

I should also not that the equality comparison of GUID values in .NET is actually even faster for GUIDs that are not equal than those that are equal. It may seem scary at first when thinking of GUID comparisons as when we view the human-readable form it looks like a big, messy string, but internally it is a sequence of various integral types and is treated as such when comparing values against others.


4. String IDs

The heaviest memory footprint of this list for multiple reasons. I do generally advise against using string values as IDs if at all possible unless you fully understand the inner workings of strings and how to make optimal use of them.

String values do provide the largest possible range of values and most flexibility. Names can be randomly generated, strategically assigned, and can be made very meaningful. One attractive use-case could be fully qualified names i.e.: (Player.SomeGuy, or Creature.Humanoid.SomeBadGuy, etc). That is an attractive feature with a lot of possibility.

Due to the way strings are handled in the .NET framework (via the string intern table), the way you implement and manage these IDs is really what will decide how good or bad it performs. String equality comparison can be relatively fast if handled properly but many things such as size, storage methods, etc become factors. Explicitly choosing the comparison type will be in your best interest when comparing string values. I prefer case-sensitive ordinal comparison personally but some may wish to be culture-sensitive in certain scenarios. This will be a design choice based on your requirements.

Generating string ID values could get tricky if required to be done automatically and of course, thread safety will something you will have to accommodate in your implementation.


There's a fair bit to take into consideration when deciding which route you will go with ID types but the above break-down gives some strong points to consider when choosing. My personal preferences are as follows:

  • signed 32-bit integer IDs for static ID values that will be persisted in databases, etc.
  • signed 64-bit integer IDs for static ID values that will be persisted in databases when I want to provide some sort of sub-identifiers within the ID itself for use with bit-masking to speed up searches/ordering, etc. An example would be: player entity types may have a bit-mask of 0x0100000000000000 and creature entity types may have a mask of 0x0200000000000000, just as an example as it can go even further in-depth than that.
  • GUID IDs for instance IDs since these values aren't persisted, easily generated in-place without worrying about threadsafety and the likeliness of me needed to perform any sort of ordering on instance IDs is slim to none as it's usually just simply equality comparison (Equal or Not Equal).

Just my 2 cents on the issue anyway but feedback is always welcome :)

share|improve this answer

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.