游戏开发技术杂谈10：绳索模拟

fwalker

绳索的模拟主要通过维莱尔积分（Verlet Integration）来实现，类似于水面的模拟，它也会通过一种方式来计算物体的运动，本次是基于维莱尔-位置算法来实现。
1.维莱尔算法的基本原理
1.1 二次近似与泰勒展开式
对于一个二次曲线 来说，在点 附近，与之最近似的函数可以用下列泰勒展开式来拟合

可以构建一个关于  的函数，用于描述在  时刻，物体的位置，该函数记为  ，对它在  时刻处进行泰勒展开可得(在运动学中忽略较小的项)

1.2 维莱尔积分推导
所以可知  时刻的位置为

消去部分  项可得

同理可得  时刻的位置为

联立两式可得

最终可以计算出  时刻的位置函数为

1.3 维莱尔积分简化

所以有了上面的公式，就可以开始写代码了。不过还需要做进一步的解读和优化。关于项 ，由于  是一个很小的项，如果不是进行科学研究，只是为了实现游戏效果。那么该项可以直接忽略。也就是我们最终会得到一个终极简单的公式。

其中 是要计算的下一时刻的位置，而  是当前时刻的位置， 是上一时刻的位置。用代码来描述基本如下
newPosition = currentPosition * 2 - oldPosition更简单来说是
newPosition = currentPosition + currentPosition - oldPosition由于newPosition最终还是要赋值给currentPosition，所以最终的代码非常简单，如下所示
currentPosition = currentPosition + currentPosition - oldPosition或
currentPosition += currentPosition - oldPosition这就是维莱尔积分简化后的运动公式

其中  是  时刻与 时刻的差分项。
1.4 维莱尔积分和绳索模拟基础

维莱尔积分只是用于模拟物体的运动，所以模拟绳索还需要追加更多的内容进来。对于一个2D的绳索来说，它本质上可以视为一组连接点，每个点的运动都通过维莱尔积分来控制。以及由于它是绳索，所以需要模拟其重力。所以在维莱尔积分运动公式中，我们还需要追加重力的影响。
匀加速直线位移公式如下

所以在  时刻内由于重力所产生的位移为

其中 是属于维莱尔积分的速度在重力方向上的速度，但是维莱尔积分中不涉及到初速度  项，要想得到初速度，需要用位移来除以消耗的时间。初速度  项可以通过下面的公式来计算。原理很简单，就是计算出 与  的距离差，然后除以消耗的时间。

由于我们已经推导出

代入上式可得

而 正好就是我们的差分项  ，所以最终的由于重力所产生的位移公式如下

不过在计算 的时候， 项已经存在于 中，关于这个问题，我们必须要解释清楚，从下面的代码来看。
pos = pos + pos - prevPos                        # r(t + dt) = 2r(t) - r(t - dt)是直接将新计算出来的位置赋值给pos变量的，这个做法有两个理解方式，第一个理解方式就是通过直接计算出位置。这个上面已经推导过了，但其实也可以用反过来用欧拉积分来理解，即pos = pos + velocity * deltaTime，我们已经知道了velocity的公式如下

所以pos += velocity * deltaTime，本质上就得到了位移增量  ，因为我们有

所以重力位移公式中的这一项 不用再叠加给pos变量了，我们只需要后面的加速度项即可。最后我们修正位移公式如下：

以及由于 是我们手动指定的，它可以和前面的系数 合并为一个重力系数 ，而后面的  ，在0-1的范围内可以用  来近似以获取更高的计算性能，所以最终得位移公式如下。

当然，关于为什么维莱尔积分的移动中包含了重力的部分，这个部分我会在文章末尾的时候按照我自己的理解再做一次解释。
1.5 基于霍克定理来约束绳索

我们将绳索视为一组刚体节点，每个节点都按照上述的公式来进行运动。但是此时它们是相互独立的，也就是它们之间没有任何关联。类似于2D水面的传播，这一组刚体节点之间每两个相邻的点都会相互约束。所以在这一节当中，我们来解释一下它们是如何约束彼此的。
暂时先考虑两个节点之间的连接，一个点是固定的，视为固定端，另外一个点会因为重力下坠。它们之间的连接可以通过弹簧来实现，因为弹簧描述起来比较简单。但是这里的弹簧略有不同的是，它有点像是一根橡皮筋，只有当两个节点的之间的距离超过基准值时，它才会产生约束，否则它不会产生任何约束。设两个节点之间距离差为 ，那么会产生一个收缩的力，将两个节点相互拉近。
也就是两个节点会朝着彼此的方向进行一定的位移，目前要做的就是把这段距离的公式推算出来。由于弹簧在收缩时所产生的力服从霍克定理（Hooke's Law）

又因牛顿第二定理（Newton's second law），可得最终的加速度为

其中 为弹性系数，弹性系数越小时，绳子越松弛，反之则越硬。已经知道加速度，则可以推算在  时间内，绳索因弹性约束而走过的距离为

同样，项 已经包含于  中，因而只考虑后面一项即可。

可以把 视为一个完整的弹性系数  ，以及 可以近似为 ，所以上述公式可以简化为

以及两个节点之间是双向奔赴的，所以每个节点在被约束的时候，走一半的距离
1.6 基于其他方式来约束绳索
我看到的原视频中，约束绳索的方式完全不一样，但是我没有搞懂它为什么这样做。所以这里先空着，等后面有时间搞懂了把这块补一下。但是我会将两者的代码都贴出来并给出彼此的演示效果。
2.绳索模拟的python代码实现

接下来我们通过python+pygame来实现一套对2D的绳索模拟，但上述的公式可以同样运用到3D场景中，我们先将之前推导的两个重要公式复制过来作为备用，第一个是维莱尔积分公式，第二个是霍克定理下的约束公式

2.1 实现节点类和节点的运动

这次的代码除了用到了pygame之外还用到了numpy，因为这次的运动不单纯是y坐标的变化，还包含x坐标的变化。所以先设置一个全局重力
# 绳索模拟
# python: 3.8.10
# pygame: 2.1.0
# numpy : 1.21.4

import pygame
import numpy as np

def normalize(arr: np.ndarray):
    '''求标准向量'''
   
    if arr[0] * arr[1] != 0:
        return arr / np.linalg.norm(arr)
    if arr[0] != 0:
        return np.array([1, 0])
    elif arr[1] != 0:
        return np.array([0, 1])
    return np.array([0, 0])

GRAVITY = np.array([0, 1])                                # 模拟重力然后增加一个Point类，用于代表绳索的每个节点。
class Point:

    def __init__(self, pos: tuple):
        '''@pos: 节点的坐标位置'''

        self.pos = np.array(pos, dtype=np.float32)         # current position
        self.prev = np.copy(self.pos)                                 # old position

    def update(self, deltaTime:float):
        '''call in each frame
        @deltaTime: frame time'''

        delta = self.pos - self.prev
        self.prev = np.copy(self.pos)
        self.pos += delta + GRAVITY * deltaTime                # 维莱尔积分公式它会记录当前的位置和上一帧的位置，用于在update函数中进行维莱尔积分的计算。计算下一帧的位置，但是一个究极简化过的版本，只适用于游戏中。其他真实性模拟场景还是需要更加精确一些。
然后就是绳索主体了，它需要创建一组Point然后调用它们的update函数以更新位置。
class Rope:

    def __init__(self, pos:tuple, count=30, spring_const=2.3, baseLength=10):
        '''
        @pos: 头节点的位置
        @count: 节点的数量
        @spring_const: 绳索连接线的弹性系数
        @baseLength: 绳索连接线的基准长度值 '''

        self.baseL = baseLength
        self.lockPosition = np.array(pos, dtype=np.float32)
        self.points = [Point((pos[0], pos[1] - i * baseLength)) for i in range(count)]
        self.spconst = spring_const

    def update(self, deltaTime):
        '''模拟绳索
        @deltaTime: 每帧的时间'''

        self.points[0].pos = self.lockPosition          # 将第一个节点的位置固定在lockPos
        for pt in self.points[1:]:
            pt.update(deltaTime)            # 更新每个节点的位置然后我们还需要追加约束函数，约束的函数有两个，第一个是我个人根据霍克定理推出的弹性线，最终实现的效果有点像皮筋，另外一个外网视频上算法。
    def constraintBasedOnHooke(self, deltaTime):
        '''将两个节点之间视为弹性连接
        @deltaTime: 每帧的时间'''

        for step in range(10):
            # 重复十次以达到快速约束
            for idx in range(len(self.points) - 1):
                pt1, pt2 = self.points[idx], self.points[idx + 1]

                vec = pt1.pos - pt2.pos
                dst = np.linalg.norm(vec)
                if dst > self.baseL:
                    err = dst - self.baseL
                    delta = err * self.spconst * deltaTime * normalize(vec)
                    if idx != 0:
                        delta /= 2
                        pt2.pos += delta
                    else:
                        pt2.pos += delta主要注意的就是delta的计算，它符合公式

其中err是  ，spconst是  ，deltaTime是  ，后面乘了normalize(vec)，主要是获取两个节点之间的方向。最后除2表示双向奔赴时，两个节点各跑一半的距离。
第二个约束函数如下所示
    def constraintUnknown(self, deltaTime:float):
        '''约束'''

        for step in range(10):
            for i in range(len(self.points) - 1):
                pt1, pt2 = self.points, self.points[i + 1]
                dst = np.linalg.norm(pt1.pos - pt2.pos)
                err = abs(dst - self.baseL)
                d = np.array((0, 0), dtype=np.float32)
                if dst > self.baseL:
                    _dir = normalize(pt1.pos - pt2.pos)
                else:
                    _dir = normalize(pt2.pos - pt1.pos)
                changeAmount = _dir * err
                if i != 0:
                    changeAmount /= 2
                    pt1.pos -= changeAmount
                    pt2.pos += changeAmount
                else:
                    pt2.pos += changeAmount最后搞一个绘制函数
    def draw(self, s):
        '''绘制绳索
        @s: pygame.Surface'''

        last = self.points[0]
        for pt in self.points[1:]:
            pygame.draw.line(s, (255,255,235), tuple(last.pos), tuple(pt.pos))
            last = pt最后创建一个绳索然后丢入主循环即可。
rope = Rope((500, 100))
screen = pygame.display.set_mode((1000, 600))
clock = pygame.time.Clock()
while 1:
    deltaTime = 1/clock.tick(240)
    screen.fill((67, 67, 79))
    rope.update(deltaTime)
    rope.lockPosition = np.array(pygame.mouse.get_pos(), dtype=np.float32)
    rope.draw(screen)
    pygame.display.flip()
    for e in pygame.event.get():
        if e.type == pygame.QUIT:
            pygame.quit()
            exit(0)下面是运行的结果



基于霍克原理约束



基于其他方式约束

完整的代码可在下面的链接获取

stonstad

好..好硬