javascript - 在递归计算中为 Javascript Canvas 设置动画

Question

我正在尝试为 latin-square-problem 的解决方案制作动画在 JavaScript 中。

为此，我编写了下面的递归回溯算法。

解决问题是通过调用 search(0,0) 开始的，它工作得很好，在计算后显示解决方案。但我希望它在更改一个正方形的颜色后重新绘制整个 Canvas 方面显示有关其进度的动画。

我尝试将许多类似问题的解决方案结合起来，这些解决方案可在 stackoverflow 上或有关 Canvas 游戏循环的教程中找到。它们都不适合我，所以我尽可能接近我的伪代码算法(没有任何 setTimeout 或 requestAnimationFrame)

Here's a working jsfiddle包含所有代码。

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;
        }
    }
}

Answer 1

在此解决方案中，创建了一个数组来保存 latinSquare 数组的每次迭代。超时间隔是数组长度的函数。

这种方法的一个优点是动画直到所有的计算都完成后才开始，所以它运行得相当快(假设找到了解决方案):

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