撰写了文章发布于 2019-12-17 22:16:17

Computer Science in Game Development

由于某些原因(学分2333)，写了一些和游戏开发以及计算机科学之间的内容。~~虽然目前没有参与过大型游戏开发，也没开发过游戏就是了...~~

希望能对那些目前在CS专业想参与游戏开发，或者想开发游戏但是不知道学什么的有点帮助吧。

Abstract

计算机科学是一门研究计算理论(theory of computation)和软件系统设计(designing software systems)的学科。其所包含的范围非常广，基本来说可以分为理论方面和应用方面。理论方面例如复杂度理论，数据结构和算法，信息和编码理论，编程语言理论，应用方面例如计算机图形学，人机交互，科学计算，人工智能等方面。实际上还有一些其他方面的内容，例如计算机系统方面。

通常来说，子领域之间不是互相独立的，有些是互相依赖的。例如计算机图形学需要一些信息理论，数据结构和算法需要复杂度理论。

同样的，一个产业所依赖的方面或者说技术通常不会是单一的，而是多元的。例如，游戏的开发就依赖于多个方面的技术。游戏内容的表现依赖于计算机图形学，游戏能够满足实时性(RealTime)则依赖于数据结构和算法以及计算机系统等方面的技术的优化。游戏内NPC的行为，则依赖于人工智能技术。多人游戏的稳定和流畅则需要优秀的网络技术。

由于整个计算机科学在游戏开发中扮演者非常多的角色，以及其有着非常重要的作用。因此这里只是提取出一些方面来阐述和介绍。

Introduction

假设你想开发一款有着业界优秀画面，运行流畅的游戏。抛开游戏内容设计以及美术资源设计。我们需要什么？

一个足够优秀并且高性能的语言以及擅长它，虽然说游戏的大部分性能瓶颈在于GPU。但是一门性能不足的语言，可能就能够将一些优化直接抵消。特别是一些解释性语言，其对计算机系统底层的交互能力相对要弱，从而使得优化更加的困难。
优秀的算法和数据结构能力。如果想要游戏高效的运行，最直观的角度就是减少计算量(复杂度)。而这正是算法和数据结构能够做到的。例如计算游戏中物体是否碰撞，如果单一的枚举其无论什么情况，其需要处理的情况是O(n^2)的，而基于BVH优化的碰撞检测则在大部分时候达不到这复杂度(最坏情况也是O(n^2))。
丰富的底层知识和底层优化能力。底层的优化能够带来的性能提升通常是巨大的。提高CPU缓存的命中率，减少从硬盘读取资源的次数等方法能够极大的提高性能。用一个简单的例子来说，完成一个计算需要100次运算，而每次运算需要1s。数据结构和算法专注于将100次运算减少，而底层优化则注重于如何让每次运算所需要的时间减少。即便所需要的时间只减少0.1s，其相当于减少了10次运算。
多线程能力，现代CPU从以前发展单核频率到现在发展多核心。如果没有优秀的多线程能力，那么很难将现代CPU的性能发挥到极致，从而出现一核有难，多核围观的局面，浪费了性能。
优秀的计算机图形学能力，游戏是计算机图形学主要应用的方向之一。通常复杂的游戏场景需要一帧渲染非常多的三角形网格，以及多到无法计数的着色运算(shading)。而这还只是一帧所需要进行的运算，而需要达到稳定的60帧，则代表只有16ms左右的时间去渲染一帧的内容，并且还需要保证渲染的质量。即便运行在计算密集型的GPU上也是比较大的负担。因此这也是游戏最容易产生瓶颈的部分。
优秀的程序架构能力，虽然这个部分很容易被忽略。但这一部分也非常的重要，糟糕的框架意味着糟糕的代码，意味着极低的维护性。甚至还会影响一些算法的实现，以及优化的实现。最糟糕的可能导致整个游戏都没法开发出来。

Data Structure and Algorithm

应用于游戏的数据结构和算法基本上是根据需求来决定是否需要的。或者说，需要什么功能，那么能够解决这个功能的数据结构或者算法就会拿来使用。常用的数据结构和算法则有：

哈希, 通常用于映射，例如字符串映射其他数据。
排序, 快排，基于分块的桶排等。
BVH, 通常用于处理包围盒之间的相交问题。
BSP, 二叉空间分割。
A* , 通常用于寻路算法。
一些常见的图算法，例如最短路等。
一些简单的结构，栈，队列，链表等。
一些基于分治的算法。

Optimization

底层优化在游戏开发中是非常重要的，开发者也重视。

通常的优化思路主要是提高CPU缓存命中率，或者说提高缓存命中率。缓存在计算机中是非常重要的一个存在。因为从内存中加载数据到高速缓存或者寄存器中需要的周期是单个指令需要的周期的几十倍，从硬盘中加载到内存中更是几百倍甚至更多。如果需要访问的数据不在高速缓存中，那么就需要浪费很多时间去等待数据的载入。
除此之外，加快指令运行速度(这里并不是指的汇编指令)或者减少指令数目(这里指的汇编指令)也是一个可行的方法。比如说将一些乘法运算换成位运算运算(位运算指令需要的周期很少)，减少虚函数调用等。
减少因为同步所需要的时间，在多核处理器和多处理器的计算机上，通常完美的并行是不存在的。比如说有些时候CPU需要等待GPU完成任务，有时候CPU需要等待所有核心完成分配的任务才能进入下一个阶段。这就是同步。如果能够减少同步所需要的时间，那么程序的运行速度就会加快。

基于上面的一些想法，ECS(Entity Component System)， DOD(Data-oriented design)等一系列设计被应用于游戏。例如在Unity3D中的DOTS(Data-Oriented Technology Stack)中就使用了ECS。

Entity Component System

ECS被分为Entity, Component, System三个部分。整个的设计目的是高效使用CPU缓存，以及多核处理器的能力。

单个System的执行通常是并行的，其处理的对象则是多个Entity。同时多个System之间的运行也可以是并行的，从而使得CPU的核心能够充分利用。

而Entity通常并不是一个实体，而是一个编号(Identity)，其引用一些Component，从而构成一个实体。而Component则尽量减少指针，引用，虚函数等类型的使用，使得对Component的访问都是对其所存储的一段内存的访问。并且将同种的Component存储在一段连续的内存里面。从而在System处理的时候能够顺序访问内存，提高缓存命中率。

并且，ECS能够在运行时高效的添加和删除Entity和Component。这在实现一些粒子效果或者一些经常被添加和删除的元素的时候非常有用。

Data-oriented design

DOD相比OOP，其更加注重于数据的布局，数据的变换，数据的读写等。其目的同样也是为了提高缓存命中率。实际上ECS的设计是非常适合使用DOD的。这里以一个简单的例子比较OOP和DOD的不同以及DOD的优势。

上面的代码执行Object::move函数的缓存未命中的概率高很多，比如说调用move的时候可能未命中一次，然后进入到函数体内，mPosition和mDirection之间的距离可能超过一个cache block的大小。从而无法同时将两个变量拉入缓存，而需要两次。一次执行移动函数可能就会导致几次缓存未命中。

而上面的代码，最开始调用的时候将length, position, direction的一部分加载到缓存中去，然后后面的一部分运算根本不会未命中缓存。也就是说一部分更新只会发生最多三次未命中。其缓存未命中的次数要比OOP的要少很多。

Computer Graphics

应用于游戏的图形学技术非常的多，大致可以分为一些类型：

Cull, Depth Test, Blend等基础技术。
AA，抗锯齿技术，例如FXAA, TAA, MSAA等。
LOD，动态分辨率等降低不重要部分的细节来提高性能的技术。
SkyBox，天空盒。
Lighting，一系列光照计算相关的技术，例如PBR，SSAO，Shadow等。
HDR，Gamma Correct等和颜色相关的技术。
Virtual Texture，大型纹理支持，通常硬件和图形API会限制纹理的大小，而虚拟纹理技术可以突破这样的限制。
RTRT，实时光线追踪。

其中最为主要最复杂的还是和光照相关的技术，无论是基于物理的光照模型还是全局光照等技术(RTRT才刚发展，实际上光线追踪本身实现并不难，然而可优化的性能空间却特别难发现)。

Physically Based Rendering

PBR虽然很早就在电影行业中使用(电影行业中的PBR不仅仅只是使用基于物理的光照模型)，但是在游戏行业却相对较晚。其主要原因是PBR的光照模型的计算开销要比以前是用的光照模型要大很多。而光照计算的次数在一次场景渲染中又特别的多。

传统的光照模型例如BP等都不是基于物理的，其不满足一些物理性质。例如能量守恒，即一个物体通过散射(scatter)发出的能力不会比它收到的能量要多。

使用的Cook-Torrance BRDF

哪怕只有单纯的着色计算(没有环境光等)，PBR渲染出来的物体也比BP要真实许多。

Real Time Ray Tracing

随着支持光线追踪的硬件的出现，实时级别的光线追踪开始尝试在游戏中使用。虽然目前来说效果并不显著。虽然RTX需要硬件的支持，但是在RTX出来之前早就有基于GPU的光线追踪框架，并且DXR也并不要求RTX显卡。

光线追踪简单的来说就是逆向追踪光线的传播方向，从摄像机或者说人眼中发射出射线，和物体进行相交测试(通常来说是先和BVH进行测试，然后再和包围盒测试最后和物体进行测试)。之后能够得到物体的表面属性。例如面法线，切线等。通过法线，入射光线等，根据菲涅尔效应，可以得到折射的光线方向和反射的光线方向。从而继续追踪这些光线。同时也会在表面发射出朝向光源的射线，我们称之为shadow ray，用于着色计算以及判断是否被光线照射到。

而实时级别的并不会和上述流程有什么太大的区别，但是由于光线追踪发出的射线是互相独立的，能够很好的使用GPU并行计算，从而在现代GPU上能够做到实时级别的效果。然而实际上游戏中的实时光线追踪仍然只是辅助作用。

HDR

HDR的全称是高动态范围图像，计算机不能存储连续的信息，只能存储离散的信息。因此存储在计算机中的颜色信息也是离散的。通常我们使用的图片是24位的，RGB三种颜色分别占用8位。因此每种颜色能够表达的范围只有[0, 255]。而HDR则使用更大空间来存储颜色，通常来说是RGB各32位。因此能够表示的颜色范围会更大，从而使得画面能够更加真实。