4 ms·

Terrain Generation with Midpoint Displacement

68 points by stevelosh 11y ago

jchung 11y ago
Live demos were definitely helpful. Nicely done tutorial!
teddyh 11y ago
$ man triangle NAME triangle - random mountains using iterative subdivision of triangles. […] $ /usr/lib/xscreensaver/triangle
smrtinsert 11y ago
This reminds me, does wisp work on Windows yet?
kazinator 11y ago
(defn safe-average [a b c d] (let [total 0 count 0] (when a (add! total a) (inc! count)) (when b (add! total b) (inc! count)) (when c (add! total c) (inc! count)) (when d (add! total d) (inc! count)) (/ total count))) Doesn't appear so safe against division by zero!
- whitegrape 11y ago
  The demo and step by step blog is great but there is some really bad code in it... Is it idiomatic Wisp to keep the surface-level syntax of Clojure but none of the important bits like immutability and abstractions?
munificent 11y ago
I remember learning about midpoint displacement as a teen and having its recursive implementation blow my mind. At the time, I don't think I could ever implement it correctly because, like Steve notes here, most explanations really elide about bunch of details around how you do it. In particular, they aren't clear how you do two "stages" of midpoints: corners to sides, then sides to center. Much later, I got it working, but I was disappointed with the visible seams it tends to lead to. After some trial and error, I came up with an algorithm I liked better for the game I was trying to write at the time. I thought it was cool enough that I wrote a little tutorial. It's the very first piece of writing I ever put on the web, I think. It's still online (though, alas, I lost my old robot-frog.com domain ages ago): http://stuffwithstuff.com/robot-frog/3d/hills/index.html http://stuffwithstuff.com/robot-frog/3d/hills/index.html
- robohamburger 11y ago
  I had a similar experience writing a terrain engine using the quake gl mini-drivers. That was a fun summer! I never managed to make an actual game out of it though... It seems like these days at least a noise function like perlin or simplex are far better. I doubt I would have understood those at the time though.
jacquesm 11y ago
If this stuff interests you there is a nice book called the fractal geometry of nature that has some interesting techniques. http://www.amazon.com/Science-Fractal-Images-Heinz-Otto-Peitgen/dp/1461283493 http://www.amazon.com/Science-Fractal-Images-Heinz-Otto-Peit...
daraosn 11y ago
Thanks for sharing, this is very nicely documented. Funny fact: it can be used as Grass Generator Exponent: 7 Starting Spread: 35.3 Spread Reduction Constant: 20.5
jokoon 11y ago
So is this a variant of this https://en.wikipedia.org/wiki/Diamond-square_algorithm https://en.wikipedia.org/wiki/Diamond-square_algorithm Or is this exactly this algorithm? > The diamond step. For each square in the array, set the midpoint of that square to be the average of the four corner points plus a random value. > The square step. For each diamond in the array, set the midpoint of that diamond to be the average of the four corner points plus a random value. Seems pretty straightforward. If you couple this with a deterministic random function, you could generate a terrain which always is the same, so that would make multiplayer possible. That's obviously what you would want in game which is very large, without having a game which is too large to download.

68 points by stevelosh 11y ago

Live demos were definitely helpful. Nicely done tutorial!

$ man triangle NAME triangle - random mountains using iterative subdivision of triangles. […] $ /usr/lib/xscreensaver/triangle

smrtinsert 11y ago

This reminds me, does wisp work on Windows yet?

kazinator 11y ago

(defn safe-average [a b c d] (let [total 0 count 0] (when a (add! total a) (inc! count)) (when b (add! total b) (inc! count)) (when c (add! total c) (inc! count)) (when d (add! total d) (inc! count)) (/ total count))) Doesn't appear so safe against division by zero!

whitegrape 11y ago
The demo and step by step blog is great but there is some really bad code in it... Is it idiomatic Wisp to keep the surface-level syntax of Clojure but none of the important bits like immutability and abstractions?

munificent 11y ago

I remember learning about midpoint displacement as a teen and having its recursive implementation blow my mind. At the time, I don't think I could ever implement it correctly because, like Steve notes here, most explanations really elide about bunch of details around how you do it. In particular, they aren't clear how you do two "stages" of midpoints: corners to sides, then sides to center. Much later, I got it working, but I was disappointed with the visible seams it tends to lead to. After some trial and error, I came up with an algorithm I liked better for the game I was trying to write at the time. I thought it was cool enough that I wrote a little tutorial. It's the very first piece of writing I ever put on the web, I think. It's still online (though, alas, I lost my old robot-frog.com domain ages ago): http://stuffwithstuff.com/robot-frog/3d/hills/index.html http://stuffwithstuff.com/robot-frog/3d/hills/index.html

robohamburger 11y ago
I had a similar experience writing a terrain engine using the quake gl mini-drivers. That was a fun summer! I never managed to make an actual game out of it though... It seems like these days at least a noise function like perlin or simplex are far better. I doubt I would have understood those at the time though.

jacquesm 11y ago

If this stuff interests you there is a nice book called the fractal geometry of nature that has some interesting techniques. http://www.amazon.com/Science-Fractal-Images-Heinz-Otto-Peitgen/dp/1461283493 http://www.amazon.com/Science-Fractal-Images-Heinz-Otto-Peit...

daraosn 11y ago

Thanks for sharing, this is very nicely documented. Funny fact: it can be used as Grass Generator Exponent: 7 Starting Spread: 35.3 Spread Reduction Constant: 20.5

jokoon 11y ago

So is this a variant of this https://en.wikipedia.org/wiki/Diamond-square_algorithm https://en.wikipedia.org/wiki/Diamond-square_algorithm Or is this exactly this algorithm? > The diamond step. For each square in the array, set the midpoint of that square to be the average of the four corner points plus a random value. > The square step. For each diamond in the array, set the midpoint of that diamond to be the average of the four corner points plus a random value. Seems pretty straightforward. If you couple this with a deterministic random function, you could generate a terrain which always is the same, so that would make multiplayer possible. That's obviously what you would want in game which is very large, without having a game which is too large to download.