CODEWITHSUNDEEP
javascriptjqueryalgorithm
Dan Rubio
Dan Rubio

Reputation: 4907

How can I optimize this floodFill algorithm? Advice needed

I have a fiddle with the following code. ColorWalk clone

Here is the js code:

function floodFill(x, y, selectedColor, grayColor) {
  if (x < 0 || x >= 600) return;
  if (y < 0 || y >= 400) return;
  let square = $('.blockattribute').filter(function(ind, el) {
    return $(el).css('left') == x + 'px' && $(el).css('top') == y + 'px'
  });
  let squareColor = square.css('background-color');
  if (squareColor === grayColor || squareColor === selectedColor) {
    square.removeClass().addClass('blockattribute gray');
    floodFill(x + 20, y, selectedColor, grayColor);
    floodFill(x, y + 20, selectedColor, grayColor);
    floodFill(x - 20, y, selectedColor, grayColor);
    floodFill(x, y - 20, selectedColor, grayColor);
  }
  else {
    return;
  }
}

I've been working on learning javascript/jquery and algorithms and I've pretty much have this clone working except for the fact that when I get deeper and deeper into the grid, the slower and slower the code is. I've been reading about memoization and trying to use it on the grid but I'm getting stuck as to how to approach. All I'm really looking for is a little push regarding how to do this. Maybe memoization isn't the way to go and maybe I can optimize my code some other way. My current thinking is that I need to grab the last gray square and then proceed from there. Am I on the right track?

----Edit------

I realized that I can combine the if/else operator to check for matching gray color or selected color

Upvotes: 1

Views: 306

Answers (1)

Andy Ray
Andy Ray

Reputation: 32076

Reading from and writing to the DOM are very expensive in Javascript. You also should never use the DOM as the source of your data.

To speed up your algorithm, store the pixel data offline as regular Javascript data, manipulate the data only, then update the visual code only once. This way you minimize the number of DOM operations.

Additionally, Javascript is not "tail call optimized," meaning you can't recurse forever, and every level of recursion will slow down the program to some degree. If you can use a non-recursive flood fill algorithm in this case, it will likely be faster.

Upvotes: 3

Related Questions