<p>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) :</p>

<pre><code>function fill ( x, y, touched, elem ) {
    if ( count &lt;= 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);
}
</code></pre>

<p>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 <a href="https://en.wikipedia.org/wiki/Depth-first_search" rel="nofollow noreferrer">Depth-First Search (DFS)</a></p>

<p>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 <a href="https://en.wikipedia.org/wiki/Breadth-first_search" rel="nofollow noreferrer">Breadth-First Search (BFS)</a>. It goes roughly as follows (once again, this code probably wouldn't work, even if you implemented the missing bits):</p>

<pre><code>function fill ( starting_point, count, elem ) {
    if ( count &lt;= 0 ) return;
    if ( isOutOfBounds(starting_point) ) return;

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

    while ( count &gt; 0 &amp;&amp; queue.length &gt; 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 ] &amp;&amp; gArr[ neigbor.idx ][0] == 0 ){
                    touched[ neighbor.idx ] = true;
                    queue.push(neighbor);
                }
            }
        }
    }
}
</code></pre>

<p>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.</p>

<p>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.</p>

<p>Hope this helps! </p>

CC BY-SA 4.0
2018-11-22T05:18:20.473Z
Worked very well. I need to only push a neighbour on the queue only if it was not currently a queue entry. The problem was a point (x,y) may have been in the queue and a new neighbour search would find the same (x,y) and since the touch array had not been updated, 2 entries of the same point would be in the queue and this would be replicated many times so the queue got massive and performance really suffered. Also, the multiple entries of the same point would decrement cspots more than once for the same point causing only a section of each group to be drawn.
ImTalkingCode
CC BY-SA 4.0
2018-11-22T09:42:01.023Z
Ohh, i just fixed the code to take that into account. good catch!
Sebastián Mestre
CC BY-SA 4.0
2018-11-22T23:17:39.363Z
Chris, I need to do a lot of testing to determine if the algorithm creates any orphan spots/areas which does not allow additional group areas to be added.
ImTalkingCode
CC BY-SA 4.0
2018-11-23T01:54:21.180Z
@SebastiánMestre you can share jsfidle(code complete) please
information
CC BY-SA 4.0
2018-11-22T01:16:32.930Z
2018-11-22T09:41:30.903Z
2018-11-22T09:41:30.903Z
Sebastián Mestre
<p>I have a flood-fill algorithm (<a href="https://en.wikipedia.org/wiki/Flood_fill" rel="nofollow noreferrer">Flood-fill</a>) to fill a 24x24 matrix as follows (matrix is 24x24 here but will be much bigger in production):  </p>

<pre><code>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 &gt;= 0) &amp;&amp; (x &lt;= 23) &amp;&amp; (y &gt;= 0) &amp;&amp; (y &lt;= 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&lt;=(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);
    }
  }
};
</code></pre>

<p>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:</p>

<p><a href="https://i.sstatic.net/8FjCF.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8FjCF.png" alt="enter image description here"></a></p>

<p>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):</p>

<pre><code>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
</code></pre>

<p>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:</p>

<pre><code>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 &gt;= 0) &amp;&amp; (x &lt;= 23) &amp;&amp; (y &gt;= 0) &amp;&amp; (y &lt;= 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&lt;=(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);
    }
  }
};
</code></pre>

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

<p>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.</p>

<p><a href="https://i.sstatic.net/HL3gn.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/HL3gn.png" alt="enter image description here"></a> </p>

<p><strong>UPDATE:</strong></p>

<p>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:</p>

<pre><code>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
</code></pre>

<p>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):</p>

<pre><code>  X
X X Y Y
X X Y Y
</code></pre>

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

<pre><code>0 X
X X Y Y
X X Y Y
</code></pre>

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

<pre><code>1 1
0 X
X X Y Y
X X Y Y
</code></pre>

<p>Try to build 2nd level square</p>

<pre><code>2 2 2
1 1 2
0 X 2
X X Y Y
X X Y Y
</code></pre>

<p>3rd level</p>

<pre><code>3 3 3 3
2 2 2 3
1 1 2 3
0 X 2 3
X X Y Y
X X Y Y
</code></pre>

<p>4th level</p>

<pre><code>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
</code></pre>

<p>.. and so on. I just need to find the implementation now.</p>

<p><strong>UPDATE 2</strong></p>

<p>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).</p>

<pre><code>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&gt;0 &amp;&amp; queue.length&gt;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 &amp;&amp; gArr[gord][0] == 0) {
          for(var qi in queue) {
            if (queue[qi][0] == el[0] &amp;&amp; queue[qi][1]==el[1]) {
              cb2();
              return;
            }
          }
          queue.push(el);
        }
      }
      cb2();
    }, function(err) {
    });
  }
};
</code></pre>

<p>Image file produced:</p>

<p><a href="https://i.sstatic.net/ylMKg.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ylMKg.png" alt="enter image description here"></a></p>

CC BY-SA 4.0
2018-11-22T00:12:58.210Z
Hello there! Welcome to the CG stack! I am afraid your question is sort of hard to follow. Particularly, it doesn't quite make clear what you intend your result to be...   Do you want your code to always draw a square of fixed width and height without changing what was already there?  Do you want your code to draw a shape as similar as possible to a square using exactly cspots spots? Please clear up what you want to achieve so that we can help you out!
Sebastián Mestre
CC BY-SA 4.0
2018-11-22T00:22:42.053Z
@SebastiánMestre Yes I would like to draw a shape as similar to a square using exactly cspots spots for each group as cspots can contain any number. The total of all groups cspots value will equal (24*24) so as the drawing progresses, the areas will become less and less square-like but I would like to keep the semblance of a square. In this example, there are 10 groups of varying cspots values and they need to be all drawn within the 24*24 matrix as square-like as possible.
ImTalkingCode
CC BY-SA 4.0
2018-11-22T01:15:24.107Z
@Chris. Sorry. I've updated it with a possible solution.
ImTalkingCode
CC BY-SA 4.0
2018-11-23T08:03:16.557Z
@ImTalkingCode 
What do you mean by cspots?
information
CC BY-SA 4.0
2018-11-24T06:58:25.803Z
Cspots is the number of pixels within each group. It gets decremented with each new entry into the global grid array (gArr) until 0.
ImTalkingCode
CC BY-SA 4.0
2018-11-26T00:16:49.007Z
@ImTalkingCode 
I'm starting in this world of graphics, can you pass your code please?
information
<algorithm><javascript>
Flood-Fill and scanLine algorithms are line-based floods but I want square based floods
ImTalkingCode
# Flood-Fill and scanLine algorithms are line-based floods but I want square based floods

(Asked by: username_0 on 2018-11-21)

I have a flood-fill algorithm ([Flood-fill](https://en.wikipedia.org/wiki/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:

[![enter image description here](https://i.sstatic.net/8FjCF.png)](https://i.sstatic.net/8FjCF.png)

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.

[![enter image description here](https://i.sstatic.net/HL3gn.png)](https://i.sstatic.net/HL3gn.png)

**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:

[![enter image description here](https://i.sstatic.net/ylMKg.png)](https://i.sstatic.net/ylMKg.png)

**Tags:** algorithm, javascript

> **Comments:**
> **username_1**: Hello there! Welcome to the CG stack! I am afraid your question is sort of hard to follow. Particularly, it doesn't quite make clear what you intend your result to be...   Do you want your code to always draw a square of fixed width and height without changing what was already there?  Do you want your code to draw a shape as similar as possible to a square using exactly cspots spots? Please clear up what you want to achieve so that we can help you out!  
> **username_0**: @username_1 Yes I would like to draw a shape as similar to a square using exactly cspots spots for each group as cspots can contain any number. The total of all groups cspots value will equal (24*24) so as the drawing progresses, the areas will become less and less square-like but I would like to keep the semblance of a square. In this example, there are 10 groups of varying cspots values and they need to be all drawn within the 24*24 matrix as square-like as possible.  
> **username_0**: @Chris. Sorry. I've updated it with a possible solution.  
> **username_2**: @username_0  What do you mean by cspots?  
> **username_0**: Cspots is the number of pixels within each group. It gets decremented with each new entry into the global grid array (gArr) until 0.  
> **username_2**: @username_0  I'm starting in this world of graphics, can you pass your code please?  

---

## 1 answers

### Answer by username_1 on 2018-11-22. Score: 0 | Accepted answer

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)](https://en.wikipedia.org/wiki/Depth-first_search)

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)](https://en.wikipedia.org/wiki/Breadth-first_search). 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!

> **Comments:**
> **username_0**: Worked very well. I need to only push a neighbour on the queue only if it was not currently a queue entry. The problem was a point (x,y) may have been in the queue and a new neighbour search would find the same (x,y) and since the touch array had not been updated, 2 entries of the same point would be in the queue and this would be replicated many times so the queue got massive and performance really suffered. Also, the multiple entries of the same point would decrement cspots more than once for the same point causing only a section of each group to be drawn.  
> **username_1**: Ohh, i just fixed the code to take that into account. good catch!  
> **username_0**: Chris, I need to do a lot of testing to determine if the algorithm creates any orphan spots/areas which does not allow additional group areas to be added.  
> **username_2**: @username_1 you can share jsfidle(code complete) please  

---

