Анимация Javascript Canvas в рекурсивном расчете

Я пытаюсь оживить решение проблемы латинского квадрата в JavaScript.

Для этого я написал рекурсивный алгоритм обратного отслеживания ниже.

Решение проблемы инициируется звонком search(0,0) и он работает просто отлично, отображая решение после расчета. Но я хочу, чтобы он отображал анимацию прогресса, с точки зрения перерисовки всего холста, после изменения цвета одного квадрата.

Я попытался включить многие из решений аналогичных проблем, которые можно найти в stackru или в руководствах по холстам. Ни один из них не работал для меня, поэтому я представляю код JavaScript как можно ближе к моему алгоритму псевдокода (без каких-либо setTimeoutили requestAnimationFrame"S)

Вот рабочий 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;
        }
    }
}
Источник

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

скрипка

Источник

Вы можете просто обернуть вызов основной вычислительной функции, чтобы она отобразилась, а затем задержать вызов действительной вычислительной функции:

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/

Источник
Другие вопросы по тегам