云风的 BLOG

我认为 ECS 框架针对的问题是传统面向对象框架中，对象数量很多而对象的特性非常繁杂，而针对对象的不同方面 aspect 编写处理逻辑会非常繁杂。每个针对特定的方面执行业务，都需要从众多对象中挑选出能够操作的子集，这样性能低下，且不相关的特性间耦合度很高。

所以 ECS 框架改变了数据组织方式，把同类数据聚合在一起，并用专门的业务处理流程只针对特定数据进行处理。这就是 C 和 S 的概念：Component 就是对象的一个方面 aspect 的数据集，而 System 就是针对特定一个或几个 aspect 处理方法。

那么，Entity 是什么呢？

我认为 Entity 主要解决了三个问题。

1. 生命期管理。如果我们把对象的不同方面分拆到了不同的 Component 中，同类的 Component 群聚在一起。这样就达到了 System 间的解耦。但是这些 Component 依然在生命期上属于一个整体，换句话说，它们还是属于一个对象。所以 Entity 就是联系同一对象上不同组件生命期的东西。我们可以通过删除一个 Entity 来从世界中剔除一组相关的 Component 。

2. 组件关联性。有些系统只处理单一类型的 Component ，那么它们可以无视对象身上的其它方面。但很多系统必须处理一个对象所属的多个方面 ，例如你需要把物理系统针对碰撞体计算出来的结果反馈给对象的空间位置信息。碰撞体组件 A 和空间变换组件 B就发生了联系。整个世界中有众多的 A 和众多的 B ，Entity 就是负责把特定的 A 和特定的 B 关联在一起。

3. 跨世界的对象关联。这个需求多见于 C/S 结构的网络游戏。服务器和客户端有两个世界，但是两个世界中的对象是互为镜像，它们是有关联的。我们需要有一个手段知道服务器上的某个对象到底对应着是客户端上哪个对象。这里的对象就指 Entity ，两个世界中的互为镜像的 Entity 有两个独立的数据拷贝，所以，我们需要用一个 id 来指代它们其实是同一个东西。这就是为什么 ECS 框架中，Entity 为何用 id 来表示的原因之一。

我们一开始开发 ECS 框架时，限制了一个 Entity 上只能由不同类型的 Component 构成，不允许多个同类的 Component 加到同一个 Entity 上。

现实需求总是复杂的。往往我们会碰到更复杂的数据组织需求。例如，一个玩家身上有多个 buf ；一个场景物件需要由多个几何体来描述碰撞体。这都涉及多个同类 Component 组合成一个 Entity 。

Unity 采取的方案是支持同类 Component 组合。例如你可以给一个对象添加多个碰撞体。但我认为并非很好的解决方案。

因为，从 Entity 索引特定的 Component 变得复杂，遍历世界中所有同类 Component 接口不仅需要关心每个 Component 隶属于哪个 Entity ，还需要关心是 Entity 上多个同类 Component 中的哪一个。很难简单的把同类 Component 置于一个简单集合中。

另外需要把同类子物件摊平为单个组件。就以碰撞体为例，它原本可分为集合形状和空间位置两部分，或者你还可以给碰撞体添加颜色（用于开发调试）、分层等等其它属性，但由于我们需要把多个碰撞体加在物件上，不得不把碰撞体的所有属性都加到同一个叫碰撞体的特定类型 Component 上。

这样是不利于 ECS 框架原有希望做到的数据解耦：例如空间剔除器只关心空间位置和包围盒，并不关心形状、阻挡属性等等；而物理系统则关心几何体的外形描述，质量等等其它方面。

事实上，Unity 也做了场景树这种不同 Entity 间的组合。可以把一个 Entity 挂接到场景树上，让空间关系受另一个 Entity 影响。我认为场景树和 Component 组合在功能上有重叠。

我现在的想法是，应该抽象出另外两类 Component ，一个是 subset ，就是一个 entity id 集合，表示一组 Entity 是一体的，满足前面所说的生命期管理需求和关联性需求。

另一个是 owner ，指向一个 entity id ，表示自身被另一个 Entity 管理。

subset 和 owner 作为可选项，可以随意添加到 Entity 上。根据 System 的实现需求，有时仅用其中之一即可。

subset 的实现可以是一个简单的 table ，但针对 3d engine 来说，我们开发了名为 hierarchy 的数据结构，可以表示一棵树。也就是可以用一个 set 包容下整个树的节点，并储存下针对根节点的空间变换信息。

以场景组织为例，一个场景物件可以有多个碰撞体来描述碰撞信息。这些碰撞体会被物理系统处理。但在场景编辑过程中，我们在场景中挪动物件，则会改变相关碰撞体组的空间位置。所以我们可以把多个碰撞体加入场景物件的 subset 中，储存在一个 hierarchy 数据结构里。当编辑场景时，一个特定的 system 会负责从物件的空间位置更新碰撞体在空间中的位置，方便物理碰撞系统去处理。

Posted by 云风 at 03:08 PM | Permalink | Comments (9)

我们的 3d engine 项目从 2018 年 1 月底开始，已经过去 10 个月了。比原计划慢，但是进度还可以接受。目前已经大致完成了运行时的基础渲染框架（基于 ecs 模式），整合了 bullet 物理引擎，开发了一个基于网络的虚拟文件系统，可以不依赖本地的资源/代码直接远程运行。另外还开发了一个 lua 的远程交互调试器，可提升 lua 的开发效率。

单从 runtime 角度，引擎的完成度已经较高。但和之前开发 ejoy2d 不同，这次希望把引擎的侧重点放在工具链上。所以虽然有计划开源，但在工具链不成熟的现阶段，暂时还是闭源开发。

目前团队有全职程序 3 名，我个人没有全职加入，但也花了颇多精力在上面。所以在关键节点上，我们已有 4 个人全力开发。

现在想再招聘一名成员，主要想补充工具链，尤其是开发环境/编辑器的开发。让引擎可以在半年内可用于新游戏 demo 的开发。对于这个职位，可以列出下列明确的需求：

1. 需要对 lua 有相当的理解，喜欢这门语言。因为我们的开发工作 90% 以上是基于 lua 开发的。
2. 有基本的编写 C/C++ 代码的能力，能够自行解决编译开源 C/C++ 工程时遇到的问题。
3. 不需要对 3d 图形学知识有了解，但有学习的意愿。
4. 了解 Unity 的工作流程，有使用 Unity 开发游戏的经验。因为 Unity 是游戏引擎易用性的标杆，需要了解怎样的工具才是方便易用的。

这个职位现阶段会承担的工作主要是整合我们现在已经开发出来的一系列小工具，包括虚拟文件服务器、动画编辑器，场景编辑器等等，进行综合考虑设计，集成为一个集成开发环境。这个工作会基于 lua iup 框架完成。编辑器框架设计会和我一同完成，并承担实现工作。目标是做出一个易用的游戏引擎。

工作地点在广州，入职阿里游戏，职位大致在 P6 水平。在过去近一年我们项目组没有任何形式的加班要求，每天 9 点半上班，在公司晚饭后 19 点下班，中午有稍许午休时间，周末双休。不排除日后有可能有加班，但我更希望通过合理的安排开发进度，在正常的工作时间内稳步推进。

有感兴趣的同学可以直接 email 和我联系。

2018 年 11 月 23 日：

已经收到很多不错的简历，这次不再需要了，谢谢大家。

Posted by 云风 at 05:01 PM | Permalink | Comments (13)

今天一个同事反应，在使用 recastnavigation 库时，判断一个点是否在一个三角形内，遇到了精度问题，而且精度误差很大。

具体是 dtClosestHeightPointTriangle 这个函数。

他给出了一组测试参数，abc 三点为 {261.137939, 8.13000488} , {73.6379318, 8.13000488}, {76.9379349, 10.2300053} ，测试 p 为 {74.4069519 , 8.6093819 } 应该在这个三角形内，但是这个函数计算出来并不是。

我看了一下源代码，把这个函数提出来，改写了一点点，方便独立测试。

#include <stdio.h>

// #define float double

static float
dtVdot2D(const float v0[3], const float v1[3]) {
    return v0[0] * v1[0] + v0[2] * v1[2];
}

static float *
dtVsub(float p[3], const float v0[3], const float v1[3]) {
    p[0] = v0[0] - v1[0];
    p[1] = v0[1] - v1[1];
    p[2] = v0[2] - v1[2];
    return p;
}

static int
dtClosestHeightPointTriangle(const float p[3], const float a[3], const float b[3],const float c[3], float *h) {
    float v0[3], v1[3], v2[3];

    dtVsub(v0, c,a);
    dtVsub(v1, b,a);
    dtVsub(v2, p,a);

    float dot00 = dtVdot2D(v0, v0);
    float dot01 = dtVdot2D(v0, v1);
    float dot02 = dtVdot2D(v0, v2);
    float dot11 = dtVdot2D(v1, v1);
    float dot12 = dtVdot2D(v1, v2);

    // Compute barycentric coordinates
    float InvDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
    float u = (dot11 * dot02 - dot01 * dot12) * InvDenom;
    float v = (dot00 * dot12 - dot01 * dot02) * InvDenom;

    // The (sloppy) epsilon is needed to allow to get height of points which
    // are interpolated along the edges of the triangles.
    float EPS = 1e-4f;

    // If point lies inside the triangle, return interpolated ycoord.
    if (u >= -EPS && v >= -EPS && (u+v) <= 1+EPS) {
        *h = a[1] + (v0[1]*u + v1[1]*v);
        return 1;
    }
    return 0;
}

int
main() {
    float a[3] = {261.137939, 0, 8.13000488};
    float b[3] = {73.6379318, 0, 8.13000488};
    float c[3] = {76.9379349, 0, 10.2300053};
    float p[3] = {74.4069519 , 0, 8.6093819 };
    float h;

    int r = dtClosestHeightPointTriangle(p, a, b, c, &h);

    printf("%d %f\n", r, h);

    return 0;
}

如果你在前面加上 #define float double ，把所有 float 换成双精度，那么测试是可以通过的。

我认为问题出在 dot00 * dot11 - dot01 * dot01 这样的运算上。dot00 点乘已经是单个量的平方，在测试数据中，大约这个量会是 261 - 73 = 188 ，小数点前大约是 8bit 的信息含量，如果我们计算 dot00 * dot11 ，差不多会得到一个这个量的 4 次方的结果，也就是 28bit ~ 32bit 之间。

但是 float 本身的有效精度才 23bit ，对一个 2^32 的数字做加减法，本身的误差就可能在 2 ~ 2^9 左右，这个误差是相当巨大的。

这段程序一个明显可以改进的地方是把乘 InvDenom 从 u v 中去掉，但 Denom 看起来可能是负数，需要增加符号判断。那么代码应该写成：

    float Denom = (dot00 * dot11 - dot01 * dot01);
    float u = (dot11 * dot02 - dot01 * dot12);
    float v = (dot00 * dot12 - dot01 * dot02);

    if (Denom < 0) {
        Denom = -Denom;
        u = -u;
        v = -v;
    }
    float EPS = 1e-4f * Denom ;

    // If point lies inside the triangle, return interpolated ycoord.
    if (u >= -EPS && v >= -EPS && (u+v) <= Denom+EPS) {
        *h = a[1] + (v0[1]*u + v1[1]*v) / Denom;
        return 1;
    }       

光这样写还是不够，其实我们应该进一步把 dot00 * dot11 - dot01 * dot01 展开为 (v0[0] * v1[1] - v0[1] * v1[0]) * (v0[0] * v1[1] - v1[0] * v0[1]) 。这样，就不会在四次方的基础上再做加减法，而是在二次方的基础上先做加减，再做乘法。这样就最大化的保持了精度。

由于简化过后，发现 Denom 是个平方数，一定为正，所以可以去掉符号判断。我优化过的函数是这样的：

static int
dtClosestHeightPointTriangle(const float p[3], const float a[3], const float b[3],const float c[3], float *h) {
    float v0[3], v1[3], v2[3];

    dtVsub(v0, c,a);
    dtVsub(v1, b,a);
    dtVsub(v2, p,a);

    float Denom = (v0[0] * v1[2] - v0[2] * v1[0]) * (v0[0] * v1[2] - v1[0] * v0[2]);
    float u = (v1[0] * v2[2] - v1[2] * v2[0]) * (v1[0] * v0[2] - v0[0] * v1[2]);
    float v = (v0[0] * v2[2] - v0[2] * v2[0]) * (v0[0] * v1[2] - v1[0] * v0[2]);

    float EPS = - 1e-4f * Denom;

    if (u >= EPS && v >= EPS && (u+v) <= Denom - EPS) {
        *h = a[1] + (v0[1]*u + v1[1]*v) / Denom;
        return 1;
    }
    return 0;
}

由于 u,v,denom 都有共同的项 (v0[0] * v1[2] - v1[0] * v0[2]) 可以约掉，能进一步保留精度。但需要处理一下符号问题。所以最终版本是这样的：

static int
dtClosestHeightPointTriangle(const float p[3], const float a[3], const float b[3],const float c[3], float *h) {
    float v0[3], v1[3], v2[3];

    dtVsub(v0, c,a);
    dtVsub(v1, b,a);
    dtVsub(v2, p,a);

    float Denom = v0[0] * v1[2] - v0[2] * v1[0];
    float u = v1[2] * v2[0] - v1[0] * v2[2];
    float v = v0[0] * v2[2] - v0[2] * v2[0];

    if (Denom < 0) {
        Denom = -Denom;
        u = -u;
        v = -v;
    }

    float EPS = - 1e-4f * Denom;

    if (u >= EPS && v >= EPS && (u+v) <= Denom - EPS) {
        *h = a[1] + (v0[1]*u + v1[1]*v) / Denom;
        return 1;
    }
    return 0;
}

最后这个优化版本可以通过测试。

Posted by 云风 at 08:02 PM | Permalink | Comments (10)

今天我发布了 skynet 1.2.0。

距离上次发布 1.1.0 已经有一年了。虽然我觉得给 skynet github 仓库里某个特定版本起个有意义的名字并无太大意义，因为我也不会刻意去维护一个所谓稳定版。但在 issues 中还是发现有一些同学还在基于上个 1.1.0 的 release 版提问题，我认为还是保持一年一个版本号比较好。

其实，对于活跃项目，最好的方法还是始终跟进 github 上的 master 比较好。我也刻意在维持代码的向前兼容性。skynet 的 api 已经很稳定，不用太担心更新造成项目跑不起来。话说回来，即使某次更新打破了兼容性，每次一小步的跟进也比隔上一年才同步一次，或是永不升级来得好。

跟进及时可以减少更新带来的新问题。有麻烦可以马上反馈，我更容易帮助解决；不更新容易让 bug 滞留，原本已经解决的 bug 可能在未来再次困扰你。随着 skynet 的用户越来越多，隐藏在犄角旮旯的 bug 更容易被找出来。在 issues 板块，已经有很多问题其实是在 issue 提出时已经被解决了的，仅仅只是因为未更新代码。这种问题无疑浪费了大家的时间。

这次 1.2.0 主要是累积修复了许多 bug 。例如死掉的服务可能在调用过它的服务中残留信息，导致服务地址回滚复用时系统工作不正常。还有 cluster 发包乱序，socket 并发写等问题。这些都是在大量使用时才会发现的 bug 。

另外，mongodb 和 redis 的 driver 都一定程度上增强了。这部分改进的代码都并非来自于我，而是由使用它们的同学根据实际需求完成的。

由于调试需要，我还增加了许多调试相关的指令。在过往的 blog 中都有介绍，可以通过查看本 blog 的 skynet 标签浏览。未来 skynet 的主要发展方向还是以增强运行维护功能为主，核心功能不会有太大改动。

我希望明年的 1.3 版本可以用上 lua 5.4 。这是 lua 的版本大更新，但应该对已有的项目影响不大。lua 5.4 会极大改进 lua 的 gc 效率，更及时的内存回收，能极大减少内存峰值占用。

Posted by 云风 at 11:16 AM | Permalink | Comments (8)