Quadtree Efficiency?

I was reading a post on optimization of collision detection and I read that a quadtree isn’t a good choice after 1000 or so objects. Sadly, I have already spent a while implementing one and my game, by the end, should have many, many entities being moved around simultaneously. If you have played the game Factorio, it is much like this - for those who don’t know, a large source of lag in Factorio is thousands of items moving along conveyor belts. Is the impact of a Quadtree likely to make this performance even worse, and, if so, what should I use?

Use grids. They have a lot less cache-trashing, and the logic is trivial. You will have quite a lot of empty cells, but that’s OK.

Someone posted this article a while back.

Its a very good read for your problem, especially if you are trying to decide whether to use quad trees for collision detection.

Grids are extremely fast and trivial, but you need to spend some time tweaking them when you have objects with negative positions. Since you’ll typically implement them as 2D arrays, negative indices will be a problem.

I really really prefer using boundary volume hierarchies, like aabb trees or circle trees. You can read up more here:


You just add a value to the coords to ensure they are positive… you’ll never need negative cell index logic.

A good pragmatic solution :slight_smile:

Cell grids are currently perfect for my use case which is thousands of approximately similarly sized entities moving slowish around a grid upon which they can only “just” intersect each other on briefly. That’s really the important thing… choosing the right data structure for your specific use case. One-size-fits-all never works best.

Cas :slight_smile:

Cell grids are good, I agree, but @Riven, I don’t know which type of game the OP is making, so I recommended one that works for all sorts of games. Even with adding a number to make the indices positive, it won’t work well when we have open world games. However, AABB trees are easy to understand, and yet the same time, give good performance.

Developers asking these questions shouldn’t be making games that require anything more than grids :point:

It may sound patronizing, but it’s true :slight_smile:

(I’ll show myself out :-*)

Thanks for all the info, and it’s true, I’m pretty new XD however, I’m sure I’ll be able to figure out to some extent AABB trees/grids. :slight_smile: