Optimized collision

How can I optimize the collision between object? I have always used two for loops but when there is a lot of object it start to lag. All the object are moving and all of them are in the screen so I can't stop checking their collision

How many objects are we talking about?

Something like 500-700

Outch. Lol

I remember having the same problem when i was playing around with boids once. Some solutions optimize it by dividing the area into quadrants and evaluate those one by one.

I was able to improve it by splitting it up in the update cycle. Only evaluated lets say 100 per cycle ( forgot the number, in the end i got so frustrated that i deleted it ... ) and had a marker that showed me when all were ready to be drawn.

I wonder if one now would be better of using a separate thread?

Experts?

Dividing the area in quadrants seems a good idea, i Will try that. Thanks!

I watched a video on yt - which game engine is better - Unity vs Godot. Both engines with 2000 objects ( circles ) falling into the box had 15 FPS . https://www.youtube.com/watch?v=GPgkW0h4r1k

The best solutions in my opinion

1. Use an existing physics engine - don't write what someone else has already written.
2. Use surrounding circles instead of other shapes.
3. If you count the collisions yourself - do not use the square root when calculating the distance between the circles.

https://en.wikipedia.org/wiki/Quadtree

https://microstudio.dev/i/Loginus/quadtree/

Here is my code implementing QuadTree. The white circles do not collide.

You press the mouse and change the collision detection algorithm.

For me, 200 circles have 60 FPS when tested in QuadTree. 10 FPS when brute force detection. My algorithm fails to detect two colliding circles when they are in different parts of the QuadTree.

Thanks @Loginus but it's still not enough, on my computer when there are more than 400 object the FPS go below 30

MicroScript 1.0 , Transpiler version >> https://microstudio.io/i/Loginus/quadtree2/

400 objects and 60 FPS on my laptop.

Edit

JavaScript version >> https://microstudio.io/i/Loginus/quadtree22/

800 - Objects and 60 FPS .

A more advanced design might create a subtree only when the number of objects in a given area exceeds a certain threshold. When objects are grouped together, this will improve efficiency.