<译> Simulating Object Collisions With Canvas

发表于 | 分类于 ， ，

翻译系列第三篇，在canvas里模拟物体碰撞，原文地址

作者开篇给了成品效果但是直接canvas绘制的不是gif，看原文吧，非常炫酷（强烈建议直接阅读原文，因为效果作者是用canvas绘在博客的，我后面的懒得截gif…），源码在这里

canvas起步

如果你还不知道<canvas>，可以看看MDN，这里不展开了

使用ES6的类将使我们能够稍后管理状态并创建常量，因此让我们从构造函数开始。要初始化画布，我们需要定义父元素、宽度和高度。最重要的是，我们需要把它的上下文分配给一个属性，我们可以在以后的绘图中使用

1
2
3
4
5
6
7
8
9
class Canvas {
  constructor(parent = document.body, width = 400, height = 400) {
    this.canvas = document.createElement('canvas');
    this.canvas.width = width;
    this.canvas.height = height;
    parent.appendChild(this.canvas);
    this.ctx = this.canvas.getContext('2d');
  }
}

这样，我们就可以添加方法来绘制特定的形状。在这案例中，我们只画圆

1
2
3
4
5
6
7
8
9
10
class Canvas {
  ...
  drawCircle(actor) {
    this.ctx.beginPath();
    this.ctx.arc(actor.position.x, actor.position.y, actor.radius, 0, Math.PI * 2);
    this.ctx.closePath();
    this.ctx.fillStyle = actor.color;
    this.ctx.fill();
  }
}

请注意，drawCircle需要一个具有position和radius属性的actor。让我们实现一个稍后将在其上构建的基本类

1
2
3
4
5
6
7
class Ball {
  constructor(x = 20, y = 20, color = 'red', radius = 10) {
    this.color = color;
    this.position = { x: x, y: y };
    this.radius = radius;
  }
}

现在测试一下

1
2
3
const canvas = new Canvas();
const ball = new Ball();
canvas.drawCircle(ball);

下一步是使用动画循环在画布上添加一些动作

添加动画

在我们开始之前，让我们用一些有用的线性代数方法创建一个向量类，这样我们就可以在坐标平面上轻松地工作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Vector {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }

  /**
   * Returning a new Vector creates immutability
   * and allows chaining. These properties are
   * extremely useful with the complex formulas
   * we'll be using.
   **/
  add(vector) {
    return new Vector(this.x + vector.x, this.y + vector.y);
  }

  subtract(vector) {
    return new Vector(this.x - vector.x, this.y - vector.y);
  }

  multiply(scalar) {
    return new Vector(this.x * scalar, this.y * scalar);
  }

  dotProduct(vector) {
    return this.x * vector.x + this.y * vector.y;
  }

  get magnitude() {
    return Math.sqrt(this.x ** 2 + this.y ** 2);
  }

  get direction() {
    return Math.atan2(this.x, this.y);
  }
}

让我们更新Ball，使用一个向量的实例来表示它的位置

1
2
3
4
5
6
7
class Ball {
  constructor(x = 20, y = 20, color = 'red', radius = 10) {
    this.color = color;
    this.position = new Vector(x, y);
    this.radius = radius;
  }
}

这将使添加运动，碰撞和质量变得更加简单。 因此，关于动画循环，这将变得复杂。 MDN的指南使用了非常简单的动画循环来实现这一目标。 但是，我将效仿Eloquent JavaScript实现一个State类，该类提供某种程度的封装。 这使添加新形状或替换WebGL之类的显示变得更加容易（如果需要）。

State应该跟踪正在使用的显示以及在动画中出现的对象。最后，需要一个方法来更新每一帧中每个actor的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class State {
  constructor(display, actors) {
    this.display = display;
    this.actors = actors;
  }

  update(time) {

    /**
     * Provide an update ID to let actors
     * update other actors only once.
     **/
    const updateId = Math.floor(Math.random() * 1000000);
    const actors = this.actors.map(actor => {
      return actor.update(this, time, updateId);
    });
    return new State(this.display, actors);
  }
}

现在状态中的每个actor都应该有一个更新方法来增加每个帧中的位置。对于Ball，我们需要添加更新以及速度属性。因为Ball获得了很多我们想要控制的属性，所以我们将如clean JavaScript所述使用Object.assign为构造函数提供一个配置对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Ball {
  constructor(config) {
    Object.assign(this,
      {
        type: 'circle',
        position: new Vector(20, 20),
        velocity: new Vector(5, 3),
        radius: 10,
        color: 'red',
      },
      config
    );
  }

  update(state, time, updateId) {

    // Check if hitting left or right of display
    if (this.position.x >= state.display.canvas.width || this.position.x <= 0) {
      this.velocity = new Vector(-this.velocity.x, this.velocity.y);
    }

    // Check if hitting top or bottom of display
    if (this.position.y >= state.display.canvas.height || this.position.y <= 0) {
      this.velocity = new Vector(this.velocity.x, -this.velocity.y);
    }

    return new Ball({
      ...this,
      position: this.position.add(this.velocity),
    });
  }
}

为了使画布保持最新，我们需要添加一个同步方法来调用每一帧。它应该重新绘制每个actor的State

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Canvas() {
  ...
  sync(state) {
    this.drawActors(state.actors);
  }

  drawActors(actors) {
    for (let actor of actors) {
      if (actor.type === 'circle') {
        this.drawCircle(actor);
      }
    }
  }
}

最后，我们需要一个递归调用requestAnimationFrame来创建动画循环的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const runAnimation = animation => {
  let lastTime = null;
  const frame = time => {
    if (lastTime !== null) {
      const timeStep = Math.min(100, time - lastTime) / 1000;

      // return false from animation to stop
      if (animation(timeStep) === false) {
        return;
      }
    }
    lastTime = time;
    requestAnimationFrame(frame);
  };
  requestAnimationFrame(frame);
};

这样我们就可以在技术上运行动画了。然而，canvas会跟踪绘制在其上的每一帧，因此生成的动画看起来就像在画布上拖动画笔一样。这是它的样子

1
2
3
4
5
6
7
8
const display = new Canvas();
const ball = new Ball();
const actors = [ball];
let state = new State(display, actors);
runAnimation(time => {
  state = state.update(time);
  display.sync(state);
});

要改变这一点，我们可以修改sync 以在每次画布更新的时候清除画布。利用之前的帧没有被破坏这一事实，我们可以通过在整个画布上画一个白色矩形来实现这一点。如果矩形是不透明的，之前绘制的圆通过时它将创建一个trail效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Canvas() {
  ...
  sync(state) {
    this.clearDisplay();
    this.drawActors(state.actors);
  }

  clearDisplay() {

    /**
     * If the rgba opacity is set to 1, there
     * will be no trail. The lower the opacity,
     * the longer the trail.
     **/
    this.ctx.fillStyle = 'rgba(255, 255, 255, .4)';
    this.ctx.fillRect(0, 0, this.canvas.width, this.canvas.height);
  }
  ...
}

现在我们有了移动

检测碰撞

在我们上次更新的球你已经看到了一点碰撞检测，我们检查球是否击中墙壁的画布，并更新相应的速度

然而，要发现一个球是否与另一个球碰撞，我们必须检查每个球对每个球（every ball against every ball）。对于O(n2)复杂度，这是非常低效的，但这是除了创建一个复杂的矩阵来表示坐标之外的最佳解决方案。而且它对少于1000件物品也很有效

这可以通过在每次更新Ball时使用for循环来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Ball {
  ...
  update(state, time, updateId) {
    ...
    for (let actor of state.actors) {

      // A ball can't collide with itself
      if (this === actor) {
        continue;
      }

      const distance = this.position.subtract(actor.position).magnitude;

      if (distance <= this.radius + actor.radius) {
        this.color = 'grey';
        actor.color = 'grey';
      }
    }

    return new Ball({
      ...this,
      position: this.position.add(this.velocity),
    });
  }
}

因为我们使用一个矢量来跟踪球的位置，我们可以用两个物体之间的位置差的大小来测量两个物体之间的距离。记住，位置是在物体的中心测量的，所以要检测当边缘碰撞时，我们需要检查这个距离是否小于两个物体的半径的总和。

现在，当球碰撞的时候没有什么有趣的事情发生，它们只是改变了颜色。但这只是个开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const display = new Canvas();

const ball1 = new Ball({
  position: new Vector(40, 100),
  velocity: new Vector(1, 0),
  radius: 20,
});

const ball2 = new Ball({
  position: new Vector(200, 100),
  velocity: new Vector(-1, 0),
  color: 'blue',
});

const actors = [ball1, ball2];
let state = new State(display, actors);

runAnimation(time => {
  state = state.update(time);
  display.sync(state);
});

二维弹性碰撞计算

数学时间到了!我们将使用弹性碰撞，因为我发现这是一个有趣的动画，不用太复杂的重力和摩擦。但如果这就是你想要的，那就试试吧。

维基百科有一个奇妙的动画在弹性碰撞页面上展示了在2D碰撞中会发生什么。

在数学上，这可以被定义为如下。记住还有另一个使用角度的公式，但是因为我们用的是向量，这个公式更容易实现。

其中v‘为最终速度矢量，v为当前速度，m为质量，x为位置。尖括号表示矢量的点积，双竖条表示矢量的大小或长度。

目前，球的质量没有一个表示。假设密度恒定，我们可以用圆的球形面积作为质量。

1
2
3
4
5
6
class Ball {
  ...
  get sphereArea() {
    return 4 * Math.PI * this.radius ** 2;
  }
}

使用我们添加到Vector类中的方法，我们可以用JavaScript编写它。这不是一个很好的公式，但它是紧凑和准确的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const collisionVector = (b1, b2) => {
  return b1.velocity

    // Take away from the starting velocity
    .subtract(

      // Subtract the positions
      b1.position
      .subtract(b2.position)

      /**
       * Multiply by the dot product of
       * the difference between the velocity
       * and position of both vectors
       **/
      .multiply(
        b1.velocity
        .subtract(b2.velocity)
        .dotProduct(
          b1.position
          .subtract(b2.position)
        )
        / b1.position
        .subtract(b2.position)
        .magnitude ** 2
      )

      /**
       * Multiply by the amount of mass the
       * object represents in the collision.
       **/
      .multiply(
        (2 * b2.sphereArea)
        / (b1.sphereArea + b2.sphereArea)
      )
    );
};

值得注意的是，不变性是如何使这成为可能的。我们可以在同一个向量上执行多个操作而不改变它的属性，同时返回可以用于链接的新向量。

现在我们可以在Ball的更新方法中使用这个。然而，我们还需要解决另一个问题。我们不能一次只更新一个速度因为两个角色的当前速度是确定它们新的速度所必需的。如果我们现在更新两个行动者的速度，速度会更新两次因为每个actor检查每个actor。

所以我们需要一种方法来同时更新两个角色。可能还有更好的方法，但我想到的是为每个冲突创建一个ID，并在一个数组中跟踪这些ID，这样我们就可以在当前更新中跳过它们。碰撞ID由对象ID和更新ID组成。

我们已经为State添加了一个更新ID，那么让我们为Ball添加一个对象ID以及一个碰撞数组。这些是我们需要计算的部分，在球中碰撞。我们把这个也更新一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Ball {
  constructor(config) {
    Object.assign(this,
      {
        id: Math.floor(Math.random() * 1000000),
        type: 'circle',
        position: new Vector(40, 40),
        velocity: new Vector(5, 3),
        radius: 10,
        color: 'red',
        collisions: [],
      },
      config
    );
  }

  update(state, time, updateId) {

    // Check if hitting left or right of display
    if (this.position.x >= state.display.canvas.width || this.position.x <= 0) {
      this.velocity = new Vector(-this.velocity.x, this.velocity.y);
    }

    // Check if hitting top or bottom of display
    if (this.position.y >= state.display.canvas.height || this.position.y <= 0) {
      this.velocity = new Vector(this.velocity.x, -this.velocity.y);
    }

    for (let actor of state.actors) {

      /**
       * A ball can't collide with itself and
       * skip balls that have already collided.
       **/
      if (this === actor || this.collisions.includes(actor.id + updateId)) {
        continue;
      }

      const distance = this.position.subtract(actor.position).magnitude;

      if (distance <= this.radius + actor.radius) {
        const v1 = collisionVector(this, actor);
        const v2 = collisionVector(actor, this);
        this.velocity = v1;
        actor.velocity = v2;
        this.collisions.push(actor.id + updateId);
        actor.collisions.push(this.id + updateId);
      }
    }

    return new Ball({
      ...this,
      position: this.position.add(this.velocity),
    });
  }
  ...
}

看看效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const display = new Canvas();

const ball1 = new Ball({
  position: new Vector(40, 100),
  velocity: new Vector(1, 0),
  radius: 20,
});

const ball2 = new Ball({
  position: new Vector(200, 100),
  velocity: new Vector(-1, 0),
  color: 'blue',
});

const actors = [ball1, ball2];
let state = new State(display, actors);

runAnimation(time => {
  state = state.update(time);
  display.sync(state);
});

这太棒了。但不幸的是，我们还没有完成。我们需要处理一些边界情况。

修复bug

还有这么多要干的：

  • 更新墙壁检测，使只有边缘接触
  • 修复粘性碰撞
  • 修复墙壁挤压碰撞（wall squeeze collisions）
  • 防止过度使用内存

壁面碰撞的第一个问题相对简单。我们只需要根据画布墙给位置更新一个上界和下界。

对于第二个问题，你可能想知道什么是粘性碰撞。正如描述所示，当两个物体重叠和粘在一起时，会有一些瞬间。这导致了一个持续的碰撞更新，通常会导致一个疯狂的螺旋。这是一个只在特定情况下才会出现的问题，但是当框架中有10个以上的球时就变得很常见了。

这里有一个粘性碰撞的例子（在原文）。

我实现的解决方案是一个简单的”创可贴“。检查下一帧是否有碰撞，并更新当前帧，就像它们发生了碰撞一样。这样物体就不会有重叠的机会。然而，他们也没有机会碰撞。值得庆幸的是，这种影响并不明显。

为了寻求更好的解决方案，我考虑了计算重叠的数量，并在添加新的速度之前消除与当前位置的距离。它在一个小的环境中工作，但是当模拟中有10个以上的球时，问题再次出现。我不确定这是否是由于浮动精度，或球备份到另一个（or balls backing up into another）。

当一个球与另一个球同时撞击墙壁时，墙挤压就发生了。我没有一个完美的解决方案。如果先计算壁面碰撞，速度就会损失。如果在之后计算，则获得速度。这是由于我们为壁面碰撞创建的边界条件，即当边缘与壁面接触时位置停止。但是，如果我移除这个边界条件，物体可能会卡在墙上。

我决定采用速度下降的解决方案，因为它在长时间运行的动画中看起来最好。

最后，因为我们一直在追踪每个球的每次碰撞，它会很快淹没我们的内存。一个简单的解决方法是在一定的限制下减小数组的大小。我选择10作为极限，因为我很难想象一个球会同时与10个其他球相撞的情况。不过，这可以根据需要进行调整。

这里有一个解决这些bug的稳定方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Ball {
  ...
  update(state, time, updateId) {

    /**
     * Limit the size of the collisions array to
     * prevent memory issues. If slice occurs on
     * too many elements, it starts to lag.
     **/
    if (this.collisions.length > 10) {
      this.collisions = this.collisions.slice(this.collisions.length - 3);
    }

    /**
     * Set the upper and lower bounds based on the
     * size of the canvas and size of the ball.
     **/
    const upperLimit = new Vector(
      state.display.canvas.width - this.radius,
      state.display.canvas.height - this.radius
    );
    const lowerLimit = new Vector(0 + this.radius, 0 + this.radius);

    // Check if hitting left or right of display
    if (this.position.x >= upperLimit.x || this.position.x <= lowerLimit.x) {
      this.velocity = new Vector(-this.velocity.x, this.velocity.y);
    }

    // Check if hitting top or bottom of display
    if (this.position.y >= upperLimit.y || this.position.y <= lowerLimit.y) {
      this.velocity = new Vector(this.velocity.x, -this.velocity.y);
    }

    for (let actor of state.actors) {

      /**
       * A ball can't collide with itself and
       * skip balls that have already collided.
       **/
      if (this === actor || this.collisions.includes(actor.id + updateId)) {
        continue;
      }

      /**
       * Check if actors collide in the next frame
       * by adding the current velocity and updating
       * now if they do.
       */
      const distance = this.position.add(this.velocity)
        .subtract(actor.position.add(actor.velocity))
        .magnitude;

      if (distance <= this.radius + actor.radius) {
        const v1 = collisionVector(this, actor);
        const v2 = collisionVector(actor, this);
        this.velocity = v1;
        actor.velocity = v2;
        this.collisions.push(actor.id + updateId);
        actor.collisions.push(this.id + updateId);
      }
    }

    /**
     * Use the bounds to limit the position
     * update.
     **/
    const newX = Math.max(
      Math.min(this.position.x + this.velocity.x, upperLimit.x),
      lowerLimit.x
    );

    const newY = Math.max(
      Math.min(this.position.y + this.velocity.y, upperLimit.y),
      lowerLimit.y
    );

    return new Ball({
      ...this,
      position: new Vector(newX, newY),
    });
  }
  ...

现在粘性只会发生在两个物体产生在彼此之上的时候。这可以使用一个随机生成器来实现，就像我在本文的介绍动画中所做的那样。

完成了！ 让我们最后尝试一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const display = new Canvas();

const ball1 = new Ball({
  position: new Vector(40, 100),
  velocity: new Vector(2, 3),
  radius: 20,
});

const ball2 = new Ball({
  position: new Vector(200, 100),
  velocity: new Vector(-1, 3),
  color: 'blue',
});

const actors = [ball1, ball2];
let state = new State(display, actors);

runAnimation(time => {
  state = state.update(time);
  display.sync(state);
});

最终成品

我将所有这些包在一个函数中，并使用一个循环来生成随机大小、颜色、不同位置和速度的球。您可以在源代码中看到所有这些内容。但是作为本文的总结，下面是我用于生成本文中的介绍动画的脚本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const random = (max = 9, min = 0) => {
  return Math.floor(Math.random() * (max - min + 1) + min);
};

const colors = ['red', 'green', 'blue', 'purple', 'orange'];

const collidingBalls = ({ width = 400, height = 400, parent = document.body, count = 50 }) => {
  const display = new Canvas(parent, width, height);
  const balls = [];
  for (let i = 0; i < count; i++) {
    balls.push(new Ball({
      radius: random(8, 3) + Math.random(),
      color: colors[random(colors.length - 1)],
      position: new Vector(random(width - 10, 10), random(height - 10, 10)),
      velocity: new Vector(random(3, -3), random(3, -3)),
    }));
  }
  let state = new State(display, balls);
  runAnimation(time => {
    state = state.update(time);
    display.sync(state);
  });
};

collidingBalls({
  count: 40,
  height: 260,
  width: 460,
  parent: document.getElementById('hero'),
});

这很有趣。但它并不完美。不完美的碰撞(因为球不接触)、挤压墙壁和球在彼此之上产生的问题仍然存在。如果你有解决这些问题的办法，请告诉我