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

Improve this question
$\endgroup$
7
  • $\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$ Commented Nov 22, 2018 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$ Commented Nov 22, 2018 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$ Commented Nov 22, 2018 at 0:43
  • $\begingroup$ @Chris. Sorry. I've updated it with a possible solution. $\endgroup$ Commented Nov 22, 2018 at 1:15
  • $\begingroup$ @ImTalkingCode What do you mean by cspots? $\endgroup$ Commented Nov 23, 2018 at 8:03

1 Answer 1

Reset to default
0
$\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!

Improve this answer
$\endgroup$
5
  • $\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$ Commented Nov 22, 2018 at 5:18
  • $\begingroup$ Ohh, i just fixed the code to take that into account. good catch! $\endgroup$ Commented Nov 22, 2018 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$ Commented Nov 22, 2018 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$ Commented Nov 22, 2018 at 23:17
  • $\begingroup$ @SebastiánMestre you can share jsfidle(code complete) please $\endgroup$ Commented Nov 23, 2018 at 1:54

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.