在上一篇研发日志《研发日志技术篇(上)-如何死磕GPU》里，我们提到了《异星前哨》制作人的疯狂要求：同屏十万只怪。
技术组的性能优化方案，是基于GPU 和CPU两个模块来同步进行的，本篇日志主要来谈谈CPU的部分，与GPU不同，CPU承受的大部分压力在于：
海量的虫子寻路时产生的效率问题
基于这个关键点，我们将在下面分享CPU层面优化《异星前哨》的整个过程。
一、寻路算法的问题
开发初期，技术组分析了产品的地图需求：
1、游戏开始时创建随机地形
2、定时在多角落刷10万只若干虫子，向地图中心移动
3、角色、虫子都要有碰撞
这些需求看起来并不复杂，公司在另一个项目《铁甲雄兵》上已经积累了比较丰富的地图开发经验，所以技术组很快得到了初步方案结论，即：
使用“导航网格（Navigation Mesh）”技术
依靠已有经验来看，导航网格可以完美适配复杂、不规则、多层的地形，在寻路效率和效果上，都表现得非常优秀。
但是，当第一个DEMO出来时，问题就开始暴露：
随着建筑、单位、虫子数量的不断增加，FPS开始出现大范围的跳动，连角色行走路线也变得飘忽不定，整个游戏透露出奇怪的BUG感（误）。
经过了漫长而脱发的Debug流程，我们最终得到了结论，导航网格这玩意儿在《异星前哨》的地图上，根！本！不！适！用！
先谈谈导航网格为什么不适用，相较于传统寻路方案，导航网格的优势是：
‒ 对网格进行合并，减少网格数量，较少计算量，提升效率
‒ 利用三角形贴合不规则的地形，让拐弯更自然
而带来的缺点是：重构网格相当费时，耗费的时间和地图的阻挡复杂度成正比
我们再来看《异星前哨》这个产品里，产品的运行逻辑如下：
1、玩家会频繁的摆放/拆除建筑
2、地图阻挡属性因为建筑变动而变更
3、开始重构导航网格，重新定位虫子所在的三角网格
4、开始废弃旧的寻路路径，虫子开始重新寻路
5、性能逐渐被拖垮
我们通过上述的例子会发现，导航网格这种地图类型：
地形不规则、阻挡几乎不变。
比如，一个MMORPG的副本，导航网格允许离线生成，相对较为静止
但遗憾的是，在《异星前哨》这种即时战略类游戏中，情形刚好相反：
地形非常规则，阻挡频繁变动。
无奈之下，资深程序员在一个月黑风高的加班之夜，抚摸着自己仅剩的几缕头发，在报告PPT上写道：放弃使用导航网格寻路，改用传统网格寻路。
技术组的性能优化方案，是基于GPU 和CPU两个模块来同步进行的，本篇日志主要来谈谈CPU的部分，与GPU不同，CPU承受的大部分压力在于：
海量的虫子寻路时产生的效率问题
基于这个关键点，我们将在下面分享CPU层面优化《异星前哨》的整个过程。
一、寻路算法的问题
开发初期，技术组分析了产品的地图需求：
1、游戏开始时创建随机地形
2、定时在多角落刷10万只若干虫子，向地图中心移动
3、角色、虫子都要有碰撞
这些需求看起来并不复杂，公司在另一个项目《铁甲雄兵》上已经积累了比较丰富的地图开发经验，所以技术组很快得到了初步方案结论，即：
使用“导航网格（Navigation Mesh）”技术
依靠已有经验来看，导航网格可以完美适配复杂、不规则、多层的地形，在寻路效率和效果上，都表现得非常优秀。
但是，当第一个DEMO出来时，问题就开始暴露：
随着建筑、单位、虫子数量的不断增加，FPS开始出现大范围的跳动，连角色行走路线也变得飘忽不定，整个游戏透露出奇怪的BUG感（误）。
经过了漫长而脱发的Debug流程，我们最终得到了结论，导航网格这玩意儿在《异星前哨》的地图上，根！本！不！适！用！
先谈谈导航网格为什么不适用，相较于传统寻路方案，导航网格的优势是：
‒ 对网格进行合并，减少网格数量，较少计算量，提升效率
‒ 利用三角形贴合不规则的地形，让拐弯更自然
而带来的缺点是：重构网格相当费时，耗费的时间和地图的阻挡复杂度成正比
我们再来看《异星前哨》这个产品里，产品的运行逻辑如下：
1、玩家会频繁的摆放/拆除建筑
2、地图阻挡属性因为建筑变动而变更
3、开始重构导航网格，重新定位虫子所在的三角网格
4、开始废弃旧的寻路路径，虫子开始重新寻路
5、性能逐渐被拖垮
我们通过上述的例子会发现，导航网格这种地图类型：
地形不规则、阻挡几乎不变。
比如，一个MMORPG的副本，导航网格允许离线生成，相对较为静止
但遗憾的是，在《异星前哨》这种即时战略类游戏中，情形刚好相反：
地形非常规则，阻挡频繁变动。
无奈之下，资深程序员在一个月黑风高的加班之夜，抚摸着自己仅剩的几缕头发，在报告PPT上写道：放弃使用导航网格寻路，改用传统网格寻路。
