#+date: <2013-08-31> #+options: toc:1 #+property: header-args :results output :exports both :wrap export html :cache yes #+title: Noise Functions and Map Generation #+filetags: procgen noise #+property: preamble from noise import * #+comment: for some reason setting the preamble at the buffer level doesn't work #+begin_export html #+end_export As I was studying audio signal processing, my brain started making connections back to procedural map generation. So here are some notes on how signal processing concepts relate to map generation. I don't think any of this is new but some of it is new to me, so I wanted to write it down and share. I only cover simple topics (frequency, amplitude, colors of noise, uses of noise) and not related topics (discrete vs continuous functions, FIR/IIR filters, FFT, complex numbers). The math on this page is mostly sine waves. *This page is about the concepts* starting from the simplest ideas and working up. If you want to skip ahead to terrain generation using noise functions, see [[../../maps/terrain-from-noise/][my other article]]. I'm going to start with the basics of using random numbers and work my way up to explaining how 1D landscapes work. The same concepts work for 2D (see *[[./2d/][demo]]*) and 3D. *Try moving this slider* to see how a single parameter can describe many different styles of noise: #+begin_export html
0
1
2
3
4
Exponent: =
#+end_export This article covers: - how to generate landscapes like these in under 15 lines of code - what red, pink, white, blue, and violet noise are - how you can use noise functions for procedural map generation - how midpoint displacement, Simplex/Perlin noise, and fBm fit in I also have some 2D noise experiments, including 3D visualization of a 2D heightmap. * Why is randomness useful? :PROPERTIES: :CUSTOM_ID: randomness :END: What we're trying to do with procedural map generation is to generate a set of outputs that have /some/ things in common and /some/ things different each time. For example, all the maps in Minecraft have a lot of similarities: the set of biomes, the size of the grid, the average sizes of biomes, the heights, the average sizes of caves, the percentage of each type of rock, and so on. But they also have some differences: where the biomes are placed, the location and exact shapes of caves, the placement of gold, and so on. As a designer, you need to decide which aspects are the same and which aspects will vary, and how they will vary. For the parts that vary, you'll typically use a random number generator. Let's make an /extremely/ simple map generator: it will generate a line of 20 blocks, and one of the blocks will contain a gold treasure chest. Let's write out some maps that we might like to see ("x" marks the treasure): #+BEGIN_EXAMPLE map 1 ........x........... map 2 ...............x.... map 3 .x.................. map 4 ......x............. map 5 ..............x..... #+END_EXAMPLE Note how much these maps have in common: they're all made of blocks, the blocks are in a line, the line is 20 blocks long, there are two types of blocks, there is exactly one gold treasure chest. But there is one thing that varies: where the block is. It can be anywhere from position 0 (leftmost) to position 19 (rightmost). We can use a random number to choose the location of that block. The simplest thing to do is to use a /uniform random selection/ from 0 to 19. That means every location from 0 to 19 is equally likely to be chosen. Most languages will include some function to generate random numbers uniformly. In Python it's =random.randint(0,19)= but I'll write =random(0,19)= in these notes. Here's some Python code: #+begin_comment NOTE TO SELF if you re-run this code make sure the output "looks" random. Sometimes things are actually random but look like they have a pattern. #+end_comment #+BEGIN_SRC python :preamble from noise import * def gen(): map = [0] * 20 # make an empty map pos = random.randint(0, 19) # pick a spot map[pos] = 1 # put the treasure there return map for i in range(5): # make 5 different maps print_chart(i, gen()) #+END_SRC #+results: #+BEGIN_export html
0
1
2
3
4
#+END_export But suppose we wanted maps that had the treasures more likely to be on the left than the right? To do this we would use a /non-uniform random selection/. There are lots of ways to do this. One way is to choose a random number uniformly, then move it towards the left. For example, we might try =random(0,19)/2=. Here's some Python code for that: #+BEGIN_SRC python :preamble from noise import * 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()) #+END_SRC #+results: #+BEGIN_export html
0
1
2
3
4
#+END_export However, that's not quite what I want. I want treasures to sometimes be on the right, but more often on the left. Another way to move treasures to the left is to square the number, with something like =sqr(random(0,19))/19=. If it's 0, then 0 squared divided by 20 is 0. If it's 19, then 19 squared divided by 19 is 19. But in between, if it was 10, then 10 squared divided by 19 is 5. We've kept the range from 0 to 19, but we've moved the middle numbers like 10 over to the left. This kind of redistribution is a very useful technique on its own, and I've used square and square root and other functions in past projects. ([[https://easings.net/][This site]] has some common reshaping functions used for animations; hover over a function to see the demo.) Here's Python code that uses squaring: #+BEGIN_SRC python :preamble from noise import * 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()) #+END_SRC #+results: #+BEGIN_export html
1
2
3
4
5
#+END_export Yet another way to move things to the left is to first randomly choose a range limit, then randomly choose a number from 0 to the range limit. If the range limit were 19 then we could get a number anywhere. If the range limit were 10 then we only get numbers on the left half. Here's some Python code: #+BEGIN_SRC python :preamble from noise import * 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()) #+END_SRC #+RESULTS: #+BEGIN_export html
0
1
2
3
4
#+END_export There are lots of tricks for taking /uniform/ random numbers and turning them into /non-uniform/ random numbers that have the properties you want. As the game designer you get to choose the distribution of the random numbers you want. I've written an article about [[https://www.redblobgames.com/articles/probability/damage-rolls.html][how to use random numbers for damage in role-playing games]] where I give a bunch of tricks like this. To review: - For procedural generation we have to decide what will stay the same and what will change. - Random numbers are useful for filling in the parts that change. - Uniformly chosen random numbers are what most programming languages give us, but we often will want non-uniformly chosen numbers. There are many ways of getting them. * What is noise? :PROPERTIES: :CUSTOM_ID: noise :END: Noise is a series of random numbers, typically arranged in a line or a grid. In old TV sets, if you tuned to a channel that didn't have a station, you'd see random black and white dots on the screen. That's noise (from outer space!). On radios, if you tune to a channel that doesn't have a station, you hear noise (I'm not sure if this comes from space or elsewhere). In signal processing, noise is typically the unwanted aspect. In a noisy room it's harder to hear someone than in a quiet room. Audio noise is random numbers arranged in a line (1D). In a noisy image it's harder to see a pattern than in a clean image. Image noise is random numbers arranged in a grid (2D). You can also have noise in 3D, 4D, etc. Although in most applications you're trying to /subtract/ the noise, a lot of natural systems look noisy, so if you're trying to procedurally generate something that looks natural, you typically want to /add/ noise. Although real systems look noisy there's usually an underlying structure; the noise we add won't have that same structure, but it's much simpler than programming the simulation, so we use it and hope the end user doesn't notice. This is a tradeoff that I'll talk about later. Let's look at a simple example of where noise is useful. Let's say we have a 1D map as before, but instead of a single treasure chest, we want to create a landscape of valleys, hills, and mountains. Let's start by using a uniform random selection at each location. If =random(1,3)= is 1 we'll set it to a valley, if 2 set it to hills, and if 3 set it to mountains. I'm using random numbers to create a /height map/: at each location in the array, I store the height of the landscape. Here's Python code to create the landscape: #+BEGIN_SRC python :preamble from noise import * for i in range(5): random.seed(i) # give the same results each run print_chart(i, [random.randint(1, 3) for i in range(mapsize)]) # note: I'm using Python's list comprehension syntax: # output = [abc for x in def] # is shorthand for: # output = [] # for x in def: # output.append(abc) #+END_SRC #+RESULTS: #+BEGIN_export html
0
1
2
3
4
#+END_export Hm, these maps look "too random" for our needs. Maybe we'd like larger areas of valleys or hills, and we'd also like mountains to be less common than valleys. Earlier we saw that uniform selection of random numbers may not be what we want; there are times we want non-uniform selection. Can that help here? We could use some random selection where valleys are more likely than mountains: #+BEGIN_SRC python :preamble from noise import * for i in range(5): random.seed(i) print_chart(i, [random.randint(1, random.randint(1, 3)) for i in range(mapsize)]) #+END_SRC #+RESULTS: #+BEGIN_export html
0
1
2
3
4
#+END_export That decreases the number of mountains but doesn't really show any interesting patterns. The problem is that non-uniform random selections change what happens in each location /in isolation/ but instead we want something where the random selection in one location is related to to the random selections in nearby locations. This is called "coherence". That's where noise functions come in. They give us a /set/ of random numbers instead of one at a time. Here we want a 1D noise function to give us a sequence. Let's try a noise function that modifies a sequence of uniformly selected random numbers. There are lots of ways to do this but let's take the minimum of two adjacent numbers. If the original noise was 1, 5, 2, then the minimum of (1, 5) is 1, and the minimum of (5, 2) is 2. So the resulting noise will be 1, 2. Note that it removed the high point (5). Also note that the resulting noise has one fewer value than the original. That means when we generate 60 random numbers below we will only get 59 out. Let's apply this function to the first set of maps: #+BEGIN_SRC python :preamble from noise import * 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)) #+END_SRC #+RESULTS: #+BEGIN_export html
0
1
2
3
4
#+END_export Compared to the previous maps we made, these have larger areas of valleys, hills, or mountains. Mountains are often near hills. And because of the way we modified the noise (by taking the min), valleys are more common than mountains. If we had taken the max, mountains would be more common than valleys. If we had wanted neither valleys nor mountains more common, we could've taken the average instead of min or max. We now have a noise modification routine that can take some noise and make some new, smoother noise. Hey, let's run it again! #+BEGIN_SRC python :preamble from noise import * def adjacent_min(noise): # same as before 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))) #+END_SRC #+RESULTS: #+BEGIN_export html
0
1
2
3
4
#+END_export Now our maps are even smoother and there are even fewer mountains. I think we've smoothed too much, since we're not seeing mountains near hills very often. So maybe it's better go back to one level of smoothing in this example. This is a common process with procedural generation: you try something and see whether it looks right, and if not, you change it back or try something else. Side note: smoothing is called a [[https://en.wikipedia.org/wiki/Low-pass_filter][low-pass filter]] in signal processing. It's sometimes used to remove unwanted noise. To review: - Noise is a set of random numbers, usually arranged in a line or grid. - In procedural generation we often want to add noise to produce variation. - Simply picking random numbers (whether uniformly or non-uniformly) leads to noise that has each number unrelated to its surroundings. - We often want noise with some characteristics, like having mountains be near hills. - There are lots of ways to make noise. - Some noise functions produce noise directly; others take existing noise and modify it. Picking a noise function sometimes takes guesswork. Understanding how noise works and how you can modify it means you can make more educated guesses. * Making noise :PROPERTIES: :CUSTOM_ID: making :END: In the previous section we chose noise by using random numbers as the output, then smoothing them. This is a common pattern. You start with a noise function that uses random numbers as /parameters/. We used one where the random number picked where the gold was, and then we used another one where the random number selected valleys/hills/mountains. You can then /modify/ existing noise to shape it to your needs. We modified the valleys/hill/mountain noise function by smoothing it. There are lots of other ways to modify noise functions. Some of the basic 1D/2D noise generators are: 1. Use random numbers directly for the output. This is what we did for valleys/hills/mountains. 1. Use random numbers as parameters for sines and cosines, which are used for the output. 1. Use random numbers as parameters for gradients, which are used for the output. This is used in Simplex/Perlin Noise. Some of the common ways to modify noise are: 1. Apply a filter to reduce or amplify certain characteristics. For valleys/hills/mountains we used smoothing to reduce the bumpiness, increase the size of valleys, and make mountains occur near valleys. 1. Add multiple noise functions together, typically with a weighted sum so that we can control how much each noise function contributes to the total. 1. Interpolate between the noise values the noise function gives us, to generate smooth areas. There are /so many ways/ to make noise! To some extent it doesn't matter how the noise was made. It's interesting but when using it in a game, focus on two things: 1. How are you going to /use/ the noise? 1. For each use, what /properties/ do you want from your noise function? * Ways to use noise :PROPERTIES: :CUSTOM_ID: uses :END: The most straightforward way to use a noise function is to use it directly as elevation. In an earlier example I generated valleys/hills/mountains by calling =random(1,3)= at each location on the map. The noise value is directly used for the elevation. Using midpoint displacement noise or Simplex/Perlin noise as elevations are also direct uses. Another way to use noise is as a movement from a previous value. For example, if the noise function returns =[2, -1, 5]= then you can say the first position is 2, the second is 2 + -1 = 1, and the third position is 1 + 5 = 6. Also see [[https://en.wikipedia.org/wiki/Random_walk]["random walk"]]. You could also do the inverse, and use the differences between noise values. You can also think of this as a modification of a noise function. Instead of using noise for elevation you might be using it for audio. Or maybe you're using it to make a shape. For example, you can use noise as a radius in a polar plot. You can convert a 1D noise function like [[https://www.wolframalpha.com/input?i=plot+y%3Dmax%280.4+%2B+0.3+cos%281.313+%2B+7+x+%2B+0.5+*+sin%2819+x%29%29%2C+0.7+-+0.3+sin%282.473+%2B+3+x+-+sin%287+x%29%29%29][this]] into a polar form by using the output as a radius instead of as an elevation. [[https://www.wolframalpha.com/input?i=polar+plot+r%3Dmax%280.4+%2B+0.3+cos%281.313+%2B+7+theta+%2B+0.5+*+sin%2819+theta%29%29%2C+0.7+-+0.3+sin%282.473+%2B+3+theta+-+sin%287+theta%29%29%29][Here]] is what that same function looks like in polar form. Or you might be using noise as a graphical texture. Simplex/Perlin noise is often used for this. You might use noise to choose the locations of objects, such as trees or gold mines or volcanos or earthquake fault lines. In an earlier example, I used a random number to choose the location of the treasure chest. You might use noise as a /threshold/ function. For example, you can say that any time the value is greater than 3, then one thing happens, otherwise something else happens. One example of this is using 3D Simplex/Perlin noise to generate caves. You can say that anything above a certain density threshold is solid earth and anything below that threshold is open air (cave). In my [[http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/][polygon map generator]] I had several different uses of noise, but none of them were directly using noise for elevation: 1. The graph structure is simplest as a square grid or a hexagonal grid (and in fact I started with a hex grid). Each tile in a grid is a polygon. I wanted to add some randomness to the grid. You can do that by randomly moving the points around. I wanted something slightly more random. I used a /blue noise/ generator to position the polygons, and Voronoi to reconstruct them. This is a lot more work but fortunately I had a library (=as3delaunay=) that did all the work. But I started with a grid, which is much easier, and that's what I recommend starting with. 1. The coastline is a way to divide land from water. I have two different ways to generate this with noise, but you could also have a designer draw the shape directly, and I demonstrated that with the square and blob shapes. The radial coastline shape is a noise function that uses sines and cosines, and plots them in polar form. The Simplex/Perlin coastline shape is a noise generator that uses noise and a radial dropoff as a threshold. Any number of noise functions could be used here. 1. The river sources are placed randomly. 1. The borders between polygons are changed from straight lines to noisy lines. It's similar to midpoint displacement but I scaled it to fit within the bounds of the polygons. This is a pure graphical effect, and the code is in the GUI (=mapgen.as=) instead of the core algorithm (=Map.as=). Most of the tutorials out there use noise in straightforward ways but there are /lots/ of different ways to use noise. * Frequency of noise :PROPERTIES: :CUSTOM_ID: frequency :END: Frequency is the main property we want to look at. The simplest way to understand this is with sine waves. Here's a lower frequency sine wave followed by a medium frequency sine wave followed by a high frequency sine wave: #+BEGIN_SRC python :preamble from noise import * print_chart(0, [math.sin(i*0.293) for i in range(mapsize)]) #+END_SRC #+RESULTS: #+BEGIN_export html
0
#+END_export #+BEGIN_SRC python :preamble from noise import * print_chart(0, [math.sin(i*0.511) for i in range(mapsize)]) #+END_SRC #+RESULTS: #+BEGIN_export html
0
#+END_export #+BEGIN_SRC python :preamble from noise import * print_chart(0, [math.sin(i*1.57) for i in range(mapsize)]) #+END_SRC #+RESULTS: #+BEGIN_export html
0
#+END_export You can see that lower frequencies make wider hills and higher frequencies make narrower hills. /Frequency/ describes the horizontal size of the features; /amplitude/ describes the vertical size. Remember above when I said the valley/hill/mountain maps looked "too random" and I wanted larger areas of valleys or mountains? I was essentially asking for a /lower frequency/ of variation. If you have a continuous function such as =sin= that produces the noise, then increasing the frequency means multiplying the /input/ by some factor: =sin(2*x)= will have twice the frequency of =sin(x)=. Increasing the amplitude means multiplying the /output/ by some factor: =2*sin(x)= will have twice the amplitude of =sin(x)=. In the code above you can see that I changed the frequency by multiplying the input by various numbers. We'll use the amplitude in the next section when adding together multiple sine waves. *Try changing the frequency*: #+begin_export html

Frequency:
#+end_export *Try changing the amplitude*: #+begin_export html

Amplitude:
#+end_export All of the above is for 1D but the same thing happens in 2D. Look at Figure 1 on [[http://devmag.org.za/2009/04/25/perlin-noise/][this page]]. You'll see examples of high wavelength (low frequency) and low wavelength (high frequency) 2D noise. Notice how the higher the frequency, the smaller the features. When noise functions talk about frequency or wavelength or octaves, this is what they're talking about, even when they're not using sine waves. Speaking of sine waves, you can do fun things by combining them in weird ways; in this example there are some low frequencies on the left and high frequencies on the right: #+BEGIN_SRC python :preamble from noise import * print_chart(0, [math.sin(0.2 + (i * 0.08) * math.cos(0.4 + i*0.3)) for i in range(mapsize)]) #+END_SRC #+RESULTS: #+BEGIN_export html
0
#+END_export Typically you'll have multiple frequencies at the same time, but there's no one right answer of what you should use. Ask yourself: what kinds of frequencies do you want? It depends of course on how you're using it. * Colors of noise :PROPERTIES: :CUSTOM_ID: colors :END: The "color" of noise describes what kinds of frequencies it has. In [[https://en.wikipedia.org/wiki/White_noise][white noise]] all frequencies contribute equally. We played with white noise earlier, when we picked 1, 2, or 3 to represent valleys, hills, or mountains. Here are 8 sequences of white noise: #+BEGIN_SRC python :preamble from noise import * for i in range(8): random.seed(i) print_chart(i, [random.uniform(-1, +1) for i in range(mapsize)]) #+END_SRC #+RESULTS: #+BEGIN_export html
0
1
2
3
4
5
6
7
#+END_export In [[https://en.wikipedia.org/wiki/Brownian_noise][red noise]] (also called Brownian noise) the /low/ frequencies are more prominent (have higher amplitudes). This means you'll see longer hills and valleys in the output. We can generate reddish noise by averaging adjacent values of white noise. Here are the same 8 white noise samples from above, except put through the averaging process: #+BEGIN_SRC python :preamble from noise import * 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)) #+END_SRC #+RESULTS: #+BEGIN_export html
0
1
2
3
4
5
6
7
#+END_export If you look closely at any of these 8 you'll see it's smoother than the corresponding white noise. There are longer runs of high or low values. [[https://en.wikipedia.org/wiki/Pink_noise][Pink noise]] is somewhere between white noise and red noise. It occurs in lots of places in nature, and it's often what we want for landscapes: big hills and valleys, plus small bumpiness along the terrain. On the opposite site of the spectrum, we have blue noise. The /high/ frequencies are more prominent. We can generate bluish noise by taking the difference of adjacent values of white noise. Here are the same 8 white noise samples from above, except put through the differencing process: #+BEGIN_SRC python :preamble from noise import * 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)) #+END_SRC #+RESULTS: #+BEGIN_export html
0
1
2
3
4
5
6
7
#+END_export If you look closely at any of these 8 you'll see that it's rougher than the corresponding white noise. There are fewer long runs of high/low values, and more short variations. Blue noise is often what we want for object placement: no super-dense or super-sparse areas, but a roughly even distribution of objects across the landscape. The position of rods and cones in your eye have blue noise characteristics. Blue noise might also make for a cool cityscape. Wikipedia has a [[https://en.wikipedia.org/wiki/Colors_of_noise][page where you can listen to the different colors of noise]]. The [[http://steveharoz.com/research/natural/][brain sees red noise as "natural"]], which is why we use it for terrain generation. We've seen how to generate white, reddish, and bluish noise. We'll be more precise and look at more colors of noise later on. To review: - Frequency is a property of repeating signals like sine waves, but we can look at noise this way too. - White noise is the simplest. It has all frequencies. It's uniformly chosen random numbers. - Red, pink, blue, and violet are other colors of noise that can be useful for procedural generation. - You can turn white noise into reddish noise by averaging (~+~). - You can turn white noise into bluish noise by differencing (~-~). * Combining frequencies :PROPERTIES: :CUSTOM_ID: spectrum :END: In the previous sections we looked at the "frequencies" of noise, and how there are various "colors" of noise. White noise means it has all the frequencies; pink and red have low frequencies stronger than high; blue and violet have high frequencies stronger than low. One way to generate noise that has the frequency characteristics you want is to find some way to generate noise at specific frequencies, then combine it together. For example, suppose we had a noise function =noise= that generated noise at a specific frequency =freq=. Then if you want noise that has 1000 Hz frequencies to be twice as strong as 2000 Hz frequencies, and no other particular frequencies, we could use =noise(1000) + 0.5 * noise(2000)=. Now, I admit, =sine= does not look particularly noisy, but it's easy to give it a frequency, so let's start with that and see how far we can get with it. #+BEGIN_SRC python :preamble from noise import * 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)) #+END_SRC #+RESULTS: #+BEGIN_export html
0
1
2
#+END_export So that's it. Our basic building block is a sine wave shifted sideways by a random amount (called /phase/). The only randomness here is how far we shifted it. Let's combine some noise functions together. I'm going to add 8 noise functions together, at frequencies 1, 2, 4, 8, 16, 32 (powers of two are called octaves in some of the noise functions). I'll multiply each of those noise functions by some factor (see the =amplitudes= array) and add them together. I need a way to calculate a weighted sum: #+BEGIN_SRC python :results output silent 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 #+END_SRC #+RESULTS: #+begin_export html #+end_export And now I can use the =noise= function from earlier and the new =weighted_sum= function: #+BEGIN_SRC python :preamble from noise import * 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) #+END_SRC #+RESULTS: #+BEGIN_export html
0
1
2
3
4
5
6
7
8
9
#+END_export Even though we started out with sine waves, which aren't noisy looking at all, the combination of them looks reasonably noisy, no? What if I used =[1.0, 0.7, 0.5, 0.3, 0.2, 0.1]= for the weights? That uses a lot more low frequencies and doesn't have high frequencies at all: #+BEGIN_SRC python :preamble from noise import * :exports results amplitudes = [1.0, 0.7, 0.5, 0.3, 0.2, 0.1] 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) #+END_SRC #+RESULTS: #+BEGIN_export html
0
1
2
3
4
5
6
7
8
9
#+END_export What if I used =[0.1, 0.1, 0.2, 0.3, 0.5, 1.0]= for the weights? That makes the low frequencies have very little weight and the high frequencies have much more: #+BEGIN_SRC python :preamble from noise import * :exports results amplitudes = [0.1, 0.1, 0.2, 0.3, 0.5, 1.0] 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) #+END_SRC #+RESULTS: #+BEGIN_export html
0
1
2
3
4
5
6
7
8
9
#+END_export All we've done here is a weighted sum of noise functions at different frequencies, all in under 15 lines of code, and we're able to generate a wide variety of different styles of noise. To review: - Instead of choosing an array of random numbers, we're choosing a single random number, and using it to shift a sine wave left or right. - We can make noise by taking a weighted sum of other noise functions that have different frequencies. - We can choose the characteristics of the noise by choosing the weights for the weighted sum. * Generating the rainbow :PROPERTIES: :CUSTOM_ID: rainbow :END: Now that we can generate noise by mixing together noise at different frequencies, let's revisit the colors of noise. Look again at [[https://en.wikipedia.org/wiki/Colors_of_noise][the Wikipedia page on the colors of noise]]. Notice they show the /frequency spectrum/. That tells you the amplitude of each frequency present in the noise. White noise is flat; pink and red are sloped downwards; blue and violet are sloped upwards. [NOTE: <2018-10-15> instead of amplitudes, the noise should correspond to /power/, which is the square of amplitude. I need to go back through this page and update the terminology. I think what might have confused me is that for Simplex/Perlin noise you halve the amplitude, but also skip most of the frequncies — is this equivalent to decreasing the amplitudes faster, but including all frequencies? Need to study more.] The frequency spectrum corresponds to our =frequencies= and =amplitudes= arrays from the previous section. Previously we used frequencies that were powers of two. The various types of colored noise have many more frequencies than that, so we'll need a longer array. For this code I'm going to use all integer frequencies from 1 to 30, instead of only the powers of 2 (1, 2, 4, 8, 16, 32). Instead of writing out the amplitudes by hand, I'm going to write a function =amplitude(f)= that returns the amplitude at any given frequency, and then build the =amplitudes= array from that. We can reuse the =weighted_sum= and =noise= functions from before, but this time instead of a small set of frequencies we'll have a longer array of them: #+BEGIN_SRC python :preamble from noise import * 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) #+END_SRC #+RESULTS: #+BEGIN_export html
0
1
2
3
4
5
6
7
8
9
#+END_export In the above code the =amplitude= function sets the shape. By having it always return 1, it produces white noise. How do we generate the other colors of noise? I'm going to use the same random seed but use a different amplitude function for these: ** Red noise :PROPERTIES: :CUSTOM_ID: red-noise :END: #+BEGIN_SRC python :preamble from noise import * random_ift(5, lambda f: 1/f) #+END_SRC #+RESULTS: #+begin_export html
0
1
2
3
4
#+end_export ** Pink noise :PROPERTIES: :CUSTOM_ID: pink-noise :END: #+BEGIN_SRC python :preamble from noise import * random_ift(5, lambda f: 1/math.sqrt(f)) #+END_SRC #+RESULTS: #+begin_export html
0
1
2
3
4
#+end_export ** White noise :PROPERTIES: :CUSTOM_ID: white-noise :END: #+BEGIN_SRC python :preamble from noise import * random_ift(5, lambda f: 1) #+END_SRC #+RESULTS: #+BEGIN_export html
0
1
2
3
4
#+END_export ** Blue noise :PROPERTIES: :CUSTOM_ID: blue-noise :END: #+BEGIN_SRC python :preamble from noise import * random_ift(5, lambda f: math.sqrt(f)) #+END_SRC #+RESULTS: #+begin_export html
0
1
2
3
4
#+end_export ** Violet noise :PROPERTIES: :CUSTOM_ID: violet-noise :END: #+BEGIN_SRC python :preamble from noise import * random_ift(5, lambda f: f) #+END_SRC #+RESULTS: #+begin_export html
0
1
2
3
4
#+end_export ** Colors of noise :PROPERTIES: :CUSTOM_ID: colors-of-noise :END: So that's pretty neat. You change the /exponent/ on the amplitude function to get some simple shapes. - Red noise is f^-1 - Pink noise is f^-½ - White noise is f^0 - Blue noise is f^+½ - Violet noise is f^+1 [2018-10-13] As Eric S. pointed out to me, the exponent depends on what you are looking at. If you're working with all frequencies, the exponents are -2, -1, 0, +1, +2 for the /power/, and power is the square of the amplitude. If you are working only with octaves (e.g. Simplex/Perlin noise), the exponents are -2, -1, 0, +1, +2 for the /amplitude/. I'm not 100% sure about this. *Try varying the exponent* to see how the noise from sections 8.1-8.5 are all generated from the same underlying function: #+BEGIN_SRC python :preamble from noise import * :exports none :wrap COMMENT # Capture the random numbers from python so we can reuse them in javascript # NOTE: the offsets array is at the top of the page import random, math mapsize = 60 output = [] for i in range(5): random.seed(i) output.append([random.uniform(0, 2*math.pi) for k in range(1, mapsize//2)]) print(output) #+END_SRC #+RESULTS: #+BEGIN_COMMENT
[[5.305658970563565, 4.7623679680665845, 2.642529177293657, 1.6268219212234332, 3.2124338172355777, 2.544276222803882, 4.924751778411374, 1.9057700639797035, 2.994546979776625, 3.6654974587763136, 5.705841537519793, 3.171041037198489, 1.7708394029393855, 4.74885787066523, 3.885326994325826, 1.5739777634038004, 5.7161043087612855, 6.175023263149277, 5.090745032837427, 5.668475844439693, 1.948714650604693, 4.585668117381231, 5.647567524490951, 4.297597791358023, 2.966560172624361, 0.6327243509503904, 2.7279820973144067, 3.8383160558895004, 5.736617634996921], [0.8442354444173306, 5.324583204732311, 4.798937463950548, 1.602645954842546, 3.112910459877322, 2.8242356539891067, 4.094079392473133, 4.955694971284102, 0.5897371765578201, 0.17811244797868833, 5.251267021202746, 2.7191556824922216, 4.789547014055384, 0.013232723471835035, 2.7984502736910715, 4.533569729745489, 1.4373554275242735, 5.939310945611832, 5.6638357571527225, 0.1922025319432964, 0.15988105992264706, 3.401794894179865, 5.900848220819947, 2.395176865277171, 1.3609341495950262, 2.6522366656182905, 0.18246864979933375, 1.392929820250894, 2.7513288946214995], [6.0069404902946655, 5.955375740432253, 0.3553227228019942, 0.5332664729735533, 5.249594275227985, 4.624235821840466, 4.208040218100682, 1.9360784629304766, 3.807259478762108, 3.8126477371832137, 3.6518125407918904, 0.9951489232939251, 2.7059771561264165, 2.472633350622028, 4.542818885744579, 6.250635661220641, 5.9652276872422805, 3.4191652289122776, 2.795101302439578, 1.6854062867180135, 0.2257192186114827, 0.17244112283067747, 2.921014283727804, 2.000975412179294, 2.3877041737955493, 5.6032784185243445, 3.303402074307306, 3.521790464923623, 1.483607122266542], [1.495175848572241, 3.4194930721172536, 2.3244968667700685, 3.7945415132189377, 3.9315166211756676, 0.411729965571833, 0.08273693106265005, 5.261973431845652, 1.6295693321837814, 1.4723448514658746, 6.255821001648576, 2.9547527609677817, 5.2556423006693525, 2.9930154819275123, 4.015383550953657, 0.946350902444536, 3.988947160243856, 5.454089519808953, 3.287244494072791, 4.657422771804799, 4.218602717113993, 0.40232139186544674, 4.76410114292849, 3.713988214554036, 1.892920531797506, 0.1948525811846381, 5.438268018349855, 2.9703701278854004, 4.516503918139429], [1.483133889226057, 0.6482113104784197, 2.488507330758799, 0.9737194949259602, 0.41792667187964366, 2.5232707617079666, 5.767681639380159, 5.029390454015814, 4.807658421665465, 1.3944158527465735, 3.3720599420210084, 1.7384483200229284, 1.0848832334769094, 0.6671693028737434, 1.3471176478327955, 5.827501260155898, 5.208258271311151, 5.068346172801972, 5.029362098296823, 1.2153918330236917, 1.9468446991346642, 3.939403893042249, 4.598630081229241, 5.369914005736391, 5.5295219505250435, 0.5448668508200283, 3.806679654115824, 4.220424722395433, 3.1790013296557174]]
#+END_COMMENT #+begin_export html
0
1
2
3
4
Exponent: =
#+end_export To review: - We can generate noise by a weighted sum of sine waves at different frequencies. - The various colors of noise have weights (power spectra which is the square of the amplitude) that follow a function f^c. - By changing the exponent you can get different colors of noise from the same set of random numbers. * More shapes of noise :PROPERTIES: :CUSTOM_ID: shapes :END: To generate the various colors of noise we set the amplitudes to follow a simple exponential function, with various exponents. /You aren't limited to these shapes./ This is the simplest pattern, showing up as straight lines on a log/log plot. There are probably other sets of frequencies that produce interesting patterns for our needs. You can use an array of amplitudes and set them however you want instead of using a simple function. It's something to explore but I haven't done so yet. One way to think about what we did in the previous section is in terms of [[http://www.thefouriertransform.com/#introduction][Fourier Series]]. The main idea is that any continuous function can be represented as a weighted sum of sine and cosine waves. How you assign the weights determines what the resulting function will look like. The /Fourier Transform/ connects the original function to its frequencies. Normally you start with the original data and ask it to tell you the frequencies/amplitudes. You see this in music players that show you the "spectrum" of the noise. The forwards direction lets you /analyze/ data into frequencies; the backwards direction lets you /synthesize/ data from frequencies. For noise we're mostly focused on synthesizing. In fact, we've already been doing this. In the previous section we chose some frequencies and amplitudes, and generated the noise. The Fourier Transform has tons of cool ideas and math and applications. [[https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/][This page]] has an explanation of how the Fourier Transform works. The diagrams on that page are interactive---you can enter the strength of each frequency and it will show you how they combine. You can form lots of interesting shapes by combining sine waves. For example, try entering =0 -1 0.5 -0.3 0.25 -0.2 0.16 -0.14= into the Cycles input field, and then uncheck the Parts checkbox. See how it looks like a mountain? The Appendix on that page has a version that also shows you how the sine waves look like in polar coordinates. For one use of the Fourier Transform for map generation, see Paul Bourke's [[http://paulbourke.net/fractals/noise/][Frequency Synthesis]] approach to landscape generation, which first generates 2D white noise, then converts it to frequencies using the Fourier Transform, then shapes that into pink noise, then converts back using the Inverse Fourier Transform. My limited experiments with 2D so far suggest that it's not as straightforward as the 1D scenario. If you want to take a look at my incomplete experiments, scroll down to the bottom of [[./2d/][this page]] and *play with the sliders*. * Other noise functions :PROPERTIES: :CUSTOM_ID: functions :END: In this article we've been using sine waves for generating noise. It's pretty simple. We take several functions and /add/ them together. Even though the original functions don't look noisy, the result looks pretty good, especially for 15 lines of code. I haven't studied other noise functions much, but I use them in my projects. I think a lot of them are generating pink noise: - I believe midpoint displacement is using a sawtooth wave instead of a sine wave, and then adding together higher and higher frequencies with lower and lower amplitudes. I think that's red noise. You end up with visible edges, which is either due to sawtooths (not as smooth as sine waves) or due to it only using frequencies that are a power of two instead of using all frequencies. I'm not sure. - Diamond square is a variant of midpoint displacement that attempts to somewhat hide the edges that you get with midpoint displacement. - A single octave of Simplex/Perlin Noise is generating smooth noise at a particular frequency. You typically add up several octaves of Simplex Noise together to make the noise red. - I believe Fractal Brownian Motion is also generating red noise by adding multiple noise functions together. - The [[https://www.firstpr.com.au/dsp/pink-noise/][Voss-McCartney algorithm]] seems similar to midpoint displacement. It adds up several white noise functions at different frequencies. - You can directly generate pink noise by calculating the Inverse Fourier Transform from the frequencies you want. That's what the example in the previous section did. Paul Bourke [[http://paulbourke.net/fractals/noise/][describes this as Frequency Synthesis]], and shows how it looks for 2D noise generating 3D heightmaps. Some of the pages on Voss-McCartney make me think that adding up noise at different frequencies will not exactly be red noise, but is probably close enough for map generation. The seams you get from midpoint displacement are likely from this, or maybe from the interpolation function. I don't know. I haven't found as many ways to generate blue noise. - For my polygon map generator project, I used Lloyd Relaxation with Voronoi diagrams to generate the blue noise I needed. I already had a library that gave me Voronoi diagrams, and it was easier to reuse it than to implement a separate step. - [[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.3366&rep=rep1&type=pdf][Poisson Disks]] [PDF] are another way to generate blue noise. If I don't already have a Voronoi library in the project, Poisson Disk seems simpler. Also see [[http://devmag.org.za/2009/05/03/poisson-disk-sampling/][this article]] describing some uses of it in games. - [[http://johanneskopf.de/publications/blue_noise/][Recursive Wang Tiles]] can also generate blue noise. I haven't studied these at all but hope to one day. - You should be able to directly generate blue noise by calculating the Inverse Fourier Transform from the blue noise frequency spectrum. I haven't tried this yet. - The easiest way to get blue noise is to [[http://momentsingraphics.de/BlueNoise.html][download it]]. I'm not even sure that proper blue noise is what I need for maps, but it's described as blue noise in the literature. The blue noise I'm generating with sine waves seems somewhat like what I want but the above techniques seem to better match what I want for games. * More :PROPERTIES: :CUSTOM_ID: more :END: This page was originally notes for myself, kept in Emacs org-mode. I improved the diagrams and added a few interactive ones when publishing to the web. I spent nowhere near as much time on this as I do on most of my articles, but I'm experimenting with covering some topics with less polish, in the hopes that it will allow me to write about more things. *I also have some [[./2d/][2D experiments]]* that aren't as polished as the stuff on this page, including a *3D visualization of a 2D heightmap*. Other things I haven't really investigated: - [[https://libnoise.sourceforge.net/noisegen/][The libnoise page]] has a fantastic explanation of noise and interpolation functions, including an explanation of why your interpolation function needs to have smooth derivatives - [[http://eastfarthing.com/blog/2015-04-21-noise/][This introduction to Perlin noise]] describes the theory behind Perlin and related noise functions - [[https://eev.ee/blog/2016/05/29/perlin-noise/][Another introduction to Perlin noise]] also describes the theory - [[https://www.cs.unm.edu/~brayer/vision/fourier.html][This introduction to 2D fourier transforms]] has a lot of nice images that might help you build intuition around the frequency space - [[https://www.jezzamon.com/fourier/][Interactive explanation of Fourier series]] - [[https://old.reddit.com/r/proceduralgeneration/comments/31v5bg/any_guidesresources_on_using_noise_to_create/][green_meklar on reddit]] describes ways to combine and distort noise for terrain generation - [[https://math.stackexchange.com/questions/1002/fourier-transform-for-dummies][Math/StackExchange has some descriptions of the Fourier Transform]] - [[https://weber.itn.liu.se/~stegu/TNM022-2005/perlinnoiselinks/][Stefan Gustavson has notes about Perlin Noise]], including how to make it tileable, and why you might use Simplex Noise instead - [[https://jeremykun.com/2012/07/18/the-fast-fourier-transform/][This page]] and [[http://jakevdp.github.io/blog/2013/08/28/understanding-the-fft/][this page]] explain how the Fast Fourier Transform works - [[https://web.archive.org/web/20160530124230/http://freespace.virgin.net/hugo.elias/models/m_perlin.htm][Using interpolation functions other than linear]] - [[https://sites.me.ucsb.edu/~moehlis/APC591/tutorials/tutorial7/node2.html][Weiner Process]] - [[https://en.wikipedia.org/wiki/Brownian_bridge][Brownian Bridge]] on Wikipedia - [[https://ccrma.stanford.edu/~jos/log/][Julius Smith has a more mathematical set of notes on Fourier Transforms]] especially for audio applications - [[https://www.gamedeveloper.com/legacy/view/feature/131507/a_realtime_procedural_universe_.php?print%3D1][Noise for procedural planet generation]] - [[http://www.stuffwithstuff.com/robot-frog/3d/hills/][Generating terrain with hills instead of sine waves]] - [[https://developer.nvidia.com/gpugems/gpugems3/part-i-geometry/chapter-1-generating-complex-procedural-terrains-using-gpu][Generating noise on the GPU]] - [[https://web.archive.org/web/20120209042104/https://notch.tumblr.com/post/3746989361/terrain-generation-part-1][Notch's notes about Minecraft terrain generation]]---he originally used both 2D Perlin for height and 3D Perlin for density threshold, but now uses a 2D height map and generates caves with [[http://libnoise.sourceforge.net/examples/worms/][Perlin worms]] - [[http://accidentalnoise.sourceforge.net/minecraftworlds.html][3D procedural world generation]] - [[https://www.gamedev.net/blog/33/entry-2138456-seamless-noise/][Making 2D noise functions seamless]] - use 4D noise to make tileable 2D noise, instead of using blending functions on 2D noise - [[https://www.cs.umd.edu/~zwicker/publications/AnisotropicNoise-SIG08.pdf][Anisotropic noise]] #+BEGIN_COMMENT - generate-and-test vs constraint-based Look at techniques used in http://www.dwarfcorp.com/site/2013/07/31/update-4-landmarks/ Cave building techniques in http://gamedev.tutsplus.com/tutorials/game-design/create-a-procedurally-generated-dungeon-cave-system/ example of generate-and-test Cave building techniques in http://gamedev.tutsplus.com/tutorials/implementation/cave-levels-cellular-automata/ might be more appealing to Terry (white noise followed by smoothing function) #+END_COMMENT #+begin_footer Created August 2013, updated 2018. Made with [[https://orgmode.org/][Emacs Org-mode]] from [[file:introduction.org][introduction.org]] and the helper Python file [[file:noise.py][noise.py]]. Last modified {{{modification-time(%F)}}}. #+end_footer