Thread: Collision boxes,zones, and allocation

I have come to the conclusion that dividing a large map into zones is probably the best way to handle having many updates all the time for things that would be trivial to players. So my thought is to use bounding boxes to limit player's movements throughout the world.

I have come to the point where I am wondering how to make a bounding box divide itself into multiple sub boxes if one is placed over a zone seam...

example: lets say zones are 10 by 10 units big and we want a 10 by 10 unit box starting on zone0 5,5 and extending to zone4 5,5 making it a 10 by 10 bounding box. Now each zone would need it's own 5x5 box to use for updates in that specific zone. What routine would I use to split that box into sub boxes?

something like this maybe?:

Code:

if(box_x + box_w > zone_max)//push into next zone dec box_w by zone_max - box_x

Something like this?

Code:

zones = set of zones this box intersects

if (size of 'zones' == 1)
    exit //don't have to split this box
else
    for each 'z' in 'zones':
        create a box that covers the intersection of this box and 'z'

    delete this box //the boxes we made cover the same area
end

So then it remains to get this set of zones (which can be done with some simple rectangle intersection tests) and to be able to find the intersection of two rectangles:

Code:

box intersect; //will contain a intersect b
intersect.xmin = max(a.xmin, b.xmin);
intersect.ymin = max(a.ymin, b.ymin);
intersect.xmax = min(a.xmax, b.xmax);
intersect.ymax = min(a.ymax, b.ymax);

You could probably combine these two steps, finding the set and finding the intersections (eg, find the "intersection" and create a box only if it is a valid area: width and height > 0).