LavishNav:Best Container
Overview
The best container algorithm is meant to track changes in location within a coordinate system, not to search through all regions to find the smallest-sized region that contains a given point.
In a nutshell, given a previously known containing region, this algorithm will help find the region that best contains the current location. This can be a child of the current region, an ancestor region, or a descendant of any ancestor region, within the current coordinate system.
The Algorithm
The best container algorithm finds a region that contains a given location. This algorithm starts at a given region, ideally a region that is already known to contain the given point. It first checks the region to ensure that the location is contained. If the location is not contained, the algorithm backs up the tree until it finds a region that does contain the location (it will not cross coordinate system boundaries, forward or backward). The algorithm then checks to see if a child region contains it. If a child region is found to contain the location, the algorithm continues in the same fashion with that child -- it checks to see if one of its children contains the location.
The first region found to contain the location, with no children that also contain the location, will be retrieved as the best container by the algorithm. This means that even though multiple children may contain the location, the first one checked will be retrieved -- remember that the tree is a containment tree, and only one child of any given region should contain a given location. In other words, if multiple universes are defined as a child of a region, and the search begins at the region that contains those universes, the first universe (or one of its children) will always be retrieved, because it contains the location.
Suggested Use
This algorithm can be used to track the progress of a player through a world. Each frame, the best container can be efficiently updated by performing the algorithm starting with the best container from the previous frame. This can begin with finding the best container starting with the region that defines the coordinate system the player is present in.
Maximizing Efficiency
The efficiency of this algorithm is increased by favoring region tree depth, as opposed to having many children of the same region. This is because for every region checked by the algorithm, you can expect to loop through every one of its children to find one that contains a given location (or to find that none of the potentially hundreds of children contains it). Instead of having 1,000 regions as the children of a single parent region, consider dividing those into smaller sections within the parent. For example, a rect could be divided into halves, which would make the algorithm twice as efficient for that region (because it will only go through half of them!). If those two halves were then divided themselves into halves, the algorithm would also be twice as efficient for those two regions, ad infinitum -- reaching toward the efficiency of a binary search tree (very fast). It is not entirely practical to always use halves, but you should have the idea that the fewer the children of a single region (divide them into sub-regions!), the better.
