Javascript Floodfill Algorithm

A floodfill algorith is commonly used to find connected nodes of the same 'type'. in a multi-dimensional array. This algorithm is commonly used in games like minesweeper, and in paint programs as bucket-fill tools. Here I will demonstrate a recursive implementation of a 4-way floodfill search.

For this example, we will be assuming the following variables/objects:

//node object structure
var node = {
  name: name,
  xy: [x, y]
}
//storage object for visited nodes
var visited = {}

Here is the final product:

var floodfill = function(node, oppositeNode)
  if(visited[node.name]] || 
      node === oppositeNode ||
      node === null){
    return;
  }

  visited[node.name] = [node.x, node.y];
  var x = node.xy[0];
  var y = node.xy[1];

  var neighbors = [[x, y+1], [x+1, y], [x, y-1], [x-1, y]];

  for(var i = 0; i < 4; i++){
    var node = {xy: neighbors[i]};
      this.floodfill(next[0], next[1], color);
  }
  return;
} 

We first establish the base case for recursion. If we have visited the node previously, the node is equal to the opposing node type, or if the node is empty, then return.

if(visited[node.name]] || 
    node === oppositeNode ||
    node === null){
   return;
}    

Next we save the node to our visited storage, and extract coordinate data.

visited[node.name] = [node.x, node.y];
var x = node.xy[0];
var y = node.xy[1];

And lastly we recurse over the neighboring nodes, and return at the end of the function.

var neighbors = [[x, y+1], [x+1, y], [x, y-1], [x-1, y]]; 
for(var i = 0; i < 4; i++){
  var node = {xy: neighbors[i]};
    this.floodfill(next[0], next[1], color);
}
return;