在递归计算过程中使用Javascript Canvas进行动画

Question

我正在尝试使用JavaScript动画解决拉丁方问题。

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

通过调用search(0,0)来启动解决问题，并且它可以正常工作，在计算后显示解决方案。但是我希望它能够展示其进展的动画，即在更改一个正方形的颜色后重新绘制整个画布。

我尝试了许多类似问题的解决方案，这些解决方案都是从stackoverflow或关于画布游戏循环的教程中找到的。但是它们都对我不起作用，因此我尽可能接近我的伪代码算法（没有任何setTimeout或requestAnimationFrame）提供JavaScript代码。

这里有一个工作的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;
        }
    }
}

- dende

---

如果你想要为每一步添加动画效果，就需要将算法改写成纯递归版本——不要使用while、for等循环语句。然后，你就可以轻松地插入带有回调函数的setTimeout来控制下一步操作。 - Bergi

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

的英文意思是：在一个段落中插入一个带有加粗字体的链接，链接名称为“Fiddle”，并且保留该段落的HTML格式。

- Rick Hitchcock

---

由于我在计算时不需要同时绘制，所以这是我要使用的解决方案。 - dende

Answer 2

您可以将对主要计算函数的调用进行包装，以便在延迟实际计算函数的调用之前显示它：

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

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

问题在于对于“大”n来说，组合太多了，无法全部显示：你应该选择想要展示的内容。

另外，如果我是你，我会先进行第一次遍历，以查看迭代次数，这样你就可以显示进度条或类似的东西。

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

- GameAlchemist

---

我有一个非常相似的解决方案，但对其性能感到非常失望。就像你的解决方案一样，我无法理解为什么它会在一段时间后变慢，并留下访问过的单元格为空白。 - dende