粒子系统的应用
我们会经常在 2D 和 3D 游戏或者新媒体艺术上看到过粒子系统。粒子系统可以用来模拟火、水流、爆炸、烟雾、云雾、雪等效果，用途非常广泛。
在成熟的游戏引擎如 Unity、UE 上都有自己的粒子系统：
粒子系统的构成
从系统设计的角度来看的话，粒子系统一般可以分为发射器、运动器、渲染器、回收器这样 4 个模块。
- 发射器：发射器负责粒子的生成、初始位置、初始速度、角速度等等
- 运动器：运动器负责修改粒子的运动状态和参数，会受到用户交互、环境参数的影响，如果粒子在物理世界中，粒子的运动还需要物理引擎来驱动
- 渲染器：顾名思义，就是渲染绘制，如粒子的大小、颜色、贴图或者 shader 这样的控制，使用渲染器来进行渲染绘制出来。比如下图中 Unity 粒子系统中，给粒子加了材质。
- 回收器：粒子通常有生命周期，会消亡掉，回收器用来将这些消亡的粒子注销移除掉，减少不必要的计算和渲染，否则随着发射器产生的粒子越来越多，将会耗费越来越多的内存和计算资源，运行粒子系统的程序后面会越来越卡直至卡死这样的情况。在一些性能要求很严格的场景下，为了避免发射器不必要的对象创建，还时常采用了缓存池的手段，将回到的粒子放到缓存池中，粒子发射器再产生粒子的时候，从缓存池中取出，然后对初始速度等等参数进行初始化。
我们通过一个开源的在线粒子编辑器http://pixijs.io/pixi-particles-editor/#[1]来看下一个粒子系统大概都有哪些元素。
http://mpvideo.qpic.cn/0b2e54aaeaaa4iaa3pnck5qvb36dalxqaaqa.f10002.mp4?dis_k=a31bd8faef8458ce00fd14b36031154c&dis_t=1642668042&vid=wxv_2154502663860731906&format_id=10002&support_redirect=0&mmversion=false
有些读者朋友可能会说，小菜你又忽悠人了，我平时写的没这么复杂呀。但其实如果仔细研究你写的粒子系统而言，虽然没有严格按照上面的模块去划分，但从代码上看，却常常会具备上面的 4 个模块或者其中某几个模块（因为有些粒子系统是固定的数量，也不涉及到消亡，所以可能没有回收器这个模块）。
下面我们就进入 Processing 的世界，来看下我们平常是怎么写粒子系统的。
粒子系统的代码编写
下面，我们抛开上面视频中那么那么多的参数，太复杂啦，简单的，只给粒子带上速度、加速度、位置这些属性，看看一个简单的粒子系统如何编写，对思路进行剖析。
我们按照图中的流程来分析下 Daniel Shiffman 的一个 demo，这个例子在官方的 examples 中，地址为 https://processing.org/examples/multipleparticlesystems.html[2]。
最后运行效果为下图的效果
跟着小菜来解析下这块实现吧！
思路解析
- 基本粒子类：
Particle，内部有速度、加速度、位置、存活时长等常见的属性 - 疯狂粒子类：
CrazyParticle，这个类继承自Particle类，实现了旋转特性，为了能看清粒子能旋转，所以加了一个横线，从粒子的中心穿过去，旋转的话，横线发生转动，方便我们知道发生了旋转 - 粒子系统类：
ParticleSystem，包含 4 个重要实现，粒子的出生（发射器），运动（运动器）、渲染（渲染器）、消亡处理（回收器） - Processing入口类：
MultipleParticleSystems，根据鼠标点击的位置，加入一个粒子系统，上面 GIF 图中小菜加了 4 个粒子系统在不同的位置上
Particle
CrazyParticle
ParticleSystem
MultipleParticleSystems
从这个经典的例子中，我们可以看到一个简单的粒子系统的实现大概模型是什么样子的。
粒子系统的优化 - 空间分割
对于粒子之间互相有影响的粒子系统而言，我们常常因为粒子数量的增加，而运行效率变得缓慢，画面变得卡顿。
海量的粒子之间，每一帧都要循环遍历两两粒子的作用影响，而关键的是，很多计算其实是没有必要的。
我们举一个大家经常见到的一个粒子效果
不少读者朋友或许都写过类似的实现，大概思路就是让运动的粒子，当距离一定小的时候，将他们用线连接起来。
我们常规的思路一般是要双层 for 循环，来计算找出两两粒子之间的距离。如下面的实现思路
代码语言：javascript复制void draw() {
background(0);
for (Particle p : particles) {
p.update(); // 粒子的运动
makeConnections(p); // 粒子的彼此链接
p.display(); // 粒子的渲染绘制
}
}
void makeConnections(Particle p1) {
for (Particle p2 : particles) {
if (p1 != p2) { // 粒子不是自身
double dis = p1.distance(p2); // 计算距离
if (dis < RANGE) { // 距离小于规定的阈值
float distance = (float) dis;
stroke(255);
line(p1.pos.x, p1.pos.y, p2.pos.x, p2.pos.y); // 粒子连接画线
}
}
}
}
粒子数量小还好，但如果达到几十万、几百万、千万、亿万级别，程序还这样计算，就会捉襟见肘，力不从心了。
假设粒子之间距离小于30，那么就连接一条线。我们试想下，如果一个粒子位于画面左上角，一个位于画面右下角，距离非常远，明显大于 30，我们计算他们距离是否有必要？有什么办法能避免这种不必要的计算吗？
类似这种优化，就涉及到了一个很重要的优化思想，空间分区。
小菜了解到空间分区这个思想，是在做游戏开发的时候，阅读《Game Programming Patterns》这本书上学到的。
小菜与《游戏编程模式》书籍的缘分：在2015-2016做游戏开发期间，阅读到了《Game Programming Patterns》这本书，但是这本书并没有中文版本。小菜在 github 上建立了一个翻译小组，有几个热心的朋友参与了进来。后来人民邮电的陈编辑联系到了小菜，告知这本书已经取得了作者的翻译授权，为了避免侵权，需要关闭和删除掉 github 的翻译，我们小组作为 GPP 翻译组负责了这本书的中文化。小菜作为主译，在 2016 年的时候，大量业余时间扑在了这本书的翻译和反复校稿上。陈编辑提了很多意见，我们 GPP 小组这边不断调整，最终在 2016.09.01 这本书《游戏编程模式》得以出版。
在《游戏编程模式》中的空间分区这一张章节，阐述了这个空间分区的原理。
设想你在开发一个即时战略游戏。对立的阵营的上百个单位将在战场中厮杀，勇士们需要知道攻击那个最近的哪个敌人，最简单的方式就是查看每一对敌人的距离的远近，使用双重循环，和上面的粒子链接一样，算法的复杂度在 O(n^2) 级别，随着士兵数量的增多，游戏的性能会急剧下降。
刚才的粒子所在的平面空间，就好比下图中的战场，空间分区就是要将战场人为的按照一定的空间大小进行切分，在战场中厮杀的双方士兵，也就被划分到了相应的战场格子单元里面。厮杀的士兵在单元格内进行战斗，程序在处理战斗的时候，会以单元格为一个单元，处理近距离士兵们的战斗。当一个士兵因为移动，到了另外一个单元格，程序也要同步将士兵同步到新的单元格上进行战斗处理。
类比到上面的粒子连接的例子，当空间大，粒子足够多时，我们就需要将粒子按照空间分区的做法，按照合适的分区大小，将粒子归宿划分到单元格内，只需要处理每个粒子所在的单元格和相邻单元格间的粒子链接就可以了，相比双重遍历海量粒子来计算两两粒子距离，性能上提升非常巨大。
上周阅读到了十万只鸟儿在 GPU 上飞行：一次关于算法与自然的探索，作者倪豪在文章中也提到了，在极限优化粒子性能的时候，采用了空间分割算法。
由于每个粒子都有最大的观察半径 40，我便可以将 1280 × 720 的活动区域分割成 32 × 18 个长宽 40 的正方形网格，这样，每个粒子只需要遍历所在网格周围的九个网格。理由是，间隔了一个网格的粒子，相互距离肯定超过了 40。 在经过空间分割优化后，性能相比未优化平均提升三倍。
空间分区在粒子系统优化的时候，是一个非常有效的手段。感兴趣的读者可以尝试实现下。
最后
粒子系统是生成艺术中一个很重要的表现形式，我们可以对此多加练习。其中运动器掌握的运动模式和渲染器负责的渲染是非常重要的两个 part，直接决定了最后的效果的好坏。
在 openprocessing 上 郑越升[3]的 Messy Curve Draw[4]，从某种角度，也可以认为是一种特殊的粒子系统。
读者朋友们思考下面几个问题：
- 系统的发射器：粒子从哪里产生？粒子本身有什么属性？
- 系统的运动器：粒子如何运动？才会形成飞线涂鸦的效果？
- 系统的渲染器：怎么渲染粒子？以及粒子运动产生的飞线？
- 系统的回收器：粒子何时结束运动？怎么算消亡？
当然作者并不是这样的思路（见公众号坏打印机 Processing 飞线作画简单分析及代码），但从粒子系统的 4 个模块去思考，会帮我们更好的去认识这个问题，以及应对未来更复杂的系统。
参考资料
[1] http://pixijs.io/pixi-particles-editor/#: http://pixijs.io/pixi-particles-editor/#
[2] https://processing.org/examples/multipleparticlesystems.html: https://processing.org/examples/multipleparticlesystems.html
[3] 郑越升: https://openprocessing.org/user/111166
[4] Messy Curve Draw: https://openprocessing.org/sketch/486307
