The isometric room

The following is a demonstration coded in JavaScript of the Filmation technique we described at a prior entry. Click on the image so that it gains the keyboard focus and then use the keys Q, S, P, L and the space bar to move the hero around. Much of the graphic material has been obtained or adapted from Supertotto with the kind permission of its author Totto Renna.

The most interesting part of the code deals with the key issue of sorting the scene objects according to the "is behind" relation:

function depth_sort(objs)
{
  for(var pivot=0;pivot<objs.length;){
    var new_pivot=false;
    for(var i=pivot;i<objs.length;++i){
      var obj=objs[i];
      var parent=true;
      for(var j=pivot;j<objs.length;++j){
        if(j==i)continue;
        var obj2=objs[j];
        if(obj2.is_behind(obj)){
          parent=false;
          break;
        }
      }
      if(parent){
        objs[i]=objs[pivot];
        objs[pivot]=obj;
        ++pivot;
        new_pivot=true;
      }
    }
    if(!new_pivot)++pivot;
  }
}

depth_sort can be seen as a very crude implementation of topological sorting where an edge from object A to object B exists if A is behind B. depth_sort running time is O(n³), acceptable only for low values of n. During the execution of the routine, the variable pivot separates the elements that have been sorted so far from those that still have not. The observant reader might have noticed that the presence of the following line:

if(!new_pivot)++pivot;

is an expedient hack that acts just in case the pivot did not advance after a pass through the elements; this happens when there are "is behind" cycles as we discussed previously. You can try yourself to move the blocks into such cyclic positions and see the effect on rendering.