# How to detect Lagoons and Lakes on a random Island Map

I have an engine which generates random Islands. At the moment it tends to generate quite a lot of lagoons and lakes. I would like to know of a feasible way of detecting them so that I can mark them as different terrain (i.e., salt water for lagoons).

Note: lagoons must be treated differently than lakes. I don't know what the threshhold for a lake should be, but obviously bodies of water close to the coast should be marked as salt water so the player is affected properly when trying to drink the water.

• How is the terrain represented? What kind of generation data you have access to? Aug 30, 2014 at 10:55

I think the easiest way to do this is with a flood-fill algorithm.

• Pick a square that you know is water, and not a lagoon (eg. top-left corner's water tile)
• Flood fill, marking any water tile with a flag
• Mark any water tiles left that don't have the flag as lakes/lagoons.

I assume you know what flood fill is (looking at all adjacent tiles recursively until you run out of tiles).

• So... that is BFS, right? Aug 30, 2014 at 11:49
• I'll try some different methods to see if I can get the behavior I want. I need to mark lagoons as salt water, and lakes as fresh water. Aug 30, 2014 at 17:39
• @Truncheon I think you're confused. How do you know, simply from the data, what's a lake and what's a lagoon? What are the discriminating criteria? If you can't tell, you are stuck. Aug 30, 2014 at 19:18
• @wondra not necessarily. Both breadth-first and depth-first search can be applied equally to flood-fill algorithms. Aug 30, 2014 at 19:18
• An arbitrary value will have to be set of course; if part of the water body is within a certain distance of the coast then it's marked as a logoon, otherwise it's a lake. Jus wanted to know the most efficient way of doing this; the way I have in my mind already would be very slow. Aug 31, 2014 at 9:36

There is always brute force solution if you find yourself stuck and speed is not priority (one-time generation).
In you case simple BFS/DFS might suffice. Just pick a node of desired type(either land of water) and continue your search, finding all tiles of same type within the graph(terrain part). Continue while there are any nodes not visited.