Animation in Javascript using canvas

Question

I am trying to implement bubble sort animation on canvas using the update render animation loop.

so if following is the actual non animated version of bubble sort

for(var i = 0 ;i < arr.length - 1; i++)
    for(var j = 0 ;j < arr.length - 1; j++)
        if(arr[j] > arr[j+1]) { swap arr[j], arr[j+1]}

my requirement now is, on every swap or compare instruction, all the bars(array elements) should be re-drawn. But since javascript doesnot support any sleep function i cannot simply convert the above code to animated version shown below

for(var i = 0 ;i < arr.length - 1; i++)
    for(var j = 0 ;j < arr.length - 1; j++){
        if(arr[j] > arr[j+1]) { after swap..... }
        call to draw method // draw all bars
        sleep(); // doesnot work in javascript
    }

Partly I am able to implement it using setTimeout function. But I am unable figure out, how can we refractor the code(compare and swapping) present inside the nested loops completely into a separate function(update function) with out loosing the state of index variables.

So please let me know if there is any elegant solution to the problem following is my implementation by unrolling the loops in to separate functions. Definitely my implementation doesnot scale if the algorithm contains loops that are more tightly wired up.

$(function(){
    var canvas = $("#mycan");
    var ctx = canvas.get(0).getContext("2d");
    (function Graph(nBars,ctx){
        this.nBars = nBars;
        this.Bars = [];
        var MaxBarLen = 250;
        function Bar(color,height,x,y){
            this.color = color;
            this.height = height;
            this.width = 10;
            this.x = x;
            this.y = y;

        };
        Bar.prototype.toString = function(){
            return "height: "+height+" x: "+x+" y: "+y;
        };
        function init(){
            //create bars randomly of size 10 - 250
            for(var i = 0;i < nBars; i++){
                Bars.push(new Bar("rgb(0,0,0)", Math.floor(Math.random()*MaxBarLen+10),15*i+1,MaxBarLen))
            }
            algo();
            //draw();
        };
        //method to draw the bars collection to the given context
        this.draw = function(){
            ctx.clearRect(0,0,500,500);
            for(var i = 0; i < nBars; i++){
                if(Bars[i].color == "rgb(0,0,0)")
                    ctx.fillRect(Bars[i].x,Bars[i].y,Bars[i].width,-Bars[i].height);
                else{
                    ctx.fillStyle = Bars[i].color;
                    ctx.fillRect(Bars[i].x,Bars[i].y,Bars[i].width,-Bars[i].height);
                    ctx.fillStyle = "rgb(0,0,0)";
                }
            }
        };
        // BUBBLE SORT ALGORITHM
        var I = -1, J = -1;
        this.algo = function(){
            updateI(); // invocate outer loop
        };
        //outer loop
        var updateI = function(){
            console.log("updateI", I, J );
            if(I < Bars.length - 1){
                J = -1;
                I++;
                updateJ();

            }
        };
        //inner loop
        var updateJ = function(){
            console.log("updateJ", I, J );
            if(J < Bars.length - 2){
                J++;
                setTimeout(compare,100); // trigger the compare and swap after very 100 ms
            }else{
                updateI();
            }
        };
        //actual compare function
        var compare = function(){
            console.log("compare ", I, J );
            Bars[J].color = "rgb(0,255,0)";
            Bars[J+1].color = "rgb(0,0,255)";
            draw(); //draw the frame.
            if(Bars[J].height > Bars[J+1].height){
                    //update    
                temp = Bars[J].height;
                Bars[J].height = Bars[J+1].height;
                Bars[J+1].height = temp;
            }

            Bars[J].color = Bars[J+1].color = "rgb(0,0,0)";
            updateJ(); //render next iteration  
        };

        //invoke bar creation and bubble sort algorithm
        init();
    })(10,ctx);  // 10 bars and context
});

Answer 1

If you can rewrite the loop using setTimeout to trigger each iteration then that gives the browser a moment to redraw in between each iteration. So maybe something like:

function doIteration(i,j,max,callback) {
   callback(i,j);
   if (++j >= max){
     j = 0;
     i++;
   }
   if (i < max)
      setTimeout(function() { doIteration(i,j,max,callback); }, 100);
}

var arr = [12, 3, 4, 1, 20, 2, 5, 7, 9, 13, 19, 6, 8, 14, 18, 10, 15, 11, 16, 17];

function drawFunction() {
   document.getElementById("output").innerHTML = arr.join(",") + "<br>";   
}

doIteration(0,0,arr.length-1,function(i,j){
   var t;
   if(arr[j] > arr[j+1]) {
      t = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = t; 
   }
   drawFunction();
});

Call doIteration with the starting values for i and j and maximum value (in this case they both had the same maximum value so I've left it as a single parameter), and a callback function that will be called on each iteration and passed the current i and j. Really should test the values of i and j before calling the callback the first time, but I'll leave that as an exercise for the reader.

Here's a demo with a much simplified draw process: http://jsfiddle.net/Kpkxw/2/

I guess you were kind of headed in this direction already, but I found the way your iteration was spread across several functions a little confusing and I preferred to put it in one function.

Note: this is kind of a dodgy implementation just done off the top of my head, so I didn't have time to build it to scale or to paint it...

Answer 2

You can do it like this

var iMax = 10, jMax = 10;
var i = 0, j=0;

function firstloop(){

  if(i < iMax){

     secondloop();   

  }else{

    //final statements

  }
}

function secondloop(){

   if(j < jMax){

       //statements

       j++;
       setTimeout(secondloop, 100)      

   }else{

       j = 0;i++;
       firstloop();    // You can add a time out here if needed
   }

}

firstloop();