I read this very interesting blog posts on the topic yesterday, it goes into different 2d collision optimizations as well as benchmarking. https://0fps.net/category/programming/collision-detection/
The main verdict is:
- cells are super fast if the cell size is tuned properly and the distribution of instances is uniform
- the tree structures try to fix that by putting more cells where more instances are so it can handle random distribution and clusters more efficiently
Looking at the benchmarks this person does it seems like rBush (https://github.com/mourner/rbush) is performing very well in a wide variety of cases, so I added it to Wacky Toasters benchmark https://drive.google.com/file/d/1aM894Ckvqb-BVBREuXN34CqDtpzmuZQ3/view?usp=sharing (just hacked in)
Test 1:
3x faster than quadTree and 100x faster than collision cells. But that is probably only due the collision cell size being tuned badly, as in theory this bench should be very favorable to collision cells.
Test 2:
I don't really understand how events are so fast in that benchmark.
Another side note: to me it seems like wasm is a good fit for a collision system like this as it seems easy to separate from the main js logic and could lead to some nice perf improvements.