Address performance issues of QuadTreeBroadphase collision detection

[filiph]

What could be improved

I noticed that when having a lot of moving components with collision detection, the HasQuadTreeCollisionDetection algorithm is significantly slower than the standard HasCollisionDetection (using Sweep). For something like 800 entities, quad tree is about 3 times slower.

(Sidenote: the "benchmark" code isn't trying to be particularly correct — you can see that many objects that are clearly colliding are white instead of red. This is because we're just blindly switching colors on collision start and on end, and don't care whether there are other collisions active. My point is to stress the collision detection code, not to build a simulation.)

I realize no optimization is a good fit for all cases, but this was a surprise to me, as I thought that QuadTree would deal with this exact case (lots of moving objects, some of which are far away from each other) better than the default.

I looked into it in profile mode, and it seems that a lot of the slowness comes from adding things into the HashSet of CollisionProspects and doing other operations on various Sets.

I tried different low-effort optimizations (such as caching CollisionProspect's hashCode or trying different ways to implement CollisionProspect.==) but nothing yielded significant improvements. It's of course possible that I'm missing something obvious, but I'm thinking that maybe the whole approach of using Sets of prospects might need to be rethought.

One idea I had was to try to implement a much simpler broadphase algorithm (based on a simple grid of static proportions). But I think the current API would still force me to use Sets of prospects, which could undermine any performance improvements over Sweep.

I'm seeking opinions and feedback. Maybe I'm just holding it wrong?

Code of my simple "benchmark" in this repo. DartPad here:
https://dartpad.dev/?id=a36320487f5a18fd6418f1db1e21a1da

Why should this be improved

Movement of a lot of collidable objects on a large map is a prerequisite for quite a lot of 2D game genres (shoot 'em ups, RTS, physics games, etc.).

It should be easy to make this relatively fast, and potential pitfalls should be documented.

Any risks?

• The options I see could lead to breaking changes of the CollisionDetection API (especially for the "internals" — when someone is providing their own Broadphase — other users might not even notice).
• This could be a lot of finicky work that ultimately only serves a small minority of Flame users.

More information

I'd be interested in taking this on but I have trouble gauging how big of a problem this is for Flame as a whole. My game is pretty special in that it has a big world with lots of entities — but that might be an outlier. I'd hate to work on a scalable solution to a problem that only a few people actually have. In such cases, my policy is to solve only the particular problem at hand (my own game) and document it, instead of throwing hours of work at an "elegant" solution that isn't needed (YAGNI).

[spydon]

Thanks for a well written issue! I have seen this behavior previously before too on the quad tree implementation.
@ASGAlex has done a lot more work on this after the current QuadTree broadphase was released, so he might be able to provide some insights too.

But I think the current API would still force me to use Sets of prospects, which could undermine any performance improvements over Sweep.

I think we could create a breaking change and use another type than sets here.

The options I see could lead to breaking changes of the CollisionDetection API (especially for the "internals" — when someone is providing their own Broadphase — other users might not even notice).

What options have you thought about?

[filiph]

My current thinking is, instead of using a separate Broadphase object, do the less elegant and more direct thing and just filter things out in CollisionDetection.run(). That should avoid creating and updating collections of CollisionProspect instances.

An even more radical approach would be to save collision detection data directly to Hitboxes or Components... But that's an extreme.

[spydon]

That would make it impossible to run with different broadphases though, so I don't think that is an option unfortunately, since in the more advanced cases you sometimes have to have a broadphase that is specific to your use-case.

An optimization that I see directly is that we should make the CollisionProspect mutable and start pooling it.
I see there are new lists created in the quad tree implementation that are very easy to get around too.

[ASGAlex]

Quad Tree is not a good thing for continuously moving objects, because it become necessary to recalculate all spatial partitioning for every run. You need a static spatial grid for such purposes and yes, you need to cache everything you can.

Every Quad Tree modification will not solve your problem. I think it's future in Flame engine should be like staying in it's current state, receiving bug-fixes and compatibility patches only.

I can suggest you to try my experimental library, it has statical partitional grid and works with object's speed and size , offers advanced type filtering and so on to reduce collision checking as much as possible ...
But I am not sure that architecture is final and of course not all bugs are solved.

https://github.com/ASGAlex/flame_spatial_grid

You can check a live demo, press C to spawn more moving components and compare performance with another approaches. I'm sure, my will be faster 🤟

I have plans to port it into Flame, but it will not happen too soon

[filiph]

Got it, thanks both!

What would you say, @ASGAlex, is the best-case scenario for QuadTreeBroadphase? Is it a game with, say, 70-90% non-moving entities (such as a platformer)? I think that if we come up with some guidance, we can put it in the API docs, at the very least. Something like:

/// Use [HasQuadTreeCollisionDetection] if you have lots of collidable entities in your game,
/// but most of them are static (such as platforms, walls, trees).

I think that would address this issue, and I'm happy to create the PR.

Also, I love that you're already working on a spatial grid implementation. Is this meant to become a Broadphase subclass at some point? (Something like SpatialGridBroadphase?) Or is that a separate approach? (Just curious. This is not blocking this issue.) Ignore this question. I'm reading through flame_spatial_grid's code and I'm getting that it's so much more than just a collision detection broadphase.

[ASGAlex]

I'm not sure about exact list of game types such as platformer and so on... With QuadTree you can make something like old-school Fallout or Arcanum but without map streaming. With QuadTree you can also create a classic RTS, but not something such epic as Supreme Commander is. With Spatial grid you have a chance, but the chance would be bigger with normal multithreading support and with shared memory, but Dart is too limited here, sadly.

My custom spatial grid implementation already extends core Flame classes, just check the sources. I prefer to write separate compatible library first, rather then to modify engine itself for every R&D experiment. And after creation of such separate library - to move well-tested features with stable architecture into the Engine one-by-one. But this is a long story. So if you need a solution right now - just use the library. Maybe next year it will be ported to engine, at least it's core part. But! Maybe not 🤷🏽‍♂️😔 This is just hobby project, I'm even not a Flutter developer in my everyday work.

[filiph]

Thanks!

What do you think about the proposed doc comment, then?

/// Use [HasQuadTreeCollisionDetection] if you have lots of collidable entities in your game,
/// but most of them are static (such as platforms, walls, trees).

I know there are exceptions, and exceptions to exceptions, and so on. But I believe it's better to say something than to leave folks to learn this lesson the hard way.

[ASGAlex]

I'm agree, that additional doc comment might be useful, along with explaining same things at Flame *.md documentation.
I'm not so risky to write documentation longreads because of compassion to @spydon , who always corrects my crooked English 😂

[filiph]

Thanks, I'm going to prepare a PR soon.

For what it's worth, my very simplistic benchmark does show an increase in performance when I make most of the components static (as in, I don't move them) but it's still a lot slower than Sweep.

DartPad: https://dartpad.dev/?id=2addd7ce85842c60d5a16e05a4f1caa7

What do you think, @ASGAlex? Is it because the entities are too close together and too uniformly distributed for the QuadTree optimization to really kick in?

[ASGAlex]

It looks like you faced the main issue of QuadTree algorithm itself, I described it in my article https://asgalex.medium.com/make-flame-32-times-faster-with-collision-detection-and-additional-tricks-3c212404b0b0 at "Problems" section. Unfortunately, there is no fix. And this is another reason why I think that Quad Tree itself does not worth any additional performance improvements: it always will have this general problem and general limitations. We just need to find a better approach.