生存RTS《异星前哨》技术分享——燃烧你的CPU ——九四玩

大家好，我们是云蟾游戏国产科幻生存RTS《异星前哨》项目组成员，是一群热爱RTS的老炮儿。在不久前我们在游戏发售之际，分享了一些关于GPU的知识，这次我们会分享CPU相关的技术积累，希望给国内游戏的开发环境提供一些微末帮助。


在对《异星前哨》制作人的要求：同屏十万只怪进行技术拆解后，技术组的性能优化方案，围绕GPU和CPU两个模块来同步进行的，本篇日志主要来谈谈CPU的部分，与GPU不同，CPU承受的大部分压力在于：

海量的虫子寻路时产生的效率问题

基于这个关键点，我们将在下面分享CPU层面优化《异星前哨》的整个过程。

一、寻路算法的问题

开发初期，技术组分析了产品的地图需求：

1、游戏开始时创建随机地形

2、定时在多角落刷10万只若干虫子，向地图中心移动

3、角色、虫子都要有碰撞

这些需求看起来并不复杂，公司在另一个项目《铁甲雄兵》上已经积累了比较丰富的地图开发经验，所以技术组很快得到了初步方案结论，即：

使用“导航网格（Navigation Mesh）”技术


依靠已有经验来看，导航网格可以完美适配复杂、不规则、多层的地形，在寻路效率和效果上，都表现得非常优秀。

但是，当第一个DEMO出来时，问题就开始暴露：

随着建筑、单位、虫子数量的不断增加，FPS开始出现大范围的跳动，连角色行走路线也变得飘忽不定，整个游戏透露出奇怪的BUG感（误）。

经过了漫长而脱发的Debug流程，我们最终得到了结论，导航网格这玩意儿在《异星前哨》的地图上，根！本！不！适！用！

先谈谈导航网格为什么不适用，相较于传统寻路方案，导航网格的优势是：

‒        对网格进行合并，减少网格数量，减少计算量，提升效率

‒        利用三角形贴合不规则的地形，让拐弯更自然

而带来的缺点是：重构网格相当费时，耗费的时间和地图的阻挡复杂度成正比

我们再来看《异星前哨》这个产品里，产品的运行逻辑如下：

1、玩家会频繁的摆放/拆除建筑

2、地图阻挡属性因为建筑变动而变更

3、开始重构导航网格，重新定位虫子所在的三角网格

4、开始废弃旧的寻路路径，虫子开始重新寻路

5、性能逐渐被拖垮


我们通过上述的例子会发现，导航网格这种地图类型：

地形不规则、阻挡几乎不变。

比如，一个MMORPG的副本，导航网格允许离线生成，相对较为静止


但遗憾的是，在《异星前哨》这种即时战略类游戏中，情形刚好相反：

地形非常规则，阻挡频繁变动。


无奈之下，资深程序员在一个月黑风高的加班之夜，抚摸着自己仅剩的几缕头发，在报告PPT上写道：放弃使用导航网格寻路，改用传统网格寻路。

二、传统网格算法

传统网格就是我们常说的A星算法，对于做了多年开发的技术组来说几乎轻车熟路

使用A星(A-star algorithm)算法


当玩家摆放建筑时，只需要更新该建筑所占网格的阻挡属性，剩下的工作就由强大的A*算法自行解决。


一般情况下，一次寻路所消耗的时间不足1毫秒。

新的寻路模块编码工作结束后，项目再次开展了一次深度测试。

一路稳定运行，配合上GPU的优化，整体运行的FPS稳定在80。

直到虫巢发生暴动。


数千只虫子相互拥挤在路口，相互碰撞，大量虫子被挤出原有寻路路线，他们很快开始重新寻路。

偏离路线的虫子数量越来越多，FPS也急剧下降到了10。

显然，单次寻路消耗时间虽然少，但也架不住数量的增加，优化寻路效率并不能从根本上解决问题。

技术组亮出第一把武器：多线程寻路

利用CPU多核优势，成倍提升计算力，FPS明显回升。

随着虫子数量的持续增加，FPS再次回落。

技术组亮出第二把武器：采用队列来削峰

寻路队列的本质，是把大量的寻路计算，分散到不同的帧上执行，设定一个合适的并行数量，将剩余的寻路请求丢进缓存等待，控制每一帧的计算量，利用时间消化掉所有的寻路请求，稳定FPS。

当碰到提交的寻路请求源源不断的时候，自然会掉进缓存队列数量只增不减的黑洞。

所以技术组很快发现尽管帧数稳定了，但另一个问题愈加严重，出现了“成片虫子原地呆滞”的现象


尽管对自信心打击很大，但这里的问题非常明确：

海量虫子的并发寻路存在很大问题，必须解决！

三、选择洋流图方案

技术组重新回到第一步，分析产品的地图需求，经过多次的讨论，意外发现了一个突破口：

《异星前哨》虫潮爆发时有一个特点，所有怪物的目的地只有1个，就是主基地。

基于这个特点，我们的目光逐渐转移到了一个不常用的方案上：

使用“洋流图寻路法”Flow Field Pathfinding


这个方案的特点：地图上的每一个网格，都记录了前进的方向，避免大范围的遍历计算。

虫潮冲锋的时候，目的地只有主基地，非常简单粗暴，而且，玩家本身无法改变地形，玩家建造的建筑物只产生阻挡，并不影响虫潮的进攻路线。

所以，洋流图在地图生成的初期即可确定下来，无需在玩家游戏过程中动态生成。

静态生成，避免大范围遍历网格，简直是量身定做

同时，技术组还考虑到：为了降低难度，避免虫子分流，在生成洋流图时优化了部分路线，使虫子尽可能不会到处乱跑，更容易挤在一个小路口供玩家战斗。

另外，洋流图还支持多层结构，可以支持更复杂的寻路机制，有更好的拓展性。

之后还会做更多优化，针对虫群出现的位置，将虫群看成一个整体，优化前进路线，重算洋流图，让虫群的进攻看起来更加饱满、有压迫感。

虫子满载，CPU满载，帧数稳定


上述就是《异星前哨》技术组对游戏CPU效率优化的总结了，希望大家的CPU不会太热。

关于游戏：

《异星前哨》是一款融合即时战略的国产科幻生存RTS，不同于传统RTS游戏，本作舍弃了PVP对战，将核心玩法聚焦于生存模拟。玩家将成为探索外星的领导者，建立基地并抵御外星虫潮的攻势。游戏首创英雄体系融入核心玩法，每个英雄拥有专属技能、兵种以及建筑单位等；数万虫潮同屏效果震撼，可暂停和随时存档。诚邀各位体验！