Tag: optimisation

Al Jazari – scooping out the insides of planets with scheme

Optimisation is a game where you write more code in order to do less. In Al Jazari 2 doing less means drawing less blocks. Contiguous blocks of the same type are already automatically collapsed into single larger ones with the Octree – but if we can figure out which blocks are completely surrounded by other blocks, we can save more time by not building or drawing them either.

Here is a large sphere – clipped by the world volume, showing a slice through the internal block structure:

aj2-skin1

The next version has all internal blocks removed, in this case shaving 10% off the total primitives built and drawn:

aj2-skin2

The gaps in the sphere from the clipping allow us to look inside at how the octree has optimised the structure. The gain is higher in a more normal Minecraft set up with a reasonably flat floor covering a large amount of blocks. Here is the code involved, built on top of a functional library I’m building up on to manipulate this kind of data. It maps over each Octree leaf checking all the blocks it touches on each of its six sides, taking into account that the size of the leaf block may be bigger than one.

(define (octree-check-edge f o pos size)
  (define (do-x x y)
    (cond
     ((eq? x -1) #f)
     ((octree-leaf-empty? (octree-ref o (vadd pos (f x y)))) #t)
     (else (do-x (- x 1) y))))
  (define (do-y y)
    (cond
     ((eq? y -1) #f)
     ((do-x size y) #t)
     (else (do-y (- y 1)))))
  (do-y size))

(define (octree-is-visible? o pos size)
  (or
   (octree-check-edge (lambda (x y) (vector size x y)) o pos size)
   (octree-check-edge (lambda (x y) (vector -1 x y)) o pos size)
   (octree-check-edge (lambda (x y) (vector x size y)) o pos size)
   (octree-check-edge (lambda (x y) (vector x -1 y)) o pos size)
   (octree-check-edge (lambda (x y) (vector x y size)) o pos size)
   (octree-check-edge (lambda (x y) (vector x y -1)) o pos size)))

(define (octree-calc-viz o)
  (octree-map
   (lambda (v pos size depth)
     (octree-leaf
      (octree-is-visible?
       o pos size)
      (octree-leaf-value v)))
     o))

Fast HTML5 sprite rendering

After quite a lot of experimentation with HTML5 canvas, I’ve figured out a way to use it with the kind of big isometric game worlds used for Germination X which are built from hundreds of overlapping sprites. There are lots of good resources out there on low level optimisations, but I needed to rethink my general approach in order to get some of these working.

It was quite obvious from the start that the simple clear screen & redraw everything way was going to be far too slow. Luckily HTML5 canvas gives us quite a lot of options for building less naive strategies.

A debug view of the game with 10 frames of changes shown with two plant spirits and one butterfly moving around.

The secret is only drawing the changes for each frame (called partial re-rendering in the link above). To do this we can calculate sprites which have changed and the ones they overlap with. The complication is maintaining the draw order and using clipping to keep the depth correct without needing to redraw everything else too.

In the game update we need to tag all the sprites which change position, rotation, scale, bitmap image, transparency etc.

Then in the render loop we build a list of all sprites that need redrawing, along with a list of bounding boxes for each overlapping sprite of the changed sprites that touch them. There may be more than one bounding box as a single sprite may need to be redrawn for multiple other changed sprites.

For each changed sprite:
    Get the bounding box for the changed sprite
    For each sprite which overlaps with this bounding box: 
        If overlapping sprite has already been stored:
            Add the bounding box to overlapping sprite's list 
        Else:
            Store overlapping sprite and current bounding box.
    Add the changed sprite to the list.

Assuming the sprites have been sorted into depth order, we now draw them using the list we have made (we would only need to loop over the redraw list if we built it in depth sorted order).

For each sprite:
    If it's in the redraw list:
        If it's not one of the originally changed sprites:
            Set a clipping rect for each bounding box.
        Draw the sprite.
        Turn off the clipping, if it was used.

With complex scenes and multiple moving objects, this algorithm means we only need to redraw a small percentage of the total sprites visible – and we start to approach Flash in terms of performance for games (I suspect that flash is doing something similar to this under the hood). The code is here, currently written in HaXE, but will probably end up being ported to Javascript.