1
$\begingroup$

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:

enter image description here

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

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Sebastián Mestre Nov 22 '18 at 0:12
  • $\begingroup$ @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. $\endgroup$ – ImTalkingCode Nov 22 '18 at 0:22
  • $\begingroup$ It's probably a good idea to add the explanation of cspots (or inArr) to the beginning of the question so that you don't have to read through the comments first. Nice problem by the way, it kind of reminds me of the knapsack problem. $\endgroup$ – Chris Nov 22 '18 at 0:43
  • $\begingroup$ @Chris. Sorry. I've updated it with a possible solution. $\endgroup$ – ImTalkingCode Nov 22 '18 at 1:15
  • $\begingroup$ @ImTalkingCode What do you mean by cspots? $\endgroup$ – x-rw Nov 23 '18 at 8:03
1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ImTalkingCode Nov 22 '18 at 5:18
  • $\begingroup$ Ohh, i just fixed the code to take that into account. good catch! $\endgroup$ – Sebastián Mestre Nov 22 '18 at 9:42
  • $\begingroup$ You may run into problems if at some point none of the remaining groups fit entirely in any of the remaining untouched components. I'm not sure if sorting the groups by size or choosing the neighbors in a particular order would solve this. $\endgroup$ – Chris Nov 22 '18 at 11:11
  • $\begingroup$ 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. $\endgroup$ – ImTalkingCode Nov 22 '18 at 23:17
  • $\begingroup$ @SebastiánMestre you can share jsfidle(code complete) please $\endgroup$ – x-rw Nov 23 '18 at 1:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.