LavishNav:Best Container
Overview
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). 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.
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.
