[bemmu]

I got curious about how CPU-intensive it would be to run a server for a game like agar.io or diep.io. In these games there are a lot of circles moving around on a 2D map, and you have to check collisions between them.

First was a naive Python version. Test every circle against every other circle for collision, O(N^2). This way I managed only 200 circles on my playing field. I wanted to see how much faster it would be rewritten in C. That got me to 1500 circles.

Now obviously the way I was checking for collisions is silly, some kind of subdivision of space is required to avoid having to check everything against everything. I split the playing field into a grid, and only test collisions between circles in nearby grid cells. That got me to 3000 circles running in Python.

Next I want to write that in C as well, to see how fast it would go.

[rosspackard]

Look into Axis aligned Bounding Box Tree algorithms