干货！深度解析游戏引擎开发中的算法

为什么在做游戏引擎开发中要有算法存在，那是为了让游戏角色能够有真实物理体验，游戏引擎需要有计算运动，碰撞，接触点等相关的方程，有一套基本算法帮助角色实现这种效果。例如，Runge-Kutta方法使用数值积分法计算运动方程。Gilbert-Johnson-Keerthi（GJK）算法使用Minkowski差来进行碰撞检测。 Sutherland-Hodgman算法通过剪切多边形来识别碰撞接触点。

 

　　数值积分方法

 

　　计算运动方程允许角色在空间中自由落体运动，就好像重力作用在这个角色上。运动方程使用的是牛顿第二定律：

游戏引擎集成运动方程以获得角色的速度和位移。引擎用连续循环来进行这个操作，这个循环包括以下步骤：

 

　　1.识别作用于对象的所有力和力矩。

 

　　2.取所有力和力矩的矢量和。

 

　　3.求解线性和角加速度的运动方程。

 

　　4.在时间上对加速度进行积分以得到线性速度和角速度。

 

　　5.在时间上对速度进行积分以得到线性位移和角位移。

 

　　如果角色拥有重力和扭矩力，则游戏引擎连续循环将会产生物体下落和旋转的感觉。

 

 干货！深度解析游戏引擎开发中的算法

 

　　问题是加速度和速度的积分。计算机只能通过使用数字积分技术来逼近积分的值。

 

　　游戏引擎开发中使用了三种数值积分方法。他们分别是：

 

　　1.Euler法

 

　　2.Verlet方法

 

　　3.Runge-Kutta方法

 

　　Euler方法计算在一个时间间隔中的速度，并预测在t +△下一速度。该方法实现起来很简单，但它是最不准确的。下图显示了这种方法的缺点。你可能觉得，使得Δt越无限的小，得到的解就越准确。但是，值得考虑的实际问题是你能有多少时间来进行每步积分。

在Runge-Kutta方法是一个数字集成技术，提供更好的近似运动方程。与欧拉方法（其计算一个间隔的一个斜率）不同，Runge-Kutta计算四个不同的斜率，并将这四个斜率用作加权平均值。

 

　　这些斜率通常被称为k1，k2，k3和k4，并且引擎需要在每个时间步长计算它们的值。

Runga-Kutta使用这些斜率作为加权平均值，从而更好地近似出物体的实际斜率和速度。然后使用该新斜率计算出对象的实际位置。专业玩家网游戏比价器为游戏工作室提供即时游戏比价信息，外服游戏币比价查询，是游戏出货的最佳外服游戏交易平台。