Sort, sweep, and prune: Collision detection algorithms
排序、清扫和修剪：碰撞检测算法

Sweep-and-prune is my go-to algorithm when I want to quickly implement collision detection for a game. I think it’s an awesome and elegant algorithm, so I wrote a post about it.
扫掠与修剪是我在想要快速实现游戏碰撞检测时的首选算法。我认为这是一个很棒且优雅的算法，所以我写了一篇关于它的文章。

This post is lengthy with many examples and explanations, thus split into two parts. You can jump to specific bits using this special springboard:
这篇文章很长，包含许多例子和解释，因此分为两部分。您可以使用这个特殊的跳板跳到特定的部分：

• Part 1: Simplified version
  第一部分：简化版
  • 🔍 Visual comparison
    🔍 视觉比较
  • 📝 Code 📝 代码
• Part 2: Sophisticated versions
  第二部分：复杂版本
  • 🔍 Visual comparison
    🔍 视觉比较
  • 📝 Final code
    📝 最终代码

As for the rest of the post, I try to paint a picture of what I think are first principles and show it with interactive demos! Let’s go!
至于帖子其余部分，我试图描绘我认为的基本原则，并通过互动演示展示它！让我们开始吧！

Collision detection 碰撞检测

As you may know, the problem of collision detection is pretty common in video game programming. It’s a prerequisite to the implementation of certain game mechanics or simulations.
如您所知，碰撞检测问题在视频游戏编程中非常常见。这是某些游戏机制或模拟实现的前提条件。

Goombas colliding 哥布林相撞

Some of these mechanics include: preventing characters from passing through each other, goombas turning around when bumping into another, big cells eating smaller cells in agar.io, or just about any game physics. All of these need some kind of collision detection.
这些机制包括：防止角色相互穿过，库巴在碰到其他角色时转身，大细胞在agar.io中吃掉小细胞，或者几乎任何游戏物理。这些都需要某种碰撞检测。

Cells consuming smaller cells on contact
细胞在接触时吞噬较小的细胞

Here I’ll cover several related approaches, starting with the simplest and building up to the sweep-and-prune algorithm. I won’t cover other approaches, such as space partitioning or spatial tree subdivision.
在这里，我将介绍几种相关的方法，从最简单的开始，逐步深入到扫掠和修剪算法。我不会介绍其他方法，例如空间划分或空间树细分。

Balls. 球。

I’ll use this rigid-body ball simulation as a recurring example to demonstrate the algorithms throughout the post:
我将使用这个刚体球模拟作为一个反复出现的例子来演示整个帖子中的算法：

Alright, let’s dive in! How do we detect these collisions?
好的，让我们开始吧！我们如何检测这些碰撞？

Naive approach 🐥 幼稚的方法 🐥

The straightforward solution is to test every potential pair of objects for collision. That is, check every ball against every other ball.
直接的解决方案是测试每一对潜在对象的碰撞。也就是说，检查每个球与其他每个球。

// for each ball
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  // check each of the other balls
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];
    // check for collision
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}

Note in the above code that the inner loop starts at i + 1 to prevent duplicate pairs from being counted (A-B vs B-A). Other than that, it’s a pretty simple solution.
在上述代码中，内部循环从 i + 1 开始，以防止重复对被计数（A-B 与 B-A）。除此之外，这是一种相当简单的解决方案。

These checks are done on every time step, ensuring that balls will bounce exactly when they collide.
这些检查在每个时间步上进行，确保球在碰撞时会准确反弹。

Here’s a slowed-down, highlighted simulation, showing pairs being tested for intersection per time step:
这是一个减速的、高亮的模拟，显示每个时间步骤中测试交集的配对：

And it works. But if we had more than just a handful of balls we would start seeing performance issues.
而且它有效。但如果我们有的不仅仅是少数几个球，我们就会开始看到性能问题。

Performance, or lack thereof
表现，或缺乏表现

This naive algorithm runs in O(n²) time in Big O terms. That is, for an input of n balls, the algorithm’s running time grows proportionally to the square of the input n. That’s a lot! 📈
这个简单的算法在 O(n²) 时间内运行，使用 大 O 符号 表示。也就是说，对于 n 个球的输入，算法的运行时间与输入 n 的 平方 成正比。这可真多！ 📈

This is because for n balls, there are around (n * (n-1))/2 pairs to test, or 0.5n² - 0.5n. For example, if n = 5 there would be a total of 10 pairs. For n = 10, there would be 45 pairs. For n = 15, 105 pairs (!). And so on… Using Big O notation, we can simplify this information into a compact expression “O(n²)”
这是因为对于n个球，有大约(n * (n-1))/2对需要测试，或者0.5n² - 0.5n。例如，如果 n = 5，则总共有 10 对。对于 n = 10，将有 45 对。对于 n = 15，将有 105 对（！）。等等……使用大 O 符号，我们可以将这些信息简化为一个紧凑的表达式“O(n²)”。

To (painfully) demonstrate how the performance scales badly for bigger inputs, here’s a simulation with n = 20:
为了（痛苦地）演示对于更大输入性能如何恶化，这里有一个 n = 20 的模拟：

That’s a lot of tests per frame! Clearly, the naive solution does not scale well for large numbers of objects.
这每帧的测试数量太多了！显然，简单的解决方案在处理大量对象时无法很好地扩展。

How can we improve this solution?
我们如何改进这个解决方案？

Prologue: Improving the solution
序言：改进解决方案

Usually when optimising algorithms, you wanna find redundant or unnecessary work. Then find a way to consolidate that redundancy. (That sounded corporate-ish.)
通常在优化算法时，您想要找到冗余或不必要的工作。然后找到一种方法来整合这些冗余。（这听起来有点像企业用语。）

A good place to start would be the intersects() function since it is called for every candidate pair. If we take the typical object intersection test to be its implementation, we get a bunch of these inequality checks:
一个好的起点是 intersects() 函数，因为它会被调用每对候选项。如果我们将 典型的对象交集测试 视为它的实现，我们会得到一堆这些 不等式检查：

function intersects(object1, object2) {
  // compare objects' bounds to see if they overlap
  return object1.left < object2.right
      && object1.right > object2.left
      && object1.top < object2.bottom
      && object1.bottom > object2.top;
}

In the above code, the intersects() function checks if two objects intersect by comparing their opposing bounds for each direction. (Refer to this MDN article for a better explanation.)
在上述代码中，intersects() 函数通过比较每个方向的相对边界来检查两个对象是否相交。（有关更好的解释，请参阅 这篇 MDN 文章。）

We can break the test down to its constituent checks:
我们可以将测试分解为其组成检查：

1. object1.left < object2.right
2. object1.right > object2.left
3. object1.top < object2.bottom
4. object1.bottom > object2.top

Each check is solely concerned with one particular axis in a specific direction.
每个检查仅关注特定方向上的一个特定轴。

Here’s the key thing: Due to the && operator’s short-circuit evaluation, if any one of these checks turns out to be false, then the overall test will immediately evaluate to false.
关键点是：由于 && 运算符的 短路求值，如果其中任何一个检查结果为假，则整体测试将立即评估为假。

Our goal then is to generalise the case where at least one of these checks is false across many tests as possible.
我们的目标是将至少 一个 这些检查在尽可能多的测试中为假的情况进行概括。

It’s the same idea as the separating axis theorem, which implies that two objects can’t be colliding if there’s at least one axis where their shadows don’t overlap.
这与分离轴定理的想法是一样的，它意味着如果至少有一个轴上它们的阴影不重叠，那么两个物体就不能发生碰撞。

Let’s say we focus only on the second check - object1.right > object2.left. Don’t worry about the rest of the checks. As hinted above, optimising in just one axis can still make a big difference later, so we’ll focus on this single check for now.
让我们说我们只关注第二个检查 - object1.right > object2.left。不用担心其余的检查。如上所述，仅在一个轴上进行优化仍然可以在后面产生很大差异，因此我们现在将专注于这个单一的检查。

Let’s look at it in the context of multiple objects. Consider three objects - A, B, and C - in this horizontal configuration:
让我们在多个对象的上下文中来看这个问题。考虑三个对象 - A、B 和 C - 在这个水平配置中：

There are three potential pairs to be checked here: A-B, B-C, and A-C. Remember, we’re trying to find redundant work. Pretend we’re running all the pairs through the check, like so:
这里有三个潜在的配对需要检查：A-B、B-C 和 A-C。请记住，我们正在尝试找出冗余的工作。假装我们正在对所有配对进行检查，如下所示：

A.right > B.left // returns false
B.right > C.left // returns false
A.right > C.left // returns false

See any redundant work? Maybe abstractify it a little…
看到任何多余的工作吗？也许可以稍微抽象一下……

A > B // returns false
B > C // returns false
A > C // returns false

Voilà. Due to the transitive property of inequality, realise that we don’t need to run the third test! If we know that A > B and B > C are both false, then we would know that A > C is false as well.
瞧。由于不等式的传递性，我们意识到不需要进行第三次测试！如果我们知道A > B和B > C都是false，那么我们也会知道A > C是false。

“If a ≤ b and b ≤ c, then a ≤ c.”
“如果 a ≤ b 且 b ≤ c，那么 a ≤ c。”the transitive property of inequality
不等式的传递性

So in this example, we don’t really need to run intersects(A, C).
所以在这个例子中，我们实际上不需要运行 intersects(A, C)。

// 1. Test A-B
intersects(A, B) // A.right > B.left evals to false.

// 2. Test B-C
intersects(B, C) // B.right > C.left evals to false.

// 3. Infer that A.right > C.left is false.
// ∴ Therefore I don’t need to call intersects(A, C)
// to know that it will return false.

We’ve skipped one intersects() call for free! ✨
我们已经跳过了一个 intersects() 调用，免费！✨

You might be wondering how this contrived example could apply to general n-body collision detection. A smart reader such as you might also have realised that this skip only works if A, B, and C are in a particular order.
你可能会想知道这个牵强的例子如何适用于一般的 n 体碰撞检测。像你这样的聪明读者可能也意识到，这个跳过只有在 A、B 和 C 处于 特定顺序 时才有效。

What particular order? Try dragging the balls below to see when the optimisation applies and when it does not:
什么特定的顺序？尝试 拖动 下面的球，看看优化何时适用，何时不适用：

// LIVE OUTPUT:
intersects(A, B) // A.right > B.left evals to false
intersects(B, C) // B.right > C.left evals to false
intersects(A, C) // Can’t skip, returns false// Deduce that intersects(A, C) will be false

Tip: Drag the balls so that they’re horizontally spaced out in this order: A‑B‑C
提示： 拖动球，使它们水平间隔排列为：A‑B‑C

While it’s true that this skip only works when A, B, and C are ordered, remember that these labels are arbitrary! What if we simply decided to always call the leftmost ball A, the middle ball B, and the rightmost C? Then the optimisation would always be applicable! 🌌🧠
虽然这个跳过仅在 A、B 和 C 有序时有效，但请记住这些标签是任意的！如果我们决定始终将最左边的球称为 A，中间的球称为 B，最右边的球称为 C 呢？那么优化将始终适用！🌌🧠

But wait… labeling objects according to some logical ordering is essentially ✨sorting✨! What if we sorted the list of objects every time? Would the number of skipped tests be worth the cost of sorting?
但是等等……根据某种逻辑顺序对对象进行标记本质上就是✨排序✨！如果我们每次都对对象列表进行排序呢？跳过的测试数量是否值得排序的成本？

Chapter 1. Sorting 第一章。排序

Sorting, inequalities, and optimisation go hand in hand in hand. A sorted list allows us to exploit the transitive property of inequality en masse.
排序、不等式和优化密切相关。排序列表使我们能够大规模利用不等式的传递性质。

The inequality relationships of elements in a sorted list.
排序列表中元素的差异关系。

Even if we had to sort the list of objects every frame, the quickest general sorting algorithm runs in O(n log n) time which is certainly lower than O(n²).
即使我们必须在每一帧中对对象列表进行排序，最快的一般排序算法的运行时间为O(n log n)，这显然低于O(n²)。

As shown by the tri-object example above, to achieve the power to skip tests we need to sort the list of objects by x position.
如上面的三对象示例所示，要实现跳过测试的能力，我们需要按 x 位置对对象列表进行排序。

However, objects aren’t zero-width points. They’re widthy, by which I mean having a size thus occupying an interval in the x-axis, also known as “width”. How can one unambiguously sort by x position if objects span intervals in the x-axis?
然而，物体并不是零宽度的点。它们是宽度的，我的意思是它们有大小，因此在 x 轴上占据一个区间，也称为“宽度”。如果物体在 x 轴上跨越区间，如何能够明确地按 x 位置进行排序呢？

Sort by min x 按最小 x 排序

A solution to sorting widthy objects is to sort them by their minimum x (their left edge’s x-coordinate). This technique can be applied to improve the naive approach.
对宽物体进行排序的一个解决方案是按其最小 x（左边缘的 x 坐标）进行排序。可以应用此技术来改进简单的方法。

It involves minimal modifications to the O(n²) solution. But it will result in a good chunk of tests skipped. I’ll explain later.
它对 O(n²) 解决方案的修改很小。但这将导致大量测试被跳过。我稍后会解释。

First, the modified code:
首先，修改后的代码：

+ // sort by min x
+ sortByLeft(balls);
+ 
  // for each ball
  for (let i = 0; i < balls.length; i++) {
    const ball1 = balls[i];
    // check each of the other balls
    for (let j = i + 1; j < balls.length; j++) {
      const ball2 = balls[j];
+ 
+     // stop when too far away
+     if (ball2.left > ball1.right) break;
+ 
      // check for collision
      if (intersects(ball1, ball2)) {
        bounce(ball1, ball2);
      }
    }
  }

It’s mostly the same as the naive solution, differing only in two extra lines of code.
它与简单的解决方案基本相同，仅在两行额外的代码上有所不同。

The first line sortByLeft(balls) simply sorts the list, with ranking based on the balls’ left edge x-coords.
第一行 sortByLeft(balls) 只是对列表进行排序，排名基于球的左边缘 x 坐标。

function sortByLeft(balls) {
  balls.sort((a,b) => a.left - b.left);
}

And in the inner loop, there is now this break:
在内部循环中，现在有这个中断：

if (ball2.left > ball1.right) break;

Let’s break that down. 让我们来分解一下。

First, we know that the list is sorted, so the following statement holds true for any positive integer c:
首先，我们知道列表是排序的，因此以下语句对于任何正整数 c 都成立：

balls[j + c].left >= balls[j].left

The break condition, which is derived from the first operand of the intersection test, if true indicates early that the current pair being tested for intersection would fail:
中断条件是从交集测试的第一个操作数派生的，如果为真，则早期指示当前正在测试交集的对将失败：

balls2.left > ball1.right
or balls[j].left > ball1.right
或 balls[j].left > ball1.right

But there are more implications. If it was true, then by combining the above two inequations…
但还有更多的含义。如果这是真的，那么通过结合上述两个不等式……

balls[j + c].left >= balls[j].left > ball1.right

And by transitive property, the following statement would also be true!
根据传递性，以下陈述也将是真实的！

balls[j + c].left > ball1.right

Which means the intersection tests of balls at balls[j + c] would also fail. We know this without needing to test those balls individually. A range of balls have been eliminated from testing!
这意味着在balls[j + c]的交集测试中，球也会失败。我们知道这一点，而无需单独测试这些球。一系列球已被排除在测试之外！

In conclusion, when the current ball2 balls[j] stops overlapping with the current ball1, then any further ball2s in the iteration balls[j + c] would be guaranteed to not overlap ball1 as well. In other words, we stop the inner loop when it gets too far away.
总之，当当前的 ball2balls[j] 停止与当前的 ball1 重叠时，那么在迭代中任何进一步的 ball2 balls[j + c] 将被保证不会与 ball1 重叠。换句话说，当它离得太远时，我们停止内循环。

Finally, here’s a demo: 最后，这里有一个演示：

Pretty cool, right! It’s much faster now.
挺酷的，对吧！现在快多了。

Some observations: 一些观察：

• Since the list is sorted, the tests are performed from left to right.
  由于列表是排序的，测试是从左到右进行的。
• More importantly, it visibly does fewer tests than the naive approach. 📉 This is due the above optimisation which effectively limits pairs to those that overlap in the x-axis!
  更重要的是，它明显比简单的方法进行的测试更少。📉 这是由于上述优化，它有效地将配对限制为在 x 轴上重叠的配对！

Let’s analyse the time complexity. 👓
让我们分析一下时间复杂度。👓

The sort - if we take the "fastest" sorting algorithm, like mergesort or quicksort - would add an O(n log n) term.
排序——如果我们采用“最快”的排序算法，比如归并排序或快速排序——将会增加一个O(n log n)项。

The two-level loop, now with an early break, would average out to O(n + m) where m is the total number of x-overlaps. This could degenerate into n² but as mentioned above, it’s more useful to look at the average and best cases. At best, the loop would be O(n), wasting no excess processing when there are no overlaps. On average it’s O(n + m).
两个级别的循环，现在有了提前中断，平均为O(n + m)，其中m是 x 重叠的总数。这可能退化为 n²，但如上所述，查看平均情况和最佳情况更有用。最好情况下，循环将是O(n)，在没有重叠时不会浪费多余的处理。平均情况下是O(n + m)。

The average case refers to a world where objects are mostly evenly distributed and only a couple intersections per object is happening. I think this is a reasonable assumption for a relatively simple video game like a platformer or side-scroller.
平均情况是指一个物体大多均匀分布且每个物体只有几个交点的世界。我认为这是对像平台游戏或横向卷轴游戏这样相对简单的视频游戏的合理假设。

Here’s the code with running time annotations:
这是带有运行时间注释的代码：

// O(n log n)
sortByLeft(balls);

// O(n + m)
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  // O(1) at best; O(m/n) on average; O(n) at worst
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];
    if (ball2.left > ball1.right) break;
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}

Adding those together we get O(n log n + m).
将它们加在一起，我们得到 O(n log n + m)。

This is a super good improvement over the naive approach’s O(n²), because [1] n log n is much smaller than n² and [2] it is partially output-based - depending on the number of overlaps, it does not process more than necessary.
这是一个相对于天真的方法的超级好改进 O(n²)，因为 [1]n log n 比 小得多 n²，并且 [2] 它是部分基于输出的 - 根据重叠的数量，它不会处理超过必要的部分。

bigocheatsheet.com 大车作弊表.com

Furthermore, the choice of sorting algorithm could be improved. We’ll look into that in the next part (somehow better than n log n!).
此外，排序算法的选择可以改进。我们将在下一部分中讨论这个问题（某种程度上比 n log n 更好！）。

Visual comparison 视觉比较

Here’s a side-by-side comparison of the strategies we’ve covered so far! Observe the amount of intersection tests required per frame. 🔍 n = 10
这是我们迄今为止讨论的策略的并排比较！观察每帧所需的交集测试数量。🔍 n = 10

(Not shown: the cost of sorting. Let’s just say the intersection test is sufficiently expensive.)
（未显示：排序的成本。我们只需说交集测试的成本足够高。）

Aaand that concludes the first part. Those two lines of code definitely were the MVPs.
而这就结束了第一部分。这两行代码绝对是 MVP。

How will it compare to the more advanced versions?
它将如何与更高级的版本进行比较？

Continued in part 2. 继续在第二部分。