0
\$\begingroup\$

I have been studying several entity component systems (Anax and EntityX) to get an idea of how they work.

For Entity ids, both use 2 numbers. The first number is basically a position in an array, and a second number is the "version" for the entity at that index. If a handle to an entity at a given index has a "version" older than the the version the container currently has, the handle is considered invalid. This would occur when an entity is deleted from the world and its index becomes free for a new entity.

This approach seems to suggest the maximum number of times an index can be reused is limited to whatever the max number a uint32_t (or whatever the system chooses to use) can hold.

In practice, I suppose this wouldn't occur often, but it doesn't seem impossible. If I made a simulation that endlessly spawned entities, moved them around on the screen a bit, and deleted them once they were off screen, then the program would eventually crash, or exhibit strange behavior, once the version number for an index reached the max for an int.

Here are some of the specific lines I've been looking at for each:

Is this a shortcoming of reusing indexes, and needing to invalidate old handles? Is there any real practical concern since even a 32bit in has a max value of 4 billion or so? Could these systems be broken by a soak test with a long, ongoing stream of short-lived entities?

\$\endgroup\$
0
\$\begingroup\$

This isn't a entity system specific issue; this pattern of versioned or salted handles can be used in almost any generic data structure (e.g., Sean Middleditch's slot map example). Related is the fact that you don't need to use this kind of versioned handle system in an entity/component system, either.

That said, your concerns are valid, but not quite as dire as you may think.

The purpose of the version bits are to allow you to differentiate between stale references to objects. The version bits don't actually have to impose an upper limit on the number of times the slot can be reused. You can make them do so if you like, but generally rolling over the version bits from the maximum value will not immediately crash you.

Once the version bits roll over, however, you can't reliably detect those stale references. If you allocate slot 10, version 0 to object A at the start of the program, and then release object A some time later, any handles referring to slot 10, version 0 are stale. You can detect that when you try to use them, since slot 10 will actually be at version 1.

If, eventually, you execute long enough to roll the versions over so that object Z ends up slot 10, version 0 and you happened to have kept a stale handle to object A around that long without dereferencing it, then at that point you won't be able to tell that that handle to A is stale. It will quietly, safely, dereference to object Z.

The likelihood of this occurring is exceedingly small. Small enough that it's generally not worth worrying about, given the value of the other benefits of this system.

You can help this by accounting for hysteresis. When you build the system, a simple approach is to use a stack of "free" slots. When you go to allocate, just pop the top entry off the stack, right? The problem with this is that if you allocate and destroy frequently, you tend to quickly increase the version of one slot. This can cause you to roll over the versions sooner. If instead you use a queue approach, you can distribute the versioning over a wide range of slots (although this is not without its own drawbacks).

You have to examine the expected use cases and decide which approach to reusing slots fits your case the best.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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