游戏开发

发表于 更新于 分类于 阅读次数：

…

基本架构

帧

  1. 每秒绘制的帧数不固定，需要计算帧与帧之间的间隔时间，以便物理引擎使用。
  2. 多线程渲染，显示帧，处理帧，输入帧都不在一个帧上，渲染线程比主线程慢一帧。
  3. 渲染游戏对象，游戏对象分为三类：需要渲染和更新的（子弹，人物），只更新的（触发器，摄像机），只渲染的（背景）。游戏对象需要有两个接口，渲染接口，更新接口。
  4. 程序维护一个渲染队列，一个更新队列。

2D 渲染

垂直同步：采用双缓冲技术，在场消隐期减缓缓冲区。有时也可以采用三缓冲。

精灵：是使用图片绘制的2D图像，表示一个角色或其他动态对象。载入精灵可以采用库stb_image.c。每个精灵都有一个绘制顺序，采用画家算法绘制；还有图像数据；以及位置数据。

画家算法：先画背景后画角色，即所有精灵按位置排好顺序，按顺序绘制到屏幕上。

动画：定义如下

1
2
3
4
5
6
7
8
9
10
// 一个动画
struct AnimFrameData
    int startFrame  // 第一帧的动画索引
    int numFrames   // 动画总帧数
end
// 一组动画
struct AnimData
    ImageFile images[]        // 所有动画图片
    AnimFrameData frameInfo[] // 所有动画用到的帧
end

对于一个角色，定义它的动画可以包括如下属性

  • 所有动画数据
  • 当前动画编号
  • 当前动画帧号
  • 动画的播放速度

纹理数据应打包传递给GPU，但注意一些设备的最大纹理尺寸是有要求的。

滚屏：

  • 单轴滚屏：只能左右滚屏，图片可以切分后按需加载。绘制哪张背景，根据摄像机位置决定。
  • 无限滚屏：连续使用某种图片循环绘制。
  • 平行滚屏：背景分为多层，例如云朵比地面滚动的慢。
  • 四向滚屏：原点放置问题。

砖块地图：地图中的每个网格可以存放一个编号，代表一个或多个精灵。通过这些精灵的拼凑来绘制地图。还有一类是斜视等视角砖块地图，例如《暗黑破坏神》。

线性代数

向量：加，减，单位化，点积，叉积。

卡马克快速平方根倒数：

1
2
3
4
5
6
7
8
9
10
11
float Qsqrt(float number) {
    int i;
    float x2, y;
    x2 = number * 0.5F;
    y = number;
    i = *(int*)&y;
    i = 0x5F3759DF - (i>>1);
    y = *(float*)&i;
    y = y * (1.5F - x2 * y * y);  // 牛顿迭代
    return y;
}

向量反射：
0. 定义：入射速度V1，出射速度V2，碰撞墙面的单位法向量N。

  1. 将-V1向N投影得到V0
  2. 令S=V0+V1
  3. 则V2=-V1+2S
  4. 推导得V2=V1-2N*(V1*N)

平面旋转：
0. 定义：当前单位方向C，目标单位方向N。

  1. 计算两向量夹角arccos(C, N)。
  2. 向量增广为三维，计算旋转方向cross(C, N)，若为正，逆时针转；若为负，顺时针转。

线性插值：Lerp(a, b, f) = (1-f) * a + f * b

坐标系：DirectX默认为左手系，OpenGL默认为右手系。

矩阵：加，减，数乘，矩阵乘积，求逆，转置。

矩阵表示3D变换：OpenGL用列向量表示位置，其他引擎用行向量表示位置。

3D

模型：由基本的三角形面构成。单个模型称为网络，一般一个角色模型可能由一万多个多边形构成，一个木桶模型可能由几百个多边形构成。

坐标系：

  1. 模型坐标系：原点通常在模型中央，或角色两脚中间。
  2. 世界坐标系：所有对象都相对于世界原点偏移。
  3. 摄像机坐标系：需要定义左方、上方、前方、位置4个向量。最终世界坐标将映射到摄像机视野中。
  4. 投影坐标系：分为正交投影和透视投影。一般采用透视投影。需要定义视角，近平面，远平面。

齐次坐标系：使用4维向量表示3维坐标，4维矩阵可以用乘法方式表示平移变换。（3维矩阵乘法只能表示旋转和缩放）

矩阵变换：平移、旋转、缩放。

变换矩阵 = 缩放 x 旋转 x 平移

缩放：
$$
\begin{bmatrix}
{s_{x}}&{0}&{0}&{0}\
{0}&{s_{y}}&{0}&{0}\
{0}&{0}&{s_{z}}&{0}\
{0}&{0}&{0}&{1}\
\end{bmatrix}
$$

平移：
$$
\begin{bmatrix}
{1}&{0}&{0}&{0}\
{0}&{1}&{0}&{0}\
{0}&{0}&{1}&{0}\
{t_{x}}&{t_{y}}&{t_{z}}&{1}\
\end{bmatrix}
$$

X轴旋转：
$$
\begin{bmatrix}
{1}&{0}&{0}&{0}\
{0}&{cos(\theta)}&{-sin(\theta)}&{0}\
{0}&{sin(\theta)}&{cos(\theta)}&{0}\
{0}&{0}&{0}&{1}\
\end{bmatrix}
$$

Y轴旋转：
$$
\begin{bmatrix}
{cos(\theta)}&{0}&{sin(\theta)}&{0}\
{0}&{1}&{0}&{0}\
{-sin(\theta)}&{0}&{cos(\theta)}&{0}\
{0}&{0}&{0}&{1}\
\end{bmatrix}
$$

Z轴旋转：
$$
\begin{bmatrix}
{cos(\theta)}&{-sin(\theta)}&{0}&{0}\
{sin(\theta)}&{cos(\theta)}&{0}&{0}\
{0}&{0}&{1}&{0}\
{0}&{0}&{0}&{1}\
\end{bmatrix}
$$

颜色：由RGBA四个通道构成。可以附着在顶点上。

顶点：包括位置、颜色、法线、纹理映射坐标(UV)等属性。

光照：

  • 环境光：没有光源，充满整个空间
  • 方向光：例如太阳光
  • 点光源：可以使用衰减半径
  • 聚光灯：方向固定

光照模型( BRDF 反射分布函数 )：

  • Phong 光照模型：环境光、漫反射、高光。不考虑光的二次反射。

着色：

  • 平面着色：三角形只使用一种颜色着色。
  • Gouraud 着色：为3个顶点着色，中间部分通过插值着色。
  • Phong 着色：利用顶点法线与光源方向计算着色的强度着色，中间部分对法线插值着色。

深度缓冲：仅在渲染过程中使用，计算每个像素到摄像机的距离。当新的像素距离更近时，更新深度缓冲，同时绘制像素。绘制透明物体时，需关闭深度缓冲的写功能，当透明像素距离超过缓冲区值时，不绘制该像素，当透明像素距离小于缓冲区值时，叠加绘制该像素。该方法无需排序对象。

帧缓冲区：每帧都要用。

  1. 深度缓冲：一般采用24位或32位。
  2. 颜色缓冲
  3. 模板缓冲

欧拉角：会产生方向锁。

四元数：可以任意旋转。

  • 线性插值
  • 球形插值

标准四元数：长度为1，写作

$q = [ {q_v}, {q_s} ]$

其中

${q_v} = a sin({\theta} / 2 )$

${q_s} = cos({\theta} / 2)$

a 表示旋转轴， ${\theta}$表示旋转角度

Grassmann积：

(pq)v = ps * qv + qs * pv + pv x qv

(pq)s = ps * qs - pv * qv

共轭四元数：将向量分量取逆即可。

单位四元数：iv = (0, 0, 0), is = 1

3D对象的表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class GameObejct3D {
    Quaternion rotation;
    Vector3 position;
    float scale;
    Matrix GetWorldTransform() {
        // 必须 先缩放 后旋转 再平移
        return CreateScale(scale) 
                * CreateFromQuaternion(rotation) 
                * CreateTranslation(position);
    }
}

class Quaternion {
    Vector3 qv;
    float qs;
}

输入设备

按键类型：模拟输入、数字输入、同时按键、序列按键。

使用跨平台库解决设备输入问题。SDL

处理按键输入：

  • 释放 -> 释放：未按
  • 释放 -> 按下：按下
  • 按下 -> 释放：松开
  • 按下 -> 按下：一直按着

处理模拟输入：

  • 需要对模拟量滤波处理，例如在摇杆中心位置附近设置无效区。

基于事件的输入：

  • 采用订阅、发布模型
    • 发布者持续关注按键变化，并通知有关的订阅者
    • 订阅者关注感兴趣的按键变化

按键映射：游戏可以将角色动作和按键定义分离开，例如游戏中绑定Fire，Hide等虚拟按键，再在这些按键上绑定真实按键。

移动设备输入：

  • 触屏与手势：
    • 模拟摇杆
    • 手势操作：例如两指缩放。检测方法：Rubine算法。
  • 加速计与陀螺仪

声音

播放声音的频道有限，因此需要尽可能利用所有频道播放声音。此外，还需要给音频设置优先级，在频道不够用的时候优先播放优先级高的音频。

音频格式：

  • wav：无压缩，适合短音频。
  • ogg/mp3：压缩音频，适合长音频。

音频解决方案：OpenAL

声音事件：将音频与元数据打包二成。例如，爆炸音效，可以包含多个爆炸音频，当使用时，可以随机选择其中一个音频播放，同时还可以指定音频优先级，渐入渐出效果；脚步音效，可以根据地面材质选择脚步的效果（草地，雪地，石头）。

3D声音：需要考虑音源与监听者的相对位置。监听者的位置一般使用摄像机作为监听者，或摄像机与角色之间33%-66%的位置，朝向与摄像机一致。

衰减：声音随着距离线性分贝衰减。常用方法有线性分贝衰减函数等。

环绕声：例如5.1环绕系统或7.1环绕系统。

数字信号处理：可以用来做声音特效，如回声，闷音，可以采用预设特效。

预设音频特效：

  • 回声：Freeverb3
  • 音高偏移：例如多普勒效果。
  • 低通滤波器：蜂鸣声。
  • 声音遮挡：高音部分被遮挡，低音部分穿透障碍物。降低高频部分的声音。
  • 声音衍射：声音经过柱子衍射成多个波源，监听者可能会听到两次声音。
  • 声学衍射：Fresnel声学衍射，在监听者附近构建一个圆弧，发射者向圆弧射去一系列直线，判断中间是否有遮挡，或部分遮挡。

区域标记：指定特效声音生效的区域。例如回声特效只能在山洞中生效。一般采用凸多边形。进入该区域时，回声特效渐变出现。

物理

平面：表达式 P * n + d = 0。P为任意一点，n为法向量。

1
2
3
4
struct Plane {
    Vector3 normal;
    float d;
}

射线与线段：表达式 R(t) = R0 + v * t。v为法向量。t的取值范围决定线的类型。

1
2
3
4
struct RayCast {
    Vector3 startPoint;
    Vector3 endPoint;
}

碰撞集合体：检测碰撞通常采用简单的集合体碰撞检测，例如球体，方盒，圆柱，胶囊体。此外，一个物体可以有多个级别的碰撞体，以便简化计算。根据不同的场合，也可以选择不同的碰撞检测体，例如判断子弹入射，可以使用高精度的组合几何体碰撞检测，判断是否与建筑碰撞，采用胶囊体即可。

包围球：精度较低，适合初级碰撞检测。

1
2
3
4
struct BoundingSphere{
    Vector3 center
    float radius
}

轴对齐包围盒：保存包围盒的左上角和右下角坐标，通常用于角色。也适合初级碰撞检测。

1
2
3
4
struct AABB2D{
    Vector2 min
    Vector2 max
}

朝向包围盒：表示方法众多，可以参考Real-time Collision Detection。

胶囊体：圆柱加两个半球。常用于角色。

1
2
3
4
5
struct Capsule{
    Vector3 startPoint
    Vector3 endPoint
    float radius
}

凸多边形：效率很低。

当前帧碰撞检测：

  • 球与球的交叉：采用距离与半径之和。
  • AABB与AABB交叉
  • 线段与平面的交叉：如果不平行，则解方程组看交点。
    1
    2
    R(t) * n + d = 0
    (R0 + v * t) * n + d = 0
  • 线段与三角面的交叉：除了与平面交叉的要素之外，还应考虑交点是否在三角形内。判断方法，采用三角形AB、AC、BC叉乘AP、BP、CP的方式。
  • 球与平面交叉：过球心做与目标平面平行的平面，测量两平面距离与球半径。
    1
    2
    3
    4
    bool SpherePlaneIntersection(BoundingSphere s, Plane p) {
        float ds = - DotProduct(p.normal, s.center);
        return (abs(d - ds) < s.radius)
    }

后续帧碰撞检测：某些高速运动的物体可能会直接穿过碰撞体，跳过碰撞发生的帧。如子弹穿过纸。因此需要用一种连续性的方法检测碰撞。

  • 球形扫掠体检测：用来判断两帧之间是否有碰撞发生。将上一帧与当前帧的子弹位置构成一个胶囊体，然后判断与另一个胶囊体或平面是否碰撞。求解思路：将两个胶囊体构造成参数方程，求解两个参数方程当RA + RB == ||P(t) - Q(t)||时，t的根的情况。

响应碰撞：当碰撞发生后，碰撞的游戏对象做出的响应。

  • 碰撞后消失
  • 碰撞后减少生命值
  • 碰撞后弹开

两个球体碰撞后弹开：需要考虑碰撞切面，碰撞后的速度，碰撞的时刻（防止粘到一起）。求解思路：求解碰撞切面，用两球心的连线做切面的法线即可；求解碰撞点，根据两球半径在两球心连线上插值得到；求解碰撞后的速度，速度大小可以考虑弹性碰撞和非弹性碰撞，速度方向。

优化碰撞：采用八叉树的方式，每次剔除与玩家不产生碰撞的一半的空间，剔除过程还可以采用启发式搜索进行。

基于物理的移动：采用经典力学

  • 线性力学
  • 角力学

基于时间的积分：需要防止因为帧率变低导致的积分结果变大的问题。

力的计算：力一直作用在物体上，有时需要用冲量来代替力，即力 x 帧数。例如跳跃时，先给角色一个帧的冲量起跳，到空中再计算加速度让角色回落到地面。

欧拉积分：新的位置由旧的位置加上旧的速度与时间的积得到。该算法的问题是，速度一直采用旧的速度，会产生累计误差。

半隐式欧拉积分：新的位置由旧的位置加上新的速度与时间的积得到。在Box2D中就是这一算法。

Verlet积分法：相比于前两者，该方法采用平均速度代替其他的速度进行积分。

四阶Runge-Kutta方法：采用泰勒近似求解的结果表示近似解，通常用于模拟汽车。

角力学：转动惯量、力矩、角加速度、角速度、速度等。

物理中间件：

  • Havok：一个商业物理引擎
  • PhysX：工业级物理引擎，小制作免费，收入高时收费。
  • Box2D：2D游戏的物理引擎，例如愤怒的小鸟就在用。

摄像机

透视投影：

  • 视场：看到的场景的广度，又称FOV。人的眼睛可以看到180°的范围，但是超过120°的范围一般是模糊不清的，只能察觉到运动物体。视场的大小和用户与屏幕的距离有关，一般屏幕占用户多大视角，就采用多大的视场。在PC中，可以采用90°的视场，不宜太大，会产生鱼眼效果。

宽高比：4:3、16:9、16:10等。

固定摄像机：根据玩家位置判断使用几号摄像机，如《生化危机1》。有些固定摄像机也可以小范围移动，例如在《战神》中的摄像机。

第一人称摄像机：放在眼睛位置，但是为了看见手臂，会同时调整手臂和腿的位置（这些位置可能并不合理）。但是在考虑阴影时，或其他人视角时，又采用正常的模型。

场景摄像机：利用样条线制作摄像机运动轨迹，达到电影级别的运镜效果。

跟随摄像机：

  • 基础跟随摄像机：总是在物体后面保持一定距离，始终指向被观察物体。
  • 弹性跟随摄像机：与被观察物体的距离根据情况随时平滑调整。
  • 旋转摄像机：可以围绕被观察物体运动。控制模式可以采用增量偏航、增量俯仰，距离等参数，但是不使用横滚。
  • 第一人称摄像机：放在角色相对的位置上，采用绝对偏航，绝对俯仰记录摄像机角度。
  • 样条摄像机：利用Catmull-Rom样条线，实现摄像机的运动。样条线的切线表示了摄像机的朝向。

摄像机碰撞：

  • 从目标射出一条射线到摄像机，判断二者之间是否存在不透明物体。
  • 或给摄像机设置碰撞模型。
  • 距离被观察物体太近时，可以考虑让被观察物体消失。

拣选：使用鼠标选中屏幕中的物体。可以利用反投影，从摄像机的近平面某个坐标射出一条射线射向远平面同一个坐标，选中第一个交叉的物体。

人工智能

游戏AI通常采用状态机或脚本的方式实现，而传统的AI算法更注重广泛存在的问题，例如寻路、决策树等算法。

寻路：

  • 搜索空间的表示：一般采用图实现。可以将游戏世界用方格划分成网格，然后基于网格实现寻路。或使用路点划分。
    • 寻路节点：只能沿着各个节点移动。
    • 导航网格：可以在划定的多边形区域内运动。当然，对于不同的游戏对象，可以使用不同的导航网格。例如小鸡和牛，狭小的地方牛去不了，但是小鸡可以去。
  • 启发式算法：令h(x)为曼哈顿距离或欧式距离，根据h(x)进行启发式搜索。
  • 贪心算法：每次只选择当前最优的走法，不做长远考虑。
  • A*算法：除了考虑于目标的距离h(x)外，还考虑已经寻路的开销g(x)。
  • Dijkstra算法：令h(x)=0，只保留g(x)进行搜索。该方法适用于同时有多个目标，选最近的目标的情况。

状态机：

  • 有限状态机：定义状态，以及状态切换的条件。
  • 状态机的设计模式：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    // 基类，具体的状态需要继承该类
    class AIState {  
        AIController parent;
        void Update(float deltaTime);
        void Enter();
        void Exit();
    }

    class AIController{
        AIState state;
        void Update(float deltaTime);
        void SetState(AIState newState);
    }

    void AIController::Update(float deltaTime){
        state.Update(deltaTime);
    }

    void AIController::SetState(AIState newState){
        state.Exit();
        state = newState;
        state.Enter();
    }

策略于计划：AI需要有宏观的、长远的目标，然后为达到目标尽力而为。一般在RTS游戏中较为常见。

  • 策略：微观策略由单位行动构成，采用状态机算法即可；宏观策略则更为复杂，例如可以采用优先级方式选择当前目标，同时兼顾重要于不重要的事情。
  • 计划：为达成目标采取的一系列行动。由于计划可能会失败，AI需要根据情况调整计划。

UI

菜单栈：菜单的构成是一颗树，进入子级菜单时父级菜单要入栈。

菜单按钮：可以点选，也可以使用上下左右选择。可以采用2D包围盒包围一个按钮，检测用户是否点击。

HUD元素：在游戏场景中，显示玩家生命值等信息。

准心：利用反投影，用屏幕中心的准心拣选目标。

雷达：只需遍历游戏对象，并显示在2D屏幕上即可。

多套分辨率支持：使用相对坐标定义UI元素位置。

本地化：使用外部文件定义显示的文本。

UI中间件：Autodesk ScaleForm。

脚本系统

可以将摄像机、AI行为、UI界面分开，使用脚本开发。

脚本语言的类型：

  • Lua：轻量级解释器(150KB)，且容易调用C/C++。
  • Python
  • UnrealScript：编译型脚本语言，也可以调用C/C++。还可以使用可视化脚本系统Kismet。
  • QuakeC