CODEWITHSUNDEEP
javascriptalgorithmrecursionflood-fill
Dean Nasseri
Dean Nasseri

Reputation: 81

Javascript flood fill algorithm getting caught in an infinite loop

Hello I am trying to implement a simple flood fill type algorithm in javascript. Basically I have a 3x3 board which I represent as a 1 dimensional array. I want to append the index for every equal value that is "touching" to a separate array. So for instance this board:

[1][1][0]
[3][1][3]
[0][0][0]

Would be represented as a 1D array ie [1,1,0,3,1,3,0,0,0]. And after running the floodFill on one of the [1] it would result with an array that looks like this [4, 1, 0] because those are the indexes in the 1d array that are touching, which have the same value.

Here is the code: 

var boardArray = new Array(1,1,0,3,1,3,0,0,0);
var comboArray = new Array();
function floodFill(n, diceVal) {
    if(boardArray[n] != diceVal) {
        return;
    }
    comboArray.push(n);

    if (n >0 && n < 8) {
    // right
    if(!(n%3==2)) {
        floodFill(n+1, diceVal);
    }

    // left
    if(!(n%3==0)) {
        floodFill(n-1, diceVal);
    }

    // up
    if(n>2) {
        floodFill(n-3, diceVal);
    }

    // down
    if(n<5) {
        floodFill(n+3, diceVal);
    }
    } else {
        return;
    }
}
floodFill(4,1);

Can anyone tell me why this is getting stuck in an infinite loop?

Upvotes: 1

Views: 796

Answers (1)

Paul Roub
Paul Roub

Reputation: 36438

In your "up" case, the first time through, you'll call floodFill(1,1);. That call, in its "down" case, will call floodFill(4,1);, which will soon call floodFill(1,1)

You're already keeping track of the matching squares - the only ones that will really cause any trouble. Just confirm that you're not checking the same square again:

function floodFill(n, diceVal) {
  if(boardArray[n] != diceVal) {
    return;
  }

  // have we been here before?
  if (comboArray.indexOf(n) >= 0)
    return;

  comboArray.push(n);

  // ...
}

Upvotes: 1

Related Questions