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:
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:
- Resolving collision by moving each collision partner by separation/2
- updating all circles first, then resolving the collision
- Recursive separation (seems to work pretty good, but killed the frametime)
Note: I am currently working on a single thread