《游戏编程算法与技巧》物理篇
平面
平面在游戏中倾向的数学定义：
$$ P \cdot \hat{n} + d = 0 $$
$P$是平面上任意一点，$\hat{n}$是平面法线，$d$是平面到原点的最小距离
1// 平面的数据结构
2struct Plane {
3 Vector3 normal;
4 float d;
5}
射线和线段
游戏中射线基本就是线段，因为基本不会让射线无限延伸下去。数学定义为：
$$ R(t) = R_0 + \vec{v}t $$
$R_0$是起点，$\vec{v}$是射线方向，$t$必须大于等于0。而在代码中的数据结构我们存两个点一个起点(startPoint)，一个终点(endPoint)。则$R_0$就是startPoint，$\vec{v}$就是endPoint-startPoint，而$t$的取值就为0~1了
1struct RayCast {
2 Vector3 startPoint
3 Vector3 endPoint
4}
碰撞几何体
包围球
通过中心点和半径表示
1class ShpereCollider {
2 Vector3 center;
3 float radius;
4}
轴对齐包围盒(AABB)
每条边都与x轴或y轴平行的矩形，只能随轴旋转，多用于2D
1class AABB2D {
2 Vector2 min
3 Vector2 max
4}
朝向包围盒OBB
可以自由旋转的类AABB包围盒，较复杂
胶囊体
3D中为一个圆柱加上两个半圆，还可看作带半径的线段
1struct Capsule2D {
2 Vector2 startPoint;
3 Vector2 endPoint;
4 float radius;
5}
凸多边形
简称凸包。凸多边形比其他前几个方式效率低，但是更精准
组合碰撞几何体
可用多个几何体，组合成一个近似于物体的碰撞盒。提高精度，效率相对来说毕竟高
碰撞检测
球与球的交叉
如果两个球的半径之和小于两个球的距离则发生交叉
1void ShpereIntersection(ShpereCollider a, ShpereCollider b) {
2 Vector3 centerVector = b.center - a.center;
3 float distSquared = Dot(centerVector, centerVector);
4 if (distSquared < ((a.radius + b.radius) * (a.radius + b.radius))) {
5 return true;
6 }
7 return false;
8}
AABB 与 AABB交叉
检测2D的两个AABB交叉的时候，检测没交叉会毕竟容易。有四种没交叉的方式
- A.max.x < B.min.x;
- B.max.x < A.min.x;
- A.max.y < B.min.y;
- B.max.y < A.min.y;
1void AABBIntersection(AABB2D a, AABB2D b) {
2 bool test = (a.max.x < b.min.x) || (B.max.x < A.min.x)
3 || (A.max.y < B.min.y) || (B.max.y < A.min.y)
4 return !test;
5}
线段与平面交叉
由上文的平面和线段公式可得，应为判断是否存在一个值$t$，使其线段与平面相交。
$$ R(t) \cdot \hat{n} + d = 0 \newline (R_0 + \vec{v}t) \cdot \hat{n} + d = 0 $$
解出t的值：
$$ R_0 \cdot \hat{n} + (\vec{v} \cdot \hat{n})t + d = 0 \newline (\vec{v} \cdot \hat{n}) = -(R_0 \cdot \hat{n} + d) \newline t = \frac{-(R_0 \cdot \hat{n} + d)}{\vec{v} \cdot \hat{n}} $$
$t$的取值范围应该为0~1，所以如果不在此范围则线段就不予平面相交
如果线段和平面的法线点乘的结果为0，则表示线段与平面平行，肯定无交点
1// 将返回值包装成结构体
2struct LSPlaneReturn {
3 bool intersects; // 是否相交
4 Vector3 point; // 相交的点
5}
6
7void LSPlaneIntersection(RayCast r, Plane p) {
8 LSPlaneReturn retVal;
9 retVal.intersects = false;
10 Vector3 v = r.endPoint - r.startPoint; // 计算向量v
11 float vDotn = Dot(v, p.normal);
12 if (vDotn != 0.0f) { // 说明线段和平面平行
13 t = -1 * (Dot(r.startPoint, p.normal) + p.d);
14 t /= vDotn;
15 if (t >= 0 && t <= 1) { // 说明线段与平面有交点
16 retVal.intersects = true;
17 retVal.point = r.startPoint + v * t; // 计算交点
18 }
19 } else {
20 // 测试起点是否在平面上
21 // ...
22 }
23
24 return retVal;
25}
球与平面交叉
用球的重心建立于平面平行的另一个平面，判断两个平面的距离是否小于半径
1void SpherePlaneIntersection(SphereCollider s, Plane p) {
2 float dSphere = -Dot(p.normal, s.center);
3 return (abs(d - dSphere) < s.radius);
4}
球形扫掠体检测
前面几种检测方式都是即时碰撞检测。只能检测当前帧状态。但是物体每一帧都是会运动的，所以连续碰撞检测（CCD）是必须的。两个球星扫掠体的碰撞检查可以看作两个胶囊体的碰撞检查。此处就不做详细展开了
响应碰撞
实际碰撞的响应事件应该抛出给应用层。比如Unity中有碰撞器和触发器，触发器不需要处理碰撞，而碰撞器则需要处理两个物体之间的物理状态。
找到碰撞的准确位置
比如使用球与球的交叉来找出碰撞发生的时间。算出时间后回滚到那个时间点。
碰撞后的速度
两个对象碰撞的时候，有一个恢复系统，衡量两个物体在碰撞后的反弹程度： $$ C_R = \frac{碰撞后的相对速度}{碰撞前的相对速度} $$ 在弹性碰撞($C_R > 1$)的情况下，碰撞后的相对速度大于碰撞前的相对速度。在无弹性碰撞($C_R < 1$)就会导致碰撞后相对速度降低
优化碰撞
如果游戏对象过多则会由过大的性能问题，一般用四叉树优化。将游戏世界递归切割成矩阵，直到每一个叶子节点引用一个对象
基于物理的移动
游戏一般用经典物理，此处聚焦最基础部分：线性力学
线性力学
- 力：是一种相互作用，可导致物体运动。有方向和大小。可用向量表示
- 质量：表示物体所害物质的量。质量越大，物体越难运动
- 牛顿第二定律：$F = m \cdot a$。$F$是力，$m$是质量，$a$是加速度
游戏使用物理计算位置的时候，使用可变时间步长计算会很复杂。所以游戏基本都已固定步长来计算物理
力的计算
游戏中常见的做法就是算出所有力的合力，然后除以质量算出加速度：
数值积分计算方式：
- 欧拉积分
- 半隐式欧拉积分：比欧拉积分更合理，更稳定
- Verlet积分：比前两个准确，计算更昂贵
- 四阶Runge-Kutta：更准确，计算最昂贵
Verlet积分法
首先算出本次时间步长中点的速度值。然后将它看作平均速度计算整个步长的位置。然后，加速度根据力和质量计算出来，最终利用新的加速度在步长结束的时候计算出速度
1void Update(float deltaTime) {
2 Vector3 sumOfForces = //... 计算所有力的合力
3 Vector3 avgVelocity = velocity + acceleration * deltaTime / 2.0f;
4 position += avgVelocity * deltaTime; // 位置用平均速度计算
5 acceleration = sumOfForces / mass; // 计算新的加速度和位置
6 velocity = avgVelocity + acceleration * deltaTime / 2.0f; // 计算速度
7}