--- a/content/blog/2016/02/midpoint-displacement.html Fri Feb 19 19:21:41 2016 +0000
+++ b/content/blog/2016/02/midpoint-displacement.html Fri Feb 19 19:48:12 2016 +0000
@@ -5,7 +5,7 @@
{% hyde
title: "Terrain Generation with Midpoint Displacement"
snip: "A first step toward growing worlds with computers."
- created: 2016-02-19 19:30:00
+ created: 2016-02-19 19:45:00
%}
{% block extra_js %}
@@ -25,7 +25,9 @@
just finished our midterm [project][] where we played around with procedural
terrain generation in [Unity][]. It was a lot of fun and I really enjoyed
creating terrain out of numbers, so I thought I'd write up a little introduction
-to a few of the algorithms. For this post we'll look at Midpoint Displacement.
+to a few of the algorithms.
+
+In this post we'll be looking at Midpoint Displacement.
[project]: https://www.youtube.com/watch?v=G5u79w4qiAA
[Unity]: http://unity3d.com/
@@ -56,7 +58,7 @@
one][paper].
Unfortunately, while there are a *lot* of places that describe algorithms like
-this, there are relatively few that explain it thoroughly. Academic papers in
+this, there are relatively few that explain it *thoroughly*. Academic papers in
particular tend to have a really bad case of
[draw-the-rest-of-the-fucking-owl-syndrome][owl]. They tend to slap an equation
or two on the page and move on without showing any code.
@@ -73,12 +75,14 @@
describing the algorithm, but showing *actual code* that runs and generates
a terrain.
-TODO The code is at:
+The full code is [here][code], but we'll be going through the important parts
+below.
[wikipedia-ds]: https://en.wikipedia.org/wiki/Diamond-square_algorithm
[pcgw-midpoint]: http://pcg.wikidot.com/pcg-algorithm:midpoint-displacement-algorithm
[paper]: http://micsymposium.org/mics_2011_proceedings/mics2011_submission_30.pdf
[owl]: https://i.imgur.com/RadSf.jpg
+[code]: https://bitbucket.org/sjl/stevelosh/src/default/media/js/terrain1.wisp
### Wisp
@@ -86,19 +90,18 @@
dialect of Lisp that compiles down to vanilla Javascript.
I went with Javascript because it means I can actually put demos inline in this
-post. Sometimes it's so much easier to explain something when you can actually
-see it running.
+post. Sometimes it's so much easier to understand something when you can
+actually see it running.
I've tried to write the code so that it's readable even if you don't know Lisp.
The point of me showing you this code is not to give you something to copy and
paste. The point is that until you *actually write and run* the code, you don't
know all the edge cases and problems that can happen. So by making examples
-that actually run I feel a bit more confident that I'm explaining this well
-enough.
+that actually run I feel a bit more confident that I'm explaining things enough.
I haven't focused on performance at all. If you want a fast implementation of
-this, you'll probably want to use a language with real arrays (contiguous chunks
-of memory holding a bunch of unboxed floats).
+this, you'll probably want to use a language with real arrays (i.e. contiguous
+chunks of memory holding a bunch of unboxed floats or integers).
[wisp]: https://github.com/Gozala/wisp
@@ -107,19 +110,20 @@
[Three.js][three.js] is a Javascript library for 3D rendering. I'm using it
here to get something on the screen you can play with. I'm not going to cover
the code to put the terrains on the screen because it's really an entirely
-separate problem to generating terrain.
+separate problem to *generating* the terrain, and it's mostly uninteresting
+boilerplate for these little demos.
-I also haven't been able to get these demos working on my iPhone. Sorry about
-that, but I'm not much of a frontend developer. You'll have to use a computer
-to see the demos. [Pull requests][slc] are welcome.
+I haven't been able to get these demos working on my iPhone. Sorry about that,
+but I'm not much of a frontend developer. You'll have to use a computer to see
+them. [Pull requests][slc] are welcome.
[slc]: http://bitbucket.org/sjl/stevelosh/
[three.js]: http://threejs.org/
## Heightmaps
-Let's get started. The main data structure we're going to be using here is
-called a [heightmap][].
+Let's get started. The main data structure we're going to be using is
+a [heightmap][].
### Overview
@@ -152,10 +156,14 @@
using floats between zero and one because it's easy to roughly visualize them in
your head (e.g. `0.1` is ten percent of the maximum height).
-One common way to visualize heightmaps by turning them into greyscale images
+One common way to visualize heightmaps is by turning them into greyscale images
with one pixel per number, with black pixels for lowest value in the map's range
and white for the highest. The [Wikipedia article][heightmap] has an example of
-this.
+this. This is handy because you can also write some code to *read* images, and
+then you can use any image editor to draw your own heightmaps by hand.
+
+We're going to visualize the heightmaps in 3D. It's a lot more fun, and they
+start to actually look like real terrains.
[heightmap]: https://en.wikipedia.org/wiki/Heightmap
@@ -163,7 +171,7 @@
We're going to start by writing a few functions that will hide away the internal
details of how our heightmaps are implemented, so we can talk about them in
-nice, high-level terms for the rest of the program. We'll also need a couple of
+nice high-level terms for the rest of the program. We'll also need a couple of
helper functions along the way.
We'll start with something to create a heightmap:
@@ -180,7 +188,7 @@
(zero-heightmap heightmap)))
`make-heightmap` takes an exponent and creates a heightmap. For reasons that
-will become clear later all of our heightmaps will be square, and they'll need
+will become clear later, all of our heightmaps must be square, and they'll need
to have \\(2^n + 1\\) rows and columns. This means we can make heightmaps of
sizes like 3x3, 5x5, 9x9, 17x17, 33x33, etc. So our function just takes the
\\(n\\) to use and creates a correctly-sized array.
@@ -319,7 +327,7 @@
between, plus or minus a random amount.
3. Set the center of the square to the average of those edge midpoints you just
set, again with a random jitter.
-4. Recurse on the four squares inside this one.
+4. Recurse on the four squares inside this one, reducing the jitter.
That's the standard description. Now let's draw the fucking owl.
@@ -382,6 +390,8 @@
(I'm using 0 to 10 instead of 0 to 1 because it's easier to read in the
ASCII-art diagrams.)
+The code is about what you'd expect:
+
:::clojure
(defn mpd-init-corners [heightmap]
(heightmap-set! heightmap 0 0 (rand))
@@ -527,10 +537,10 @@
For the first iteration we want to work on the entire heightmap, so we pass in
`0` and `heightmap.last` for the left/right and top/bottom indices.
-<div id="demo-mpd-2" class="threejs"></div>
+Run the demo a few times and watch how the midpoints fall between the corner
+points because they're averaged (with a little bit of jitter thrown in).
-Run the demo a few times. Look at how the midpoints fall between the corner
-points because they're averaged (with a little bit of jitter thrown in).
+<div id="demo-mpd-2" class="threejs"></div>
[SICP]: http://www.amazon.com/dp/0262510871/?tag=stelos-20
[lectures]: https://youtu.be/2Op3QLzMgSY
@@ -724,16 +734,16 @@
Let's think about what's happening here.
-* On pass `0`, we break up the grid into a 1x1 set of "chunk" and displace it.
+* On pass `0`, we break up the grid into a 1x1 set of chunks and displace them (well, "it").
* On pass `1`, we break up the grid into a 2x2 set of chunks and displace them.
* On pass `2`, we break up the grid into a 4x4 set of chunks and displace them.
This 9x9 heightmap was made with an exponent of 3 (\\(2^3 + 1 = 9\\)) and we
need 3 "passes" to finish it. This isn't a coincidence -- it's the reason we
-chose our heightmap resolutions to be \\(2^n +1).
+chose our heightmap resolutions to be \\(2^n + 1\\).
-At iteration \\(i\\), we need to displace a \\(2^i\\)x\\(2^i\\) collection of
-squares.
+So at iteration \\(i\\), we need to displace a \\(2^i\\)x\\(2^i\\) collection of
+squares. Let's go:
:::clojure
(defn midpoint-displacement [heightmap]
@@ -815,7 +825,10 @@
We loop over the indices of the chunks, calculate the bounds for each one, and
displace it. Simple enough, but a bit fiddly to get right. And now we've
-finished displacing all the points:
+finished displacing all the points!
+
+We could have done this recursively, but I was in an iterative mood when I wrote
+this. Feel free to play around with it.
<div id="demo-mpd-4" class="threejs"></div>
@@ -830,17 +843,19 @@
<div id="demo-final" class="threejs"></div>
<div id="demo-final-controls">
- <label>Exponent
- <input type="number" id="input-exponent" value="5"></input>
- </label>
- <br/>
- <label>Starting Spread
- <input type="number" id="input-starting-spread" value="0.3"></input>
- </label>
- <br/>
- <label>Spread Reduction Constant
- <input type="number" id="input-spread-reduction" value="0.5"></input>
- </label>
+ <p>
+ <label>Exponent
+ <input type="number" id="input-exponent" value="5"></input>
+ </label>
+ <br/>
+ <label>Starting Spread
+ <input type="number" id="input-starting-spread" value="0.3"></input>
+ </label>
+ <br/>
+ <label>Spread Reduction Constant
+ <input type="number" id="input-spread-reduction" value="0.5"></input>
+ </label>
+ </p>
</div>
And that's it, we've grown some mountains!