为 luaecs 增加内置 64bit ID
去年设计 luaecs 时遗留了一个问题：如何引用特定 entity。一开始，我认为可以灵活使用 tag 系统来解决大部分问题；或者用户自己构建一个 64bit ID 的 component ，采用二分查找的方法来引用特定 Entity 。
今年初，我发现我们的自己的使用者和外部使用者都无法避免引用特定 Entity ，所以增加了一个非侵入式的引用方案。
最近又围绕它做了一些讨论，让我重新考虑内置一个 Entity 引用的方案。
原本关联同一个 Entity 的不同 Components 使用了一个 32bits id ，在过去的代码中我称之为 entity id ，这可能造成了一些误解。它虽然是一直递增的，但 32bit ID 在长期运行的系统上无法避免回绕问题，也就是新的 entity 可能会复用已被删除的 id 。我用一个叫 rearrange 的机制来解决这个问题，当 id 超过 31bit 范围后，在update 环节会重新排列系统中所有的 id ，让它们重新变得足够的小。
如果这个 id 并不暴露给上层使用，那么怎么变化它们都无所谓。但如果把 id 暴露出去充当 entity 的引用就会有问题。
一个简单的解决方案是换成 64bit ID ，这样就不会再有回绕问题了。但是，每个 component 都会增加 32bit 的 payload ，查找它们的效率也会随之下降。我认为是不值当的。
所以，新的方案回归了最初的方案：为每个 Entity 生成一个独立的 64bit ID component ，这样可以用来引用 Entity ，又能保持稳定。需要解引用的时候，可以二分查找，最坏的时间复杂度也能控制在 O(Log N) 。最多使用 ecs 的特性是对 Entity 集合的筛选和遍历，并不操作特定 Entity 。
本来，这个方案可以留给上层自己实现。最初 luaecs 还提供了在有序 Component 集合上二分查找的 API 。但是，如果把这个特性内置，不管是空间上，还是时间上，都能实现的更高效。用于关联 Componets 的内部 ID 可以缩减到 24bits ，也就是 3 字节。每次 update 时，如有 entity 删除，就依次向小的数字压缩。这会把整个系统同时可容纳的 Entity 总数限制在 16M 个，对我们现在的应用场合完全够用，同时为每个 Component 节省了一个字节的内存，操作效率或许能有所提高。
另外，今年增加的 group 的特性 可实现的更好。
Group 指：我们可以在构建 Entity 时分配一个 32bit group id 给它。之后，可以给一组 group 的所有 Entity 打上特定的 tag 。然后，利用这些 tag 做快速筛选。我们的引擎目前大量使用这个特性做对象预筛，在特定应用场景下，极大的提高了性能。
原本 group 的实现就单独增加了 64bit ID ，现在两者可以合并了。而且，group 中的对象是只增不减的，只有在 entity 删除时才会去掉；另外，因为只有在 entity 创建的时候才会加入 group ，所以每个 group 中对象的 id 也是单调递增。group 只有一个操作，那就是遍历。没有随机访问的需求。
基于这些，我们甚至并不需要在 group 中用 64bit 数组来保存所有 id 。我采用的方法是保存相邻 id 的差值，并对这些差值进行变长编码。从 1 字节到 10 字节不等。由于数据量极大的减少，所以遍历效率也随之提高。
例如，我们在 group 中需要保存 1, 2, 5, 200 四个 64bit ID ，我们可以先计算出差值为 1, 1, 3, 195 。因为 id 必不相同，还可以把这些差值再减 1 变成 0,0,2, 0xc2 。
储存的时候采用 128bit varint ，即每个字节保存 7bits ，额外的 1bits 表示是否还有后续。以上 4 个差值数字可以表示为 0,0,2, 0xc2, 1 。只需要 5 个字节就可以储存下 4 个 64bits ID 。
Entity 删除并不需要从对应的 group 中删除 id ，而是等下次遍历 group 时，一边遍历一边删除那些已经不存在的 id 。
以上的重构工作暂时放在 v2 分支上。