十万只鸟儿在 GPU 上飞行：一次关于算法与自然的探索

曾经有一个问题困扰了我很久，为什么这个世界上的人和物质，都会在不同尺度下呈现不同的聚团和排斥。人与人相互靠近，却会形成人群与人群的竞争与敌对，原子和分子相互靠近，却能产生相互分离的物体，乃至星球和星系。

怀着这份朴素的思考，我克服了艺术生的专业壁垒，开始研究起了复杂系统（Complex System）、群体智能（Swarm Intelligence）、元启发式（Metaheuristics）、自组织（Self-Organization）、涌现（Emergence）、ABM（Agent-Based Modeling）这些曾经离我十分遥远的概念，将这些研究与发现做成了艺术作品，发布了人生第一个 App Store / Steam 应用。

如果你也有兴趣，不妨了解一下这个故事，和我们一起探索……

最初的启发

我是一个很少玩游戏的人，但《Frost》和他的续作《Lifelike》却给我留下了异常深刻的印象，游戏的官网告诉我，目前没有任何 CPU 能提供如此高性能的集群模拟，而该游戏基于 Metal 开发了 GPU 算法。

后来学习到了 Unity Visual Effect Graph，一个先进且易用的 GPU 粒子系统，但这个系统没有办法模拟粒子间作用，这加深了我的困惑。Frost 是怎么实现的？

和吕老师分享了我的困惑

从鸟群开始

在学术界，群集系统的开山之作是一个 1986 年的仿生程序 Boids，它将鸟群的运动归纳成了个体运动的三个基本法则，排斥（Separation）、对齐（Alignment）、靠近（Cohesion），且每个个体只能观察到一定范围甚至一定视域的其他个体。

，时长00:27

经典的鸟群算法 Boids

Processing 官网的 Boids 算法案例，https://processing.org/examples/flocking.html

两群鸟的相遇

项目网站：https://bingweb.binghamton.edu/~sayama/SwarmChemistry/

当我发现这一研究时，瞬间兴奋了起来，粒子系统继承了鸟群模型的三个基本法则，添加了更多的行为法则，同时在一个场景里，添加了不同的鸟群。多样性在一瞬间涌现了出来。

项目官网上可以下载 Java 程序，同时也开源了代码。

但是，程序把粒子的个数限制在了 300，而我们都清楚的一点是，CPU 的（单线程、遍历）找邻居算法，复杂度是 O(N2)，即粒子数量多一倍，计算的耗时是原来的四倍，模拟的瓶颈一下子就出现了。

GPU：一万倍性能提升

英伟达的老黄曾经说过一句话，根据摩尔定律，GPU 相比 CPU 的提升相当于把十年后的计算资源交到现在的研究人员手中，这也是 GPU 计算感知明显的原因吧。

YouTube 上的一位博主，游戏 Headmaster 的制作人，实现了 50w 粒子的 Boids 模拟，原理和 Processing 的 Pixel Flow 库例子程序一样，并不是真正在查找邻居，而是将粒子的信息写入一张向量材质，从而改变每一个粒子的位置。

基于向量场材质绘制的模拟，可以轻松实现十万级别的 Boids 近似模拟，但这种方法不适用我想实现的复杂模型

第一次尝试
Python + Numba

我的第一次实验是在 Python 上使用 Numba 库绑定 CUDA 进行加速，借助 Python 极低的门槛和 Numba 神奇的语法，我们很快就将 CPU 算法移植到了 GPU 平台，并用 OpenGL 绘制出来。

Numba 库，只需要添加几行代码就可以让一个函数在 GPU 上并行

第一次跑通算法，当时的画面还是黑白的

，时长00:27

使用 OpenGL 渲染的程序

在教室里测试运行

展览效果图

第二次尝试
TouchDesigner

第一次用 TouchDesigner，很多效果都不知道该怎么做，但至少是跑通了

结课忽悠人的时候，已经有了 60 倍的性能提升

遗憾的是，我们并没有在 TouchDesigner 中直接调用 OpenGL 计算着色器（因为 macOS 不支持），所有的运算仍然是在 Python 的 Numba 中完成，只是将绘图部分从 OpenGL 转移到 TouchDesigner 中。

除此之外，Python（Numba）没有结构体和向量类型，所有的数据都需要存在数组中，x、y 坐标的运算就都得写两次，非常麻烦。

第三次尝试
Houdini

在学习了 Houdini 之后，我打开了新的世界，对 OpenCL 的支持让我有了编写底层 GPU 程序的机会（CUDA C++ 对我来说真的太困难了），便捷的数据绑定、超高的性能，只用几个节点几次连接就把算法全部移植成功了。

在 Houdini 中运用 OpenCL 节点加速模拟，借助向量语法轻松改写三维

用 Redshift 渲染（没对上焦就很艺术）

Houdini OpenCL 的表现让我有了进一步优化的动力，甚至也有了想做跨平台应用的念头。明明是一个离线特效软件，却能拥有异常流畅的实时性能，比 Python 的 Numba 不知道好多少……

最后的集大成

Unity

在踩遍无数坑后，我终于找到了最最合适的平台。

计算着色器：解决互操作问题，多平台编译

在此前的 Python / Houdini 程序中，所有粒子数据的计算和渲染都需要在 CPU、GPU 之间来回拷贝，由于传统架构的内存不共享，这将严重影响计算性能，而事实上，GPU 的计算程序和绘图程序是可以互操作的，即索引同一段数据（Buffer）。

而 Unity 恰好提供了一个完美的解决方案，HLSL Compute Shader。Unity 会将写好的 HLSL 程序编译成 Metal、DirectX、Vulkan 和 OpenGL，从而省去多平台重写代码的麻烦，同普通的 Shader 程序一样，都支持读取 GPU 中的 Buffer。

即便什么优化都没有做，也能轻松实现数倍的性能提升，在粒子数量大的情况下尤为明显。

追求极限的优化：空间分割算法

直到现在，所有粒子的找邻居计算都是一整个暴力遍历，而有几种奇妙的方法，可以让程序对每个粒子只查找周围的粒子，大大省去检索的时间。其中最好理解也最适合这个场景的方法，就是空间分割。

由于每个粒子都有最大的观察半径 40，我便可以将 1280 × 720 的活动区域分割成 32 × 18 个长宽 40 的正方形网格，这样，每个粒子只需要遍历所在网格周围的九个网格。理由是，间隔了一个网格的粒子，相互距离肯定超过了 40。

在经过空间分割优化后，性能相比未优化平均提升三倍。

除此之外，还有排序算法、K-D Tree 分割，值得探索。

经过基本的网格空间分割后，性能达到了 20w 粒子 60FPS，3070Ti，对比 Processing 的 CPU 程序性能提升达一万倍

经过基本的网格空间分割后，性能达到了 20w 粒子 60FPS，3070Ti，对比 Processing 的 CPU 程序性能提升达一万倍

新的发现：粒子系统生成斑马纹

一次偶然的尝试，我发现只要给粒子加入一个小小的机制：敌我识别，即根据类型区别对待近邻粒子，就可以产生非常奇妙的自组织形态。可能是一朵小花，也可能是一个斑马纹样。

以往斑马纹只能通过 Reaction-Diffusion 算法或是 Multi-Neighborhood Cellular Automata 算法实现，而现在，基于粒子的模型也能做到了，这或许能打开生命科学的新思路，因为，生物的基础是细胞，而不是像素。

，时长01:16

粒子运动时开出的一朵小花，也是现在的应用图标

类似蠕虫的效果，完全由粒子自组织，破坏后依旧可以恢复

独特的斑马纹路

连接 MIDI 键盘后的效果，24 个参数正好对应了 AKAI MPD218 上的二十四个旋钮，体验极佳

在学院里测试时拍摄的照片

我为作品制作的移动端 UI，可以选择有趣的预设，拍摄截图、复制粘贴参数。

VR 版本，正在开发中～

从想法到上架

一些小体会

迈出第一步，坚持尝试

还记得头一回和老师分享这个想法，是在今年的三月，那个时候我是有一些畏惧，毕竟我不是科班出身，却想去研究大部分计算机本科都不会教的 GPU 计算。

突然有一天，我被丹琪姐拉到学院问，环保部要办一个 COP15 生物多样性大会的展览，你们有没有兴趣做一些作品？

我才再一次想起这个话题，心想，要不要挑战一下？

我找来了有着同样追求的朋友们：我的高中死党，跑通了第一个 Python 程序的陈同学（Github：CPunisher），过着美国时间、每晚 24 点交接工作的 Unity 队友时辰（抖音@时辰不死于背锅），以及一起做创意、策划和展览的金希、杜西大师哥。

一路上遇到了不少高人，给了我们成吨成吨的帮助。

Github 好♂友，懂得都懂

连肝了三天三夜，才把 iOS 程序的黑屏点亮了，这时队友带上来的 0.72（楼下一串串香店名）让我顿时心虚激荡，双厨狂喜

班主任杨老师，我们的显卡爸爸，承包了一整个专业的算力，带领全班秒杀 R9000P

沈浩老师向我引荐的新媒体艺术家任远，《Processing 创意编程》一书的作者，给我提的一个 “小目标”，成为了我不断追求极限的动力

游戏系的萌神呼风唤雨，请费老师、郑师哥教我空间分割等算法

这位研究群集化学的可爱的日本教授回复了我的邮件，并问我能不能做出带进化算法的版本

和上面提到的游戏开发者分享了我的程序

系主任：你们这是雁过拔毛，我要收管理费

高手，都是高手

课程海报，感谢环保部赏脸！

聆听 WWF 官方介绍生物多样性

特别感谢孙老师、丹琪姐、博哥以及黑弓的大佬们，鸥哥、老曹、小鹿姐，挤出时间亲临指导，带我们混吃混喝，希望速速再来玩

（都说我们这届是最惨的，因为疫情一众小学期出国访学的项目都取消了，但也还是成功拥有了一个个精彩的小学期，只能说，中传数媒，入股不亏 👍）

发布、提交审核

终于过审了！

一直听说苹果的审核很严格，经历了一次后觉得，是真的很麻烦，但踩这些坑特别值。

曾经做过的很多东西，都停在了原型、Demo，从未想过要发布出来，让更多的人看到。这一次我选择放下了心里的完美主义，不等功能 100% 完善，先发了再说。

然后迎接我的，是开发者账号注册，出口合规，美国报税单，外汇账户，分级评定，打包上传，这些完全没接触过的东西。

App Store 必须提交的废话文学作品：隐私政策（没有别的意思，只想说对于这种不收集任何隐私数据的程序还要专门开一个网页说明没有收集真的很费事）

第一次打包上传成功

一直在打包，一直在测试

上传了几十张不同尺寸的截图、宣传图，终于见到了自己的商店页面

Steam 过审！

App Store 过审！

写在最后

就在不久前，2021 年诺贝尔物理力学奖颁发给了三位对复杂物理系统作出重要贡献的科学家，复杂性思维正变得越来越重要。天气在确定性中无端变化，生命在无序世界中积累秩序。每一个个体都有独立的目标，在有限的连结中传递信息，却能产生令人震惊的群体智慧。这大概也是我如此痴迷于此的原因吧。

正在构筑东京铁路的黏菌

大一时绘制的朋友圈点赞关系网，根据图关系进行聚集分区

我的奇异吸引子的生成艺术作品

多近邻感知细胞自动机（Multi-Neighborhood Cellular Automata）

反应—扩散（Reaction-Diffusion）

完。

点击阅读原文或在 App Store 中搜索 “参数生命” 即可购买应用（Steam 版本 2021.12.3 上线）。如果你有任何疑问，欢迎添加我的微信（nhciao，请备注名字），一起交流！