I'm working on implementing a feature in a 2D map editor that I'm sure there's a common algorithm for. It's a fill tool where if you click a certain tile, that tile and all identical tiles orthogonal and adjacent to it are set to a new value. The data structure I'm working with is a 2D array of integer values. Here's the function definition:
void FillArea(int x, int y, int value);
Is there a name for this type of algorithm? I've tried searching online but wasn't sure exactly how to describe it. Essentially, this is the same algorithm that a raster image editor like Photoshop or Gimp would use when you fill a selected area with a color. I've had a couple ideas so far, but both have flaws:
First Solution: Use a recursive call to check adjacent tiles
The solution starts at the x/y tile. It sets the new value, then looks at all adjacent tiles to see if it matches the value. And the calls continue until it finds the edges of the map.
The problem with this one is it doesn't seem very efficient with how many recursive calls it has to make. These maps can be fairly big, so the call stack can easily get to a size of 100s or even 1000s. Plus I'd have to keep track of which nodes I've already visited, since there's more than one path to a node from the start.
Second Solution: Set the tiles one row at a time
From the starting position, we only look to the left and right and find all tiles that match. Then we have a line with two end points. Using that line, we then look at the lines above and below it and see if those tiles match. We do this until we reach the boundaries of the data structure or there's no more tiles above or below.
The problem here is that for certain shapes, this just won't work. For example, imagine the following structure:
[o x x x x x o o o]
[x x o x X x x o o]
[x o o o o o o o o]
The capital X is the starting point, and all the small x's are locations that match the value of X. The o's are points that we do not want to set. With this algorithm, it would only set the segment of four x's with the big X in it. The two x's to the left of that line segment would never be set, and neither would the single x on the bottom line. An adjustment to this algorithm might work where you revisit each row and check again, but that seems kind of hackish.
I'm still thinking about alternative approaches, but really I think the best solution here would be to use an existing solution rather than coming up with one on my own. Any suggestions for how to solve this problem or pointers to existing solutions?
