Entities struct doesn't properly recycle IDs

[amethyst]

Entities struct doesn't properly recycle IDs

[ebkalderon]

@ebkalderon replied: 2016-02-04 @ 12:25PM EST

Uh oh! Good catch. I think we need to have the create() method pop the first element from the vector, not the last.

[ebkalderon]

@boguszaur replied: 2016-02-04 @ 12:25PM EST

do we need to have vec of alive entities in the Entities struct? we can just have next_id and vec of dead entities.. so if we need to add new entity we either pop from dead entities, or return next_id and increment it. To determine if the entity is alive we make sure that its less than next_id and its not in dead vec. num_alive function just returns next_id - length of dead vec

[ebkalderon]

@ebkalderon replied: 2016-02-04 @ 12:27PM EST

@boguszaur I was thinking of something similar, yes. Please watch the ecs branch; it will undergo some minor code churn in a few moments.

[ebkalderon]

@ebkalderon replied: 2016-02-04 @ 4:20PM EST

@Oflor @boguszaur Thanks to you both for the feedback! I've tweaked the Entities struct and it seems to work better now. Let me know if you have any other main suggestions or complaints.

[boguszaur]

But is it really important to get entities from the dead vec in the order they were put there? whats wrong with pushing to the end and popping the last added? Our destroy method right now uses self.dead.insert(0, entity); so it shifts all elements to the right every time..not the best for performance.

[lschmierer]

Yes, it should not matter in which order we are getting the dead entities. Performance is more important imo.

[lschmierer]

Or use VecDeque.

[palodequeso]

What about just using uuid4s?

[ebkalderon]

@lschmierer That sounds like a good idea. I presume it's based on the standard Vec, so performance should be similar?

@palodequeso That certainly could work, but it's unnecessary computational overhead in my mind, since simple unsigned integers can do the job just as well. However, UUIDs could be useful for resource management, though. What library did you have in mind?

[palodequeso]

@ebkalderon: Yea, the up front generation overhead can be cumbersome, especially if you're tracking say, particles for physics simulation in mass, and you are constantly creating and destroying them by the thousands. Also, I'm not sure what library to use, I just know I've used UUIDs in a lot of places instead of iterative unsigned integers.

[ebkalderon]

Looks like VecDeque lacks a contains() method, so I guess I'll revert to the original .iter().filter(|&e| *e == entity).count() == 1 approach again.

[lschmierer]

Or just don't care about the order dead entities are returned.

When using normal Vec we can use binary_seach instead of contains which might be faster. However the vector then needs to be sorted.
We can use binary_search as well for inserting. If element is not found binary_search resturn position to insert.

[shawnscode]

Actually, id recycles might not be a good idea in real game development. For example, if we have two logical system A, B handle Entity(0) at same time.

1. System A Disposed Entity(0);
2. System A Created a new Entity, and will get Entity(0) as identifier again;
3. System B now may treats the newer Entity as old Entity, even if they might have different components and meanings.

Its a common case in my game based on ECS.

[lschmierer]

Iny understanding, Systems should probably handle the entities based on the components. So System B would not work on Entity(0).

[shawnscode]

its common to reference some entity identifier manually cross multi-system. Every time before performing real things based on it, i could do checks by calling is_alive to make sure its available. So if the identifier could be recycled, is_alive might returns confused result about the Entity(0) i used to reference.

[White-Oak]

Another problem may be networking - the common way to send updates/states is to send them by id, which may lead to corruption or confusion with recycling ids.

[Aceeri]

Probably best to not recycle ids, given the problems it could cause. Either way a u64 (I believe that is the type you are using that for the Entity Ids?) goes up to the incredible amount of 18 quintillion, so it is incredibly unlikely that a game will ever create that many entities.

[White-Oak]

@Aceeri +1

[Oflor]

I've already removed id recycling, @ebkalderon will just have to review it now.

[kvark]

Posting here what I mentioned a while ago on Gitter:

there is an old general solution to this problem with ID recycling - adding the generation count to the ID. When an ID gets recycled, it's generation count increases, so that the (ID,generation) pair is never equal to the (ID,previous_generation)

Was this approach ever considered? I imagine that without ID recycling you'd lose the ability to directly index your component arrays by the IDs, which imposes a significant performance hit. That, of course, only applies to array storage of the components. Did you rule out the arrays completely?

[Aceeri]

@kvark I'm thinking we might have something similar to the (id, generation) pair you suggested if we just make the entity unique and the components recycle. We could use the entities unique id for things like networking and such, but not risk duplication ids that would give an entity unwanted components.

(I would also suggest changing the dead list to a set of alive entities. Otherwise that could lead to a memory leak.)

This is resolved by the migration to specs which does this internally.