游戏开发中的算法

mypro334

游戏技术这条路，可深可浅。你可以满足于完成GamePlay玩法层面的东西，你也可以满足于架构和框架设计层面的东西，你也可以醉心于了解某一游戏引擎带来的掌控感。但是，我们不该止步于此，止步与目前所见或所用，这里有一条路，无关乎游戏玩法，跨越引擎和游戏服务器架构，是一条超级硬核的路，尝试去了解比引擎或服务器框架更底层，更通用的东西，由于涉及到大量数学公式、物理知识和算法，并且跨越计算机多个领域，所以会异常艰难，需要翻跃千山万水，才能一探究竟。
结构是技术的骨骼，那么算法就是技术的灵魂。下面只能简单列举在游戏开发的几个基础领域，算法要求比较高的地方：图形学、AI、物理、分布式计算及其需要的数学知识。另外，游戏玩法层面的，比如场景管理、各种子系统也会涉及到算法，不在此列。由于内容众多，只能简单列举算法所在子领域，具体详情可去翻阅推荐的参考资料。



游戏开发中的算法

1、游戏开发中的图形学

图形学，是游戏开发中，最核心的部分，是游戏引擎最重要的，没有之一。想要深入学习引擎，必须要了解图形学及其涉及的经典算法，另外图形学也在不断发展，有志于此的人，可能需要紧跟最新进展，看看SIGGRAPH论文之类的。
图形学的基本问题：

• 图形的输入：比如一些光学追踪设备。
  
• 图形的描述：通过数据结构描述图形及其关系。
  
• 图形的运算：图形的运动、交叉关系的计算等。
  
• 图形的输出：渲染。
  
• 几何计算及其算法。
  

几何计算：

• 几何基础知识
  
• 2D几何：点、直线、圆、弧、曲线方程。
  
• 3D几何：平面、曲面方程和3D几何体。
  
• 几何变换：平移、旋转、投影变换、透视变换、视口变换等。
  

几何模型：

• 三角网络：如何使用三角网络表示立体模型。
  
• 曲线曲面：Bezier、B样条、NURBS等。
  

光栅化图形学：

• 基本图形光栅化算法：直线、圆、椭圆、文字等。
  
• 走样和反走样：分辨率不够时的锯齿和不平滑怎么解决。
  
• 裁剪：按照视口去裁剪要能看见的图形。
  
• 消隐：只能看见物体的一个面，看不见的要怎么进行隐藏处理。
  

真实感图形学：

• 渲染管线：计算机系统提供的，应用层把几何数据和拓扑结构设置好，通过GPU进行几何运算、光栅化处理、像素处理，最终渲染出来的完整过程。通常每个步骤都可以使用Shader来精确控制GPU的运算。
  
• 几何体的变换：除了基本的平移、旋转，还有顶点融合、变形等。
  
• 颜色模型：颜色的计算机表示。
  
• 光照模型：各种不同的光源，反射/折射/散射，局部光照算法，全局光照算法，光线追踪等等，应该是游戏引擎最重要的，也是最复杂的。
  
• 纹理算法：纹理怎么显示在几何体表面。
  
• 阴影算法：模型在某种光照模型下，阴影的处理算法。
  
• 动画算法：骨骼动画、IK、FK等等，动画算法也是比较复杂的。
  
• 其他算法：太多了，没法一一列举，比如毛发、湖面、植被的模拟之类的。
  

2、游戏开发中AI

AI目前也是比较热门的话题，在游戏领域主要三类应用：


1> 游戏玩法相关的算法：

• 移动：游戏中NPC和玩家角色直接的追逐、闪躲、移动模式、群聚行为的模拟算法。
  
• 导航：自动寻路。
  
• 对话：玩家和NPC直接的对话系统。
  
• 有限状态机：FSM，明确状态和状态之间的转换规则，可以用来解决程序中的涉及到多种状态的问题。
  
• 行为树：NPC的行为进行列举，模拟根据不同的交互操作，产生某种可与预见的行为。
  
• 模糊逻辑：凡事不只是0和1，可以在区间进行随机，引入决策的不确定性。
  
• 规则式AI：类似与Prolog语言，定义好规则表，输入条件根据规则表进行推导。
  
• 遗传网络：蚁群算法、模拟退火算法。
  
• 神经网络
  
• 强化学习
  

2> 游戏内容的自动生成：

• 借助于AI算法来生成玩家可交互的元素，比如自动生成地图。
  
• 借助于AI算法来帮助开发者生产游戏内容。
  

3> 游戏玩家行为的建模：
其实就是大数据分析在游戏领域的应用：

• 游戏体验建模
  
• 游戏行为建模
  

3、游戏开发中的物理

要想搞清楚游戏引擎中的物理引擎，要祭出高中/大学物理的知识了，特别是力和运动，还有刚体力学，当然微积分也很关键，物理引擎最核心的内容就是计算运动方程。

• 力和运动：力学、运动学、动理学、不同类型力的特点。
  
• 刚体动力学：粒子、2D刚体、3D刚体、及其连结，如何描述和受力后的运动。还有发生碰撞后的检测和相应。物理引擎常见模块：
  
  
  
  • 物理模型描述
    
  • 物理对象管理器
    
  • 碰撞检测
    
  • 碰撞响应
    
  • 受力响应
    
  • 数值积分运算
    
  
  
• 物理模型：常见游戏元素物理模拟，比如：飞机、船舶、汽车、枪炮、各种体育运动。
  
• 物理设备：触摸屏、加速计、重力/压力传感器、VR显示、光学追踪设备、3D音效等。
  

4、游戏开发中的网络

对于多人游戏，游戏服务器部分也是非常关键的，特别是大型多人游戏，游戏服务器架构也是很复杂的，一般大家印象中，游戏服务器开发，只需要处理好网络和通信，还有游戏逻辑就可以了。其实，还有比这些更重的内容，游戏服务器作为分布式系统的一种应用，不同类型游戏，服务器架构也会不同，但是有些分布式系统本质性的思想，一直贯穿其中。
分布式系统涉及到的内容：

• 网络通信
  
• 并发处理
  
• 命名
  
• 同步
  
• 数据存储
  
• 多副本和一致性
  
• 容错性
  
• 安全性
  
• 模块化和可扩展性
  

分布式系统相关的算法：

• 分布式图算法和分布式路由算法
  
• 全局状态和全局时钟算法
  
• 同步和协调算法：
  
  
  
  • 物理时钟同步算法
    
  • 选主算法
    
  • 互斥量
    
  • 死锁检测和解决算法
    
  • 异常侦测算法
    
  • 垃圾回收算法
    
  
  
• 数据多副本、一致性模型、和缓存相关
  
• 分布式共享内存
  
• 可靠性和容错性相关
  
  
  
  • 一致性算法
    
  • 多副本的管理
    
  • 选举算法
    
  • 分布式提交：原子提交（APC）、两阶段提交（2PC）、三阶段提交（3PC）
    
  
  
• 负载均衡算法
  
• 实时调度算法
  

5、游戏开发中的数学

针对上述算法密集型的领域，要想理解的通透，下面的数学和物理就是必修内容：

• 图论：离散数学中非常重要的部分，是计算机网络和诸多领域的基础理论之一。
  
• 线性代数：矩阵运算，求解线性方程组。
  
• 立体解析几何：图形学的基础。
  
• 计算几何：图形学的基础。
  
• 光学：游戏引擎光照模型和算法的理论基础。
  
• 力和运动学：游戏物理引擎中理论基础。
  
• 数值计算：用计算机求解数学方程，和数学问题的基础。
  

6、小结

游戏技术，想要往深的挖，挖着挖着就碰到硬骨头了，翻来覆去地去把玩它，深入地了解它，了解的越深刻，在游戏开发过程中的奇思妙想就会越多，解决问题也会越有成效。这就是游戏技术的魅力所在，不单单是写写代码，提升自己的认知水平也很关键。享受游戏技术的乐趣，没必要全都要了解，找到自己的点，深入发掘，乐趣无穷。弱水三千，只取一瓢，一饮而尽，快哉！
PS. 要获取游戏中的算法高清大图，请关注微信公众号：狂暴的游戏程序员（fury-programer）



狂暴的游戏程序员

7、参考资料：

• Graphics：《Mathematics for 3D game programming and computer graphics 》
  
• Graphics：《Fundamentals of Computer Graphics  》
  
• Graphics：《Computer Graphics：Principles and Practice》
  
• Graphics：《Real Time Rendering》
  
• AI：《AI for Game  Developer》
  
• AI：《Artificial Intelligence and Games》
  
• Physics：《Physics for Game Developer》
  
• Network：《Distributed Algorithms》 by Nancy A. Lynch
  
• Network：《Distributed computing principles, algorithms, and systems》
  

IT圈老男孩1

我们和他们的差距就在于往深研究我们觉得这条路异常艰难无从下手，然而他们已经在多年前把这条路修好了

JoshWindsor

这是在实力劝退

kyuskoj

我之前看到過一個pro版本，比這個還恐怖[发呆]