问题

2020/09/08
数据结构与算法
很多房间和门声音传递
垃圾回收机制
C++ 11 特性
角色状态机
AI实现
寻路
技能
位移同步
骨骼动画
C++ 迭代器什么情况下会失效

2020/01/01
怎么画一个圆
怎么判断一个点是否在三角形内
一组数中找出第K大的数 TOP K
一组数中，判断有没有组合等于一个固定的数 subsetsums问题
简单计算器的实现
怎么渲染一个半透明的玻璃杯
同步如何实现的影子追随，预判法平滑处理
团队管理技术框架团队人事管理
骨骼动画

C++11有那些特性？
C++11模板中的特化和偏特化分别指什么？都在那些情况下应用？
C++11模版的高级使用有那些？请举出例子。
Java Runtime和Lua Runtime有什么区别和相同点？
游戏中状态机如何实现REDO，UNDO和MERGE？（用stack即可实现）
极大极小算法的原理和在AI中的应用？
3D游戏中相机是有那三个元素构成的（Translate，Target和Up Vector）,分别起什么作用，如何使用四元数进行相机的变换？

网易游戏的面试流程整体走下来，感觉还是蛮规范的，网易确实在认真的招人和面试，我的感觉是网易希望招聘的应届生除了有一个拿得出手的项目之外（最好是游戏相关的），还要在以下这两个方面至少熟悉一样：

计算机图形学
游戏服务器编程
然后再说一下网易的基本要求，当然了，什么数据结构，操作系统，数据库，编译原理这些的基本原理和应用就不细说了，都是本科生基础必会的东西，说些和游戏相关的要求：

对C++的模版的高级用法要了解的比较深入。
对C++的内存管理的各种解决方案要非常熟悉并亲手实验过。
对AI的各种算法要有了解：比如博弈论中的极大极小算法，A*算法的优化等等
对C++的装载链接过程和Lua的虚拟机的一些底层实现要有了解
对VS或者Xcode这两种IDE需要可以熟练的应用
需要的项目经历：自己开发过一个简单的游戏引擎或者是做过比较复杂的游戏Demo（大概是Kingdom Rush这个级别就可以了吧）
对Unity3D或者Cocos2d-x有着丰富的使用经验（可以没有，有的话加分）
对OpenGL或者是DirectX要有了解，做过一些Shader和Renderer （可以没有，有的话加分）
了解过网易的后端框架Pomelo（可以没有，有的话加分）

如何对手机游戏进行优化，我的回答基本上是以下这样的
一般分为内存优化帧数优化，内存优化和运存优化。
帧数优化可以考虑对一个message loop中的逻辑运算进行优化，比如可以考虑A*的剪枝。或者进行time slice，具体可以参考我的这篇文章
体积和运行内存优化有以下几点
使用工具对资源进行打包，使用TexturePacker等工具把多张资源合成一张图片。
采用png压缩工具，在打包图片之前对每张图片进行压缩，降低图片质量。
针对不同的平台使用特定的压缩格式的图片
如果项目中帧序列占的比较多，那么可以采用降帧的方式来优化。
缩放图片，将原来图片缩小为原来的70% ~ %80，再对图像进行放大
采用编辑器，将大图转化为拼接，那么就可以利用地图编辑器、动作编辑器等从而减少体积，降低内存的使用。
如何在对游戏的“手感”进行改进：
游戏手感一般指的是打击感，那么我就在打击到一个游戏对象时，游戏对象要产生击退的效果，产生该对象被打击的感觉。
时间控制要恰当，要让某个对象（比如火球，拳头）打击到另一个游戏对象的时候，才产生击退效果，这就需要进行使用消息机制和回调来解决。
如何在数据库中存储一个人的所有装备
建立一个人物ID和装备ID的关系表。
将人物的所有装备的id序列化为一个JSON字符串存储为人物的一个字段。
这两个最大的区别是在修改装备时，第一个只会影响一条记录，当时第二个会影响所有装备，一旦出现bug还让玩家损失所有装备。两者各有利弊，根据使用场景自己权衡。
C++11的新特性？
如何对一个快排进行优化使得它的最坏的时间复杂度达到O（LogN）？
Lua和Unity中的协程是怎么使用的，都有什么区别？
我的游戏Demo中AI的设计思路是怎样的。
如果让你设计一个暗黑破坏神的简化版手机游戏，你会从哪里开始设计。

项目要点

阴影
翅膀身体武器合并 draw
五方向
C#和lua的通信
消息分发机制广播观察者 dispatch

核心战斗
角色状态管理待机移动释放技能被击
技能实现火球瞬移石化
buff
同步
地图
寻路

游戏优化

DrawCall 优化

面数
代码逻辑优化
各个功能的逻辑优化
寻路 A*优化，剪枝
减少update刷新
渲染优化
渲染顺序
pass 数目
batch合并优化
UI batch 优化
UI层次
TexturePacker
使用LOD技术精模糙模

内存优化

帧序列减少帧数
png图片压缩
提高纹理复用率
帧序列转帧骨骼动画
纹理尺寸降低画质

字体优化

控制字体文件数量。除了系统默认字体，自定义字体控制在1~2个为宜。
少用字体的阴影/描边/发光等效果。
剔除字库中无用的字形。可以借助FontSubsetGUI或FontPruner给字库瘦身。

骨骼动画

面数
顶点数
骨骼数
贴图

模型数据

unsigned int unsigned short
三十二位浮点数压缩成十六位浮点数
unity中optimize mesh
unity中mesh compression

场景优化

画质等级
面数控制
灯光烘培
剔除不可见的三角形

粒子特效

粒子美术规范

 单个粒子的发射数量不超过50个。
 减少粒子的尺寸，面积越大就会消耗更多的性能。
 粒子贴图必须是2的N次方，尽量控制64x64以内，极少量128x128或256x256，最大不超过256x256。
 尽可能去掉粒子贴图的Alpha通道。
 尽量不用Alpha Test。
 尽量使用已有的材质，提高合并渲染的优化概率。
 材质优先用Mobile目录下的材质。
 尽可能不用模型做粒子，如果使用，要控制模型面数在100以内，最大粒子数在5以内。
 单个特效渲染数据限制：
 　　小型特效（如受击特效、Buff特效）的面数和顶点数在80以内，贴图在6464以内，材质数2个以内。
 　　中型特效（如技能特效）的面数和顶点数在150以内，贴图在128128以内，材质数4个以内。
 　　大型特效（如全局特效、大火球）的面数和顶点数在300以内，贴图在256*256以内，材质数6个以内。

材质

纹理

Read/Write
启用 Read/Write会导致纹理占用两份内存，一份在GPU端，一份在系统内存中。因为启用 Read/Write说明CPU端逻辑程序可能在运行时读取或修改纹理像素信息（GetPixel32,SetPixel32），像素信息必须在系统内存中保留一份。而在项目中，绝大多数的图片都是只供GPU渲染引用的，所以如果没有特殊需要就禁用Read/Write。

Mipmaps
mipmap主要是用在3D场景中的模型贴图，渲染底层会根据物体在屏幕中呈现的实际渲染大小选择适当的一级mipmap。如果相机的远近距离对某些物体渲染到屏幕的大小没有任何影响（如正交相机），那么这些物体的贴图就应该禁用mipmaps，最典型的就是UI界面的贴图。这几乎可以降低接近1半的贴图内存占用。

AutoCompressed
压缩图片格式对于移动设备是非常有用的，因为相对于truecolor格式，这将大大减少内存的占用。注意，这里的压缩不是单指贴图文件的压缩，而是纹理贴图像素数据在内存中就是压缩格式的，渲染采样时，由GPU负责实时解压的。所以压缩格式与GPU的厂商是具有相关性的，Android和Apple的设备支持的压缩格式就不一样。这种压缩是有损的，以牺牲贴图的像素精度为前提的，所以需要我们研发人员根据实际美术效果需要自己把握。作为程序，建议纹理贴图都采用自动压缩格式，这样Unity能根据目标平台生成其对应的压缩格式纹理。根据之前的项目经验，3D模型的贴图、特效贴图、和部分UI贴图是非常适合采用压缩格式的。而部分对画质要求很高的图片可以使用truecolor，这个需要根据项目实际情况灵活运用。下图是各平台纹理压缩格式情况介绍。

1024 2014(ARGB) 1024 2014(RGB)
ETC1(Android) 不支持 0.5M
ETC2(Android) 1M 0.5M
PVRTC(IOS) 0.5M 0.5M
DX1(Windows) 不支持 0.5M
DX5(Windows) 1M 不支持
TrueColor 4M 3M

CPU优化

缓存计算结果

std::map<KeyType, ValueType> _cache;

ValueType Calculate(KeyType key)
{
    // 先尝试从缓存中获取结果，有就直接返回。
    if (_cache.count(key) > 0)
    {
        return _cache[key];
    }
    // 缓存不存在，执行真正的计算，并缓存计算结果。
    ValueType res = DoCalculation(key);
    _cache[key] = res;
    return res;
}

复杂数学计算。Sin/Cos/Pow/Sqrt等运算要花费一定计算量，如果是第一次计算，可以将结果缓存起来，下次遇到相同的计算，直接从缓存中取值。
物理模拟结果。物体的物理模拟过程耗费大量计算，但有些物体模拟完之后就处于静止状态，可以将它之前的模拟结果存下来，防止每帧更新计算。现代主流商业引擎都支持这种优化。
光照贴图。光照贴图是离线将场景的静态光影计算并缓存成贴图，渲染时只需要采样光照贴图的颜色，极大降低了光照计算复杂度。
搜索结果。例如场景节点搜索，场景节点一般采用树形结构，如果查找的节点很深，将显著增加遍历次数，此时很有必要将查找结果缓存起来。
逻辑模块复杂的计算。游戏的逻辑模块，涉及到复杂的计算都可尝试用缓存法降低CPU负担。

预处理

限帧法

计数法。用一个变量记录更新次数，每累计到某个数才执行更新。
计时器。利用Timer机制触发，每隔固定时间触发一次更新。
协程。协程是运行于主线程的伪线程，但可以模拟异步操作，没有多线程的副作用。故而也可以用于限帧操作。
事件触发。每帧查询状态改成事件触发，也是游戏常用的一种优化手段，用来限帧也非常有效。

主次法

主次法跟LOD技法有异曲同工之妙。思路也是将物件按重要程度划分为高中低级别，然后不同级别采用不同复杂度的效果或计算。

　　这种思路在游戏中可以广泛应用，基本所有消耗高的逻辑或模块都可以采用这个技法。例如：

　　1. 画质等级。将游戏分为若干等级，画质最高到最低采用不同的渲染技术或资源，区别对待。

　　2. 资源等级。场景/特效/灯光/物理效果/导航等等模块都可以根据画质等级或物件等级对应不同级别的资源，整体上可以减少消耗，又能兼顾画质效果。

　　3. 角色分级。主角英雄/Boss等和小怪物/NPC区分开来，前者更新频率更高，AI行为更复杂更智能，而后者采用简单效果或降频更新。

多线程

在GameDev中，我们可以将一些逻辑通过创建线程的方式独立出去，交给其它CPU核心处理，以缓解上面提到的现象。

　　可独立成线程处理的模块：

　　1. 文件IO。建立一个IO线程，定时检查文件队列是否有数据，若有便启动IO加载，直至文件队列为空，又回到空闲轮询状态。主线程就不会以为文件IO而处于等待状态。

　　2. 骨骼动画。如果同屏动画角色多，将占据大量CPU计算。可创建一个或多个线程处理骨骼动画计算，加速渲染流程。但随之而来的是同步问题。

　　3. 粒子计算。粒子的多线程跟骨骼动画类似，也存在同步问题。

　　4. 渲染线程。将渲染抽离出一个线程，主要是解决CPU与GPU相互等待的问题。常见的一种做法是建立一个渲染线程，定期去查询渲染队列是否有数据，如果有就提交至GPU进行绘制。

　　5. 音视频编解码。如果游戏有涉及音频频播放，而它们又占据了较大的消耗，那么开辟独立的线程处理音视频编解码是有必要的。

　　6. 加密解密。加密解密涉及的算法通常较复杂，占用较多CPU性能，而且常常伴随着文件IO或网络IO，所以此时非常有必要将它们交给独立的线程处理。

　　7. 网络IO。目前大多数游戏都会开辟一个线程专门收发网络数据，以避免网络处理影响主线程。

　　值得注意的是，线程切换会带来额外开销，同步和死锁问题也会提高逻辑复杂度和调试难度，是悬在程序员头上的一把大刀。

动画

降低动画采用频率。

　　减少关键帧数据。

　　缓存动画的插值结果。

　　用简单曲线插值（线性插值）代替复杂插值（贝塞尔曲线）。

　　判断动画所附对象的可见性，如不可见，则不更新动画。

　　控制同屏动画的个数。

　　不同画质加载不同级别的动画资源。

渲染路径

前向渲染
延迟渲染（Deferred Shading）

场景管理

八叉树
遮挡剔除（Occlusion Culling）

阴影

贴图阴影

Projector（投射阴影）

Shadow Map（阴影图）

带宽优化

　　带宽优化的目的是减少CPU与GPU之间的数据传输。

LOD（Level Of Detail）

GPU Instance

GPU Skin

CPU Skin最基本的角色动画实现方式，它可以方便地实现很复杂的动画操作，如融合/渐隐/组合/串接等等。但它的缺点也显而易见，占用大量CPU计算性能，难以并行计算，每帧需传送模型顶点数据到GPU，增加带宽负载。

　　GPU Skin的做法是将骨骼矩阵列表作为Uniform传入Shader，然后在Vertex Shader中对模型顶点进行蒙皮计算。它可以并行计算，减轻CPU负载，此外，由于每帧传入GPU的数据是骨骼矩阵，不是顶点数据，极大降低了带宽负载。

　　当然，GPU Skin也有缺陷。它会提高GPU负载，最高骨骼数往往受限于平台（如OpenGL ES 2.0不能超过250个Vector4数据量），而且也不利于做复杂的动画操作。

避免后处理

　　后处理是场景物体渲染完成后，对渲染纹理做逐像素处理，以便实现各种全屏效果，包含以下效果：

抗锯齿：Anti-aliasing (FXAA & TAA)
环境光散射：Ambient Occlusion
屏幕空间反射：Screen Space Reflection
雾：Fog
景深：Depth of Field
运动模糊：Motion Blur
人眼调节：Eye Adaptation
发光：Bloom
颜色校正：Color Grading
颜色查找表：User Lut
色差：Chromatic Aberration
颗粒：Grain
暗角：Vignette
噪点：Dithering

降分辨率

　　降分辨率是最粗暴最有效的提升渲染性能的方法。

　　由于当前很多智能设备分辨率都是超高清，动辄2K以上，但CPU/GPU却跟不上，如果使用原始屏幕分辨率，就会出现严重的卡帧/掉帧现象。

　　通常可以将屏幕分辨率降到一半，这样渲染纹理/深度Buffer/纹理等等数据都可以缩减到原来的1/4，极大降低了CPU/GPU/带宽各项指标的消耗。

合批的数据越大越好?

　　有人会认为即然合批能够降低渲染消耗，是不是让合批后的数据越大越好，以便更多地降低Draw Call呢?

　　答案是否定的。

　　原因有二：

　　1. 移动游戏的模型索引通常做了优化，只用16位表示，也就是说如果合批后的顶点数超过65025，便会越界，导致渲染异常。

　　2. 太大的数据量可能无法充分利用LOD，遮挡剔除等技术，导致过多的数据送入GPU，反而增加带宽和GPU消耗。

片元等同于像素

　　片元（fragment）是GPU内部的几何体光栅化后形成的最小表示单元，它经过一系列片元操作（alpha测试，深度测试，模板测试等）后，才可能最终写入渲染纹理成为像素（pixel）。

　　所以，片元不是像素，但有概率成为像素。

参考

网易面试
 移动游戏性能优化通用技法

leeyupeng

经验之谈

问题