4
\$\begingroup\$

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.

enter image description here

Improve this question
\$\endgroup\$
1
  • 2
    \$\begingroup\$ How is the terrain represented? What kind of generation data you have access to? \$\endgroup\$
    – wondra
    Aug 30, 2014 at 10:55

2 Answers 2

Reset to default
1
\$\begingroup\$

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).

Improve this answer
\$\endgroup\$
6
  • 1
    \$\begingroup\$ So... that is BFS, right? \$\endgroup\$
    – wondra
    Aug 30, 2014 at 11:49
  • \$\begingroup\$ 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. \$\endgroup\$
    – Truncheon
    Aug 30, 2014 at 17:39
  • \$\begingroup\$ @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. \$\endgroup\$
    – ashes999
    Aug 30, 2014 at 19:18
  • 1
    \$\begingroup\$ @wondra not necessarily. Both breadth-first and depth-first search can be applied equally to flood-fill algorithms. \$\endgroup\$
    – ashes999
    Aug 30, 2014 at 19:18
  • \$\begingroup\$ 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. \$\endgroup\$
    – Truncheon
    Aug 31, 2014 at 9:36
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .