Efficient collision detection using quadtrees

I recently started to learn Java and OpenGL with the LWJGL and I'm making some simple games to get started.

At first, when I was going to implement collision detection I immediately thought there had to be an smarter thing than just cycle through each pair of objects (which is an ugly O(n²) operation), so I did some ressearch. It seems that in 2d, what works for most people is a data structure called quadtree.

As I've been working a lot with binary trees (and implementing them) in college, I don't find much of a difficulty in implementing a simple quadtree, but what's really blocking me right now is movement:

Many of the implementations I've seen out there treat this in a way which I consider rather inefficient, but I can't think of anything better. What they do is, each frame of the game execution, they clear the whole quadtree, and add again all the objects which need to be checked for collision that frame, so that way the position updates will be also updated in the quadtree. Is there a more efficient way to do this? I think the objects should be replaced inside the quadtree, and nodes should be added/deleted taking into account those replacements.

I don't know if I'm over-thinking it. Even with the clearing and re-adding method it turns an n² operation into an almost n·log(n) operation. But this is just theoretically, and I have to add another linear operation (clearing and re-adding the quadtree), so I'm worried it wouldn't do any improvements in the actual speed...

Also, another related doubt. I see many people with different approaches regarding quadtrees. Some state that objects that can't fit completely in a quadrant, for a given level, should be stored at least one level upwards, while some others argue that it is better to store objects only in the quadtree's leafs, and an object overlapping at several quadrants should be stored in all of them. Of course we're talking about references here (I'm using java so I can't work with anything else anyway...), I just mean that this would'nt be a serious memory issue, and thus I'm not taking that into account. Anyway, I was just wondering: Which of those might be better? and why?

Any help and other related comments will be much appreciated

Thanks in advance

• This doesn't really answer your question, but for a lot of games, especially simple games like you mentioned you were working on, a quadtree structure is overkill. I would suggest you first work on collision detection and how you handle it, then come back and work out quadtrees after you have it implemented. Commented Jun 18, 2013 at 3:36

1 Answer

I'd go with some sort of notification/event system to keep the quadtree updated when an object moves. This would require telling the quadtree the previous location of the object (since that's where it was indexed) and the updated location, so the quadtree can check if the object should be reindexed.

• I have implemented this exact suggestion before when I did quadtrees and it worked well. If the children know of their parents, then reassigning a child to its neighbor is trivial because it can ask the parent which quadrant the Agent should now occupy. Commented Jun 17, 2013 at 19:33