#+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
#+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