How can I fill the interior of a closed loop on a tile map?

Question

In my game the player can dynamically modify terrain. The map is stored within a 2D array of prefabricated 3D objects. This is working well for now. The player modifies terrain by selecting what sort of tile they'd like to create (like cliff going up or down), and then clicking individual tiles, or "painting" over multiple by holding down mouse button and scrolling.

I don't want the player to have to manually click every tile they want to rise or fall in elevation. The most elegant solution I can conceive, is for the player to "paint" a loop of cliff tiles, which is then filled in automatically when the loop closes. Imagine, perhaps, someone drawing a line using MS Paint or Photoshop, until that line closes into a shape which then autofills.

Let's say the player wants a plateau, and so they select cliff going up, and then click and drag the desired shape. Upon closing the loop, when the last cliff tile is created beside the first cliff tile, witchcraft is invoked which fills the inside.

I have no idea how this can be done, never mind elegantly or optimally. There are obvious possible solutions (find the average vector of all tiles in the loop, and then dijkstra algorithm from the average until the space is filled with the correct elevation), but these assume the shape generated is blobby or boxy. An irregular shape where the mid point falls outside of the shape is possible and would probably ruin that solution!

How can I fill the inside of a closed loop? I'd like a theoretical solution I can go away and implement in C#. At this point it seems like there is probably conceptual overlap between raster graphics and procedural maps!

Answer 1

Short: After completing the shape you should have a multiple of 2 Points for each affected row on your x-axis. From there it becomes just a matter of splitting up these Pairs of Points for each row and then fill the inbetweens.

---

Long¹: This is not a complete algorithm. This is just a description of steps to be taken. How to achieve each step is up to the reader and might differ between languages, etc.

Step 1: Draw the loop inside your game/editor/whatever and however you want to do that.

Step 2: Get the points touched by your loop. These are the edges of your shape.

Step 3: Iterate over these points and get the ones that have one or no neighbours. These are our starts and stops (or whatever name you find fitting).

Step 4: Iterate over your starts/stops and create pairs of two each.

Step 4b - Special Case: If you've got an odd number of stats/stops you can get rid of the central point.

Step 5: You can now fill the area² between each pair of points.

_{¹WITH PICTURES! I KNOW, RIGHT?
²Well, it's actually segments not areas. A line between two points is a segment. The whole thing is an area though.}

---

As mentioned in the comments this algorithm is not bulletproof at all, here's one proposed improvement to Step 4b by @DMGregory

Answer 2

For simple shapes (i.e. ones that don't self-intersect, so that the interior of the shape is a single connected area) a flood fill algorithm should work fine.

The tricky part of trying to flood fill the interior is that, as you note, you'll need to start the fill from a point that you know to be inside the loop. One way to find such a point could be to pick, say, a point just south of the northernmost point in the loop. As long as your loop shape is clean enough, and doesn't double back on itself, you could be pretty sure that this point will be inside the loop.

However, there's an alternative solution that avoids the need to find such an interior starting point completely, and also handles arbitrary self-intersecting shapes: instead of flood-filling the inside of your loop, fill the outside instead.

Of course, it's probably not practical to fill all of the outside, since your map will likely be a lot bigger than the shape drawn by the player. But it's pretty easy to compute a bounding box that encloses the shape drawn by the player (and extends at least one map tile around it on all sides, to make sure there's a connected path around the shape inside the box), and then flood-fill the part of the box that lies outside the shape, starting e.g. from any corner:

The interior of the loop will then consist of every point inside the bounding box that has not been touched by the flood fill algorithm.

The nice thing about this algorithm is that it's dead simple to implement, especially if you're already familiar with things like Dijkstra's algorithm, which is basically a special kind of flood fill. Unlike the scanline fill algorithm suggested by dot_Sp0T, there are no tricky special cases with corners or with boundary lines that align with the grid; all you need to do is make sure the boundary is continuous and closed, and then flood fill its exterior.

Note that, if the player's loop can self-intersect, these algorithms can give different results. For example, for the self-intersecting boundary shape shown in the image below, the even/odd fill rule obtained from a scanline fill would fill in the purple area on the left, while the exterior flood fill algorithm I describe would treat the entire cyan area on the right as being inside the loop:

It's up to you which behavior you'd consider more reasonable. (Of course, other fill rules are also possible, such as the non-zero winding rule, which would fill in the upper "hole" in the shape above, but not the lower one.)