4
\$\begingroup\$

I'm using a quadtree to prune collision detection pairs in a 2d world. How should I choose to what depth said quadtree is calculated?

The world is made mostly of moving objects1, so the cost of dispatching the objects between the quadtree cells matters. What is the relationship between the gain from less collision checking and the loss from more dispatching? How can I strike a balance that performs optimally?


1 To be completely explicit, they are autonomous self-replicating cells competing for food sources. This is an attempt to show my pupils predator-prey dynamics and genetic evolution at work.

\$\endgroup\$
  • 2
    \$\begingroup\$ I certainly appreciate the sharing, but this question would likely be closed on its own. Maybe you can flesh out the question a little more so that it's possible for other people to provide answers too? Currently it's primarily opinion based, since you're not stating a problem to be solved, just asking an open ended question without details. \$\endgroup\$ – MichaelHouse Jun 10 '14 at 22:28
  • \$\begingroup\$ @Byte56 I tried, though I am not sure if it is better. Feel free to ask for more details if you think it would improve the question. \$\endgroup\$ – Evpok Jun 10 '14 at 22:55
2
\$\begingroup\$

Of course, if resources are scarce and speed critical, said depth should be determined through benchmarking, but here are some maths to help cornering it.

Let us assume that we are dealing with n object for which we have to trace collisions, that their repartition in the world is uniform and they are small enough that no matter how fine the grid is, overlap will be negligible. If we use a depth d quadtree, we have 4^d leaf cells, so that's an average of n/4^d objects per cell. If the cost of detecting collisions between N objects is O(N^p), the cost of checking all collisions is

4^d⋅(n/4^d)^p

If we rebuild the quadtree from scratch, the cost of dispatching the objects between the cells is 2⋅n⋅d. So the total cost is

c(n,d,p) = 4^(d-dp)⋅n^p + 2⋅n⋅d

So finding an appropriate d should not be hard. Interestingly enough, it is not too dependent on p, for instance for 100 objects and p from 2 to 7, here is a plot c (for real-valued b to make it easier to read)

cost graphs

Here, 3 seems to be a good d. So me mostly have to take n into account. For p=2, the n thresholds I found are

   n >  │ d
  ──────┼────
  100   │ 3
  400   │ 4
  1400  │ 5
  5500  │ 6
  22000 │ 7
  87000 │ 8
  350000│ 9

Again, the numbers are quite crude and the assumptions quite strong. In particular, if you are dealing with non-ponctual objects, you should definitely make sure that size is still small enough with respect to the grid granularity. But it should at least give a order of magnitude.

\$\endgroup\$
  • \$\begingroup\$ If the partition of the objects in the world is uniform, you might as well just use a grid (i.e. spatial hash). Should perform better than a quadtree, and will have a smaller memory footprint. \$\endgroup\$ – TravisG Jun 11 '14 at 14:28
  • \$\begingroup\$ The repartition is not uniform. That is only an assumption I made to get an approximation. Prior to this investigation I had no idea if a quadtree should have 4 levels or 100. Now that I know the order of magnitude, I can run benchmarks to know the appropriate depth for the actual situation. (Which is that herbivores are usually clustered in the most bountiful areas, while barren land is, well, barren) \$\endgroup\$ – Evpok Jun 12 '14 at 10:49
1
\$\begingroup\$

For your purpose, I agree with @TravisG, that collision detection via a quadtree may be an overkill. In many Agent Based Modelling and Simulation platforms the world is simply a 2D grid and agents sharing the same grid cell are supposed to be in the same location. This approach of collision detection should be sufficient enough to demonstrate concepts like predator-prey dynamics.

You may run the Wolf Sheep Predation model from Netlogo (download link) and check if it is good enough for your goal.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the advice :) However I was less interested in my particular situation and more in an order of magnitude for the depth of a quadtree. \$\endgroup\$ – Evpok Jun 12 '14 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.