It is no secret that the canvas element in HTML(5) is a little bit slow. This makes game development quite a task as games generally need to draw things at least 60 times a second. The naive method of clearing the entire screen and redrawing every object is nowhere near a solution once more and more objects grace the stage.

Crafty was built on top of automatic redraw regions. A redraw regions is basically a minimum bounding box around some objects that change, which is cleared and then drawn again in the new position.

In the figure, the ship is facing up and is on the left side of the stage, it then moves to face the right and positioned on the right side. With redraw regions, the area which it originally occupied (box 1) is cleared and then any objects that might have intersected the area are redrawn. Then the position it is in now (box 2) is cleared and again any objects intersecting with the new area are redrawn along with the spaceship.

Even though there is a large amounts of processing going on, it is still much, much quicker than the naive solution of drawing everything even if it hasn’t changed.

The problem with this approach is the many errors it causes and the difficulty of debugging. The other problem is finding the objects that need to be redrawn which Crafty solves by using a spatial Hash Map (a data structure to quickly find entities in a spatial context). Then sorting must go on (sort by Z values followed by which entity was drawn first).

Redrawing objects that intersected with a region can’t just be redraw as a whole. You must redraw only the segment of the object that was cleared. If the entire object was redrawn, any objects that intersect with that object, would be drawn over. Unfortunately this is not always possible with canvas. It is possible to redraw segments of images but little else.

It ends up being a very complex procedure and there must be a better way to optimize it.

The solution I have been working on involves using more than one canvas element to essentially create ‘redraw canvases’ (and not regions) where objects that change are moved to a separate canvas element (whilst maintaining the order) and we can use the naive implementation because there will be a small amount of objects to draw. This solves all the problems that redraw regions introduced but is not easy to implement.

As you can see there are three stacked canvas elements. The middle canvas element is called the root canvas. All elements start off in the middle and after some time, a decision is made regarding which entities need to be moved into their own canvas.

Each entity will keep a count of how many times it has changed and the entity with the highest change count will be shifted either up or down. This depends on how many entities are on top or below in Z order. If more are on top, the entity is shifted down along with the entities below it (to preserve the order). If more are below it, the entity is shifted up along with the entities above it.

The spaceship in our example would have the highest change count and therefore be moved. The spaceship has no elements above it and plenty below so it is moved up onto the top canvas element. Therefore only the top canvas will be cleared and redrawn so is very quick.

This method is still in very early stages of development and has yet to be proven but already looks promising. More will be posted when an implementation exists.