Sunday, August 29, 2010

Animating the Canvas Part 2: Layers of Dirty Rectangles

Today I am going to look at layers and dirty rectangles. These techniques work really well together, though it is certainly possible to use layers without using dirty rectangles. Next week I will start implementing the animation system by getting some of the primitives out of the way and we will continue the implementation in the weeks following that.

Layers, when used in an animation system, can be thought of as cells as used by traditional film-based animation. Cell animation was developed as a way of drastically reducing the workload required to produce an animated sequence. The best way of explaining how, is to start with an example. Lets say we wanted a simple animated sequence consisting of two cars driving past each other on a street. If you had to draw each frame fully, then you would have to draw the background street, as well as both cars for every frame. If the background is not changing, then this is obviously a bit of a waste. In Cell animation, each element of the animation is drawn on it's own transparent sheet of celluloid and each of these sheets are then combined to form the frame which is then photographed.  Because the background doesn't change, it would only need to be drawn one time. If the celluloid sheets that the cars are on are large enough, even the number of car images can be reduced as the only thing changing are the tires.

Layers work the same way as cells. Each layer that makes up the frame is it's own separate image. The frame is created by simply drawing the layers from the background layer up. This is essentially the same thing as the painter's algorithm with the exception that the layers can change over time. Where this technique can become extremely powerful is when you add the concept of having layers being able to have their own sub-layers and sub-layers being able to have sub-sub-layers and so on. In our previous example, each car could have two layers with the tires being separate from the body of the car.

Looking at the above layering system for animating, we can see that layers do not help with the primary problem that was discussed in part 1. The layer system above would essentially require that we redraw the entire image for every frame. This is where dirty rectangles come into play.

What is this magical dirty rectangle? It is simply a rectangular section of the frame that has been marked as being dirty. In other words, it is a rectangle indicating a part of the frame that has changed and needs to be redrawn.  This very simple concept can save a vast amount of redrawing as the only thing that you need to draw each frame is the contents that make up the dirty rectangle(s).

There are a number of ways of implementing dirty rectangles. The easiest is to have a single dirty rectangle which scales itself to fit the entire dirty area of the image. This is very simple to implement but unless the changes to a display are constrained may result in having to redraw large chunks of the image. The approach I will be using will be a list of rectangles with subdivisions to remove any overlapping areas. This means that when something changes on the screen, that area gets marked as dirty. This gets added to the list of dirty rectangles. An object moving results in two dirty rectangles. One for the area where the object use to be and one for where the object is now.  When the display refreshes itself, each of these multiple small regions get redrawn. To prevent redrawing the same portion of the screen multiple times, dirty rectangles that overlap other dirty rectangles will be broken into smaller rectangles so that each dirty rectangle in the list covers a unique portion of the display reducing overdrawing.

That is all there is to it, at least concept wise. Implementing this system may be more complicated then the above makes it sound but then that is why programming is so much fun.

Sunday, August 22, 2010

Animating the Canvas Part 1: The Immediate Problem

This blog has strayed quite a bit from what I wanted when I started writing it. I want to look at game development from both the design and programming view as products are created. This article, which will be divided into an unknown number of parts due to the huge size of the topic, will get me back on track. Here I will look at the development of an HTML 5 Canvas animation system as I develop it. I will be trying to cover my train of thought as the animation system is developed to explain the choices made and why different choices might be beneficial for different projects.

One of the things that HTML 5 brings with it to the mix is the Canvas. This lets you draw things, which makes creating games that don't require a plug-in such as Flash or Silverlight much more possible. At this point in time, HTML 5 and the canvas are draft standards. This means that they are subject to change but since a lot of browsers already implement the canvas, this change would probably not be that drastic. The one thing that I am hoping will change is better support for off-canvas drawing so techniques such as double or triple buffering can be better utilised.

The canvas is what is known as an immediate mode drawing surface. This means that, in theory at least, when you draw something on the canvas it appears immediately. In reality, there are things like frame-rates and implementation issues that can alter this behaviour. Still, when working with the canvas you should always assume that your drawing happens immediately. This leads to a really big problem for animation. Animation works by drawing something in one position, then erasing it, then drawing it again in a new position.  The problem is that the erasing and re-drawing of the object can result in flickering.

The traditional way that I have solved this problem is to do the drawing in an off-screen buffer then replace the current canvas image with what is drawn in the buffer. This might be possible to do by using multiple canvases and hiding one canvas, but it is a trick which may result in all sorts of other issues. The ImageData support that the canvas does currently have can be a partial solution to the problem, but the only drawing support the ImageData objects have are direct pixel manipulation. For some games, especially tile-based games, this can be all that is needed. Other games, such as the Dozen Days series of games that is inspiring this series, require a bit more flexibility than that.

If you can't draw off-screen, then the only other real solution to this problem is to try to reduce the flicker as much as possible. The best way of reducing flicker is to only update the parts of the screen that are changing and to do so in such a way that the updated region is as completely drawn as possible. An older method, known as dirty rectangle animation, is probably the best way of dealing with this. As dirty rectangles happen to work really well with layers, this will be the approach that I will be taking.

In the next part of this series, I will be taking a look at what layers and dirty rectangles are and hopefully start coding some of the primitive classes that will be needed.

Sunday, August 15, 2010

Thirteen Spikes Unlimited 1.0

Thirteen Spikes Unlimited is now finished and has been on the Blazing Games site since Friday the 13th. As I have mentioned before, there was some plans to port the game over to HTML 5. ActionScript and JavaScript are very close as they are both variations of ECMAScript. This makes the game logic very quick to port, even if JavaScript does not have as nice of class or variable support as ActionScript. The other thing that ActionScript has that JavaScript lacks is the Flash library. Because Flash was created as a streaming vector animation system, this library is greatly tied to graphics and animation. The HTML 5 Canvas simply does not have these classes, but there would be very little stopping someone from writing them. In fact, to implement Thirteen Spikes Unlimited, only a small subset of the class library would be needed.

This would require a bit more time than I have, so the port to HTML 5 didn't happen and instead themes, campaigns, and sound were added to finish off the 1.0 version. This does not mean that the next Friday the 13th won't have a HTML 5 version of this game. That would be May of 2011, so depending what is happening with my current projects (one which may be doomed) this might be an interesting project. So, while Thirteen Spikes is finished for now, it may resurface in the future.

Sunday, August 8, 2010

Hurry up and Stop

One of the most frustrating things about doing third party work is that often you are in a hurry up and stop situation. Clients seem to always be in a rush to get things done. This is to be expected. What confuses me is the same client who is rushing you to get on things seems to continually do things that slow down progress. I am not sure why this is the case, but it probably largely is the result of people still having no clue what programmers actually do and how software development works. Considering how important computers and computing devices such as iPhones and Android phones have become, this really is inexcusable. Here are some of the pet peeves that I have had in the past.

When material is needed before programming can begin, then not getting that material to the programmer is going to delay the project. This is especially true if the required thing is legal documents. Programmers are probably more anxious to start work then you are, but I don't start work until all the legal matters are (or appear to be) settled. Assets that the project depends on are almost as vital. While it is certainly possible to work around missing images or databases, this generally requires more work on the programmers part. First, temp artwork or data has to be created. Second, when the real materials come in, the real assets then have to be integrated and far too often this requires changes to the code due to the fact that often clients don't follow the specs that were sent to them.

Real programming is very mentally taxing. Sure, there are a lot of "programmers" who just assemble other peoples code together, but if you are actually creating code it requires a lot of thought. Having someone wanting to phone you or message you every half-hour is a sure way to kill productivity. When a programmer is in the middle of coding or debugging, any interruption breaks their train of though. This train of thought takes time to recover, so you are costing the project at least 5 or 10 minutes, possibly more, every interruption.

Changes are to be expected, but when a build is sent to you to evaluate, have the courtesy to actually look at the build asap. Waiting months to tell the programmer about a problem is beyond stupid. The longer a bug is in your code, the harder it is to find. Likewise, if you are not actively working on code, it takes longer to get back in the mindset you were in when you wrote that code. And worst of all, adding features to a project when the deadline isn't increased is just asking for a project to enter doomed status.

I could go on, but I think that I've stood on the soap box long enough.