How should I choose quadtree depth?

Question

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 objects¹, 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?

---

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

Answer 1

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)

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.

Answer 2

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.