CODEWITHSUNDEEP
javascriptobjectcollision-detectioncollision
Assafi Cohen-Arazi
Assafi Cohen-Arazi

Reputation: 847

Checking Collision Lots of Objects JS

I've been working with an array allShapes. This array consists of objects with the same kinds of properties, like each object has a .x value, and a .y value.

Each shape has a "radius", so the detection can be easily done. For each object, the radius is exactly the same. It equals 10.

How can I effeciently make a function that checks if one shape is colliding with another? Thanks in advance!

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

Upvotes: 1

Views: 265

Answers (2)

yBrodsky
yBrodsky

Reputation: 5041

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
  }
}

Breakdown of detection:

- 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

Upvotes: 1

hansmaad
hansmaad

Reputation: 18905

If the naive O(n^2) solution (testing each object with all others) is not efficient enough, choose one of the well known space partitioning algorithms. There are kd-trees, octrees, quadtrees, BSP-trees etc. Maybe you should start with a simple grid. Devide your domain into cells and order your objects by cells. For a given candidate, test with all objects in the same and all adjacent cells.

Upvotes: 2

Related Questions