Difference between revisions of "LavishNav:Best Container"
| Line 4: | Line 4: | ||
== Suggested Use == | == 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. | 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. | ||
== See Also == | == See Also == | ||
* [[LavishNav]] | * [[LavishNav]] | ||
[[Category:LavishNav]] | [[Category:LavishNav]] | ||
Revision as of 18:51, 19 March 2006
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.
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.
