Quadtree

[Joshdan]

I've noticed in the logs a bit of a game of "telephone" going on with something I said about the effectiveness of the current quadtree a while back, and I was a bit confused in my description in the first place.  Luckily, Sleek has shone a brilliant light into the discussion with an excellent demo application.

Basically, I was expecting something like this:

   http://donar.umiacs.umd.edu/quadtree/points/prbuckquad.html

But phoku's implementation was more like this:

   http://donar.umiacs.umd.edu/quadtree/rectangles/cifquad.html

Note the way that in the first one, it takes at least a few dozen points before you get down to the smallest size box, while in the second, a single small rectangle will cause this.  There are advantages and disadvantages to each approach, but since I was expecting the first, and only coming to grips with the second glimpse by glimpse, I was a bit baffled.

I do think we have a bit of a solution looking for a problem with the current quadtree approach.  That is we took a quadtree optimized for one particular use, and then tried to figure out how to build our needs around it.  Rather than go further down that path, I think it would be best to determine what we want to use the quadtree for, then build the quadtree (or quadtrees, or some other data structure) up around that.

Here are some general areas that seem like likely candidates.  If someone knowledgable about these areas can comment on how they would like to utilize a quadtree (or other instance-locator), please do.  That is very specifically what data you would expect want to pass in (e.g. top left and bottom right points in floating point model-layer-substrate coordinates), and what data you would want to get out (circular doubly linked list containing all rectangles intersecting the box described).  Also, if you know of other areas that could potentially benefit from this sort of optimization, please add them.  I'll try to fill in any gaps.

Rendering -- we only want to process and draw stuff that will actually show up.  We don't want to have to check each object individually to know if it will show up or not.

User Instance Picking -- The user clicks (or just points) somewhere on the screen; the game needs to know what is there.

Pathfinding -- As the pathfinder looks around the map, it wants some way to tell if there is anything locally to avoid.

Radius effects --  A grenade goes off, or a poison cloud spreads through the air ducts.  The damage dealing code needs to look for instances near them to damage without having to check every single instance to see if it is close.  NPC/critter visibility would probably also fall into this category.

[phoku]

While the applets don't really seem to work here,
I think you came to (one of) the source(s) of misunderstanding :-)
=> Quadtrees come in different flavours.

I'll repeat the use case for the current quadtree again.

It was used for on-screen coordinates (though on a virtual screen, thus a viewport is a moving rectangle over this space).
For rendering - since the actual image sizes can be arbitrary (in case of objects as opposed to tiles), one would normally
iterate over all objects and check the object.boundingbox.intersects( viewport ) results. This can/and was avoided by the
current quadtree.

Instance/Object picking was also done in the same way, as it is simply intersection with the hotspot area of the mouse.

Note that this is different also from a performance/mem-usage perspective, as the minimum size would naturally chosen
larger than the expected image sizes (e.g. 128px).

The current way to pick by layer coordinates seems like a bit of a abuse =).

Besides the getInstanceList function is still buggy.

Another note on that - while it was nice to know that the for-all-instances loop never would cause
any problems, the exhibited performance advantages with FO2 maps were nothing to write home
about.

-phoku

[Sleek]

We should consider if LORM is implemented in the engine as well. LORM will cause larger images to be kept in nodes higher in the hierarchy. If we split them up, the images will be stored in lower level nodes.

LORM == Large Object Rendering Method ( right jwt ? )