Printable View
no, you misunderstand! The first search just finds what parts of the world the mouse lies in (it can lie in an arbitrary number, but practically in 2D the most is 4). Then, for every single part of the world the mouse is in, search the pertinent entities to see if the mouse bounding box overlaps the entity bounding box. You must search every one because typically your mouse can overlap more than one unit (if it is enclosed in a box), in that case you want the closest.
Wouldnt something like this work too:
If you always keep track of what units are visible why not store pointers to those units in a list and only search through that list? That would probably reduce the amount of units to search through quite much unless you have like 100-200 units visible at the same time.
Keep in mind that is exactly what we have been saying the whole time...the only way you can find those visible objects is by recursively searching the quadtree
There is no need to find where the mouse is. The mouse is the origin of the system. We test everything against the mouse. It is much easier to test like this instead of first finding the mouse in the tree and then finding the units as well.
We test all bounding boxes of the objects against the bounding box of the mouse. Besides if you search the entire list on the first recursion and then logarithmically reduce the number of units to search....the time involved is still nothing compared to the O(n^2) linear search.
Hm so you would have a world object with several different regions and when you move a unit you (possibly) place it into a different region? Or something along that line...Could someone post a basic class design to show how it would be set up?Quote:
typically a section of the world would contain a list of pointers to the entities that are within that particular section. Whenever an object is moved, it undergoes a process called "relinking", where you calculate what parts of the world each object's bounding box lies in, and removing itself from the previous parts of the world it no longer resides in. You do not have to recurse the entire world when you do this.
Download quake2 source
www.idsoftware.com
open project, search (in all files) 'relink' or 'linkedict'