Jump to content
  • Advertisement
Sign in to follow this  

Find flood fill boundries

This topic is 1224 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am having some trouble determining an efficent algorithm to find the size and location of a square containing all the cells within a region determined by a flood fill when the grid wraps...

Fig A. Fig B.
..... ......
.XX.. X...XX
..XX. X....X
...X. ......

Fig.A: Containing box (1,1)->(3,3)

Fig.B: Containing box (4,1)->(6,2)

Share this post

Link to post
Share on other sites

loop through each cell, and globaly remember a cell-of cycle lowest X towards global current X minimum and towards global currwent X maximum, as well as for the Y.


var minimalX,minimalY=999999999;

var maximalX,maximalY=-1;


foreachcell (as cell)


if (cell.x<minimalX)


if (cell.y<minimalY)


if (cell.x>maximalX)


if (cell.y>maximalY)





determining an efficent algorithm to find the size and location of a square containing all the cells within a region

It is much the same problem as finding an axis aligned bounding box or axis aligned bounding sphere upon verticies, 2d or 3d

Share this post

Link to post
Share on other sites

Start with all-encompassing rectangle.


You now need to perform 2 actions:

1. Cut a section off vertically

2. Cut a section off horizontally

(Section can wrap so the 2 halves of the section youre cutting off might be on different sides of the non-wrapped view)

Examples for vertical section cut (X=box, _=cut off from box):

XXXX => _XX_

XXXX => X__X



After doing these ops you should be left with a box.


You need to find an algorithm to get the size/location of the two sections (one along y other along x)

This should be fairly trivial to do using brute force. You can view the entire map as one dimensional array of booleans, so if youre cutting a vertical section, each 'column' of the map would either be true (column contains X) or false (doesnt contain X). Then youd find the longest string of false to get the coords for the section to cut off. Repeat for horizontal cut.


If you use the above algorithm the most costly part would probably be reducing the map to 2 one dimensional boolean arrays (columns and rows) so it would scale O(n) with the amount of cells in the map (since you need to iterate over all of them and set the corresponding booleans in both vertical and horizontal one dimensional array to true if you find an X)


The final step is to take the two sections you cut off and calculate the actual box from them, which shouldnt be difficult (just some min/max function calls I believe)




int mapX,mapY; //map size

bool mapShadowX[mapX],mapShadowY[mapY]; //init to false

//calculate one dimensional 'shadow' for horizontal and vertical dir

for all map cells:

if cell=='X' then set mapShadowX[cell.x]=true; mapShadowY[cell.y]=true;

end for

Section sectionX,sectionY; // contain int a,b; - section goes from some coordinate to some other coordinate in single dimension

//Find longest string of 'false' in both mapShadow arrays, taking wrapping into account, save begin and end of this string to corresponding section

//The wrapping part requires special code to handle the case where lengths of the first and last string of 'false' should be summed to get the actual length for that

//Use sectionX.a etc. which you calculated to get information about the box you wanted to find. Example:

vector2 topLeftCorner = vector2(min(sectionX.a,sectionX.b), min(sectionY.a,sectionY.b)) //Find top left corner of box in nonwrapped coords where X goes right and Y down


You can optimize this to some extent too.




no wait find the longest string of TRUE so sectionX and sectionY will directly describe the box and not the area cut off. I guess one way is optimal (find FALSE string if the box is most of the map?)

Edited by Waterlimon

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!