3

How do I separate N number of moving circles? I am making a small game where I have hundreds of moving circles colliding. I have them all stored in a qTree, which I recreate every frame. The collision detection works fine, but the separation is flawed. If only a small collection of circles collide, the separation works as expected. After a certain amount of circles cluster together tho, many of the circles start overlapping and moving in and out of each other

it looks like this: img

code:

   resolveIntersection(entity) {
     let v = p5.Vector.sub(this.pos, entity.pos);
     let sumRadii = this.r + entity.r;
     let dir = v.normalize();
    
     this.pos.x = entity.pos.x + (sumRadii + 1) * dir.x;
     this.pos.y = entity.pos.y + (sumRadii + 1) * dir.y;
   }
  intersects(entity) {
    let totalRadius = this.r + entity.r;
    let v = p5.Vector.sub(this.pos, entity.pos);
    
    return (round(v.magSq()) <= totalRadius * totalRadius)
  }

The algorithm works in the followings order:

createQTree();
insertCircles();

let found;
let area;

for(let e of this.enemies) {
  e.update(this.qTree);

  found = [];
  area = new Circle(e.pos.x, e.pos.y, e.r * 2);
      
  this.qTree.query(area, found);
  for(let other of found) {
    if(other !== e) {
      if(e.intersects(other)) {
        e.resolveIntersection(other);
      }
    }
  }
}

What I have tried:

  1. Resolving collision by moving each collision partner by separation/2
  2. updating all circles first, then resolving the collision
  3. Recursive separation (seems to work pretty good, but killed the frametime)

Note: I am currently working on a single thread

  • 1
    see [Path generation for non-intersecting disc movement on a plane](https://stackoverflow.com/a/30639417/2521214) that approach in my answer is similar to your simulation and should also solve your problem – Spektre Nov 19 '21 at 11:48

0 Answers0