检查大量对象的碰撞 JS

Question

我一直在使用数组 allShapes。该数组由具有相同属性的对象组成，例如每个对象都有一个 .x 值和一个 .y 值。

每个形状都有一个"radius"，所以检测起来很容易。对于每个物体，半径完全相同。等于 10.

我怎样才能有效地创建一个函数来检查一个形状是否与另一个形状发生碰撞？提前致谢！

var allShapes = [{70,30},{40,90},{287,245}];
// allShapes[0].x = 70
// For each object, there is a .x and .y value

Answer 1

如果简单的 O(n^2) 解决方案（测试每个对象与所有其他对象）不够有效，请选择一种众所周知的 space 分区算法。有 kd 树、八叉树、四叉树、BSP 树等。也许你应该从一个简单的网格开始。将您的域划分为多个单元格，并按单元格对您的对象进行排序。对于给定的候选对象，使用相同和所有相邻单元格中的所有对象进行测试。

Answer 2

var allShapes = [{70,30},{40,90},{287,245}];

for(let i = 0; i < allShapes.length - 1; i++) {
  for(let j = i + 1; j < allShapes.length; j++) {
    //check if allShapes[i] and allShapes[j] are colliding
  }
}

检测细分：

- allShapes[i] = {70,30}
  - allShapes[j] = {40,90} => check collision
  - allShapes[j] = {287,245} => check collision
- allShapes[i] = {40,90}
  - allShapes[j] = {287,245} => check collision

检查大量对象的碰撞 JS

Checking Collision Lots of Objects JS

javascript

object

collision-detection

collision