A redness sensation

Currently playing with some Quadtree code, I want to add items to the render demo but I also want them to be able to select them with the mouse. The quadtree is also one of the large untackled chunks of Einfall stage 3. It's early stages and I'm working on a basic library version first.

Anyway here's my small description of what and why of the Quadtree.

Let's say you have a map with a few hundred items, candle sticks, dogs, rooms, people.

Let's call in 500.

The naive collision detection goes like so: foreach(item in items) DoWeCollide?

That's 500 comparisons to see if a single object collides, or if your mouse intersects an item. That's a lot. Imagine 50 NPCs are moving thats 50*500 comparisons every frame. A big number.

Oh no, what can we do this is the end of games as we know it!
Yes, it does seem that way ... but wait there's our hero QuadTree!

In a quad tree you split the map up into regions. Cut the map in half vertically and horizontally and you get four equal size regions. Now cut those regions into four, and perhaps once more. So we now have nest regions.

First Cuts
Region1
SubRegion1
SubRegion2
SubRegion3
Subregion4
Region2
...
Region3
...
Region4
...

So we have the above type of regions, notice the hierarchy we've got going on, admire that hierarchy.

Right, now our collision detection is more a conversion like so:

NPC> Hey, First Cuts, do I collide with any of your regions.
First Cuts> Why yes, yes you do, you collide with two of them I'm afraid. Region1 and Region2.
*NPC goes to talk to Region1 and 2
NPC> Hey, Region1 and Region 2 so I collide with any of your subregions.
Region1> You collide with two of mine.
Region2> And two of mine two!
NPC> Okay, time to check if I collide with any objects in those four regions!

"Wait, wait, wait," you might sputter "stop the science train Doctor Scientopolis, what about items bigger than one subregion. What if I have castle that took up half the map?"

Well, Jimmy, the castle would exist at the very bottom of the quadtree - but crucially it would exist in more than one subsubregion. You could write special code, not to attempt an intersect with an object more than once, if efficency is worrying you.

Region1
SubRegion1
-Castle
SubRegion2
-Castle
SubRegion3
-Castle
SubRegion4
-Castle
etc.

So what we saved, let's say you have your quadtree four layers deep (how deep depends on the dimensions of your map and number of your items), then in the minimum case you'll compare each moving object 4, times once per each region. That's a lot better than the 500 we had at the start.

-What about items that span many regions - well they're still added at the lowest subregion - they may be in more than one subregion pool.

In my game I think I want circles, rectangles, points and polygons. It's a nice finite list. I will have an object called intersectCheck which will handle intersect checks between these objects.