Animate Javascript Canvas while in recursive calculation

Question

I'm trying to animate a solution to the latin-square-problem in javascript.

To do so, I wrote the recursive backtracking algorithm below.

Solving the problem is initiated by calling search(0,0) and it works just fine, displaying a solution after calculating. But I want it to show an animation on it's progress, in terms of redrawing the whole canvas, after changing the colour of one square.

I tried to incoorporate many of the solutions to similar problems, found on stackoverflow or in tutorials about canvas gameloops. Neither of them worked for me, so I'm presenting the javascript code as close as possible to my pseudo-code algorithm (without any setTimeout's or requestAnimationFrame's)

Here's a working jsfiddle containing all the code.

function search(i, j){
    if (latinSquare[i][j] != -1){
        //this square is predefined, skip it
        searchNext(i, j);
    } else {
        var colour = latinSquare[i][j];
        while(colour < n-1){
            colour = colour + 1;
            latinSquare[i][j] = colour;
            //redraw the whole canvas
            drawLatinSquare();
            //check if curent constellation is legal
            var legal = true;
            for (var k = 0; k < n; k++){
                if (k != i){
                    if (latinSquare[k][j] == colour){
                        legal = false;
                        break;
                    }
                }
                if (k != j){
                    if (latinSquare[i][k] == colour){
                        legal = false;
                        break;
                    }
                }
            }
            if (legal){
                searchNext(i, j);
                if (window.found) return;
            }
        }
        latinSquare[i][j] = -1;
    }   
}

function searchNext(i, j){
    if (i < n-1){
        //proceed horizontally
        search(i+1, j);
    } else {
        if (j < n-1){
            //proceed in the next row
            search(0, j+1);
        } else {
            //we're done
            window.found = true;
        }
    }
}

If you want to animate each step, you'll need to rewrite your algorithm into a purely recursive version - no while, no for loops. Then you can trivially insert setTimeouts with callbacks for the next step. — Bergi
– Bergi, Commented Apr 12, 2015 at 14:10

Rick Hitchcock · Accepted Answer · 2015-04-12 16:16:26Z

1

In this solution, an array is created to hold each iteration of the latinSquare arrays. The timeout interval is a function of the length of the array.

An advantage of this method is that the animation doesn't start until all the calculations are completed, so it runs quite quickly (assuming a solution is found):

var lsa= [];

function drawLatinSquare() {
  var l= [];
  for(var i = 0 ; i < latinSquare.length ; i++) {
    l.push(latinSquare[i].slice());
  }      
  lsa.push(l);
  setTimeout(function() {
    var ls= lsa.shift();
    ctx.clearRect ( 0 , 0 , canvas.width, canvas.height );
    ctx.lineWidth= 1;
    //draw the grid
    for (var i = 0; i < n + 1; i++){
      ctx.beginPath();
      ctx.moveTo(0,i*21 + 0.5);
      ctx.lineTo((n*(21)+1),i*21 + 0.5);
      ctx.stroke();
    }
    for (var j = 0; j < n + 1; j++){
      ctx.beginPath();
      ctx.moveTo(j*21 + 0.5,0);
      ctx.lineTo(j*21 + 0.5,(n*(21)+1));
      ctx.stroke();
    }
    //draw the squares
    for (var i = 0; i < n; i++){
      for (var j = 0; j < n; j++){
        colour = ls[i][j];
        if (colour == -1){
          colour = "#FFFFFF";
        } else {
          colour = colours[colour];
        }
        ctx.fillStyle = colour;
        ctx.fillRect((i*21)+1.5,(j*21)+1.5,20,20);
      }
    }
  },10*lsa.length);
} //drawLatinSquare

Fiddle

answered Apr 12, 2015 at 16:16

Rick Hitchcock

35.7k5 gold badges51 silver badges83 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

dende Over a year ago

Since I do not really need to draw while calculating, this is the solution I'm going to use.

GameAlchemist · Accepted Answer · 2015-04-12 16:11:29Z

0

You can just wrap the call to the main compute function to have it display then delay the call to the actual compute function :

function search(i,j) {
    drawLatinSquare();
    setTimeout(function() { _search(i,j)} , 15);
}

function _search(i, j){
  //... your real search function

issue being that there are too many combinations to see them all for a 'big' n : you should make a choice about what you want to show i fear.

Also if i was you i'd do a first pass to see the number of iterations, so that you can display a progress bar or like.

https://jsfiddle.net/ezstfj9f/4/

edited Apr 12, 2015 at 16:11

answered Apr 12, 2015 at 15:32

GameAlchemist

19.3k7 gold badges38 silver badges59 bronze badges

1 Comment

dende Over a year ago

I had a very similar solution but was very disappointed with its performance. Like in your solution, I could not understand why its slowing down after a while and leaving visited cells blank.

Collectives™ on Stack Overflow

Animate Javascript Canvas while in recursive calculation

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related