How can bays and straits be determined in a procedurally generated map?

Question

I've got a procedurally generated map using Voronoi cells, with a defined sea level and a believable height map.

So far, I've been successful in labelling certain geographic features: land, ocean, lakes, rivers, estuaries, confluences, mountains, and biomes. Biomes include tundra, boreal forest, grassland, and temperate forest. There are also a couple other biomes there but for my purposes they aren't important right now.

I'd like to label bays, and straits next, but I'm at a loss on how to do this properly. A bay is a recessed, coastal body of water that directly connects to the ocean.

A strait is a naturally formed, narrow waterway that connects two parts of the ocean. Basically, where two pieces of land almost touch and there's ocean on both sides. Also called a "channel".

For determining features, I can loop through any feature by type like this:

for each (var feature:Object in geography.getFeaturesByType(Geography.LAND))
  // loop through lands
  for each (var cell:Cell in feature.cells)
  // loop through cells
    for each (var neighbor:Cell in cell.neighbors)
    // loop through a cell's neighbors
      trace(neighbor.hasFeatureType(Geography.LAND));

Answer 1

The way Dragons Abound identifies bays is to walk along the coastline and find two spots on the coastline where the straight-line distance between the spots is less than the distance along the coastline between the spots. This is the sinuosity of the coastline between the two spots. By selecting a sinuosity limit and limits for the straight-line distance between the spots you can identify narrow deep bays, wide shallow bays, etc.

In this picture, the red and purple dots show the two candidate points and the green line is the coastline between the points. The sinuosity is the ratio of those two lengths:

Alternatively, you can select two points on the coast and create a polygon by connecting the two points and the coastline between the two points (i.e., connect the green line above from red dot to purple dot). Measure the area of this polygon. A bay will have a larger area than a non-bay.

In my experience, a combination of these two measures was best for reliably identifying what people see as bays.

Note that this will also detect points. To find only bays, you need to check that the "inside" of the bay contains water and not land. A quick and easy way to do this is to check the midpoint of the line between the two points to see if it is water. (This can be fooled but is generally sufficient.)

A related problem is to identify the "mouth" of the bay -- i.e., the best choice for the two points that mark the opening to the bay. Typically you'll have a bunch of candidates for the "mouth". In the example map above, you could put the mouth of that bay further in or further out. Generally speaking it probably doesn't matter too much, but one heuristic that works reasonably well is to minimize the straight-line distance across the mouth.

I haven't done straits yet, but my intuition is to check points along the coastline to find the closest point on any other coastline; if that is under some set limit it is a strait.

Answer 2

Here's a rough idea using image processing transformations to isolate the features of interest:

1. Apply a flood fill from an ocean cell to make a mask of all ocean cells. Depending on how your rivers are set up, you might need an extra elevation or clearance criterion to keep the ocean mask from flowing inland. ;)

   

2. Apply a local smoothing to the edge of this mask, keeping the connectedness/topology the same, but smoothing out small noisy coastline features that can be distracting. This lets us focus on big bays over tiny inlets. You can use the width of your filter kernal / number of iterations to finely control the scale of features you preserve.

   Here I applied a median filter a few times. Cellular automata are another popular way to erode smooth shapes from a noisy input.

   

3. Turn the mask into a distance field, where each cell stores its distance from the smoothed coastline.

   

Now we see some promising feature highlights. In a signed distance field, both bays and straits show up as sharp ridges, with distance falling off to the sides. We can use an edge detection filter to pop out these ridges:

You can then distinguish between bays and straits by following the ridge to determine its connectivity. A bay is a ridge that runs toward the coast, getting shallower and shallower (in distance from land) until it ends in a point. A strait is a ridge that connects a high-distance region to another high-distance region, going through a lower-distance region along the way.

Or, another way is to assign each island an ID (connected component search), then when you're making your distance field, propagate "closest island ID" alongside the distance frontier. A bay or inlet is then a ridge in water adjacent to the same landmass on both sides, while a channel is a ridge that separates water adjacent to two different landmasses.

You can set minimum & maximum distance-to-shore or length-of-ridge constraints to control which features to label, if you need to exclude excessively narrow/wide straits for instance.

Answer 3

Basically, you need to think about what you mean, precisely, by a bay or strait, and why you want to differentiate them (is it for AI calculations, or to label landmarks, or something else?). Play around with a few definitions to find the one that looks best to you. Then, formulate conditions to check on your Voronoi cells. A few suggestions:

Bay

• Any ocean cell that only connects to a single other ocean cell
• OR: Any ocean cell that connects to more land than ocean cells, with all ocean cells next to each other
• OR: Same as above, but with a criterion based on border length (e.g. twice as much land as water border)

Strait

• Any ocean cell that connects to exactly two ocean cells which are not next to each other
• OR: Any ocean cell that connects to two land cells that don't belong to the same landmass (you need to find out which land cells are connected first, and assign IDs to each landmass)
• OR: March around the border, and count land/water and water/land transitions. You need at least two of each.
• Depending on your method and what you want to do with the categories, you might want to eliminate straits that only lead to a bay, or label them as bay instead.