Flood-Fill and scanLine algorithms are line-based floods but I want square based floods

Question

I have a flood-fill algorithm (Flood-fill) to fill a 24x24 matrix as follows (matrix is 24x24 here but will be much bigger in production):

Main code:

  var cspots,    // number of spots per group
      gArr=[];   // global array which contains all group spots

  var tArr = new Array(gArr.length);   // touch array for flood-fill
  for(var spot in inArr) {
    for (var tspot in tArr)  // initialise touch array 
      tArr[tspot]=0;
    for(gspot in gArr) {     // find lowest open y*24+x ordinal
      if (gArr[gspot][0] == 0) 
        break;
      tArr[gspot]=1;
    }
    cspots = inArr[spot].GD;
    userFill(gArr[gspot][1],gArr[gspot][2],inArr[spot].KY,tArr);
  }

function userFill(x,y,elem,tArr) {
  var gord, qt=0;
  if (!cspots) return;
  if ((x >= 0) && (x <= 23) && (y >= 0) && (y <= 23)) {
    gord = y*24 + x;
    if (gArr[gord][0] != 0 || tArr[gord]) 
      return;
    gArr[gord][0] = elem;
    tArr[gord] = 1;
    --cspots;
    userFill(x+1,y,elem,tArr);
    userFill(x-1,y,elem,tArr);
    // before the y-change we need to see if there are any open spots on this line
    for(gord=y*24; gord<=(y*24)+23; gord++) {
      if (gArr[gord][0] == 0) {
        qt=1;
        break;
      }
    }
    if (!qt) {
      userFill(x,y+1,elem,tArr);
      userFill(x,y-1,elem,tArr);
    }
  }
};

This is a standard flood-fill recursive algorithm (with an accompanying touch array to mark any touches) with the additional code that I check if all x-values are set to non-zero on each x-plane before changing the y-value. This produces a matrix like this:

The problem is that it doesn't look very good (imo) as most of the areas are strung-out along the x-plane. What I want is each different group area to be in the shape of a square as much as I can. Sort-of like this example (using letters to indicate the different group areas):

V V V W W W W X X X X X
V V Y W W W W X X X X Z
Y Y Y W W W W Z Z Z Z Z
Y Y   W W W W Z Z Z Z Z
... and so on

So I have changed the userFill to look at a boxX variable which is just the (sqrt of each area)+1, which hopefully I can use to limit each area to make a square-shape. And a preX variable to store the anchor point from each group area so I know how many spots have been added. Here's the new userFill:

Main code:

  var tArr = new Array(gArr.length);
  for(var spot in inArr) {
    for (var tspot in tArr)  // initialise touch array 
      tArr[tspot]=0;
    for(gspot in gArr) {     // find lowest open y*24+x ordinal
      if (gArr[gspot][0] == 0) 
        break;
      tArr[gspot]=1;
    }
    cspots = inArr[spot].GD;
    boxX = Math.ceil(Math.sqrt(cspots));
    preX = gArr[gspot][1];
    userFill(gArr[gspot][1],gArr[gspot][2],inArr[spot].KY,tArr);
  }

function userFill(x,y,elem,tArr) {
  var gord, qt=0;
  if (!cspots) return;
  if ((x >= 0) && (x <= 23) && (y >= 0) && (y <= 23)) {
    gord = y*24 + x;
    if (gArr[gord][0] != 0 || tArr[gord]) 
      return;
    gArr[gord][0] = elem;
    tArr[gord] = 1;
    --cspots;
    // before the x-change we need to see if we have done a boxX number of changes to maintain square-shape
    if (Math.abs(x-preX) == boxX) {
      userFill(preX,y+1,elem,tArr);
      userFill(preX,y-1,elem,tArr);
      return;
    }
    userFill(x+1,y,elem,tArr);
    userFill(x-1,y,elem,tArr);
    // before the y-change we need to see if there are any open spots on this line
    for(gord=y*24; gord<=(y*24)+boxX; gord++) {
      if (gArr[gord][0] == 0) {
        qt=1;
        break;
      }
    }
    if (!qt) {
      userFill(x,y+1,elem,tArr);
      userFill(x,y-1,elem,tArr);
    }
  }
};

The only difference is that I check if boxX spots have been added and then call userFill recursively to change the y-plane.

Here's the output and it looks better as most areas are square-like but obviously it needs work (missing most of the spots, pale-blue group area is very oddly-shaped and not square-like at all), but I wonder if there is a better algorithm out there that changes a flood-fill from line-based to square based.

UPDATE:

I think I figured out an algorithm. You start with a single point at the lowest point in the matrix. You then add a surrounding square of points around that point followed by a larger square until cspots is exhausted. So:

0     (first spot in matrix (0,0))

1 1
0 1   (add 3 spots to make it a 2x2 square)

2 2 2
1 1 2
0 1 2   (add 5 spots to make it a 3x3 square)

and so on

This can be done even if a number of squares are drawn and you are building on top of other squares. For example (X and Y are preexisting squares):

  X
X X Y Y
X X Y Y

Place first spot of new group in the lowest point in matrix (0,2)

0 X
X X Y Y
X X Y Y

Try and build 1st level square (an 'X' will be blocking one of the 1-level spots)

1 1
0 X
X X Y Y
X X Y Y

Try to build 2nd level square

2 2 2
1 1 2
0 X 2
X X Y Y
X X Y Y

3rd level

3 3 3 3
2 2 2 3
1 1 2 3
0 X 2 3
X X Y Y
X X Y Y

4th level

4 4 4 4 4
3 3 3 3 4
2 2 2 3 4
1 1 2 3 4
0 X 2 3 4
X X Y Y
X X Y Y

.. and so on. I just need to find the implementation now.

UPDATE 2

I have created the breadth-first algorithm as suggested below and it works much better. Here's the code and the image produced (which is very square-like for each of the 10 groups).

function bfsFill(x,y,elem,tArr) {
  var gord, i=0, pt, queue=[], cnt=0;
  if (!cspots) return;
  if (isOutOfBounds(x,y)) return;
  queue.push([x,y]);
  while(cspots>0 && queue.length>0) {
    pt = queue.shift(); 
    gord = pt[1]*24 + pt[0];
    tArr[gord] = 1;
    gArr[gord][0] = elem;
    --cspots;
    var rArr = neighbours(pt);
    async.eachSeries(rArr, function(el, cb2) {
      if (!isOutOfBounds(el[0],el[1])) {
        gord = el[1]*24 + el[0];
        if (tArr[gord] == 0 && gArr[gord][0] == 0) {
          for(var qi in queue) {
            if (queue[qi][0] == el[0] && queue[qi][1]==el[1]) {
              cb2();
              return;
            }
          }
          queue.push(el);
        }
      }
      cb2();
    }, function(err) {
    });
  }
};

Image file produced:

Answer 1

Your code, as seen on your post at the time of posting this answer, looks sort of like this (the following was thrown together rather quickly and may or may not work) :

function fill ( x, y, touched, elem ) {
    if ( count <= 0 ) return;
    if ( isOutOfBounds(x,y) ) return;

    const idx = y*24 + x;

    if ( gArr[idx][0] != 0 || touched[idx] ) return;

    touched[idx] = true;
    gArr[idx][0] = elem;
    count--;

    fill(x+1, y, touched, elem);
    fill(x-1, y, touched, elem);
    fill(x, y+1, touched, elem);
    fill(x, y-1, touched, elem);
}

the problem with this style of writing a flood fill is that it always takes the path to the right before considering the other 3 paths it can take. This leads the program to use up its spots by moving only to the right. Such a search is called a Depth-First Search (DFS)

Instead, it would be nice if we could move around our grid starting from a point and growing out instead of blindly following the first path we find. A well known algorithm that does such a thing exists and it is called Breadth-First Search (BFS). It goes roughly as follows (once again, this code probably wouldn't work, even if you implemented the missing bits):

function fill ( starting_point, count, elem ) {
    if ( count <= 0 ) return;
    if ( isOutOfBounds(starting_point) ) return;

    let touched = Array(gArr.length).fill(false);
    let queue = [starting_point];

    while ( count > 0 && queue.length > 0 ) {
        let p = queue.shift();

        touched[p.idx] = true;
        gArr[p.idx][0] = elem;

        for ( let neighbor of neighbors(p) ) {
            if ( !isOutOfBounds( neighbor ) ) {
                if ( !touched[ neigbor.idx ] && gArr[ neigbor.idx ][0] == 0 ){
                    touched[ neighbor.idx ] = true;
                    queue.push(neighbor);
                }
            }
        }
    }
}

What this is does is that it puts points to be painted in a queue and then looks at them in the same order that they were put in.

Naturally, the first set of points that are added into the queue are the neighbors of the starting point of your flood fill, then the neighbors of those points, and so on. Effectively building a square of increasing size.

Hope this helps!