testOverlap() + quadTree

Post reply
2 favourites

  • I've been cooking a bit since I noticed that javascript testOverlap() does not benefit from collision cells. In other words it's a brute force check and can get quite expensive. See: github.com/Scirra/Construct-bugs/issues/5665

    So I dug out a js implementation of quadtrees, did some minor adjustments and now it works in Construct. Here's the OG github.com/timohausmann/quadtree-js

    Here's it adapted for C3.

    wackytoaster.at/parachute/quadtree.c3p

    How well does it work? It depends. If I test the overlap between 2000 vs 2000 instances, it actually outperforms events by quite some. Easily a 2.5-3x increase in fps. Cool, BUT... If I test overlap between 1 vs 4000 instances, events are better and outperform the quadtree thingy.

    The amount of collision checks still decreases compared to events, so that must mean the overhead of rebuilding the quadtree is what ends up eating a lot of potential benefit. It seems that somewhere around 150 vs 2000 instances the quadtree starts to pull ahead of events.

    There's also a fork that adds a method to update objects instead of rebuilding the quadtree. This would only need to be called for instances that move, so the benefit really only shows if there's plenty of static objects that don't need updating. With many moving objects, it performs worse than just rebuilding the quadtree.

    There's also a version 2 github.com/timohausmann/quadtree-ts that I didn't touch because I don't know typescript. Perhaps this one is a bit faster?

    Either way, I'm looking for some thoughts about this. It seems totally worth it to look into it further considering the performance increase in SOME cases. But it's also worth it because right now in javascript there is no way to access the collision cell optimization from Construct. :(

  • It's cool to see a quadtree implementation working in Construct! One of the reasons we added JavaScript coding is to open up advanced uses like this.

    I've been cooking a bit since I noticed that javascript testOverlap() does not benefit from collision cells.

    FWIW collision cells are not actually applicable to testOverlap(): the point is to eliminate even checking instances, so it is basically a filtering system that efficiently reduces the set of instances that you might call testOverlap() on. So it is not possible to implement collision cells within the testOverlap() method itself, it's something that has to come before it. Your quadtree implementation essentially takes the role of collision cells when checking collisions in event sheets - it's an alternative system of filtering the instances you check collisions for.

  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads

  • Well if you have any tips on possibly making it faster I'd appreciate it. But I honestly would really like to get access to the collision cell optimization in scripting and SDK.

    construct23.ideas.aha.io/ideas/C23-I-221

    construct23.ideas.aha.io/ideas/C23-I-408

    Or perhaps even a construct official quadtree implementation written by someone with more knowledge than me. I've talked with Federico a bit and he speculated a directly integrated quadtree would probably already be faster than getting instances through the runtime.

    construct23.ideas.aha.io/ideas/C23-I-433

    I can see the argument for it, especially since the massive success vampire survivors had, which is btw. also written in javascript. Spawns a lot of copycats of course, and I have yet to see a solution in C3 that doesn't slow my high-end PC to a crawl at 200ish instances even with nothing else happening. I would even think the current collision cells will not suffice for these type of games, considering a cell is the size of the entire screen.

    FWIW collision cells are not actually applicable to testOverlap(): the point is to eliminate even checking instances, so it is basically a filtering system that efficiently reduces the set of instances that you might call testOverlap() on. So it is not possible to implement collision cells within the testOverlap() method itself, it's something that has to come before it.

    Oh I'm aware of that, I just kinda worded it wrong.

  • I have yet to see a solution in C3 that doesn't slow my high-end PC to a crawl at 200ish instances even with nothing else happening.

    Can you share a project file that demonstrates the performance problem of doing something like this? It would be interesting to profile and experiment with it. Perhaps just using a smaller collision cell size would make it OK.

    A problem with making built-in quadtrees is Construct's collision engine needs to extend over an unlimited area (e.g. still handling activity outside the layout area, or with unbounded scrolling). Collision cells can do that with sparse cells. I'm not sure quadtrees can handle that.

  • 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.

  • I stand corrected, this is the best vampire survivors example I found, by fedca I guess I wasn't up-to-date.

    drive.google.com/file/d/1xL7J-6fcYV0DROR24FHLW_w1j78QgD4a/view

    BUT the example does not even use the collision system, it uses the physics behavior, which I assume uses it's own implementation and also runs as wasm. I don't particularly like working with the physics behavior though, it rubs me the wrong way, but that's besides the point. So I change my statement to: I have not seen a vampire survivors example that performs well that uses default methods of collision detection. I don't have any examples at hand, I just vaguely remember that one from r0j0hound.

    I'd be curious if tuning collision cell size (or even better: allowing us users to tune the collision cell size) would improve things already. It seems quite clear that at least the current settings do not fare well with densly packed sprites, due to the collision cell size. And that rBush thing Fedca just "hacked in", wow this thing is fast. :D I've never heard of it before.

  • A problem with making built-in quadtrees is Construct's collision engine needs to extend over an unlimited area (e.g. still handling activity outside the layout area, or with unbounded scrolling). Collision cells can do that with sparse cells. I'm not sure quadtrees can handle that.

    Isn't this the main benefit of a tree structure, that sparse areas can just be one large node/cell and it only sub-divides where many instances are?

  • Isn't this the main benefit of a tree structure, that sparse areas can just be one large node/cell and it only sub-divides where many instances are?

    I think the issue is that an infinite area cannot really be devided into two smaller areas as a quadtree does, because mathematically speaking infinity/2 = infinity. And a tree structure also has the limit of how many times it can divide. Even if we assume a limited size of 1 million x 1 million units, a quadtree depth of 4 would have the smallest cell size be 125k units, which possibly still contains a vast amount of instances.

    What about a plugin that can be placed like a sprite though? For infinite games you'd pin it to the player and ignore everything outside. The object could easily be adjusted with the properties bar and it being an object rather than being buried in the depths of the engine allows to tap into its optimization outside of just collision detection. It would have a "Pick candidates" action that can be called to pick the candidates from the relevant cells. This then allows to do whatever with the picked instances, be it "is overlapping" or any kind of loop. Although that means that the engine builds both collision cells and the tree then for the instances, which could again be not ideal.

  • Just use a grid hash or a AABB tree or something if you want it to work with objects being positioned anywhere. Or since you’re building the quad tree on the fly you could guess the bounding box of all the objects, build the quad tree and anything out of bounds is put into a simple list and the correct bounding box size is calculated for the next frame. If things are moving the new bounding box would still be a guess but it would be pretty close.

  • I dug out an old C2 performance benchmarks used for collision cells, and adapted it to show all the content on a single screen: https://www.dropbox.com/scl/fi/8r2r91i0q84ay5454rssh/Overlap-benchmark.c3p?rlkey=x562ztroagbmoonxr057j4tes&dl=0

    It uses 1000 objects all testing overlap with each other, which causes ~1 million collision checks per tick. On my high-end desktop system that results in ~40 FPS with CPU maxed out. I think it's true that some games will use this style of heavy content on a single screen (Vampire Survivors being a good example, as well as bullet-hell style games), so it's a good test case and collision cells don't work well by default in that case as the collision cell size is the viewport size and so collision cells don't help.

    I added a way to change the collision cell size and it does help a great deal - for this benchmark the sweet spot seems to be about 50x50, which is a lot smaller than the default. That results in a smooth 60 FPS and ~25% CPU usage, so it's several times faster. I think that also shows collision cells can be a perfectly good solution if the size can be tweaked for the game - I'm not sure there's any reason to go further with more advanced algorithms. Too small a cell size does end up slower as the overhead of tracking cells outweighs the performance saving, but it seems fairly easy to land in the right ballpark and get big improvements.

    It remains to be seen if any complications come up but I've added action to set the collision cell size for the next release cycle, so then it can be experimented with and tuned for specific games.

  • Thank you Ashley, while other algorithms are interesting this is probably the most pragmatic solution. I hope we get access to the collision cells via scripting and addon sdk too at some point!

    Btw the dropbox link doesn't work for me and I remember other people having the same issue with dropbox links on the forum recently.

  • Oh yeah, there's a forum bug there... replace & in the URL with just & and it works.

  • Glad to see my little experiments bear fruit :)

  • Interesting!

    How do you change the collision cell size? I can't find it.

Post reply
Return to board index
Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)