Quadtree vs just a grid for collision detection

Question

I was thinking of using a quadtree for collision detection of rectangles in 2D but it seemed kind of over complicated trying to find each quadrant a rectangle is touching when there all different sizes or even working out how many quadrants deep each quadrant should be.

I decided instead to just have a small grid over the entire area and find which cells each object is in by doing row = x/cell width, column = y/cell height for each of the 4 corners and then checking the collision with each of the other objects in those cells. I also optimized it a bit to prevent it rechecking the same objects

I tested it with a 32x32 grid and 5000 moving objects against a brute force method and it was around 20 times faster with 200 times less collision checks. So I'm wondering what advantages would using a quadtree have over the way i did it? Would it really be alot faster?

Answer 1

A grid becomes problematic when objects have widely varying sizes (due to the need to update many, many grid cells when a single object moves), or when they are very small and very sparse (which requires a large amount of grid memory to store mostly empty cells). These are the situations where tree-based partitioning structures such as quadtrees shine.