Getting old

With my birthday a few days ago and other things coming up to steal whatever spare time I had, there was simply no time to get to the optimisation and cleaning up of BGLayers. As middle aged programmers are treated the same way as the elderly I wonder if I have the right to blame my age for not finishing part 9? To be honest, I don't understand the trend to hire younger programmers. While they may be more willing to put in overtime, their lack of experience means that things that would take me a few hours to write will take them a few weeks. Still, I hope to have the next part ready for next week, and since Tarot is using this code and is being released next month I have extra incentive to find the time to get the work done.

Animating the Canvas part 8: Splitting Image

Right now the library is good at drawing solid blocks. To be useful, however, better image support is needed. The one class that would make this library sufficient for the creation of games, which is the goal of this after all, would be an image layer that had support for image strips and image grids. Better yet, an image atlas since image strips and image grids are a subset of an image atlas. This is actually very simple to do.

An image atlas, for those who are not familiar with the term, is simply just a large image that contains smaller images. The idea here is that instead of dealing with a large number of image files, you instead only need to load one image and show portions of that image. This speeds up loading as you only need to request a single file instead of having to request multiple files from the server. It is also commonly used with 3D rendering but that is beyond the scope of this series.

What makes this class so easy to create is simply the fact that it inherits most of its functionality from the Layer class. JavaScript does not currently have support for subclasses so I make use of the inheritProperties function that was created earlier. As it is likely that the image layer will be used to display an entire image, the constructor simply contains the image to use. The portion of the image used is set to the entire image, though this can be changed any time allowing this class to be used as an image atlas.

BGLayers.ImageLayer = function(id, image)
{
    this.supr = new BGLayers.Layer(id, image.width, image.height);
    BGLayers.inheritProperties(this, this.supr);
   
    this.clip = new BGLayers.Rectangle(0,0, image.width, image.height);
    this.image = image;
}

To set the particular portion of the image that should be displayed, the setClip function sets the new portion of the image to be shown. This can be used for animation by simply having a strip or grid of frames and altering the portion being shown every frame.

BGLayers.ImageLayer.prototype.setClip = function(rect)
{
    this.clip.x = rect.x;
    this.clip.y = rect.y;
    this.clip.width = rect.width;
    this.clip.height = rect.height;
    this.addDirty(null);
}

The hard part comes with the drawing as the portion of the image within the clipping bounds. This has to be calculated. This is done in a similar way to the calculation of the real layer position but using the clipping portion of the image. In theory it is possible to just set the canvas clipping region and draw the whole image, but I have had some issues with clipping so figure it is safest to avoid clipping whenever possible. Besides, relying on clipping makes the assumption that the canvas implementation is actually efficiently written where as manually drawing just the clip guarantees that the minimum amount of drawing is being done.

BGLayers.ImageLayer.prototype.drawSelf = function(ctx, bounds)
{
    if (this.findRealPosition().intersects(bounds) == false)
        return;
    var rect = this.realPosition.getIntersection(bounds);
    var scaleX = this.clip.width / this.realPosition.width;
    var scaleY = this.clip.height / this.realPosition.height;
    var boundClip = new BGLayers.Rectangle(
                this.clip.x + (rect.x - this.realPosition.x) * scaleX,
                this.clip.y + (rect.y - this.realPosition.y) * scaleY,
                rect.width * scaleX,
                rect.height * scaleY);
    ctx.drawImage(this.image, boundClip.x, boundClip.y, boundClip.width, boundClip.height,
                rect.x, rect.y, rect.width, rect.height);
}

And that is all that is needed. Creating a new layer is that simple. The atlas functionality of this class should be adequate for most uses so already this library is useful. Still, while doing some debugging on my Tarot project, stepping through the drawing of things did help me notice a lot of inefficiencies in how the library works so I am planning on having an optimization pass. I also want to do a bit of fine tuning to the library to make it clearer what variables are private, even though JavaScript does not support private variables. I may be renaming some things and adding some functionality so there is no need to access private variables. If something is clearly private and somebody modifies it anyway breaking their program it is their problem.

Animating the Canvas part 7: Dirty Knives

I forgot to mention last week that the source code for parts 6 though 8 is located at http://www.blazinggames.com/other/openLibrary/html5Libs. It is time to start dealing with overlap. This will all be handled by the addDirty function which adds a dirty rectangle to the list of dirty rectangles. As before, this function adds dirty rectangles to the root layer. This time, however, an additional three steps have been added to this process.

The first step is simply to go through the existing list and make sure that the rectangle to be added isn't already in the list. By in the list, we are checking to see if there is a rectangle in the dirty rectangle list that covers the rectangle being added. If there is, our work is done and we can return from the function. This code is simply a traversal of the dirty rectangle list with a call to a rectangle function called containsRect.

ContainsRect is a simple function that simply checks to see if a passed rectangle is contained within the rectangle. This is simply done by seeing if the top left corner is in the bounds of the rectangle. If it is then a check is made to see if the bottom right corner is in the rectangle. If it is, then the rectangle is contained.

If the first step does not eliminate the dirty rectangle, then a second pass through the dirty rectangle list is made. This time, we are seeing if the new dirty rectangle covers some of the rectangles in the list. If it does, those rectangles can be removed from the list. This is why having the ability to remove nodes from the dirty rectangle list is important.

The third part is a really large chunk of code which is a bit too big to dump here so if my explanation is not good enough please review the code. This pass is where we make sure that the dirty rectangle doesn't overlap other rectangles in the list of dirty rectangles. If there is an overlap, the rectangle gets split. The check to find an overlap is simply a traversal of the dirty rectangle list with the traversal being stopped if an overlap is detected.

        var overlap = null;
        nextDirty = this.dirtyList.nxt;
        while (nextDirty != null) {
            var bounds = nextDirty.rect;
            if (dirty.rect.intersects(bounds)) {
                overlap = bounds;
                nextDirty = null;
            } else
                nextDirty = nextDirty.nxt;
        }

If there is an overlap, the goal then becomes to divide the dirty rectangle. First, we see if there is overlap on the left side. If there is, we create a new rectangle that contains the left portion of the dirty rectangle up to the start of the overlap. This rectangle gets sent to the addDirty function so that it gets processed as there may be other overlaps that cause it to be split up further.

The dirty rectangle is then resized to have the dimensions without the sliced portion. At this point we check to see if there is a right overlap. If there is the rectangle is again sliced and addDirty is called for processing the right portion of the rectangle.

The same procedure is done for the top and bottom portions of the rectangle. However, with the bottom portion we do not need to adjust the size of the dirty rectangle because it will be contained by the overlap and can be discarded.

We now have the functioning dirty rectangle system I originally planned. Next week I will actually implement a custom image layer class. After that, I will either conclude this series and start work on a game or will optimise the code. I will decide next week.

Animating the Canvas part 6: Linking Dirty Rectangles

While the code we have created so far is usable, the big problem with it is that there is a lot of redrawing as dirty rectangles may overlap each other. If you are dealing with only a small number of objects then this may not be a big deal. Still, my original plan was to subdivide dirty rectangles to eliminate overlap. As I started preparing to write the code to deal with this it became clear that arrays were not the ideal mechanism for dealing with this problem. Instead, I needed a linked list. My JavaScript reference has no mention of any type of linked list class in the standard library so I am going to create my own simple doubly linked list class. This is dirty-rectangle specific class right now though I see no reason why this couldn't be modified and extended to create a general purpose class if such a thing was desired.

Linked lists are a useful concept. They simply are a list of objects with each object in the list pointing to the next object in the list. The advantage this offers is that there is no size limits, it is easy to transverse from start to end, and objects can be easily inserted in the middle of the list. Removing an item from the list isn't difficult but does require knowledge of the previous item. Arrays contain splice and slice functions to do this, but these are problematic and probably extremely inefficient. I say probably because it would depend on how the arrays were implemented.

A linked list would probably suffice for my needs, but as one of the key things I need to do is remove objects from the middle of the list, a doubly linked list would be much more convenient. This is the same as a linked list but instead of just pointing to the next object in the list, they also point to the previous object. This means that no knowledge of other items in the list are needed to remove an item.

The creation of an element in the linked list is simple enough. It is, after all, just references to three objects. In the case of our dirty rectangle class, this is the rectangle that is dirty, the previous node and the next node. The nodes are set to null initially with null being used to determine the beginning and end of the list.

BGLayers.DirtyRect = function(rect)
{
    this.rect = new BGLayers.Rectangle(rect);
    this.prev = null;
    this.nxt = null;
}

Having a node is fine but by itself it is not that useful. To be useful, the node has to be added to a list. Adding to a list only requires a node to the list in which the item is being added to. A node can only belong to one list at a time so it will remove itself from any existing list. The node from the list that this node is being added to will be considered the previous element in the list. As the previous item in the list may already have a next item, the first step then is to take the previous node next element and make it the added nodes next element. The node being added to the list then becomes the next node for the previous node. Likewise, the previous node is the added nodes previous entry. At this point everything is correct with this node, but the next node is not pointing to the added node so if the next node is not null, its previous entry will have to be changed to the added node.

BGLayers.DirtyRect.prototype.addSelf = function(parent)
{
    if ( (this.prev != null) || (this.nxt != null) )
        this.removeSelf();
    this.prev = parent;
    this.nxt = parent.nxt;
    if (this.nxt != null)
        this.nxt.prev = this;
    parent.nxt = this;
}

Removing a node is actually very easy. If the previous node is not null, it's next node becomes the removed nodes next entry. Likewise, if the next node is not null then it's previous entry becomes the removed nodes previous entry. Finally, the previous and next entries for the removed node are set to null so that it is clear that this node is not part of a list.

BGLayers.DirtyRect.prototype.removeSelf = function()
{
    if (this.prev != null) {
        this.prev.nxt = this.nxt;
    }
    if (this.nxt != null)
        this.nxt.prev = this.prev;
    this.prev = null;
    this.nxt = null;   
}

Some implementations of linked lists will have a separate class for manipulating nodes which also controls the root node. If you were going to expand on my linked list code this would be a good idea. For BGLayers, I am simply creating a root node which is not an active part of the list. This is not the best solution but it is very easy to do and doesn't require more classes be written. I might do this for a future version of this library as I am starting to think it is the proper thing to do.

Traversing the list is very simple. My implementation of renderDirty is a good demonstration of doing this. It simply grabs the first real node from the root node and then uses a while loop to continue through the list while the next element is not null. If the list is empty, the root nodes next will be null causing the while loop to exit  immediately. Of course, the loop processes the dirty rectangles by calling render, and then removes the node from the list so the list will be empty at the end of this function.

BGLayers.Layer.prototype.renderDirty = function(ctx)
{
    var nextDirty = this.dirtyList.nxt;
    while (nextDirty != null) {
        var bounds = nextDirty.rect;
        this.render(ctx, bounds);
        var curDirty = nextDirty;
        nextDirty = curDirty.nxt;
        curDirty.removeSelf();
    }
}

Now that we have the dirty rectangle doubly linked list class functioning, next time we will get to the fun part of splitting rectangles.