0

I've looked around and found a billion questions, articles, studies, theses, etc, but I haven't been able to really figure out or find an answer to this question.

Basically, I'm just wondering what the best algorithm(s) for spacial partitioning/collision detection between objects from 1 pixel to the size of the screen itself is. Currently, i'm leaning towards the the loose quadtree.

user3023235
  • 11
  • 1
    [Box2D](https://github.com/erincatto/Box2D/tree/master/Box2D/Collision) uses dynamic AABB trees for real-time broadphase collisions, so something worth considering. – meowgoesthedog Aug 15 '18 at 20:33
  • that was actually my runner-up to the loose quadtree. maybe ill have a look at it again – user3023235 Aug 16 '18 at 01:43

1 Answers1

1

First, have a look here.

It depends on your requirements. Quadtrees are perfect for small to medium sized datasets up to 100K entries or so. If that fits your requirements, there is no need to read further.

However, normal quadtrees tend to have difficulties with very large or strongly clustered (high point density in some areas) datasets. They are also not that straight forward to implement because with larger tree you may run into precision problems (divide a number by 2 30 times if you go deep in a tree and your quadrants start overlapping or have gaps between them). Otherwise they are relatively easy to implement.

I found my PH-Tree quite useful, it is somewhat similar to a quadtree, but as no precision problems and inherently limited depth. In my experience it's quite fast, especially if you do window queries with a small result set (that's basically what you do in collision detection). Unfortunately it's not that easy to implement. The link above references my own Java implementation, but the doc also contains a link to a C++ version.

You can also try the 'qthypercube2' here, it's a quadtree with some of the PH-Tree's navigation techniques. The current 1.6 version has some precision problems for extreme datasets, but you will find it to be very fast, and a solution to the precision problem is already in the pipeline.

TilmannZ
  • 1,784
  • 11
  • 18
  • I did see the first link on efficient data structures, and the loose quadtree does look like it will work for very large to very small objects (although if you actually check the animated gif's in that link, you'll notice that there are actually a lot of very noticeable errors in the collisions). Those other links look very interesting though, I'll have to take a look at them tomorrow. Thanks. – user3023235 Aug 16 '18 at 01:40