Procedural generation of planetary textures based on the Diamond-Square algorithm, part 1

Good day. As with me, as soon as I figured out some 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 textures of the planets. This time I prepared more thoroughly and will try to make the material more qualitative than in my previous post “Simple Event System in Unity” (by the way, thank you all for the responsive posts). Before proceeding, I want to draw your attention to a few points:

1) This generator does not pretend 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) But this does not mean that I will not be happy with criticism. On the contrary, one of the reasons for writing this post is to get tips on improving the algorithm, I will gladly improve it.
3) A purely technical point: I am writing in C # under Unity3d, so you will have to think about how to display the image with acceptable speed yourself, for each language and platform its own methods.
So, the plan is this: in the first article I talk about procedural generation of terra-type planets, then I get a barrage of criticism, for which everything was done, improve the algorithm, refine for other types of planets and write the second part.
')
Ready? Go.

Prologue

* This part does not carry much meaning *

As I wrote above, I absolutely needed the textures of the planets. In principle, it would be enough for 2 - 3 for each type, but even that amount for me, never used anything more difficult than paint.net, is very heavy. And even if I painted, the quality would have left much to be desired. Therefore, I decided that it is better to write a generator. Of course, immediately rushed to write a bicycle. I decided to do “cell generation”. My idea was that we create a two-dimensional array, the cells of which can take several integer values ​​(or enums, without difference), which are responsible for what “element” (grass, desert, sea, bedrock ...) will be drawn to this pixel on the screen. After a day of fruitless attempts, the idea was rejected as "hopeless." Maybe this approach has the right to life, but it has a lot of flaws:

1) Complex logic, especially if there are several cells.
2) Of all 16 million colors, we use at most 10 — the number of cells.

In general, I began to look for more optimal algorithms and comes on the scene ...

Diamond-square

A long time ago one good man, Gavin SP Miller, described the 2D noise generation algorithm. And 4 years ago another good person, deNULL , wrote a detailed article about this and some other methods of generation. Before going further, I highly recommend reading, the algorithm is described very well. But when I started writing code, there were several technical problems. What were the problems and how I managed to solve them in the course of the article. Let's start with a general scheme of actions:



First, using our algorithm, we generate a “height map” - roughly the same as what we see in the second picture. Since the value of the color component in Unity is represented by a fractional number from 0 to 1, my implementation of the algorithm fills the field with values ​​in this range, but it is easy to alter the algorithm for another range. Then this value in certain ratios is entered into the color r, g, b of the color of the corresponding pixel. Proceed to the first paragraph.

Generate elevation map

At this point you, I hope, are already imagining the general principle of operation of the diamond-square itself, if not, still read the article that I have indicated above. I will only describe my implementation. To begin with, we will create a two-dimensional array, whose dimensions should be equal to 2 ^ n + 1, for other sizes it will not work). I took 2049x1025 (2: 1 ratio is best suited for spherical planets in a vacuum). Let's write the Square and Diamond methods. The first one takes the coordinates of the lower left and right upper corners of the square and writes the value to its center. The second one takes the value of the point to be calculated (that is, the midpoints of the sides of this square) and calculates it based on the values ​​of the adjacent angles of the square, its center and the center of the adjacent square. Here at 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 is only in Unity. How will it be with System.Random I do not know. I mean, you may have to write a pseudo-random number generator yourself.

Going 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<source lang="cs"> 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 will stop in more detail. As you can see, for each point I am checking whether it goes beyond the array. If it does, then I assign the opposite value to it. Those. if, for example, we calculate a rhombus on the left side, then the abscissa of its left vertex is less than zero, instead of it we use the value of a point to it symmetric, i.e. xsize - l (l - half of the side of the square). Thus, when applied to a sphere, we get a seamless texture. In addition, for coordinates that can 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 2: 1 sides and consider it as two squares. Therefore, I entered a flag that determines in which part we act and in accordance with it considered the right border to be either 1025 or 2049 (ysize or xsize). Not a very elegant solution, but cheap, reliable and practical, I still don’t need other correlations, so I left it as it is.

Recheck all coordinates! Because of one mistake in the diamond parameter, I puzzled all day for this, certainly mathematically interesting, but not at all in the subject of the picture:

Our tools are almost ready, there is the last small method that combines 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); } 

Please note, we do NOT call this method recursively, I will explain why. Look at this picture:



I drew step by step what would happen if Diamond-Square was called recursively for sub-squares. The first square is considered normal, because diamond's tops extend beyond the array and the center of the square is used instead. But the square inside it is considered wrong, because middle squares - neighbors are not counted yet. As a result, nothing good will come of it. Thus, as 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 counting 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 through all the lengths of the sides of the squares (attentive people may have noticed that the search starts immediately from half the length; to be honest, I have no idea why, but if you take the full side at once, the continents turn out to be overgrown on the whole map) and for each of them we iterate over all left lower corners of the squares in this "layer" of lengths Thus, all the squares always "know" the centers of the neighbors and get the correct picture. By the way, as can be seen from the code, the four corners of the picture (in our rectangular case, 4 corners and midpoints of large sides) should be specified, these are the input data of the algorithm.

Voila!



Well, now the most interesting thing is color .

Disclaimer : All that is written below is my bicycle. And, frankly, not the best. It gives far from the most realistic picture, its code is cumbersome and I will be happy to hear ideas for improvement. All you are warned, prepare your keyboard for writing essays on the processes of the formation of planets, 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. Remember in geography textbooks pictures with them? Now we will do them. For this, I created a separate class. It is small, I post it 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 suggests, in this class lie the boundaries of climatic zones. They are in the form of arrays - two southern, two northern. And we generate them using the diamond-square: midpoint displacement ancestor. In our case, we use it on the line. I think the principle of its action after diamond-square is not necessary to explain, especially since deNULL has done it for me a long time ago. In fact, there lies a set of y coordinates, mapped to the x coordinate, denoting the boundary between the belts. For the belt to be closed (we will, after all, apply tension to the sphere), we make its edges equal. And for realism, the snow and the green strip make different roughness values ​​so that the polar circle is round (straight on the texture), and the belts can wriggle along the most unpredictable trajectories (but it is important not to overdo it, the desert on the snow border will look weird). However, the desert will still look weird, because they are determined not only by proximity to the equator, but also by mountains, winds and other factors.

We work with color
The most bulky and bike part of the code, get ready.
First, let's create an array of colors (in unit there is a method that quickly reads such an array and writes its elements to texture pixels, it 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; 

Incidentally, as deNULL wrote, it is useful to build the height map values ​​in a square, this will smooth it a bit and make it more similar to 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 impose the following effect on 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 either.
And now we write methods for assigning colors to different types of terrain:

 void SetSnow(int counter, float heigh) { if (heigh < waterLevel + Random.Range(-0.04f, 0.04f)) colors[counter] = new Color(Random.Range(0.8f, 0.85f), Random.Range(0.8f, 0.85f), Random.Range(0.85f, 0.9f)); else { colors[counter].r = 0.005f / heigh + Random.Range(0.8f, 0.85f); colors[counter].g = 0.005f / heigh + Random.Range(0.8f, 0.85f); colors[counter].b = 0.01f / heigh + Random.Range(0.8f, 0.85f); } } 

The winter is coming. If water gets under the distribution, cover it with a homogeneous snow crust, otherwise cover it with a snow crust with weak outlines of the continents with slight darkening in the region of the hills.

 void SetOcean(int counter, float heigh) { colors[counter].r = heigh / 5; colors[counter].g = heigh / 5; colors[counter].b = 0.2f + heigh / 2 + Random.Range(-0.02f, 0.02f); } 

Well, everything is clear here, the ocean is on the other planets the ocean.

 void SetGreen(int counter, float heigh) { colors[counter].g = 0.1f / heigh + 0.05f + Random.Range(-0.04f, 0.04f); if (heigh < waterLevel + 0.1f) colors[counter].g -= (waterLevel + 0.1f - heigh); if (colors[counter].g > 0.5f) colors[counter].g = 0.5f / heigh + 0.05f + Random.Range(-0.04f, 0.04f); colors[counter].r = 0; colors[counter].b = 0; } 

We change color in inverse proportion to height - the higher, the darker. In addition, so that the edges of the continents are not illuminated, we reduce it slightly at the water edge.

 void SetDesert(int counter, float heigh) { colors[counter].r = Random.Range(0.6f, 0.75f) + heigh / 2 - 0.35f; colors[counter].g = Random.Range(0.6f, 0.75f) + heigh / 2 - 0.35f; colors[counter].b = Random.Range(0.2f, 0.3f) + heigh / 2 - 0.35f; } 

Everything is clear, and another type of terrain:

 void SetMountains(int counter, float heigh) { float rnd = Random.Range(-0.03f, 0.03f); if (heigh > 1.1f) heigh = 1.1f + Random.Range(-0.05f, 0.05f); colors[counter].r = heigh * heigh / 2 + rnd - 0.1f; colors[counter].g = heigh * heigh / 2 + rnd - 0.1f; colors[counter].b = heigh * heigh / 2 + rnd - 0.05f; } 

Mountains, while avoiding glare (a separate question, why do values ​​appear at all greater than 1.0f, 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 a point belongs to a belt:

 bool ChechInRange(int value, int min, int max, int rand) { return ((value > min + rand) && (value < max + rand)); } 

And now the very meat:

 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 the words:
We generate a height map, generate belt boundaries, initialize the texture, square it.
In the loop:
If the height is less than the ocean level, fill the pixel with the ocean.
Otherwise, check for belonging to the green strip, inside we check the belonging of the desert, if so, then we make a desert, if not - then green.
On top of this just put the mountains, if suddenly the height was high.
And even higher, if you hit the Arctic Circle, then we call the white walkers snow.
Well, after the cycle, we smooth the image and load it into the texture.

This is the generator I got. And what is yours?


PS Sources:
Demo
Unity project