So i guess what I'm asking is
What is the best way to set up the node array(s)? (nested , associative, using objects, etc)
What i would suggest is that when you classify the hotspots, you only create the
nodes that you need.
For the data structure each node can have 4 children, so a simple array will do
containing references to its 4 child nodes, or even just 4 member variables if
you dont want to loop :)
So when constructing the tree you can just create the nodes that actually
contain hotspots..
e.g. (in the node class)
function classify(hotspot)
{
// flag to indicate if the hotspot is entirely contained
// within a leaf node
var containedInLeafNode:Boolean = false;
for(var n=0;n<4;n++)
{
// test bounds of child[n] to see if it can hold the hotspot
if(isInQuadrant(n,hotspot))
{
// Make a new node if we dont already have it.
if(childNodes[n] == undefined)
{
childNodes[n] = new Node();
}
childNodes[n].classify(hotspot);
containedInLeafNode = true;
}
}
// If none of the leaf nodes 'took ownership' of the hotspot
// then hold onto it here.
if(!containedInLeafNode)
{
candidates.push(hotspot);
}
}
So this will recurse down the tree, making sure that any item is contained
within the smallest possible leaf node. Of course you'll want to put a limit on
how small a node can get. How small that is depends on the sizes of the items
you want to classify, if i remember correctly (which i wouldnt assume i do) then
the best target size is somewhere just around the size of the smallest object
you are trying to classify, unless you are classifying lots of very small
objects relative to screen size then you can just cap it somewhere like 4 or 5
levels deep.
Then when you come to query the tree for nodes that contain items that may be
within distance of your draggable object you only need to bother with the nodes
that exist
for speed you could even not bother with a loop and also take advantage of the
fact that calling a function on something that doesnt exist wont generate an error :
so instead of
for(i=0;i<4;i++)
{
if(childNodes[n] != undefined)
{
// check childNodes[n] for candidates
}
}
you just do
candidateList.concat(childNodes[0].getThingsThatAreClose(draggableObject))
candidateList.concat(childNodes[1].getThingsThatAreClose(draggableObject))
etc..
anyway, im just typing it out as it comes into my head..some of it from hazy
memories of implementations past. :)
Theres no real canonical way of working with quadtrees, the beauty is that you
can adapt them according to your particular requirements.
Id be interested to hear other peoples opinions and experiences or just 'why
bother, you can do 'x' because its easier and quicker'
thanks,
Martin
_______________________________________________
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
