Game Physics

在电影和游戏中求解物理问题几乎是相同的任务。唯一的不同是，电影中可以花费足够长时间来求解问题，而游戏中必须在非常短时间内求解问题。

在两辆汽车碰撞的模拟中，我们需要多少这两辆汽车的运动学参数？他们的尺寸，质量，形状，轮子的直径，轮胎的类型以及轮胎的抓地力…….
也许我们可以简化该问题，将每辆汽车当作一整个铁盒子，在路上滑动，没有任何摩擦力。我们不需要考虑各个独立部分的动力学。这样我们的问题就变得非常容易，也可以快速的求解，但是会遗失掉很多的细节。
这是两个同一个物理系统的不同模型。前一个模型的求解比较难，速度也慢，但是其结果详细且真实。后一个模型的求解比较容易，速度快，但是结果缺少细节。对于游戏来说我们只能使用简单的模型，这样才能足够快的求解问题。

每次电脑重新绘制一帧时，两辆汽车必须改变他们的位置，互相接近对方直到它们碰到一起。我们必须设计一种方法来驱动这种模拟从一帧变化到下一帧。
可以通过下面的方法来更新每辆车的位置：

new position = current position + current velocity * time between frames
new velocity = current velocity + (force / mass) * time between frames

上面的伪代码通过对速度积分来获得位置，通过对加速度积分来获得速度。这是就是 Euler 积分，其是一个更新我们物理模拟的非常基础的方法，该方法速度非常快，当然，其精确度比较低。
无论我们选择如何建模我们的问题，我们都需要一个积分方案来驱动物理模拟从一帧进行到下一帧。

直到两辆车碰撞，他们的速度和位置几乎是独立的(不相关的)。碰撞之后，他们新的速度将依赖于他们质量的相对值（例如，当一辆自行车和货车撞击会导致自行车速度有很大变化，而货车的速度不会有太大变化），碰撞期间的接触点等等。这是一个涉及到多物体的问题，而不只是一个物体。
简单来说，Solver 就是一个程序，它可以处理这类问题，并进行求解。这些问题通常被表示为一个方程组，其将各个物体的多个物理属性关联在一起。
广义来说，有两种 Solvers：Direct Solver 和 Iterative Solver. Direct Solver 会在一次求解中获得确定的结果。Iterative Solver 则会执行很多个阶段，每一次会获得的结果会更加近似最终确定的结果。
Direct Solver (例如：Lemke,Dantzig) 对于小规模的问题来说是非常快的，但是当问题规模变大时，会逐渐变得越来越慢。
Iterative Solver (例如：Gauss-Seidel, Jacobi) 可以很快地给出一个近似解。它会以一个猜测的解作为开始，然后在方程组上执行一系列快速的处理来渐进地改善问题的解。执行的迭代次数越多，结果越精确。
很难百分百确定一个求解器是 Direct 类型的还是 Iterative 类型的，有些方法可以被认为既是 Direct Solver 又是 Iterative Solver（例如：Conjugate Gradient）。

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值，迭代法又分为精确迭代和近似迭代。比较典型的迭代法如“二分法”和"牛顿迭代法”属于近似迭代法。

如果我们想让游戏流畅地运行，我们需要每秒在屏幕上绘制至少 60 次，这意味着我们有 1/60 秒（16 毫秒）来处理输入、模拟物理、更新 AI 并且为当前帧显示渲染所有内容。通常每帧时间内，游戏物理的预算时间为 5 毫秒。
在如此紧张的预算下，计算草的叶子之间的碰撞毫无疑问在我们的模型中是不会考虑的。在纱线级别对角色衣服进行模拟也必然是超出我们考虑范围了。动态液体的模拟我们也不会考虑。
修剪掉这些复杂的事情后，我们就得到了典型的游戏物理模型。我们使用胶囊体来模拟角色，使用高度图来模拟地形，使用简单的盒子来模拟墙壁和地表。更多复杂的物体可以使用任意的凸形来模拟。我们假定这些简单的形状可以移动和旋转，但是不会以任何方式变形。即使在很大的压力下，他们也不会被压扁，切变，扭曲，弯曲等等。因此我们称他们为刚体。

模拟空间中一点所需要的所有信息为：

• Position 位置
  
• Linear Velocity 线性速度
  
• Mass 质量
  

因为我们可能需要支持旋转运动，我们还需要下面额外的数据：

• Orientation 朝向（类比位置）
  
• Angular Velocity 角速度 （类比线性速度）
  
• Inertia tensor 惯性张量 （类比质量）
  

下面的代码使用了 Euler 积分器来驱动刚体的旋转

new orientation = current orientation + current angular vel. * time between frames
new angular vel. = current angular vel. + (torque / inertia tensor) * time between frames

// 注意下面的 "x" 运算符是叉乘运算符。
torque =  force x (point – center of mass)

我们已经知道如何模拟各自独立的刚体了，碰撞会使他们相互影响。
对于两个重叠的刚体，给定一个接触点，我们可以在接触点上应用一个力。这个力使得这两个刚体移动和旋转，从而在下一帧开始时，这两个刚体基本上不再接触。这个力是在当前帧期间立即作用的，不会持续很长时间。这种方法被称为基于冲量的解决方法。
我们也可以计算两个刚体之间的距离，然后应用一个排斥力分别作用给它们，并且两种距离越近排斥力越大。这种方法被称为基于惩罚的解决方法。

假设有两个物体 A 和 B 分别都和第三个物体 C 接触。这会产生两个接触约束，也就是两个方程式：A vs C 和 B vs C.
我们先以求解 A vs C 开始，这会同时移动 A 和 C 使他们不再重叠。然后这使得 C 和 B 重叠的部分更多。我们再求解 B vs C，这会对他们的位置都做轻微调整来避免碰撞。此时，对 B vs C 的求解破坏了一开始对 A vs C 的求解，因为两次调节都对 C 位置做了调整，而且两次调整的方向不同。我们可以对 A vs C 再次进行求解，来使结果变得更好一些。…….
重复求解两个方程四次，可能是五次。每次迭代没对物体重叠的部分都会减少，并且最终方程的模拟会非常满意。尽管这个方法看起来有点鲁莽（只是对所有方程按顺序不停的求解直到所有物体很好的排列），但事实上这是一个解决很多问题的好方法：这就是 Gauss-Seidel 方法

在前面的情况中，如果我们求解 A vs C 之后，求解 B vs C 将 A vs C 还原为初始的状态，此时会发生什么？也就是说 A 和 B 是静态的不允许动的，C 就像三明治一样夹在 A 和 B 的中间。此时，我们无论迭代多少次求解过程，结果都没有改善。这是我们就称该问题是不收敛的。如果每次迭代使问题变得更糟糕，则该问题是发散的。
如果我们可以找到一个方法 A 迭代 5 次就可以达到另一个方法 B 迭代 10 次的效果，我们就说方法 A 比方法 B 收敛的更快。

在 Gauss-Seidel 方法中，我们再进行下一次迭代之前就会使用每个方程求解的结果。如果本次迭代全部使用上一次迭代的结果，而不使用本次迭代产生的结果，然后再将结果进行平均。这种方法被称为平均化的 Jacobi 方法。
和 Gauss-Seidel 方法相比，Jacobi 方法收敛速度比较慢，但是 Jacobi 方法每次迭代开始时所有方程都使用相同的输入，所以方便并行计算。另外，平均 Jacobi 方法是顺序无关的，而 Gauss-Seidel 方法则和求解顺序相关。

需要同时调节 Stiffness Force 和 Drag Force，首先适度增加 Stiffness Force 让物体不要太柔软，其次调节 Drag Force 使运动阻力适中。Drag Force 太小，物体以静止位置为中心来回运动次数较多，Drag Force 太大，物体回到静止位置花费时间比较长。

需要在最末端添加一个空节点，作为虚拟的绳子末端。这样就可以解决这个问题了。

需要在起始端添加一个空接点，作为虚拟的绳子起始端。这样就可以解决这个问题了。

修改 Spring Force 来改变弹簧力的方向和大小，可以使重力影响效果变的明显。