Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

On this map, the "mainland" is all the land that can be connected to the center of the map in the four cardinal directions (north, south, east, west -- not diagonally). enter image description here

I would like to detect the mainland and fill the holes in it. I thought of three things:

  1. Search in every non-water (dark cells) cell if can be connected to the center of the map using a path finding algorithm. Too expensive! But this could work for the islands.

  2. The mainland is filled with a bucket of green paint. Each hole is surrounded by paint... now what? If i check every water point inside the mainland for adjacency i'll delete some peninsulas and other geographical features displayed on the shoreline.

  3. Some kind of edge detection to figure out the mainland. Keep whatever is inside, fill it if it's water, remove what's outside. Complex?

Perhaps some game experienced developer can help me out with this, possibly giving me the name of some known algorithm or technique?

share|improve this question
4  
I'm just wondering if you used some kind of algorithm to generate this map. And if so, what did you use? –  Jon Jan 10 '12 at 11:46
    
Worth looking into when working in tilebased environments is the Marching Squares Algorithm. With it you could detect and keep the smaller islands as well, and then sort by size discarding single cell islands, or whatever criteria you might have. –  William 'MindWorX' Mariager Jan 10 '12 at 16:38
    
@Jon yes! diamond square algorithm to generate a height map, then all bellow one value is water, the rest, land. I plan to use this as continent shape, then another pass to add terrain detail. –  Gabriel A. Zorrilla Jan 10 '12 at 23:56
    
@Mind Marching Squares Algorithm will come handy to paint the continent's border. Thanks nice suggestion! –  Gabriel A. Zorrilla Jan 10 '12 at 23:58
add comment

4 Answers

up vote 32 down vote accepted

Removing Islands

I've done this sort of thing before in one of my games. To get rid of outer islands, the process was basically:

  1. First there must be a guarantee the center of the map will always belong to the main land, and each pixel starts out either as "Land" or "Water" (i.e. different colors).
  2. Then do a four direction flood fill starting from the center the map and spreading throughout any "Land" tiles. Mark every pixel visited by this flood fill as a different type such as "MainLand".
  3. Finally go over the entire map and convert any remaining "Land" pixel to "Water to get rid of other islands.

Removing Lakes

As for getting rid of the holes (or lakes) inside the island, you do a similar process but starting from the corners of the map and spreading through "Water" tiles instead. This will allow you to distinguish the "Sea" from the other water tiles, and then you can get rid of them just like you got rid of the islands before.

Example

Let me dig up my implementation of the flood fill that I have here somewhere (disclaimer, I didn't care about efficiency, so I'm sure there are many more efficient ways to implement it):

private void GenerateSea()
{
    // Initialize visited tiles list
    visited.Clear();

    // Start generating sea from the four corners
    GenerateSeaRecursive(new Point(0, 0));
    GenerateSeaRecursive(new Point(size.Width - 1, 0));
    GenerateSeaRecursive(new Point(0, size.Height - 1));
    GenerateSeaRecursive(new Point(size.Width - 1, size.Height - 1));
}

private void GenerateSeaRecursive(Point point)
{
    // End recursion if point is outside bounds
    if (!WithinBounds(point)) return;

    // End recursion if the current spot is a land
    if (tiles[point.X, point.Y].Land) return;

    // End recursion if this spot has already been visited
    if (visited.Contains(point)) return;

    // Add point to visited points list
    visited.Add(point);

    // Calculate neighboring tiles coordinates
    Point right = new Point(point.X + 1, point.Y);
    Point left = new Point(point.X - 1, point.Y);
    Point up = new Point(point.X, point.Y - 1);
    Point down = new Point(point.X, point.Y + 1);

    // Mark neighbouring tiles as Sea if they're not Land
    if (WithinBounds(right) && tiles[right.X, right.Y].Empty)
        tiles[right.X, right.Y].Sea = true;
    if (WithinBounds(left) && tiles[left.X, left.Y].Empty)
        tiles[left.X, left.Y].Sea = true;
    if (WithinBounds(up) && tiles[up.X, up.Y].Empty)
        tiles[up.X, up.Y].Sea = true;
    if (WithinBounds(down) && tiles[down.X, down.Y].Empty)
        tiles[down.X, down.Y].Sea = true;

    // Call the function recursively for the neighboring tiles
    GenerateSeaRecursive(right);
    GenerateSeaRecursive(left);
    GenerateSeaRecursive(up);
    GenerateSeaRecursive(down);
}

I used this as a first step to get rid of lakes in my game. After calling that, all I'd have to do was something like:

private void RemoveLakes()
{
    // Now that sea is generated, any empty tile should be removed
    for (int j = 0; j != size.Height; j++)
        for (int i = 0; i != size.Width; i++)
            if (tiles[i, j].Empty) tiles[i, j].Land = true;
}

Edit

Adding some extra information based on the comments. In case your search space is too big, you might experience a stack overflow when using the recursive version of the algorithm. Here's a link on stackoverflow (pun intended :-)) to a non recursive version of the algorithm, using a Stack<T> instead (also in C# to match my answer, but should be easy to adapt to other languages, and there are other implementations on that link too).

share|improve this answer
11  
If you cannot guarantee that the centre tile will always be land and part of the mainland, use flood fill to mark each land tile as belonging to a particular island (flood fill from every tile with no blob id on the map, marking filled tiles with the same blobid if it doesn't already have one). Then remove all but the blob with the most tiles. –  George Duckett Jan 10 '12 at 8:03
    
Inline with what GeorgeDuckett said - you might try Googling blob detection algorithms: it's a common problem in multi-touch using FTIR. I remember I came up with a smarter algorithm, but I can't remember for the life of me how it worked. –  Jonathan Dickinson Jan 10 '12 at 12:21
    
As i've been having stack issues in PHP i implemented the LIFO flood fill, worked marvelously. –  Gabriel A. Zorrilla Mar 2 '12 at 2:56
    
Isn't it a flood fill only when a DFS algorithm is called from a BFS algorithm? Please explain someone. –  akled Mar 2 '12 at 18:26
    
@Bane What do you mean? The difference between DFS or BFS is just the order in which the nodes are visited. I don't think the flood fill algorithm specifies the order of traversal - it doesn't care as long as it fills the entire region without revisiting nodes. The order depends on the implementation. See the bottom of the wikipedia entry for a picture comparing the order of traversal when using a queue versus using a stack. The recursive implementation can be considered as a stack too (since it uses the call stack). –  David Gouveia Mar 2 '12 at 18:40
add comment

Modify the four direction flood fill algorithm http://en.wikipedia.org/wiki/Flood_fill

share|improve this answer
add comment

This is a standard operation in image processing. You use a two-phase operation.

Start by creating a copy of the map. From this map, turn into sea pixels all land pixels that border the sea. If you do this once, it will eliminate 2x2 islands, and shrink bigger islands. If you do it twice, it will eliminate 4x4 islands, etcetera.

In phase two, you do almost the reverse: turn into land pixels all sea pixels that border the land, but only if they were land pixels in the original map (That's why you made a copy in phase 1). This regrows islands to their original form, unless they were entirely eliminated in phase 1.

share|improve this answer
    
+1 for a simple and effective approach. –  William 'MindWorX' Mariager Jan 10 '12 at 16:40
add comment

I had a similar issue but not in game development. I had to find pixels in an image that were adjacent to each other and had the same value (connected regions). I tried using a recursive floodfill but kept causing stack overflows (I am a novice programmer :P). Then I tried this method http://en.wikipedia.org/wiki/Connected-component_labeling it was actually much more efficient, for my problem anyway.

share|improve this answer
    
You should have tried the stack version of the flood algo and save the stack problems. Resulted to be much more simple than CCL (which i've been working the last 2 weeks with no luck.) –  Gabriel A. Zorrilla Mar 2 '12 at 2:57
    
Yeah I tried both, but I got the CCL to work first :P and thought it was a neat idea. Glad you solved your problem :) –  Elegant_Cow Mar 2 '12 at 7:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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