Procedural generation of planetary textures based on the Diamond-Square algorithm, part 1
Tutorial
Good day. As it happens to me, as soon as I figured out some kind of difficult question for myself, I immediately want to tell everyone the solution. Therefore, I decided to write a series of two articles on such an interesting topic as procedural generation. More specifically, I will talk about the generation of planetary textures. This time I’ve prepared more thoroughly and will try to make the material better than in my previous post “Simple System of Events in Unity” (by the way, thanks to everyone for the response posts). Before continuing, I want to draw your attention to several points:
1) This generator does not claim to be realistic, and I wrote it in order to generate unique textures for hundreds of small balls that occupy 10% of the screen and are also covered by clouds.
2) A purely technical point: I write in C # under Unity3d, so you will have to think about how to output to an image at an acceptable speed yourself, for each language and platform its own methods.
Diamond square
Once upon a time, one good person, Gavin SP Miller, described a 2D noise generation algorithm. And 4 years ago, another good person, deNULL , wrote a detailed article about this and some other generation methods. Before moving on, I highly recommend reading, the algorithm is described very well. But, when I started writing code, several technical problems arose. What were the problems and how they were solved I will tell during the article. Let's start with the general scheme of actions:
First, using our algorithm, we generate a “height map” - about the same as what we see in the second picture. Since the value of the color component in Unity seems to be a fractional number from 0 to 1, my implementation of the algorithm fills the field with values in this range, but it will not be difficult to remake the algorithm for a different range. Then, in certain ratios, this value is entered into the r, g, b values of the color of the corresponding pixel. We proceed to the first point.
We generate a map of heights
At this point, I hope you already imagine the general principle of the diamond-square itself, if not, still read the article that I indicated above. I will only describe my implementation. To begin with, we will form a two-dimensional array, the measurements of which should be equal to 2 ^ n + 1, it will not work for other sizes). I took 2049x1025 (2: 1 ratio is best for spherical planets in a vacuum). Let's write the Square and Diamond methods. The first takes the coordinates of the lower left and upper right corners of the square and writes the value to its center. The second one takes the value of the point to be calculated (i.e., the middle of the sides of this square) and calculates it based on the values of the adjacent corners of the square, its center and the center of the neighboring square. Here on this place there will be an interesting snag, but first the methods themselves:
public static int ysize = 1025, xsize = ysize * 2 - 1;
public static float[,] heighmap = new float[xsize, ysize];
public static float roughness = 2f; //Определяет разницу высот, чем больше, тем более неравномерная карта высот
public static void Square(int lx, int ly, int rx, int ry)
{
int l = (rx - lx) / 2;
float a = heighmap[lx, ly]; // B--------C
float b = heighmap[lx, ry]; // | |
float c = heighmap[rx, ry]; // | ce |
float d = heighmap[rx, ly]; // | |
int cex = lx + l; // A--------D
int cey = ly + l;
heighmap[cex, cey] = (a + b + c + d) / 4 + Random.Range(-l * 2 * roughness / ysize, l * 2 * roughness / ysize);
}
Important note: Random.Range (float min, float max) returns a pseudo-random number in the specified range. It is fast, but only in Unity. I don’t know how it will be with System.Random. I mean, you may have to write a pseudo-random number generator yourself.
We go further:
bool lrflag = false;
public static void Diamond(int tgx, int tgy, int l)
{
float a, b, c, d;
if (tgy - l >= 0)
a = heighmap[tgx, tgy - l]; // C--------
else // | |
a = heighmap[tgx, ysize - l]; // B---t g----D |
// | |
// A--------
if (tgx - l >= 0)
b = heighmap[tgx - l, tgy];
else
if (lrflag)
b = heighmap[xsize - l, tgy];
else
b = heighmap[ysize - l, tgy];
if (tgy + l < ysize)
c = heighmap[tgx, tgy + l];
else
c = heighmap[tgx, l];
if (lrflag)
if (tgx + l < xsize)
d = heighmap[tgx + l, tgy];
else
d = heighmap[l, tgy];
else
if (tgx + l < ysize)
d = heighmap[tgx + l, tgy];
else
d = heighmap[l, tgy];
heighmap[tgx, tgy] = (a + b + c + d) / 4 + Random.Range(-l * 2 * roughness / ysize, l * 2 * roughness / ysize);
}
Here we dwell in more detail. As you can see, for each point I carry out a check: does it go beyond the boundaries of the array. If it does, then I assign the opposite value to it. Those. if, for example, we calculate the rhombus on the left side, then the abscissa of its left vertex is less than zero, instead of it we use the value of the point symmetric to it, i.e. xsize - l (l is half the side of the square). Thus, when applied to a sphere, we get a seamless texture. In addition, for a coordinate that may go beyond the right border, an additional check is carried out. The fact is that diamond-square is valid only for squares. I make a rectangle with sides 2: 1 and count it as two squares. Therefore, I introduced a flag that determines in which part we are acting and according to it I considered the right border to be either 1025 or 2049 (ysize or xsize). Not a very elegant solution,
Recheck all coordinates! Because of one mistake in the diamond parameter, I puzzled all day in front of this mathematically interesting one, but not at all in the subject of the picture:
Spoiler
Our tools are almost ready, the last little method left, combining them for one square.
public static void DiamondSquare(int lx, int ly, int rx, int ry)
{
int l = (rx - lx) / 2;
Square(lx, ly, rx, ry);
Diamond(lx, ly + l, l);
Diamond(rx, ry - l, l);
Diamond(rx - l, ry, l);
Diamond(lx + l, ly, l);
}
Note that we DO NOT call this method recursively, I will explain why. Look at this picture:
I drew step by step what would happen if recursively called Diamond-Square for sub-squares. The first square is considered normal, because the peaks of the diamond go beyond the array and the center of the square is used instead. But here the square inside it is considered wrong, because the middle of the squares - the neighbors have not yet been counted. As a result, nothing good will come of it. Thus, as it is written in that article, it is necessary to consider layers and recursion in this case is not needed. Some time after realizing this fact, I managed to come up with this calculation by layers:
public static void Generate()
{
heighmap[0, 0] = Random.Range(0.3f, 0.6f);
heighmap[0, ysize - 1] = Random.Range(0.3f, 0.6f);
heighmap[xsize - 1, ysize - 1] = Random.Range(0.3f, 0.6f);
heighmap[xsize - 1, 0] = Random.Range(0.3f, 0.6f);
heighmap[ysize - 1, ysize - 1] = Random.Range(0.3f, 0.6f);
heighmap[ysize - 1, 0] = Random.Range(0.3f, 0.6f);
for (int l = (ysize - 1) / 2; l > 0; l /= 2)
for (int x = 0; x < xsize - 1; x += l)
{
if (x >= ysize - l)
lrflag = true;
else
lrflag = false;
for (int y = 0; y < ysize - 1; y += l)
DiamondSquare(x, y, x + l, y + l);
}
}
We go over all the lengths of the sides of the squares (attentive people could notice that the search starts right away with a half length; to be honest, I have no idea why, but if you take the full side at once, we get continents - overgrowths for the whole map) and for each of them we go over sequentially all the lower left corners of the squares in this “layer” of lengths. Thus, all the squares always “know” the centers of the neighbors and the correct picture is obtained. By the way, as can be seen from the code, the four corners of the picture (in our rectangular case, 4 corners and the middle of the large sides) must be specified, this is the input to the algorithm.
Voila!
Well, now the most interesting thing is color .
Disclaimer: All that is written below is my bike. And honestly, not the best. It gives far from the most realistic picture, its code is bulky and I will gladly listen to ideas for improvement. Everything, you are warned, prepare your keyboards for writing essays on the processes of planet formation, I did not listen well at school and did not remember anything.
I decided to divide the entire planet into three zones: snow, green zone, desert zone. Do you remember pictures with them in geography textbooks? Now we will do them. For this, I created a separate class. It is small, I spread all at once:
public static class TemperatureCurves_class
{
static int xsize = Heighmap_class.xsize;
public static int snowEdge = Heighmap_class.ysize / 10;
public static int greenEdge = Heighmap_class.ysize / 3;
public static int[] northGreen = new int[xsize];
public static int[] southGreen = new int[xsize];
public static int[] northSnow = new int[xsize];
public static int[] southSnow = new int[xsize];
static float snowRoughness = 0.03f;
static float greenRoughness = 0.15f;
static void MidPointDisplacement1D(ref int[] curve, int l, int r, float roughness)
{
if (r - l > 1)
{
curve[(l + r) / 2] = (curve[l] + curve[r]) / 2 + (int)Random.Range(-(r - l) * roughness, (r - l) * roughness);
MidPointDisplacement1D(ref curve, l, (l + r) / 2, roughness);
MidPointDisplacement1D(ref curve, (l + r) / 2, r, roughness);
}
}
public static void Generate()
{
northSnow[0] = northSnow[xsize - 1] = Heighmap_class.ysize - snowEdge;
southSnow[0] = southSnow[xsize - 1] = snowEdge;
northGreen[0] = northGreen[xsize - 1] = Heighmap_class.ysize - greenEdge;
southGreen[0] = southGreen[xsize - 1] = greenEdge
MidPointDisplacement1D(ref northGreen, 0, xsize - 1, greenRoughness);
MidPointDisplacement1D(ref southGreen, 0, xsize - 1, greenRoughness);
MidPointDisplacement1D(ref northSnow, 0, xsize - 1, snowRoughness);
MidPointDisplacement1D(ref southSnow, 0, xsize - 1, snowRoughness);
}
}
So, as the name implies, the boundaries of climatic zones lie in this class. They are in the form of arrays - two southern, two northern. And we generate them using the ancestor diamond-square: midpoint displacement. In our case, we use it on a straight line. I think the principle of its action after diamond-square does not need to be explained, especially deNULLIt has long been done for me. In fact, there lies a set of y coordinates mapped to the x coordinate, denoting the interface of the zones. So that the belt is closed (we will pull all this on the sphere later), we make its edges equal. And for realism in the snow and for the green strip, we make different roughness values so that the polar circle is a circle (straight on the texture), and the belts can wriggle along the most unpredictable paths (but it is important not to overdo it, the desert on the snow border will look strange). However, the desert will still look strange, because they are determined not only by their proximity to the equator, but also by mountains, winds and other factors.
Working with color
The most cumbersome and bicycle part of the code, get ready.
First, create an array of colors (there is a method in the unit that quickly reads such an array and writes its elements into texture pixels, which is much faster than any SetPixel () and others):
public Texture2D tex; //Ссылка на текстуру, в которую записываем результат
public static Color[] colors = new Color[Heighmap_class.xsize * Heighmap_class.ysize];
float waterLevel = 0.2f;
By the way, as deNULL wrote , it is useful to square the values of the height map, this will smooth it out a bit and make it more like the real one.
void SqrHeighmap()
{
for (int x = 0; x < Heighmap_class.xsize; x++)
for (int y = 0; y < Heighmap_class.ysize; y++)
Heighmap_class.heighmap[x, y] *= Heighmap_class.heighmap[x, y];
}
In addition, I apply the following effect to the finished texture:
void SmoothImg()
{
for (int i = 0; i < Heighmap_class.xsize * Heighmap_class.ysize - 2; i++)
{
Color clr1 = colors[i];
Color clr2 = colors[i + 1];
colors[i] = (2 * clr1 + clr2) / 3;
colors[i + 1] = (clr1 + 2 * clr2) / 3;
}
}
The effect is small, but it doesn’t seem to affect the speed too much.
And now we write methods for setting colors for different types of terrain:
The winter is coming. If water has come under the distribution, cover it with a uniform snow crust, otherwise cover it with snow crust with weak outlines of the continents with slight darkening in the area of elevations.
Change the color inversely with the height - the higher, the darker. In addition, so that the edges of the continents are not illuminated, we reduce it slightly at the edge of the water.
At the same time, we avoid mountains (a separate question, why do values more than 1.0f appear at all, but the unit seems to have nothing against it).
And the service method of checking the value between the minimum and maximum, will be used to determine whether the point belongs to the belt:
bool ChechInRange(int value, int min, int max, int rand)
{
return ((value > min + rand) && (value < max + rand));
}
And now the meat itself:
void Awake()
{
Heighmap_class.Generate();
TemperatureCurves_class.Generate();
tex.Resize(Heighmap_class.xsize, Heighmap_class.ysize);
tex.Apply();
SqrHeighmap();
int counter = 0;
for (int y = 0; y < Heighmap_class.ysize; y++)
for (int x = 0; x < Heighmap_class.xsize; x++)
{
float heigh = Heighmap_class.heighmap[x, y];
if (heigh < waterLevel)
SetOcean(counter, heigh);
else
{
if (ChechInRange(y, TemperatureCurves_class.southSnow[x], TemperatureCurves_class.northSnow[x], Random.Range(-10, 10)))
if (ChechInRange(y, TemperatureCurves_class.southGreen[x], TemperatureCurves_class.northGreen[x], Random.Range(-10, 10)))
{
SetDesert(counter, heigh);
if (heigh < waterLevel + 0.1f + Random.Range(-0.05f, 0.05f))
SetGreen(counter, heigh);
}
else
SetGreen(counter, heigh);
if (heigh > 0.82f + Random.Range(-0.05f, 0.05f))
SetMountains(counter, heigh);
}
if ((y < TemperatureCurves_class.southSnow[x] + Random.Range(-10, 10)) || (y > TemperatureCurves_class.northSnow[x] + Random.Range(-10, 10)))
SetSnow(counter, heigh);
counter++;
}
SmoothImg();
tex.SetPixels(colors);
tex.Apply();
}
Let's try with the words:
Generate a height map, generate the borders of the zones, initialize the texture, square.
In a loop:
If the height is below sea level, fill the pixel with the ocean.
Otherwise, check for belonging to the green strip, inside we check for the desert, if so, then make the desert, if not, then green.
We put mountains on top of this, if suddenly the height became high.
And even higher, if you hit the Arctic Circle, then we call the white walkers snow.
Well, after the cycle we smooth the picture and load it into the texture.
January 28, 2015 at 17:50
