Destructible Environment - Quad Tree

    A few weeks ago while playing the game liero I decided I wanted to try recreating it in HTML 5 Canvas. Liero is a simple shooting game where two worms battle it out in a destructible 2D dirt environment. As I have been using GWT (an amazingly useful tool for writing web apps in Java) a lot lately for work I decided to use it to write the game.
    The first thing I decided to tackle was the destructible dirt environment. My initial misguided plan was to simply keep track of every pixel, but at 600x400px this would have given me 240,000 individual pixels to track and draw to the screen. This proved to be much to slow to ever play a game with, let alone even render a single scene.
    The next idea I came up with was using a tree structure to keep track of the dirt. Each node  of the tree would either be set to draw to the canvas or null. The nodes would all have 4 children: topLeft, topRight, bottomRight, bottomLeft, this structure would recursively define the entire play area. I later discovered this data structure was called a Quadtree. What initially drew me to the Quadtree data structure was how much less information would have to be handled. If an entire area was destroyed by an explosion, then the game could simply stop tracking the pixels (or nodes rather) in this area. Also later on when I would need to implement collisions, it would be very easy to recursively narrow down my search area.

Quadtree First Version

    Unfortunately the first version of the Quadtree I wrote performed terribly. I was getting far too many nodes (many of which were undoubtedly 0 pixels in size) and after a few collisions the fps of the game would plummet to zero. Also I wasn't dividing the nodes evenly. Say if a destruction happened at (100,100), the top level node would split at (100,100) whereas the center was (256,256). This theoretically would give better performance for the first few destructions but after a while it would only slow the game down. The game also redrew every single node for every frame and with up to 13,000 nodes this proved to be impossible with canvas.

Quadtree Final Version

    After some help from some of my programmer friends I finally realized that much of the problem with the Quadtree wasn't the data structure itself but rather drawing the data to the canvas. At this point I pretty much rewrote the entire game so that instead of drawing everything for each frame, the environment would only redraw when it changed or when the draw function was called for a specific region. This ended up working out much better as you can see here. I also modified the nodes so that each child node was exactly half of the parent node, instead of some arbitrary value.

This is the current version. The borders denote the different nodes

    To handle the actual destructions I assumed that each destruction was completely contained within the node that received it (enforced by some if/else statements in the initial call)

/*this function keeps all the destructions in the viewable area
Coordinate in just a simple class that keeps track of the x and y
it also has some simple functions built in such as which quadrant
the coordinate is in when compared to another coordinate*/
private void constrain(Coordinate test)
{
 if(test.x < (topLeft.x + minPixel))
 {
  test.x = topLeft.x;
 }
 else if(test.x > bottomRight.x)
 {
  test.x = bottomRight.x;
 }
 if(test.y < (topLeft.y + minPixel))
 {
  test.y = topLeft.y;
 }
 else if(test.y > bottomRight.y)
 {
  test.y = bottomRight.y;
 }
}

and each node would simply split into 4 until the destruction completely encompassed the node at which point the node type would be changed from dirt to empty.

/*each node knows its own type which keeps track of whether
it is dirt, empty, or has sub-nodes*/

/*divider is calculated when the object is created by finding
the middle pixels*/
if(type != type_parent)
{
 //topLeft, topRight, etc. are all the sub-nodes of the node
 topLeft = new EnvironmentNode(
  environment,
  start.copy(),
  divider.copy(),
  type);
 topRight = new EnvironmentNode(
  environment,
  new Coordinate(divider.x + 1, start.y),
  new Coordinate(end.x, divider.y),
  type);
 bottomRight = new EnvironmentNode(
  environment,
  new Coordinate(divider.x + 1, divider.y + 1),
  end.copy(),
  type);
 bottomLeft = new EnvironmentNode(
  environment,
  new Coordinate(start.x, divider.y + 1),
  new Coordinate(divider.x, end.y),
  type);
 type = type_parent;
}

    One issue I ran into was that multiple nodes could keep track of the same pixels if I wasn't careful, that's why there are offsets from the divider for specific nodes.
    After splitting the node into sub-nodes the program goes through a switch statement to decide which nodes the destruction should be passed to. And finally at the end of the function I have a case to reduce nodes if all the children are of the same type.

if(type == type_parent 
 && topLeft.type != type_parent 
 && topLeft.type == topRight.type 
 && topLeft.type == bottomRight.type 
 && topLeft.type == bottomLeft.type)
{
 type = topLeft.type;
 topLeft = null;
 topRight = null;
 bottomLeft = null;
 bottomRight = null;
}

    To make the destructions circular I simply call multiple rectangular destructions on the environment which, although admittedly inefficient, is not actually noticeable when running the game. I am sure there is a much more clever way to go about this but I couldn't come up with it.

//minPixel is 2 which was easier to work with than using 1 as the mini
for(int i = minPixel; i < radius; i += minPixel)
{
 tempX = i - radius;
 tempY = (int) Math.sqrt((radius * radius) - (tempX * tempX));
 tempY = (tempY / minPixel) * minPixel;
 tempTL.x = center.x + tempX + 1;
 tempTL.y = center.y - tempY + 1;
 tempBR.x = center.x - tempX;
 tempBR.y = center.y + tempY;
 constrain(tempTL);
 constrain(tempBR);
 //calls the modify command on the root node
 //TempTL is the top left of the destruction rectangle
 //tempBR is the bottom right
 root.modify(tempTL, tempBR, changeType);
}

tl;dr here is a link to a destructible 2d environment I made in canvas