Show HN: Detecting collision between 500k circles below 5ms

[don_shadaman]

https://github.com/supahero1/hshg

Heya.

I created a flexible collision engine for broad detection in C that's also pretty fast. Personally that's my best, so I wanted to show it here. Although... still not as fast as DragonEnergy's one that supposedly handled millions of agents bouncing off each other every frame on an old i3, haha. I hope I get better at this! He set the bar pretty high for me.

I was considering including some small function that tries finding the nearest entity, although I think it might be better to simply use query for that matter. Perhaps in the future I will get a good idea of how to do that more efficiently.

This is not a clickbait. Although generally you also call other functions in a tick, a collision check between 500,000 circles ("circles", not "squares", because distance is checked and forces are applied based on the angle between) is done below 5ms on not really that demanding hardware. I achieve lower times than that on my budget laptop, slightly more on my PC (yeah, weird). The total time spent in a tick is 3-4 times that.

[MaxikCZ]

This is fascinating stuff. You write its easily expandable to higher dimensions. My particular interest is 4D, but instead of classical hypersphere I am trying to get a shape, that when sliced to 3D looks like this:

Starts at a single point, and all following slices is a sphere that's increasing in radius quadratically.

I understand a hypercone would provide me with above for linearly growing sphere, but I have trouble imagining (or mathematically deriving) the 4D shape for quadratic growth.

My main worry is the resulting shape would not be convex, but I am not sure about it yet. Do you think your algorithm could be adapted for such shapes instead of hyperspheres?

[don_shadaman → MaxikCZ]

The engine simply divides the space into parts to decrease the number of checks necessary. It doesn't constrain you in any way regarding to what shapes you want to insert, however the broad "hitbox" must be a hypercube, and later on you can do your own math to inspect if in fact your "real" hitboxes are in contact. It doesn't matter if your shapes are convex or not, the engine sees them all as hypercubes, so all you need is provide one that's equal to or larger than your model.

This has it's downsides, namely that for very slim yet long objects you will have a pretty big hitbox, but I wouldn't worry about it that much, since the collision detection step is done really quickly. Or, you can always insert multiple smaller hypercubes to ease it up a little bit, but then you need to be vary of duplicate collisions.

If you really want, I can extend the existing codebase to also include 4D. I hope I will be able to correctly deduce the 4D cells that need to be checked for collision haha, I think nobody is good at visualising 4D very well.

As for the math equation for the shape you are looking for, I'm not a 4D guru, so I can't help you with that, sorry. I tried some research just now, but this just isn't for me.

[MrLeap]

Neat! I made a regular ol' spatial grid hash (no hierarchy) in C# a few days ago for a boids thing.

It occurred to me then doing the whole simulation on GPU was the way to get nutty performance, but I haven't got to it yet.

Very cool of you to open source this.

[jimsmart]

Interesting project, thanks for sharing! :)

Just as a point of reference (in the past I was a games dev), a game / sim running at 60 frames per second means that one has a budget of ~16ms/frame — a figure that you may want to consider when benchmarking.

Obviously, games rarely have 500k objects that need collisions — and logging can also be costly (I didn't specifically look at where/when you were logging, but even one log statement in a regularly called function can significantly impact a benchmark)

[whinvik]

Very cool. The naming is somewhat confusing. On the top you mention 2D spatial grids but in the description you mention 1D, 2D and 3D. Or am I misinterpreting something.

[don_shadaman → whinvik]

You can define "HSHG_D" before including "hshg.h" to get the definitions for the dimension you want to use. Throughout the documentation I'm talking about 2D, because I think it's relatively the easiest to understand with not so much to write. In 1D, you wouldn't know the proper order of arguments to some functions.

[Genbox]

Could you provide a link to the "DragonEnergy" you mentioned?. I can't seem to find it on Google.

[don_shadaman → Genbox]

https://stackoverflow.com/questions/41946007/efficient-and-w...

[Genbox → don_shadaman]

Thank you. Amazing article he wrote.