Generation of barrier islands
The December news on Hurricane Florence often referred to the External Shoals - a series of barrier islands on the coast of North Carolina:
Barrier islands are flat or clumpy patches of sand formed by waves and surf parallel to the coast of the mainland. They often have the appearance of long chains that can stretch for many tens of miles. Barrier islands are usually separated by small tidal channels, and can form lagoons between the islands and the mainland.
According to Wikipedia , barrier islands can cover up to 15% of the coast, so you can expect to see them on most fantasy cards, but in fact they are quite rare. And because of the nature of the noise, they almost never occur on procedurally generated maps that use noise to create the relief.
To understand why this is so, let's take a look at the "vanilla" map of the island:
In essence, it is a circle distorted by a small amount of low-frequency noise added to split a circular shape. Let's now try to use noise to break up the coast and form coastal islands. Here is the same island with the addition of low-frequency noise:
It has bays and capes. The terrain elements are quite large, because I used low-frequency noise, which changes slowly. However, the noise is not strong enough to create islands. Let's strengthen it a little:
Now we have created several islands, but they are essentially round spots, not necessarily stretching along the coast. You can add high frequency noise:
This can give us very broken coastlines and small islands along the coast, but nothing like a barrier island.
The only reason for this is that the noise is not consistent in x and y, so although in general the noise is not accidental, the forms it creates are random:
This is good for some things, but not suitable for creating a specific form, for example, an island along the coast.
As in other cases, when I needed to generate a specific shape or area, I needed to create a mask of the required shape, and then use noise inside the mask. (You can also use noise to distort the mask and make it more natural.) Barrier islands are, in fact, long, thin areas that are offset from the coast. So let's create a mask for this form.
To begin with, we will define the part of the coast where the barrier island will be located. This can be done by selecting a random point on the coast, and a second point below, which are marked in the figure with a red line in the upper right corner:
To start creating a barrier island, I can simply take a straight line between these two points and project it slightly out into the water. This will give me a very straight and unnatural looking island, but you can distort its shape to hide it. The real problem is that the island will not follow the coastline. It will probably look normal for most of the direct coastal areas, but will seem strange on winding coasts. It is better to replicate the coastline and make it the basis of the island form.
For this, I need to create a copy of the coastline, and then project it into the ocean perpendicular to the coastline. I already have a procedure for calculating perpendiculars (normals) to broken lines since I implemented handwritten lines , and my coastlines always run in the same direction, so everything is pretty simple:
Or it seems simple. Let's see what happens if I project the coastline a little further out (to create the other side of the island mask) on the less flowing part of the coastline:
The two segments of the projected line intersect with each other and create an awesome “eight” on the range. This is the so-called problem of parallel curves . We can not just shift the coast to a certain distance, it is also necessary to solve the problems arising from the acute internal and external angles.
I looked up the Javascript code to solve this problem, but the only example found ( from here ) crashed amazingly even on fairly simple samples. So I wrote my own. In general, the solution is to displace each point along the normal, but then check whether the new point creates a segment that intersects one of the already existing segments. If so, then we cut the loop and insert a new segment consisting of the intersection point and the new point. In the test examples I tested, this system worked quite well for my requirements.
So, now I can generate simple masks (without loops) for the islands:
This is too even, so I distort the contours:
Contours may touch the coast at some points, but this is normal, this is often the case near barrier islands.
The next stage is to fill the contour with land, but before I do this, I want to make the islands longer and add the logic of avoiding intersecting islands in case several barrier islands are created on one coastline.
Now let's try adding land. To do this, I will raise the height of any land location (which are Delone triangles) above sea level:
Here it is worth noting a couple of aspects. First, in the upper left corner there is a rather successful barrier island. However, it is unlikely that the island fills the landfill well. Many land triangles are “included” due to their centers inside the polygon. This adds randomness to the shape of the island. Secondly, it can be seen that the other two islands were so close to the coast that they just merged with it. Since I want to create islands here, I don’t need this to happen too often, so I’ll set up generation to get a larger water gap between the coastline and the island. (I'll add a check later to prevent this from happening.)
One of the nice features of land-forming irregular triangles is that they naturally create tidal channels typical of barrier islands. What is bad about them is that they usually create island spots that look like distorted pearls on a string. They are not very similar to barrier islands, and if you take a lot of individual triangles, then they look very unnatural.
If I increase the width of the islands, both effects disappear, and I get more natural islands, but without tidal ducts:
But I would like to learn how to generate very narrow islands. Another approach is to (significantly) increase the number of locations in the world to increase the resolution:
So we can get impressively thin and detailed islands, but this greatly increases the time and memory required to create a map.
In both of these methods, there is a good chance that some parts of the island will be very uneven:
This happens because the contour intersects the two sides (and sometimes all three sides) of the underlying Delone triangles. This is an inherent problem of using the Delaunay triangulation in the generation of maps, but for some reason they rarely discuss it! This happens on the coastlines in my game is not very often, because to reduce the number of such cases, I deliberately added a smoothing step, but this step tends to destroy the narrow islands. A potential solution is to create slightly wider islands and to use anti-aliasing — if properly configured, thinner islands can be obtained without many triangle artifacts:
However, with this approach, there are still restrictions on how narrow the islands can be. In addition, this means that we will never get truly fractal coastlines.
Sometimes the smoothing algorithm splits a long barrier island into several smaller ones (as in the lower left corner of the image above), but it would be convenient to have an option that allows you to do this forcibly:
The only thing that remains is to give the islands names and map them. The only subtle aspect here is that I do not want to give names to all the islands in the chain of barrier islands. In the real chains of barrier islands, individual islands often have names, which leads to chaos on the map:
Therefore, when creating a barrier island, I take into account the whole arc and attach one name to it, even if, as a result, the generation breaks the arc into several islands:
Usually, barrier islands are called “shoals” (Banks) or “ramparts” (Bars), therefore these words are found in variants of names.
This example shows a potential problem with barrier islands:
Here the barrier island was created inside the bay. This is illogical (besides, leads to the intersection of names). To avoid this, I can use my own bay recognition logic and skip these sections of the shoreline. This method probably has no fool protection, but it works well for this card:
Barrier islands are flat or clumpy patches of sand formed by waves and surf parallel to the coast of the mainland. They often have the appearance of long chains that can stretch for many tens of miles. Barrier islands are usually separated by small tidal channels, and can form lagoons between the islands and the mainland.
According to Wikipedia , barrier islands can cover up to 15% of the coast, so you can expect to see them on most fantasy cards, but in fact they are quite rare. And because of the nature of the noise, they almost never occur on procedurally generated maps that use noise to create the relief.
To understand why this is so, let's take a look at the "vanilla" map of the island:
In essence, it is a circle distorted by a small amount of low-frequency noise added to split a circular shape. Let's now try to use noise to break up the coast and form coastal islands. Here is the same island with the addition of low-frequency noise:
It has bays and capes. The terrain elements are quite large, because I used low-frequency noise, which changes slowly. However, the noise is not strong enough to create islands. Let's strengthen it a little:
Now we have created several islands, but they are essentially round spots, not necessarily stretching along the coast. You can add high frequency noise:
This can give us very broken coastlines and small islands along the coast, but nothing like a barrier island.
The only reason for this is that the noise is not consistent in x and y, so although in general the noise is not accidental, the forms it creates are random:
This is good for some things, but not suitable for creating a specific form, for example, an island along the coast.
As in other cases, when I needed to generate a specific shape or area, I needed to create a mask of the required shape, and then use noise inside the mask. (You can also use noise to distort the mask and make it more natural.) Barrier islands are, in fact, long, thin areas that are offset from the coast. So let's create a mask for this form.
To begin with, we will define the part of the coast where the barrier island will be located. This can be done by selecting a random point on the coast, and a second point below, which are marked in the figure with a red line in the upper right corner:
To start creating a barrier island, I can simply take a straight line between these two points and project it slightly out into the water. This will give me a very straight and unnatural looking island, but you can distort its shape to hide it. The real problem is that the island will not follow the coastline. It will probably look normal for most of the direct coastal areas, but will seem strange on winding coasts. It is better to replicate the coastline and make it the basis of the island form.
For this, I need to create a copy of the coastline, and then project it into the ocean perpendicular to the coastline. I already have a procedure for calculating perpendiculars (normals) to broken lines since I implemented handwritten lines , and my coastlines always run in the same direction, so everything is pretty simple:
Or it seems simple. Let's see what happens if I project the coastline a little further out (to create the other side of the island mask) on the less flowing part of the coastline:
The two segments of the projected line intersect with each other and create an awesome “eight” on the range. This is the so-called problem of parallel curves . We can not just shift the coast to a certain distance, it is also necessary to solve the problems arising from the acute internal and external angles.
I looked up the Javascript code to solve this problem, but the only example found ( from here ) crashed amazingly even on fairly simple samples. So I wrote my own. In general, the solution is to displace each point along the normal, but then check whether the new point creates a segment that intersects one of the already existing segments. If so, then we cut the loop and insert a new segment consisting of the intersection point and the new point. In the test examples I tested, this system worked quite well for my requirements.
So, now I can generate simple masks (without loops) for the islands:
This is too even, so I distort the contours:
Contours may touch the coast at some points, but this is normal, this is often the case near barrier islands.
The next stage is to fill the contour with land, but before I do this, I want to make the islands longer and add the logic of avoiding intersecting islands in case several barrier islands are created on one coastline.
Now let's try adding land. To do this, I will raise the height of any land location (which are Delone triangles) above sea level:
Here it is worth noting a couple of aspects. First, in the upper left corner there is a rather successful barrier island. However, it is unlikely that the island fills the landfill well. Many land triangles are “included” due to their centers inside the polygon. This adds randomness to the shape of the island. Secondly, it can be seen that the other two islands were so close to the coast that they just merged with it. Since I want to create islands here, I don’t need this to happen too often, so I’ll set up generation to get a larger water gap between the coastline and the island. (I'll add a check later to prevent this from happening.)
One of the nice features of land-forming irregular triangles is that they naturally create tidal channels typical of barrier islands. What is bad about them is that they usually create island spots that look like distorted pearls on a string. They are not very similar to barrier islands, and if you take a lot of individual triangles, then they look very unnatural.
If I increase the width of the islands, both effects disappear, and I get more natural islands, but without tidal ducts:
But I would like to learn how to generate very narrow islands. Another approach is to (significantly) increase the number of locations in the world to increase the resolution:
So we can get impressively thin and detailed islands, but this greatly increases the time and memory required to create a map.
In both of these methods, there is a good chance that some parts of the island will be very uneven:
This happens because the contour intersects the two sides (and sometimes all three sides) of the underlying Delone triangles. This is an inherent problem of using the Delaunay triangulation in the generation of maps, but for some reason they rarely discuss it! This happens on the coastlines in my game is not very often, because to reduce the number of such cases, I deliberately added a smoothing step, but this step tends to destroy the narrow islands. A potential solution is to create slightly wider islands and to use anti-aliasing — if properly configured, thinner islands can be obtained without many triangle artifacts:
However, with this approach, there are still restrictions on how narrow the islands can be. In addition, this means that we will never get truly fractal coastlines.
Sometimes the smoothing algorithm splits a long barrier island into several smaller ones (as in the lower left corner of the image above), but it would be convenient to have an option that allows you to do this forcibly:
The only thing that remains is to give the islands names and map them. The only subtle aspect here is that I do not want to give names to all the islands in the chain of barrier islands. In the real chains of barrier islands, individual islands often have names, which leads to chaos on the map:
Therefore, when creating a barrier island, I take into account the whole arc and attach one name to it, even if, as a result, the generation breaks the arc into several islands:
Usually, barrier islands are called “shoals” (Banks) or “ramparts” (Bars), therefore these words are found in variants of names.
This example shows a potential problem with barrier islands:
Here the barrier island was created inside the bay. This is illogical (besides, leads to the intersection of names). To avoid this, I can use my own bay recognition logic and skip these sections of the shoreline. This method probably has no fool protection, but it works well for this card:
Source: https://habr.com/ru/post/439198/