Noise functions and map generation

When I studied audio signal processing, my brain began to draw analogies with procedural card generation. The article outlines the principles linking signal processing with card generation. I do not think that I discovered something new, but some conclusions were new to me, so I decided to write them down and share them with the readers. I consider only simple topics (frequency, amplitude, noise colors, use of noise) and do not touch on other topics (discrete and continuous functions, FIR / IIR filters, fast Fourier transform, complex numbers). Mathematics of the article is mainly related to sinusoids.



This article is devoted to concepts , starting with the simplest and ending more complex. If you want to go straight to generating terrain using the noise functions, then study my other article.



I will start with the basics of using random numbers, and then move on to explaining the work of one-dimensional landscapes. The same concepts work for 2D (see demo ) and 3D. Try moving the slider [in the original article] to see how a single parameter can describe different types of noise:

')



From this article you will learn:

• how to generate similar landscapes in just 15 lines of code
• what is red, pink, white, blue and purple noise
• how noise functions can be used for procedural map generation
• how the midpoint offset, Perlin noise and fractal Brownian motion are applied

In addition, I will experiment with 2D noise, including creating a 3D visualization of a two-dimensional height map.

1. Why is randomness useful?

We need procedural map generation to get output data sets that have something in common and something different. For example, all Minecraft maps have a lot in common: biome areas, grid size, average biome sizes, heights, average cavern sizes, the percentage of each type of rock, etc. But they also have differences: the location of the biomes, the places and forms of the caves, the placement of gold, and so on. As a designer, you need to decide which aspects should remain the same and which should be different, and take the degree of this difference.



For different aspects, we usually use a random number generator. Let's create an ultra-simple map generator: it will generate lines of 20 blocks each, and one of the blocks will contain a chest of gold. Let's describe some of the maps that we need (the “x” is the treasure):

 1 ........x...........  2 ...............x....  3 .x..................  4 ......x.............  5 ..............x..... 

Notice how much is common in these cards: they all consist of blocks, the blocks are on the same line, the line is 20 blocks long, there are two types of blocks and exactly one treasure chest.



But there is one different aspect - the location of the block. It can be in any position, from 0 (left) to 19 (right).



We can use a random number to select the position of this block. It will be easiest to use a homogeneous selection of a random number from the range from 0 to 19. This means that the probability of choosing any position from 0 to 19 is the same. In most programming languages, there are functions for uniformly generating random numbers. In Python, this is the function random.randint(0,19) , but in the article we will use the entry random(0,19) . Here is a sample Python code:

 def gen(): map = [0] * 20 #    pos = random.randint(0, 19) #   map[pos] = 1 #    return map for i in range(5): #  5   print_chart(i, gen()) 

But suppose that we need the cards on the cards to be more likely to be on the left. For this we need a non-uniform selection of random numbers. There are many ways to implement it. One of them is to choose a random number in a uniform way, and then shift it to the left. For example, you can try random(0,19)/2 . Here is the Python code for this:

 def gen(): map = [0] * 20 pos = random.randint(0, 19) // 2 map[pos] = 1 return map for i in range(5): print_chart(i, gen()) 

But actually, I didn’t really want this. I wanted the treasure sometimes to be on the right, but more often on the left. Another way to move the treasure to the left is to square the number by doing something like sqr(random(0,19))/19 . If it is zero, then 0 squared divided by 20 is 0. If it is 19, then 19 squared divided by 19 will be 19. But in the interval, if the number is 10, then 10 squared divided at 19, equal to 5. We kept the range from 0 to 19, but moved the intermediate numbers to the left. Such a redistribution is in itself a very useful technique, in previous projects I used squares, square roots and other functions. ( This site has standard shape-changing features used in animations. Hover over a function to view the demo.) Here is the squaring code using Python:

 def gen(): map = [0] * 20 pos = random.randint(0, 19) pos = int(pos * pos / 19) map[pos] = 1 return map for i in range(1, 6): print_chart(i, gen()) 

Another way to move objects to the left is to first randomly select the range limit of random numbers, then randomly select a number from 0 to the range limit. If the range limit is 19, then we can put a number anywhere. If the range limit is 10, then the numbers can be placed only on the left side. Here is the Python code:

 def gen(): map = [0] * 20 limit = random.randint(0, 19) pos = random.randint(0, limit) map[pos] = 1 return map for i in range(5): print_chart(i, gen()) 

There are many ways to obtain homogeneous random numbers and turn them into inhomogeneous, having the desired properties. As a game designer, you can choose any distribution of random numbers. I wrote an article on how to use random numbers to determine damage in role-playing games. There are various examples of tricks.



Summarize:

• For procedural generation, we need to decide what remains the same and what will change.
• Random numbers are useful for filling changing parts.
• Uniformly chosen random numbers can be obtained in most programming languages, but often we need non-uniformly chosen random numbers. To obtain them, there are different ways.

2. What is noise?

Noise is a series of random numbers, usually located on a line or in a grid.



When switching to a channel without a signal on old TVs, we saw random black and white dots on the screen. This is the noise (of their open space!). When setting up a radio channel without a station, we also hear noise (not sure if it appears from space or from somewhere else).



In signal processing, noise is usually an undesirable aspect. In a noisy room, it is more difficult to hear the interlocutor than in a quiet one. Audio noise is random numbers lined up (1D). On a noisy image, it is more difficult to see a drawing than on a clear one. Graphic noise is a random number located in a grid (2D). You can create noise in 3D, 4D, and so on.



Although in most cases we try to get rid of noise, many natural systems look noisy, so to generate something that looks like natural, we need to add noise. Although real systems look noisy, they are usually based on structure. The noise we add will not have the same structure, but it is much simpler than simulation programming, so we use noise, and we hope that the end user will not notice this. I will tell about this compromise later.



Let's take a simple example of the utility of noise. Suppose we have a one-dimensional map that we made above, but instead of one treasure chest we need to create a landscape with valleys, hills and mountains. Let's start by using a uniform selection of random numbers at each point. If random(1,3) is 1, we will consider it a valley, if 2 - hills, if 3 - mountains. I used random numbers to create a height map: for each point in the array, I saved the height of the landscape. Here is the Python code to create the landscape:

 for i in range(5): random.seed(i) #      print_chart(i, [random.randint(1, 3) for i in range(mapsize)]) # :      Python: # output = [abc for x in def] #     : # output = [] # for x in def: # output.append(abc) 

Hmm, these cards look "too random" for our purposes. Perhaps we need larger areas of valleys or hills, and mountains should not be as frequent as valleys. Earlier, we saw that a homogeneous selection of random numbers may not be entirely suitable for us, sometimes we need a heterogeneous selection. How to solve this problem? You can use any random selection in which valleys appear more often than mountains:

 for i in range(5): random.seed(i) print_chart(i, [random.randint(1, random.randint(1, 3)) for i in range(mapsize)]) 

This reduces the number of mountains, but does not create any interesting pictures. The problem with such a non-uniform random choice is that the changes occur at each point separately, and we need the random choice at one point to be somehow connected with the random choice at neighboring points. This is called coherence.



And here we will need the functions of noise. They give us a set of random numbers instead of one number at a time. Here we need the 1D noise function to create a sequence. Let's try to use the noise function, which changes the sequence of homogeneous random numbers. There are different ways to do this, but we use at least two adjacent numbers. If the original noise is 1, 5, 2, then the minimum (1, 5) is 1, and the minimum (5, 2) is 2. Therefore, the final noise will be 1, 2. Notice that we have eliminated the high point (5). Also note that the resulting noise is one value less than the original. This means that when generating 60 random numbers, the output will be only 59. Let's apply this function to the first set of cards:

 def adjacent_min(noise): output = [] for i in range(len(noise) - 1): output.append(min(noise[i], noise[i+1])) return output for i in range(5): random.seed(i) noise = [random.randint(1, 3) for i in range(mapsize)] print_chart(i, adjacent_min(noise)) 

Compared with previous maps here turned out areas of valleys, hills or mountains. Mountains often appear next to the hills. And thanks to the method of changing noise (the choice of a minimum), valleys are more common than mountains. If we took the maximum, the picture would be the opposite. If we wanted that neither valleys nor mountains were frequent, we would choose the average instead of the minimum or maximum.



We now have a noise modification procedure that receives noise at the input, and creates a new, smoother noise.



And let's try to run it again!

 def adjacent_min(noise): #     output = [] for i in range(len(noise) - 1): output.append(min(noise[i], noise[i+1])) return output for i in range(5): random.seed(i) noise = [random.randint(1, 3) for i in range(mapsize)] print_chart(i, adjacent_min(adjacent_min(noise))) 

Now the maps have become even smoother and they have even fewer mountains. I think we are too smooth, because the mountains do not appear with the hills too often. Therefore, it is probably better to return one level of smoothing back in this example.



This is a standard procedural process: you try something, see if it looks good, if not, come back and try something else.



Note: The anti-aliasing in signal processing is called a low-pass filter . Sometimes it is used to eliminate unnecessary noise.



Summarize:

• Noise is a collection of random numbers, usually lined up or grid.
• In procedural generation, you often need to add noise to create variations.
• The simple selection of random numbers (whether important or homogeneous) leads to noise, in which each number is not associated with those around it.
• Often we need noise with certain characteristics, for example, getting the mountains near the hills.
• There are many ways to create noise.
• Some noise functions create noise directly, others take existing noise and modify it.

Selection of the noise function is often a process of trial and error. Understanding the nature of the work of noise and how to modify it allows you to make a more meaningful choice.

3. Creating noise

In the previous section, we chose noise with random numbers as output and then smoothed them out. This is the standard pattern: start with a noise function that uses random numbers as parameters . We used it when a random number chose the location of the treasure, and then we used another, where random numbers would select valleys / hills / mountains. You can modify the existing noise to change its shape according to the requirements. We modified the noise / valley / hill / mountain noise function, smoothing it out. There are many different ways to modify noise functions.



Examples of simple 1D / 2D noise generators:

1. Use random numbers directly for output. So we did for valleys / hills / mountains.
2. Use random numbers as parameters for the sines and cosines that are used for output.
3. Use random numbers as parameters for gradients that are used for output. This principle is used in the noise of Perlin.

Here are some standard noise modification methods:

1. Apply a filter to reduce or enhance certain characteristics. For valleys / hills / mountains, we used anti-aliasing to reduce jumps, increase areas of valleys, and create mountains near hills.
2. Add several noise functions at the same time, usually with a weighted sum, so that the influence of each noise function on the final result can be controlled.
3. Interpolate between the noise values ​​obtained by the noise function to generate smoothed areas.

There are so many ways to create noise!



To some extent it does not matter how the noise was created. This is interesting, but when used in a game you need to focus on two aspects:

1. How will you use the noise?
2. What properties do you need from the noise function in each case?

4. Ways to use noise

The most straightforward way to use the noise function is to use it directly as a height. In the example above, I generated valleys / hills / mountains, causing random(1,3) at each point on the map. The noise value is directly used as a height.



The use of midpoint displacement noise or Perlin noise are also examples of direct use.



Another way to use noise is to use it as an offset from the previous value. For example, if the noise function returns [2, -1, 5] , then we can assume that the first position is 2, the second is 2 + -1 = 1, and the third is 1 + 5 = 6. See also "random walk" . You can do the opposite, and use the difference between the values ​​of noise. This can also be perceived as a modification of the noise function.



Instead of using noise to set heights, you can use it for audio.



Or to create forms. For example, you can use noise as the radius of the graph in polar coordinates. You can convert a 1D noise function, such as this to polar form, by using the output as a radius, not an altitude. It shows how the same function looks in polar form.



Or you can use noise as a graphic texture. Perlin's noise is often used for this purpose.



Noise can be applied to select locations of objects, such as trees, gold mines, volcanoes, or earthquake cracks. In the example above, I used a random number to select the location of the treasure chest.



You can also use noise as a threshold function. For example, you can accept that at any time when the value is above 3, one event occurs, otherwise something else happens. One example of this is the use of 3D Perlin noise to generate caves. It can be assumed that everything is above a certain density threshold, and everything below this threshold is open air (a cave).



In my polygon map generator, I used various methods of using noise, but in none of them noise was used directly to determine the height:

1. The structure of the graph is easiest when using a grid of squares or hexagons (in fact, I started with a grid of hexagons). Each mesh element is a polygon. I wanted to add randomness to the grid. This can be done by moving the points randomly. But I needed something more random. I used the blue noise generator to place polygons and the Voronoi diagram for reconstructing. It would take much more time, but, fortunately, I had a library ( as3delaunay ), which did everything for me. But I started with the grid, which is much simpler, and I recommend you to start with it.
2. The coastline is a way to separate land from water. I used two different ways to generate it using this noise, but you can also ask the designer to draw the form yourself, and I demonstrated it using square and rounded shapes. The radial shape of the coastline is a noise function that uses sines and cosines, which draws them in polar form. The Pearlline shoreline is a noise generator that uses Perlin noise and radial return as a threshold. Any number of noise functions can be used here.
3. The sources of the rivers are randomly located.
4. Borders between polygons change from straight lines to noisy lines. This is similar to midpoint displacement, but I scaled them so that they fit into the boundaries of the polygons. This is a purely graphical effect, so the code is in the GUI ( mapgen.as ) instead of the basic algorithm ( Map.as ).

Most guides use noise fairly straightforwardly, but there are many more ways to use it.

5. Noise frequency

Frequency is the most important property that we are interested in. The easiest way to understand it is to look at sinusoids. Here is a sinusoid with a low frequency, followed by a sinusoid with a medium frequency, and at the end is a sinusoid with a high frequency:

 print_chart(0, [math.sin(i*0.293) for i in range(mapsize)]) 

 print_chart(0, [math.sin(i*0.511) for i in range(mapsize)]) 

 print_chart(0, [math.sin(i*1.57) for i in range(mapsize)]) 

As you can see, low frequencies create wide hills, and high frequencies narrower ones. Frequency describes the horizontal size of the graph; amplitude describes the vertical size. Remember, I said earlier that the valleys / hills / mountains maps look "too random" and wanted to create wider areas of valleys or mountains? In essence, I needed a low frequency of variation.



If you have a continuous function, for example, sin , which creates noise, then increasing the frequency means multiplying the input data by some factor: sin(2*x) will double the frequency sin(x) . Increasing amplitude means multiplying the output by a factor: 2*sin(x) will double the amplitude of sin(x) . In the code above, you can see that I changed the frequency by multiplying the input data with different numbers. We use amplitude in the next section, when summing several sine waves.







All of the above applies to 1D, but the same thing happens in 2D. Look at Figure 1 on this page . You see examples of 2D noise with a large wavelength (low frequency) and a small wavelength (high frequency). Note that the higher the frequency, the smaller the individual fragments.



When they talk about frequency, wavelength or octaves of the noise functions, this is what is meant, even if sinusoids are not used.



Speaking of sinusoids, you can do funny things by combining them in strange ways. For example, here are the low frequencies on the left and the high frequencies on the right:

 print_chart(0, [math.sin(0.2 + (i * 0.08) * math.cos(0.4 + i*0.3)) for i in range(mapsize)]) 

Usually at the same time you will have a lot of frequencies, and no one will give the right answers about the choice you need. Ask yourself: what frequencies do I need? Of course, the answer depends on how you plan to use them.

6. noise colors

The “color” of noise determines the types of frequencies that it contains.



All frequencies are equally affected by white noise . We already worked with white noise when we chose from 1, 2 and 3 to designate valleys, hills and mountains. Here are 8 sequences of white noise:

 for i in range(8): random.seed(i) print_chart(i, [random.uniform(-1, +1) for i in range(mapsize)]) 

In red noise (also called Brownian), low frequencies are more prominent (they have high amplitudes). This means that in the output data there will be longer hills and valleys. Red noise can be generated by averaging the neighboring white noise values. Here are the same 8 examples of white noise, but subjected to the averaging process:

 def smoother(noise): output = [] for i in range(len(noise) - 1): output.append(0.5 * (noise[i] + noise[i+1])) return output for i in range(8): random.seed(i) noise = [random.uniform(-1, +1) for i in range(mapsize)] print_chart(i, smoother(noise)) 

If you look closely at any of these eight examples, you will notice that they are smoother than the corresponding white noise. Intervals of large or small values ​​are longer.



Pink noise is between white and red.It often occurs in nature, and is usually suitable for landscapes: large hills and valleys, plus a small relief over the landscape.



On the other side of the spectrum is purple noise. In it, high frequencies are more noticeable . Violet noise can be generated by taking the difference in neighboring white noise values. Here are the same 8 examples of white noise subjected to the subtraction process:

 def rougher(noise): output = [] for i in range(len(noise) - 1): output.append(0.5 * (noise[i] - noise[i+1])) return output for i in range(8): random.seed(i) noise = [random.uniform(-1, +1) for i in range(mapsize)] print_chart(i, rougher(noise)) 

, , . / , .



. : , , . . . , .



, , . , . .



:

• — , , , .
• — . . .
• , , — , .
• .
• .

7.

«» «» . . . .



— , . , , noise , freq . , 1000 2000 , , noise(1000) + 0.5 * noise(2000) .



, sine , , , .

 def noise(freq): phase = random.uniform(0, 2*math.pi) return [math.sin(2*math.pi * freq*x/mapsize + phase) for x in range(mapsize)] for i in range(3): random.seed(i) print_chart(i, noise(1)) 

That's all. — , ( ). , .



. 8 1, 2, 4, 8, 16, 32 ( ). (. amplitudes ) . :

 def weighted_sum(amplitudes, noises): output = [0.0] * mapsize # make an array of length mapsize for k in range(len(noises)): for x in range(mapsize): output[x] += amplitudes[k] * noises[k][x] return output 

noise weighted_sum :

 amplitudes = [0.2, 0.5, 1.0, 0.7, 0.5, 0.4] frequencies = [1, 2, 4, 8, 16, 32] for i in range(10): random.seed(i) noises = [noise(f) for f in frequencies] sum_of_noises = weighted_sum(amplitudes, noises) print_chart(i, sum_of_noises) 

, , , .



[1.0, 0.7, 0.5, 0.3, 0.2, 0.1] ? :







[0.1, 0.1, 0.2, 0.3, 0.5, 1.0] ? , :







, — , 15 . .



:

• .
• You can create noise by taking a weighted sum of other noise functions that have different frequencies.
• You can select noise characteristics by choosing weights for a weighted amount.

8. Generating a rainbow

Now that we can generate noise by mixing noise with different frequencies together, let's look at the noise color again.



Again, go to the Wikipedia page about the colors of noise . Notice that there is a frequency spectrum . He tells us about the amplitude of each frequency present in the noise. White noise - flat, pink and red tilted down, blue and purple rise up.



The frequency spectrum is correlated with our arrays frequenciesand amplitudesfrom the previous section.



Previously, we used frequencies that are powers of two. Different types of color noise have much more frequencies, so we need a larger array. For this code, instead of the powers of two (1, 2, 4, 8, 16, 32) I am going to use all the whole frequencies from 1 to 30. Instead of recording the amplitudes manually, I will write a function amplitude(f)that returns the amplitude of any given frequency and creates an array of these data amplitudes.



We can again use the weighted_sumand functions noise, but now instead of a small set of frequencies, we will have a longer array:

 frequencies = range(1, 31) # [1, 2, ..., 30] def random_ift(rows, amplitude): for i in range(rows): random.seed(i) amplitudes = [amplitude(f) for f in frequencies] noises = [noise(f) for f in frequencies] sum_of_noises = weighted_sum(amplitudes, noises) print_chart(i, sum_of_noises) random_ift(10, lambda f: 1) 

In this code, the function amplitudedefines the form. If it always returns 1, then we get white noise. How to generate other colors of noise? I will use the same random seed number, but I will use another amplitude function for it:

8.1.

 random_ift(5, lambda f: 1/f/f) 

8.2.

 random_ift(5, lambda f: 1/f) 

8.3.

 random_ift(5, lambda f: 1) 

8.4.

 random_ift(5, lambda f: f) 

8.5.

 random_ift(5, lambda f: f*f) 

8.6.

, . .

• — f^-2
• — f^-1
• — f^0
• — f^+1
• — f^+2

[ ], , 8.1-8.5 .



:

• .
• (), f^c.
• , .

9.

To generate different colors of noise, we forced the amplitudes to follow simple power-law functions with different exponents. But we are not limited to these forms. This is the simplest pattern, displayed on logarithmic graphics with straight lines. Perhaps there are other sets of frequencies that create interesting patterns for our needs. You can use an amplitude array and customize them as you like, instead of using a single function. It's worth exploring, but I haven't done it yet.



What we did in the previous section can be thought of as Fourier series . The basic idea is that any continuous function can be represented as a weighted sum of sine waves and cosine waves. Depending on the chosen scales, the appearance of the final function changes. . /. , «» .



; . . , . .



.



There is an explanation of how the Fourier transform works. The diagrams on this page are interactive — you can enter the strength of each frequency, and the page will show how they are combined. By combining sinusoids, you can get a lot of interesting shapes. For example, try entering the Cycles input field 0 -1 0.5 -0.3 0.25 -0.2 0.16 -0.14and unchecking the Parts box. True, it looks like a mountain? In the Appendix (Appendix) of this page there is a version that shows how the sinusoids look in polar coordinates.



One example of using the Fourier transform to generate maps is to use a frequency synthesis technique to generate a landscape.Paul Bourke, who first generates two-dimensional white noise, then transforms it into frequencies using the Fourier transform, then gives it a form of pink noise, and then transforms it back using the inverse Fourier transform.



My little experience of experiments with 2D shows that everything is not so straightforward in it as in 1D. If you want to look at my unfinished experiments, scroll to the end of this page and move the sliders .

10. Other noise functions

. . . , , , 15 .



, . , :

• , midpoint displacement , . , . , - ( , ), - , . .
• Diamond square — midpoint displacement, , midpoint displacement.
• /- . , .
• , () .
• - midpoint displacement. .
• . . (Paul Bourke) (Frequency Synthesis) 2D-, .

- , , . , midpoint displacement, , - , - , .



.

• , . , , , .
• — . , . . , .
• . , .
• , , , .

, , . , , , , , , .

11.

. . , , , , .



2D , , . 3D- .



, :

• libnoise , ,
• , ,
• ,
• green_meklar reddit
• Math/StackExchange
• (Stefan Gustavson) , , , , -
• ,
• (Julius Smith) ,
• Notch' Minecraft — , , ,
• 3D-
• 2D- — 2D- 2D- 4D-