Updated Quad Tree

Ever since I made the first version of my QuadTree I always thought the algorithm could be implemented much better. And now that I had a little free time on my hands I decided to rewrite a good portion of it.

First off, the problems with the old version:

• There was never any base case for the recursive algorithm, I always counted on the calling function to ensure that the destructions happened for even numbers (the smallest size node is 2x2). However this did not work as well as it should have, I would constantly end up with nodes that weren't square or had odd number sizes. Along with that I was constrained to canvas sizes that were powers of 2.
• I made sure that every time a destruction was called that the boundaries for the destruction would fit inside the node it was called on. This was probably my biggest slowdown because each time the function recursed it would make new Coordinate instances for the smaller nodes.
• Because of some concern of overlapping nodes I had when first making the QuadTree I originally offset each node from the other ones. I realized that with the way canvas displays rectangles this was unnecessary and that for future collision algorithms this would also not be as big a problem as I initially anticipated.

To fix the issue with recursion I set a simple check to make sure that if the node was the minimum size it wouldn't be allowed to create children. I also decided that if a minimum node received a destruction on the inside it would simply be destroyed.

if((end.x - start.x) > Environment.minPixel && 
   (end.y - start.y) > Environment.minPixel)
{
 type = changeType;
}

To fix the issues with the boundaries I completely rewrote the main recursive function. Instead of a mass of switch statements to decide which nodes would be affected I came up with a new way to see if the node would be affected.

Here is a crude sketch of how it works. To see if the node is going to be affected by the destruction (which is defined by it's upper left and bottom right corners) all I have to do is see if the upper left of the destruction is in the red area, while the bottom right of the destruction is in the blue area.

/*
modify is the main recursive function that either deletes or creates dirt for the level
*/
//check for topLeft
if((start.x < br.x && start.y < br.y) && 
   (divider.x > tl.x && divider.y > tl.y))
{
 topLeft.modify(tl, br, changeType);
}
//check for topRight
if((divider.x < br.x && start.y < br.y) && 
   (end.x > tl.x && divider.y > tl.y))
{
 topRight.modify(tl, br, changeType);
}
//check for bottomRight
if((divider.x < br.x && divider.y < br.y) && 
   (end.x > tl.x && end.y > tl.y))
{
 bottomRight.modify(tl, br, changeType);
}
//check for bottomLeft
if((start.x < br.x && divider.y < br.y) && 
   (divider.x > tl.x && end.y > tl.y))
{
 bottomLeft.modify(tl, br, changeType);
}

The results from the firebug profiling. $modify starts the algorithm so gives the most relevant time.

The changes ended up giving me some pretty good speed improvements as you can see from the firebug profile. One issue though is that I initially used functions for much of the code, but it turns out that if I inlined the functions the code would run in half the time. Unfortunately inlining is not an option (that I could find) in GWT, it is usually done at run time by the JVM but this functionality doesn't carry over to the generated JavaScript.

Here is a link to the newest version (it looks exactly the same, but trust me it's 2ms faster and works way better).

*Edit: It turns out that if you use the optimize flag the GWT compiler does inline functions, however I still got better speeds inlining it myself. The new average runtime for the $modify function ended up being 2.91ms.