Original link: https://blog.codingnow.com/2022/08/luaecs_eid.html
There was a problem left when designing luaecs last year: how to refer to a specific entity. At the beginning, I thought that the tag system could be used flexibly to solve most of the problems; or the user could build a 64bit ID component by himself, and use the binary search method to refer to a specific Entity.
Earlier this year, I found that neither our own consumers nor external consumers could avoid referencing a specific Entity, so I added a non-intrusive referencing scheme .
There’s been a bit of discussion around it recently, and it made me reconsider having a built-in Entity reference.
Different Components originally associated with the same Entity used a 32bits id, which I called entity id in the past code, which may have caused some misunderstandings. Although it is always increasing, the 32bit ID cannot avoid the wraparound problem on long-running systems, that is, the new entity may reuse the deleted ID. I use a mechanism called rearrange to solve this problem. When the id exceeds the 31bit range, all the ids in the system will be rearranged in the update link to make them small enough.
If this id is not exposed to upper layers, it doesn’t matter how you change them. But there will be a problem if the id is exposed as a reference to the entity.
A simple solution is to switch to a 64bit ID so there will be no wraparound issues. However, each component will increase the 32bit payload, and the efficiency of finding them will also decrease. I don’t think it’s worth it.
Therefore, the new scheme returns to the original scheme: an independent 64bit ID component is generated for each Entity, which can be used to refer to the Entity and maintain stability. When dereference is required, binary search can be performed, and the worst time complexity can be controlled in O(Log N). The most used feature of ecs is the filtering and traversal of the Entity collection, and does not operate on a specific Entity.
Originally, this solution could be left to the upper layer to implement by itself. Originally luaecs also provided an API for binary search on an ordered set of Components. However, if this feature is built in, it can be more efficient in terms of space and time. Internal IDs used to associate Components can be reduced to 24bits, or 3 bytes. In each update, if the entity is deleted, it will be compressed to the smaller number in turn. This will limit the total number of entities that the entire system can accommodate at the same time to 16M, which is completely sufficient for our current application, and saves one byte of memory for each Component, and the operation efficiency may be improved.
In addition, the group features added this year could be better.
Group means: we can assign a 32bit group id to it when building an Entity. After that, all entities in a group can be tagged with a specific tag. Then, use these tags to do quick filtering. Our engine currently uses this feature extensively for object pre-screening, which greatly improves performance in specific application scenarios.
The original implementation of group added 64bit ID alone, and now the two can be combined. Moreover, the objects in the group will only increase and not decrease, and will only be removed when the entity is deleted; in addition, because the group will only be added when the entity is created, the id of the object in each group is also monotonically increasing. group has only one operation, and that is traversal. There is no need for random access.
Based on this, we don’t even need a 64bit array to hold all the ids in the group. The approach I took was to save the difference between adjacent ids and variable-length encode those differences. Varies from 1 byte to 10 bytes. Since the amount of data is greatly reduced, the traversal efficiency is also improved.
For example, we need to save 1, 2, 5, 200 four 64bit IDs in the group, we can first calculate the difference as 1, 1, 3, 195. Because the ids must be different, you can also subtract 1 from these differences to become 0, 0, 2, 0xc2.
When storing, use 128bit varint, that is, save 7bits per byte, and the extra 1bits indicates whether there is a follow-up. The above 4 difference numbers can be represented as 0, 0, 2, 0xc2, 1 . It only takes 5 bytes to store 4 64bits IDs.
Entity deletion does not need to delete the id from the corresponding group, but when traversing the group next time, delete those ids that no longer exist while traversing.
The above refactoring work is temporarily placed on the v2 branch .
This article is reprinted from: https://blog.codingnow.com/2022/08/luaecs_eid.html
This site is for inclusion only, and the copyright belongs to the original author.