云风的 BLOG

我想用 C 实现一个内存紧凑的 ECS 框架，希望数据结构足够的简单，且能管理海量的对象。所以我让每个 component 就是一个不包含任何引用的 struct ，并带有一个 32bit 的 id 。并把这样的一个数据结构放在一块连续内存中。

这个 id 没有对外暴露的 API （不是 entity id ），可以在运行过程中调整。如果两个不同类型的 component 有相同的 id ，即认为它们同属一个 entity 。id 的作用是管理 component 的生命期，以及在遍历 component 时，可以找到同个 entity 上其它的组件。

对于我的应用场合来说，最多的操作是遍历单类 component 的集合。这种操作在这个数据结构下特别简单，就是 for 循环遍历一个简单的数组。但有些系统会需要在处理一个 component 时，找到它归属的 entity 上的兄弟组件。由于我不想用额外的内存建立这些 component 间的联系，所以这个开销就会特别大。如果不做任何优化，查找是 O(n) 的，n 为组件的数量。这显然不能接受。

第一步优化，我让组件在组件集数组中保持有序，按 id 排序。id 本身在分配的时候是单调递增的，所以只要 32bit id 不回绕就能一直保持有序。一旦回绕，我们重排一下即可。对于有序的数组，用二分查找可以减少到 O(log N) 的时间复杂度。

如果 N 特别大（十万以上）时，还是比较慢的。那么，有没有可能对二分查找做进一步优化呢？我做了一点尝试。

阅读全文 "带猜测的二分查找算法" »

云风 提交于 02:05 PM | 固定链接 | 留言 (5)

最近在尝试做一个类似异星工厂的游戏原型。由于最终希望在内存有限的手机上运行，所以不得不考虑内存如何有效利用的问题。

这是因为，我在玩异星工厂（加上一些 mod ）时，发现 PC 内存能占到 10G 以上，且这些内存大部分都不是图像资源，是实打实的逻辑数据。我稍微估算了一下，在一些内容丰富的 mod 中，游戏内的对象能够达到数十万，甚至上百万之多。用传统方法使用的内存势必以 G 计算。

如果希望同样的逻辑跑在手机上，我希望把逻辑数据控制在 500M 之下。除了从游戏玩法做做一些限制外，还需要对逻辑占用的内存精打细算。

阅读全文 "缓存在 Lua 中的配置表" »

云风 提交于 06:20 PM | 固定链接 | 留言 (6)

这两天想给一个想法做个简单的原型，因为涉及人机交互，需要在屏幕上绘制一些简单的交互元素。当然，现在有很多工具可供利用。过去遇到这种事情，我会尝试用已有的各种开源游戏引擎（我尤其推荐 PICO-8），或是直接在浏览器中用 css/javascript 写等等。

最近几年我玩了大量 RogueLike ，想尝试一下在 console 下用 ascii 字符来拼凑画面。这很有趣，能让我回忆起小时候 Apple ][ 上花掉的大把时光。同时我想用 Lua 来做开发，却不想引入 ncurses 这样的第三方库。最好能用几分钟就可以从零搭建起开发环境。

最好的选择当然是用 ANSI escape code 通过标准输出在 console 界面上作画了。

阅读全文 "ANSI escape code 及 Lua 封装" »

云风 提交于 10:30 AM | 固定链接 | 留言 (10)

最近，我们把自研游戏引擎的构建工具从 GNU Make 迁移到了 Ninja 。

迁移动机是这样的：

我为引擎编写了最初的 Makefile ，它可以很好的工作在 MinGW / MacOSX / iOS 平台。把基本框架搭好以后，用起来也比较方便。但是，参与开发的同事一直有用 MSVC 开发的需求，而我们迟迟没有在 Makefile 的框架里增加 MSVC 的支持。用 MSVC 的同事一直在手工维护一个 MSVC 的项目。

渐渐的，同时维护 Makefile 和 MSVC 的工程成了一个负担。

实际上，现在惯用的方法都是用一个高阶的语言去描述项目构建流程，再翻译成不同平台下的构建脚本。即使用 GNU Make ，通常我们也是先用 Make 本身设计一个框架，在这个框架下去描述构建脚本，再让 Make 在不同平台下生成不同的流程。

如果不介意引入新的工具，那么 Autoconf ，CMake ，Premake 都可以解决这个问题。

阅读全文 "构建工具从 Make 到 Ninja" »

云风 提交于 03:54 PM | 固定链接 | 留言 (7)

最近有点关于 Lua 不成熟的想法。

Lua 目前函数原型的常量表只支持了布尔、数字和字符串类型的常量。而 table function 这些是不会存在于常量表中的。

我想，如果常量如果不限于前三种类型，可能会更好一些。比如，一个惯用法是在代码前面写上

local pairs = pairs

这个惯用法是基于 local 变量比全局变量少一次 hash 表查询，性能可能会高一点。 但实际上，往往差距并不大。而这种写法还会给其它应用 pairs 的函数增加额外的 upvalue ，很有可能得不偿失。

阅读全文 "扩展 Lua 的常量类型" »

云风 提交于 11:12 AM | 固定链接 | 留言 (3)

本周末，阿里集团会在中南大学做校招。我作为校友，被邀请面向应届毕业生做一次技术分享。我想谈谈开源的问题。

由于技术分享的时间很短，我想在现场不太可能展开谈。所以在 blog 上先写一篇相关的子话题：在选择使用开源项目时，我的依据是什么？

我们在开发软件的过程中，总有一些模块的需求是普遍的，除了自己开发，使用一个具备合适的 License 的开源项目也是个不错的选择。

在一个程序员的职业生涯中，总会有那么一个阶段，不太愿意使用别人开发的代码。如果不是受项目进度压力所迫，宁愿自己实现。这并非是因为相信自己总能做得更好，而是希望少受牵制，能够自由发挥。而且，写代码往往比理解代码更简单。整合多块不同团队开发的代码也更难保证项目各个部分的一致性。

阅读全文 "选择开源项目的几点原则" »

云风 提交于 02:53 PM | 固定链接 | 留言 (18)

TL;DR 系统中每个和系统活得一样久的单元（服务），都应该提供一个关闭接口，而不是释放接口。关闭只做必要操作，不必释放资源，不必和其它单元协调。整个系统退出时，只需要命令所有单元关闭，然后让世界戛然而止。

最近在和同事一起完善 ltask 。这个项目可以看成是对 skynet 的一个回顾。我们打算把它用在客户端引擎中。

在 ltask 中，原来在 skynet 里用 C 实现的 timer network 等线程都被移到了 lua 中实现。它们被成为 exclusive service ，会独占一个操作系统线程，但之外的部分和普通服务并没有太大区别。

因为这样一些基础服务也挪到了 lua 中实现，以前在 skynet 中天然而成的层级被模糊了。在 skynet 中，这些独占线程都是先于其它服务启动，而晚于大多数服务退出。它们的启动和退出流程都在 C 代码中固定下来。

阅读全文 "服务的创建和退出问题" »

云风 提交于 10:32 AM | 固定链接 | 留言 (7)

我们的游戏引擎采用的资源格式是 gltf 2.0 。

gltf 在这几年发展很迅猛，我认为是 3d 文件格式中标准化做的最好的一个。可惜，游戏行业中，美术创作人员常用的 max maya 等工具对其支持还有瑕疵。Autodesk 在 2019 年作为 contributor 成员加入了 Khronos 组织，在 max maya 这些 Autodesk 工具中看到官方的 gltf 支持应该不会等太久。来自官方的消息 ，‎在 2020 的 3 月底，gltf 加入官方支持已经处于 Under Review 状态。希望今年内可以看到。

阅读全文 "fbx 到 gltf 转换问题" »

云风 提交于 03:07 PM | 固定链接 | 留言 (13)

TCP 连接是双工的，既可以上行数据，又可以下行数据。连接断开时，两侧通道也是分别关闭的。

从 API 层面看，如果 read 返回 0 ，则说明上行数据已经关闭，后续不再会有数据进来。但此时，下行通道未必关闭，也就是说对端还可能期待收取数据。

同样，如果 write 返回 -1 ，错误是 EPIPE ，则表示下行通道已经关闭，不应再发送数据。但上行通道未必关闭，之后的 read 还可能收到数据。

用 shutdown 指令可以主动关闭单个通道（上行或下行）。

阅读全文 "skynet 处理 TCP 连接半关闭问题" »

云风 提交于 11:06 AM | 固定链接 | 留言 (18)

ltask 是我前两周实现的一个 lua 的多任务库 。

这个项目复用了我之前的一个类似项目的名字 。目的是一样的，但是我做了全新的设计。所以我干脆将以前的仓库移除，以同样的名字创建了新的仓库。

和之前的版本设计不同。在消息通讯机制上，这个更接近 skynet 的模型，但它是一个库而不是一个框架。调度模块是按前段时间的想法实现的，不过只做了一个初步的模型，细节上还有一些工作待完善。

阅读全文 "ltask ：Lua 的多任务库" »

云风 提交于 03:51 PM | 固定链接 | 留言 (3)

这篇是继续上次的一些想法。

我最近想重新做一个新的基于消息管道的 N:M 多任务调度器。主要用在我们的客户端上。算是解决在使用 skynet 多年来总结出来的一些问题。

首先，我想改变 skynet 服务直接将待发消息投递到对方消息队列的做法。发出消息会让服务挂起，等待投递。

然后，我设计了一个叫做调度器的模块，用于把带发消息投递到对应的接收管道中。调度器是发送消息的消费者，接收管道的唯一生产者；而每个服务是它自己的发送消息的唯一生产者，接收管道的唯一消费者。这样没有竞争，当消息队列是定长的时候，也无需使用锁（但引入了消息队列满的新状态）。

阅读全文 "关于 skynet 调度器的一点想法(续)" »

云风 提交于 11:38 AM | 固定链接 | 留言 (8)

stdatomic 已经是 C11 的标准，并且成为了 C++ 标准的一部分。msvc 也将会支持 stdatomic 。在 skynet 项目开始的时候，还没有这个可以用，所以我采用的是更早一点的 gcc sync 系列的扩展 。

我想，用 stdatomic 来实现原子操作，会有利于 skynet 未来的发展。上周花了点时间熟悉这套 api 并在 skynet 中实现。同时保留了之前的实现，如果编译器定义了 __STD_NO_ATOMICS__ 就会切换回老版本。

阅读全文 "把 skynet 的原子操作换成了 stdatomic " »

云风 提交于 10:14 AM | 固定链接 | 留言 (3)

上次谈到服务器上寻路算法的优化。文末提到，其实，针对具体需求，我们实际上可以预运算所有的路径，把结果持久化在文件中，运行时用 O(1) 的时间就可以查询到任意路径。

对于半径为 N 的地图网格，选取任意两点作为起点和终点，一共有 N^4 数量级的路径，直接按起点和终点来缓存路径显然不现实。

但实际上，除非整张地图是个复杂的迷宫，大部分路径是重复的。这和人实际上行路是一样的。如果你从家中的卧室去到办公室的工位上，整条路径和你从客厅出发是高度重叠的；仅有出家门前的那一小段略有不同。

在服务器上寻路，通常解决的是 NPC 的小范围内移动绕开障碍（从卧室到家门）的问题，远距离移动的路线（从家到公司）应当在另一个层面去解决。

基于网格寻路无论是用 A star 还是基于图的 dijkstra 算法都非常简单，这里不谈算法，只谈结果的持久化问题。

为了解决起点和终点有 N^2 种可能性，这个数量级太大的问题，我们可以适当的将地图划分成若干区域。如果每个区域都是一个内部没有任何障碍物的凸多边形，那么，当我们的起点和终点都落在同一个区域时，连接两点的直线就是最短路径。

阅读全文 "预运算地图寻路的一种方法" »

云风 提交于 02:59 PM | 固定链接 | 留言 (6)