在递归计算中动画 Javascript Canvas

Question

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

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

解决问题是通过调用 search(0,0) 开始的，它工作得很好，计算后显示解决方案。但我希望它在改变一个方块的颜色后重新绘制整个 canvas 的过程中显示动画。

我尝试合并许多类似问题的解决方案，这些解决方案可在 Whosebug 或有关 canvas gameloops 的教程中找到。它们都不适合我，所以我将尽可能接近我的伪代码算法（没有任何 setTimeout 或 requestAnimationFrame）呈现 javascript 代码

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

您可以将调用包装到主要计算函数以使其显示，然后延迟对实际计算函数的调用：

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

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

问题是有太多的组合无法在 'big' n 中全部看到：我担心您应该选择要显示的内容。

此外，如果我是你，我会做第一遍以查看迭代次数，以便你可以显示进度条等。

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

Answer 2

在此解决方案中，创建了一个数组来保存 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

在递归计算中动画 Javascript Canvas

Animate Javascript Canvas while in recursive calculation

javascript

recursion

canvas

backtracking

latin-square