12 ms·

Realistic terrain in 130 lines of JavaScript

339 points by hunterloftis 12y ago

snodgrass23 12y ago
Great tutorial on a fun topic!
elwell 12y ago
Don't miss the demo: http://www.playfuljs.com/demos/terrain/ http://www.playfuljs.com/demos/terrain/
- hughes 12y ago
  Is there any way to control the demo? It doesnt seem to respond to mouse or keyboard input.
  - krilnon 12y ago
    It only draws a single perspective, so the only control you have is to refresh the page to get a new random bit of terrain.
  - kachhalimbu 12y ago
    I made a jsfiddle and added dat.gui http://workshop.chromeexperiments.com/examples/gui/#1--Basic-Usage http://workshop.chromeexperiments.com/examples/gui/#1--Basic... so you can modify the "detail" parameter to change the terrain without requiring a page refresh http://jsfiddle.net/kachhalimbu/br8Xd/1/ http://jsfiddle.net/kachhalimbu/br8Xd/1/ Full screen result here http://jsfiddle.net/kachhalimbu/br8Xd/1/embedded/result/ http://jsfiddle.net/kachhalimbu/br8Xd/1/embedded/result/
fogleman 12y ago
Perlin noise is another good algorithm for terrain generation. http://en.wikipedia.org/wiki/Perlin_noise http://en.wikipedia.org/wiki/Perlin_noise
- hunterloftis 12y ago
  I like Perlin in situations where its repetitiveness won't negatively impact the simulation, or as an additional layer of pseudo-natural-randomness on top of other algorithms.
rgrieselhuber 12y ago
Reminds me of T'Rain.
TheyCalledHimBo 12y ago
I may just be a prick, but seeing this promoted as a variant of the midpoint displacement algorithm for terrain generation seem far less gimmicky. "X done in Y lines of Z" Whoop-dee freakin' do. Still, cool algorithm.
gavanwoolery 12y ago
Just a small note, not to sound snooty, just to educate people on what realistic terrain looks like... This is what midpoint displacement looks like as a heightmap: http://imgur.com/ksETpO0,7gykFEV#0 http://imgur.com/ksETpO0,7gykFEV#0 This is what realistic terrain looks like (this is based on real-world heightmap data): http://imgur.com/ksETpO0,7gykFEV#1 http://imgur.com/ksETpO0,7gykFEV#1 That said, midpoint displacement, perlin/simplex noise, etc are good for modeling terrain at a less macroscopic scale and are plenty sufficient for the use of most games.
- gavanwoolery 12y ago
  To add another note, as complex as real world terrain is, you can generate those fractal mountain patterns and drainage basins algorithmically with a bit of work. There are many ways to go about it, one would be recursive spacial partitioning, another would be to explicitly grow out a tree pattern while minding collision and proximity to other branches. Also, it is possible to use diffusion limited aggregation or erosion simulation but I have been down both those routes and they are not as easy to get good results with.
  - mjn 12y ago
    Further reading: 1. A semi-standard textbook on the subject, but now a bit dated (don't be fooled by the 2002 date on the 3rd ed., most of the text is from the 1st ed): http://www.amazon.com/Texturing-Modeling-Third-Edition-Procedural/dp/1558608486 http://www.amazon.com/Texturing-Modeling-Third-Edition-Proce... 2. A more recent but much shorter survey paper: http://graphics.tudelft.nl/Publications-new/2009/SDGTB09a/SDGTB09a.pdf http://graphics.tudelft.nl/Publications-new/2009/SDGTB09a/SD...
    - hunterloftis 12y ago
      Thanks for this! I've been looking for resources on building out lifelike macro-terrain-structures.
- userbinator 12y ago
  Reminds me of this - pretty good looking terrain + animation + sound in a 4 kilobyte executable: http://www.youtube.com/watch?v=_YWMGuh15nE http://www.youtube.com/watch?v=_YWMGuh15nE How it was done: http://iquilezles.org/www/material/function2009/function2009.pdf http://iquilezles.org/www/material/function2009/function2009...
the_french 12y ago
can this algorithm be run lazily? ie, can you continue to generate continuous terrain using this technique or do you need to generate the whole map ahead of time?
- hunterloftis 12y ago
  It can be run lazily in two ways: first, you can lazily add detail (ie, render down to a specific level of detail and postpone the rest); second, you can lazily build grid blocks out to the horizon (eg, for walking around a terrain first-person). So detail vs size laziness.
zhemao 12y ago
There was a Clojure example of this algorithm posted a few months back. Funnily enough, it's been in my "read later" bookmarks for a while now and I just got around to reading it this morning before I saw this post. http://blog.mediocregopher.com/clojure-diamond-square.html http://blog.mediocregopher.com/clojure-diamond-square.html
colonelxc 12y ago
Reminded me of "Polygonal Map Generation For Games": http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/ http://www-cs-students.stanford.edu/~amitp/game-programming/... past comments: https://news.ycombinator.com/item?id=3868893 https://news.ycombinator.com/item?id=3868893
- hunterloftis 12y ago
  Awesome! Thanks for the link.
nijiko 12y ago
You can simplify this even further by using frameworks like lodash / underscore or ES6 native methods.
SteveDeFacto 12y ago
Some of you might find this algorithm I created a few years ago interesting: http://ovgl.org/view_topic.php?topic=91JL96IHFS http://ovgl.org/view_topic.php?topic=91JL96IHFS
brickmort 12y ago
This is awesome!! nice job!
good-citizen 12y ago
stuff like this makes me remember why I love programming
nitrogen 12y ago
This midpoint displacement algorithm is also how a lot of the "plasma" effects from 1990s-era PC demos were created.
twistedpair 12y ago
Reminds me of the results easy to achieve with Bryce3D back in the mid 90's. They had a pretty great terrain engine. I don't think they're making Bryce any more. It would be great if they could release some of that code.
- MrBuddyCasino 12y ago
  I remember that one, apparently it is still being sold, but development seems to have stalled: http://www.daz3d.com/bryce-7-pro/ http://www.daz3d.com/bryce-7-pro/
  - twistedpair 12y ago
    I guess Maya ate their lunch. Funny, from the screenshots, they've not changed the interface in a decade and a half. The much lower price is nice, though.
callumprentice 12y ago
I made a quick first pass at an interactive WebGL version this evening. http://callum.com/sandbox/webglex/webgl_terrain/ http://callum.com/sandbox/webglex/webgl_terrain/ - ground realism needs a bit of work :) but it was a lot of fun. Thanks for sharing your code Hunter.
hixup 12y ago
I was playing with something similar a while ago. It's a procedurally generated overlay for Google Maps: http://dbbert.github.io/secondworld/ http://dbbert.github.io/secondworld/
pheelicks 12y ago
Nice demo. I made a terrain rendering engine/demo in WebGL a few months back, that used Perlin noise: http://felixpalmer.github.io/lod-terrain/ http://felixpalmer.github.io/lod-terrain/ If anyone wants to play around with Hunter's algorithm in WebGL, it should be pretty straightforward to swap out the Perlin Noise implementation for his. Note the shaders do a fractal sampling of the the height map, so you may want to disable this.
- dualogy 12y ago
  Clicking "how does this work?" leads to the HTML source of the link target to be shown in plain-text instead of being rendered. Win7, both in Chrome and Firefox.....
  - pheelicks 12y ago
    Yes, I know - my blog is ruining my morning. Quick fix is to remove the trailing slash, i.e. go to http://www.pheelicks.com/2014/03/rendering-large-terrains http://www.pheelicks.com/2014/03/rendering-large-terrains instead. If anyone using WordPress + W3TC has hit this I'd be grateful for pointers to a fix
- hunterloftis 12y ago
  I love how you're using a simple but effective dynamic LoD. I'm going to riff on this a bit with a first-person ground-level camera.
huskyr 12y ago
What i like most about this demo is that the code is actually very readable, and the blog article explains it very well. Most of the times the code for these kinds of demos looks like line noise :)
blahpro 12y ago
It'd be interesting to see an animation of the diamond/square iteration progressing in 3D, starting with a flat surface and ending with the finished terrain :)
CmonDev 12y ago
Had to put "JavaScript" into the title - typical HN... It was about algorithm rather than a language.
zimpenfish 12y ago
I remember implementing this on a Sam Coupe from the description in (either BYTE or Dr Dobbs, I forget) back in ~1987. Somewhat slower and lower resolution, of course...
good-citizen 12y ago
after thinking about this one for a while, it occurred to me that this really helps illustrate the point of 'Life May Be A Computer Simulation'. Take this world creation a step further, and rather than teaching a computer how to create rocks, each one slightly different, imagine creating humans, each one slightly different. If you think about 'God' as just some alien programmer dude, it helps make so much sense of the world. How can a caring God let so many terrible things happen to us humans? Well, how much empathy do you feel about each rock in this program? When you click refresh, and create a whole new world, do you stop and think about all the exist rocks you are 'killing'? If we are living in a computer simulation, perhaps our creator doesn't even realize we are sentient?
- saraid216 12y ago
  You realize you just explained a caring God by saying he doesn't care, right?
  - good-citizen 12y ago
    I meant, a common human question is "if there is a caring God, how can there be so much suffering in the world?" And maybe the answer is, human pain means nothing to him the same way computer generated rock pain means nothing to us.
namuol 12y ago
Brings me back to a ray casting experiment I did a while ago [1]. I always wanted to revisit it to include a terrain generation step (it uses a pregenerated height map). Now I have an excuse! ;) [1] http://namuol.github.io/earf-html5 http://namuol.github.io/earf-html5
- hunterloftis 12y ago
  Wow! Really fantastic. I've already linked to your raycaster; let me know if you build one that dynamically generates the terrain as well.
sebnukem2 12y ago
I think implementing parallel computing using webworkers would be a good item for the "What's Next" list of suggestions.
- hunterloftis 12y ago
  Added!
happywolf 12y ago
For those who only want to look at the result(s) http://www.playfuljs.com/demos/terrain/ http://www.playfuljs.com/demos/terrain/ Refreshing the page will generate a new terrain
galapago 12y ago
A friend worked on something similar: http://dcc.fceia.unr.edu.ar/~rbaravalle/fractales/brownGL.html http://dcc.fceia.unr.edu.ar/~rbaravalle/fractales/brownGL.ht...
theforgottenone 12y ago
Diamond-square has a bug/limitation in that it creates seams. There are better solutions :).

339 points by hunterloftis 12y ago

snodgrass23 12y ago

Great tutorial on a fun topic!

elwell 12y ago

Don't miss the demo: http://www.playfuljs.com/demos/terrain/ http://www.playfuljs.com/demos/terrain/

hughes 12y ago
Is there any way to control the demo? It doesnt seem to respond to mouse or keyboard input.
- krilnon 12y ago
  It only draws a single perspective, so the only control you have is to refresh the page to get a new random bit of terrain.
- kachhalimbu 12y ago
  I made a jsfiddle and added dat.gui http://workshop.chromeexperiments.com/examples/gui/#1--Basic-Usage http://workshop.chromeexperiments.com/examples/gui/#1--Basic... so you can modify the "detail" parameter to change the terrain without requiring a page refresh http://jsfiddle.net/kachhalimbu/br8Xd/1/ http://jsfiddle.net/kachhalimbu/br8Xd/1/ Full screen result here http://jsfiddle.net/kachhalimbu/br8Xd/1/embedded/result/ http://jsfiddle.net/kachhalimbu/br8Xd/1/embedded/result/

fogleman 12y ago

Perlin noise is another good algorithm for terrain generation. http://en.wikipedia.org/wiki/Perlin_noise http://en.wikipedia.org/wiki/Perlin_noise

hunterloftis 12y ago
I like Perlin in situations where its repetitiveness won't negatively impact the simulation, or as an additional layer of pseudo-natural-randomness on top of other algorithms.

rgrieselhuber 12y ago

Reminds me of T'Rain.

TheyCalledHimBo 12y ago

I may just be a prick, but seeing this promoted as a variant of the midpoint displacement algorithm for terrain generation seem far less gimmicky. "X done in Y lines of Z" Whoop-dee freakin' do. Still, cool algorithm.

gavanwoolery 12y ago

Just a small note, not to sound snooty, just to educate people on what realistic terrain looks like... This is what midpoint displacement looks like as a heightmap: http://imgur.com/ksETpO0,7gykFEV#0 http://imgur.com/ksETpO0,7gykFEV#0 This is what realistic terrain looks like (this is based on real-world heightmap data): http://imgur.com/ksETpO0,7gykFEV#1 http://imgur.com/ksETpO0,7gykFEV#1 That said, midpoint displacement, perlin/simplex noise, etc are good for modeling terrain at a less macroscopic scale and are plenty sufficient for the use of most games.

gavanwoolery 12y ago
To add another note, as complex as real world terrain is, you can generate those fractal mountain patterns and drainage basins algorithmically with a bit of work. There are many ways to go about it, one would be recursive spacial partitioning, another would be to explicitly grow out a tree pattern while minding collision and proximity to other branches. Also, it is possible to use diffusion limited aggregation or erosion simulation but I have been down both those routes and they are not as easy to get good results with.
- mjn 12y ago
  Further reading: 1. A semi-standard textbook on the subject, but now a bit dated (don't be fooled by the 2002 date on the 3rd ed., most of the text is from the 1st ed): http://www.amazon.com/Texturing-Modeling-Third-Edition-Procedural/dp/1558608486 http://www.amazon.com/Texturing-Modeling-Third-Edition-Proce... 2. A more recent but much shorter survey paper: http://graphics.tudelft.nl/Publications-new/2009/SDGTB09a/SDGTB09a.pdf http://graphics.tudelft.nl/Publications-new/2009/SDGTB09a/SD...
  - hunterloftis 12y ago
    Thanks for this! I've been looking for resources on building out lifelike macro-terrain-structures.
userbinator 12y ago
Reminds me of this - pretty good looking terrain + animation + sound in a 4 kilobyte executable: http://www.youtube.com/watch?v=_YWMGuh15nE http://www.youtube.com/watch?v=_YWMGuh15nE How it was done: http://iquilezles.org/www/material/function2009/function2009.pdf http://iquilezles.org/www/material/function2009/function2009...

the_french 12y ago

can this algorithm be run lazily? ie, can you continue to generate continuous terrain using this technique or do you need to generate the whole map ahead of time?

hunterloftis 12y ago
It can be run lazily in two ways: first, you can lazily add detail (ie, render down to a specific level of detail and postpone the rest); second, you can lazily build grid blocks out to the horizon (eg, for walking around a terrain first-person). So detail vs size laziness.

zhemao 12y ago

There was a Clojure example of this algorithm posted a few months back. Funnily enough, it's been in my "read later" bookmarks for a while now and I just got around to reading it this morning before I saw this post. http://blog.mediocregopher.com/clojure-diamond-square.html http://blog.mediocregopher.com/clojure-diamond-square.html

colonelxc 12y ago

Reminded me of "Polygonal Map Generation For Games": http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/ http://www-cs-students.stanford.edu/~amitp/game-programming/... past comments: https://news.ycombinator.com/item?id=3868893 https://news.ycombinator.com/item?id=3868893

hunterloftis 12y ago
Awesome! Thanks for the link.

nijiko 12y ago

You can simplify this even further by using frameworks like lodash / underscore or ES6 native methods.

SteveDeFacto 12y ago

Some of you might find this algorithm I created a few years ago interesting: http://ovgl.org/view_topic.php?topic=91JL96IHFS http://ovgl.org/view_topic.php?topic=91JL96IHFS

brickmort 12y ago

This is awesome!! nice job!

good-citizen 12y ago

stuff like this makes me remember why I love programming

nitrogen 12y ago

This midpoint displacement algorithm is also how a lot of the "plasma" effects from 1990s-era PC demos were created.

twistedpair 12y ago

Reminds me of the results easy to achieve with Bryce3D back in the mid 90's. They had a pretty great terrain engine. I don't think they're making Bryce any more. It would be great if they could release some of that code.

MrBuddyCasino 12y ago
I remember that one, apparently it is still being sold, but development seems to have stalled: http://www.daz3d.com/bryce-7-pro/ http://www.daz3d.com/bryce-7-pro/
- twistedpair 12y ago
  I guess Maya ate their lunch. Funny, from the screenshots, they've not changed the interface in a decade and a half. The much lower price is nice, though.

callumprentice 12y ago

I made a quick first pass at an interactive WebGL version this evening. http://callum.com/sandbox/webglex/webgl_terrain/ http://callum.com/sandbox/webglex/webgl_terrain/ - ground realism needs a bit of work :) but it was a lot of fun. Thanks for sharing your code Hunter.

hixup 12y ago

I was playing with something similar a while ago. It's a procedurally generated overlay for Google Maps: http://dbbert.github.io/secondworld/ http://dbbert.github.io/secondworld/

pheelicks 12y ago

Nice demo. I made a terrain rendering engine/demo in WebGL a few months back, that used Perlin noise: http://felixpalmer.github.io/lod-terrain/ http://felixpalmer.github.io/lod-terrain/ If anyone wants to play around with Hunter's algorithm in WebGL, it should be pretty straightforward to swap out the Perlin Noise implementation for his. Note the shaders do a fractal sampling of the the height map, so you may want to disable this.

dualogy 12y ago
Clicking "how does this work?" leads to the HTML source of the link target to be shown in plain-text instead of being rendered. Win7, both in Chrome and Firefox.....
- pheelicks 12y ago
  Yes, I know - my blog is ruining my morning. Quick fix is to remove the trailing slash, i.e. go to http://www.pheelicks.com/2014/03/rendering-large-terrains http://www.pheelicks.com/2014/03/rendering-large-terrains instead. If anyone using WordPress + W3TC has hit this I'd be grateful for pointers to a fix
hunterloftis 12y ago
I love how you're using a simple but effective dynamic LoD. I'm going to riff on this a bit with a first-person ground-level camera.

huskyr 12y ago

What i like most about this demo is that the code is actually very readable, and the blog article explains it very well. Most of the times the code for these kinds of demos looks like line noise :)

blahpro 12y ago

It'd be interesting to see an animation of the diamond/square iteration progressing in 3D, starting with a flat surface and ending with the finished terrain :)

CmonDev 12y ago

Had to put "JavaScript" into the title - typical HN... It was about algorithm rather than a language.

zimpenfish 12y ago

I remember implementing this on a Sam Coupe from the description in (either BYTE or Dr Dobbs, I forget) back in ~1987. Somewhat slower and lower resolution, of course...

good-citizen 12y ago

after thinking about this one for a while, it occurred to me that this really helps illustrate the point of 'Life May Be A Computer Simulation'. Take this world creation a step further, and rather than teaching a computer how to create rocks, each one slightly different, imagine creating humans, each one slightly different. If you think about 'God' as just some alien programmer dude, it helps make so much sense of the world. How can a caring God let so many terrible things happen to us humans? Well, how much empathy do you feel about each rock in this program? When you click refresh, and create a whole new world, do you stop and think about all the exist rocks you are 'killing'? If we are living in a computer simulation, perhaps our creator doesn't even realize we are sentient?

saraid216 12y ago
You realize you just explained a caring God by saying he doesn't care, right?
- good-citizen 12y ago
  I meant, a common human question is "if there is a caring God, how can there be so much suffering in the world?" And maybe the answer is, human pain means nothing to him the same way computer generated rock pain means nothing to us.

namuol 12y ago

Brings me back to a ray casting experiment I did a while ago [1]. I always wanted to revisit it to include a terrain generation step (it uses a pregenerated height map). Now I have an excuse! ;) [1] http://namuol.github.io/earf-html5 http://namuol.github.io/earf-html5

hunterloftis 12y ago
Wow! Really fantastic. I've already linked to your raycaster; let me know if you build one that dynamically generates the terrain as well.

sebnukem2 12y ago

I think implementing parallel computing using webworkers would be a good item for the "What's Next" list of suggestions.

hunterloftis 12y ago
Added!

happywolf 12y ago

For those who only want to look at the result(s) http://www.playfuljs.com/demos/terrain/ http://www.playfuljs.com/demos/terrain/ Refreshing the page will generate a new terrain

galapago 12y ago

A friend worked on something similar: http://dcc.fceia.unr.edu.ar/~rbaravalle/fractales/brownGL.html http://dcc.fceia.unr.edu.ar/~rbaravalle/fractales/brownGL.ht...

theforgottenone 12y ago

Diamond-square has a bug/limitation in that it creates seams. There are better solutions :).