7 ms·

How to generate random terrain

95 points by SuperChihuahua 14y ago

arethuza 14y ago
Are there any systems out there that simulate the processes that go into forming real landscapes - geology, volcanoes, glaciation, water flow? [Just to list the main factors determining what I see in the local landscape here in Edinburgh every day - other places will have other factors].
- wallflower 14y ago
  Yes, there are systems but they aren't anywhere near geared towards real-time because they are basically very large Finite Element Analysis (FEA) problems. http://en.wikipedia.org/wiki/Geomorphology http://en.wikipedia.org/wiki/Geomorphology For example, OpenSees is used for earthquake modeling. http://opensees.berkeley.edu/OpenSees/workshops/OpenSeesDays2011/A6_GeoModels.pdf http://opensees.berkeley.edu/OpenSees/workshops/OpenSeesDays...
- unoti 14y ago
  You might be interested in Dwarf Fortress. Although it's not exactly what you just asked for, anyone who would phrase a question like that should fire up dwarf fortress at least once.
- DanielRibeiro 14y ago
  Andrew Price has some amazing tutorials on how to do it with just Blender: http://thenatureacademy.blenderguru.com/sp/7612-the-nature-academy-live-now http://thenatureacademy.blenderguru.com/sp/7612-the-nature-a... It is more on modelling rather than generating though. On procedural generation, we discussed[1] this app written in WebGL: http://creativejs.com/2012/06/snappytree http://creativejs.com/2012/06/snappytree Other peopled did it with Three.js: http://catchvar.com/threejs-procedurally-generated-infinite-terra#more http://catchvar.com/threejs-procedurally-generated-infinite-.... And finally, a really lively discussion[2] turned about The Death of the Level Designer: Procedural Content Generation in Games[3] [1] http://news.ycombinator.com/item?id=4161263 http://news.ycombinator.com/item?id=4161263 [2] http://news.ycombinator.com/item?id=3872615 http://news.ycombinator.com/item?id=3872615 [3] http://roguelikedeveloper.blogspot.com/2008/01/death-of-level-designer-procedural.html http://roguelikedeveloper.blogspot.com/2008/01/death-of-leve...
dexter313 14y ago
Interesting, i thought minecraft had more complicated algorithms. Does anyone have any examples on a more specific 2d terrain generation (side-scroller).
- simonh 14y ago
  Minecraft also has biomes, which customise the terrain generation to produce regions of a particular type of terrain like forest, desert, sea, etc and some intermediary biome types like beaches. I don't know how it distributes the main biomes, but it may use one noise algorithm for that and another within each biome. Plus applying some rules to handle the borders between biomes. There is a lot more to it that just "It's Perlin noise".
- rcfox 14y ago
  You can use simple cellular automata to create somewhat natural-looking cave formations: http://rcfox.ca/random-cave-map-generation/ http://rcfox.ca/random-cave-map-generation/
  - dexter313 14y ago
    By "set of stairs" do you mean a simple vertical line that cuts trough all of terrain?
    - rcfox 14y ago
      Well, I see the image as top-down view of one level in a cave. Going down stairs would mean generating another level. It's entirely legitimate to see it as a side-view, in which case yes, you'd be cutting through the terrain.
- bhickey 14y ago
  Not a side-scroller, but here's a screenshot from a terrain generator that I wrote: http://i.imgur.com/HgMWbXe.png http://i.imgur.com/HgMWbXe.png the white dot in the center is a control point that the user can drag around. That point defines a mountain. Height decays exponentially with distance from the control point. The height function is perturbed by an underlying noise function. Edit: It's all done in JS/WebGL using a fragment shader and blatting the output onto static canvas elements. These are then composited for the larger image. It supports scrolling and zooming. I could never get the performance quite to where I wanted it.
donatzsky 14y ago
So, what is the difference between value noise and perlin noise?
- stephengillie 14y ago
  Yea, the blog shows us what Value Noise would produce, and says this is easily confused with Perlin Noise, but does not show us what Perlin Noise output looks like.
  - bionsuba 14y ago
    Here is a good article showing how to implement perlin noise and its outputs: http://freespace.virgin.net/hugo.elias/models/m_perlin.htm http://freespace.virgin.net/hugo.elias/models/m_perlin.htm Also, *yeah.
    - Scaevolus 14y ago
      That's actually not quite Perlin noise either. In Perlin noise, you set each grid point to a unit gradient vector, and then interpolate between them with a specific equation. This gives it useful mathematical properties, like being continuously differentiable, so the surface normals are smooth when you render it. That's not guaranteed with value noise. http://webstaff.itn.liu.se/~stegu/TNM022-2005/perlinnoiselinks/perlin-noise-math-faq.html http://webstaff.itn.liu.se/~stegu/TNM022-2005/perlinnoiselin...
- mjn 14y ago
  Perlin noise is a kind of gradient noise. The difference is that, in a value-noise generator, you assign a random value (from some distribution) to each grid point, and then interpolate between the values. In a gradient-noise generator, you assign random gradients to each grid point, and then use dot products to produce the actual values from the gradients. There's a StackExchange discussion of the subjective differences here: http://math.stackexchange.com/questions/184121/why-is-gradient-noise-better-quality-than-value-noise http://math.stackexchange.com/questions/184121/why-is-gradie...
- 14y ago
artursapek 14y ago
This makes me think of how AoE II generated its maps randomly each time you play. They really had it right. It definitely multiplied the longevity of that game.
- xentronium 14y ago
  I'd wager they had some pre-made pieces that were later slightly modified and stitched together.
  - artursapek 14y ago
    One of my earliest memories of "programming" was fucking around with seed files for that map generator. It was very algorithmic, not pre-made.
icegreentea 14y ago
This reminded me all the hours I sunk into playing around with terragen (http://planetside.co.uk/ http://planetside.co.uk/). Definitely remember playing around in photoshop with filters (clouds! and difference clouds!... which I guess is just perlin noise) making height maps.
mjn 14y ago
If you're interested in this kind of stuff, you might like the paper "A survey of procedural methods for terrain modelling": http://www.cg.its.tudelft.nl/~rafa/myPapers/bidarra.3AMIGAS.RS.pdf http://www.cg.its.tudelft.nl/~rafa/myPapers/bidarra.3AMIGAS....
mrcharles 14y ago
If you are interested in a far more terrain like generation, the link casually mentions Diamond-Square at the bottom, but I wrote a post a while back that goes into much deeper detail, after looking at one of Notch's ludum dare entries. http://www.bluh.org/code-the-diamond-square-algorithm/ http://www.bluh.org/code-the-diamond-square-algorithm/
dpiers 14y ago
One of my friends from school wrote a paper on a procedural terrain generation method that allowed simple user inputs to control the generation process. Here's the link: http://larc.unt.edu/ian/research/terrain/ http://larc.unt.edu/ian/research/terrain/
sycren 14y ago
Terragen 2 - Landscape generator http://planetside.co.uk/index.php?option=com_content&view=article&id=32&Itemid=150 http://planetside.co.uk/index.php?option=com_content&vie... 1st version is free to download
baggers 14y ago
If you are interested in generating terrains with caves (or other formations with more that just a height detail) then I recommend following this chap http://procworld.blogspot.co.uk/ http://procworld.blogspot.co.uk/ The technique is based on dual contouring a voxel field and his results are awesome. For info on how he went about it check posts from 2010 (most of it focuses on parallelization using cuda however)
milliams 14y ago
There's an interesting article at http://accidentalnoise.sourceforge.net/minecraftworlds.html http://accidentalnoise.sourceforge.net/minecraftworlds.html about minecraft-like terrain generation. It uses PolyVox (http://www.volumesoffun.com/polyvox-about/ http://www.volumesoffun.com/polyvox-about/) to do the rendering at the end.

Are there any systems out there that simulate the processes that go into forming real landscapes - geology, volcanoes, glaciation, water flow? [Just to list the main factors determining what I see in the local landscape here in Edinburgh every day - other places will have other factors].

wallflower 14y ago
Yes, there are systems but they aren't anywhere near geared towards real-time because they are basically very large Finite Element Analysis (FEA) problems. http://en.wikipedia.org/wiki/Geomorphology http://en.wikipedia.org/wiki/Geomorphology For example, OpenSees is used for earthquake modeling. http://opensees.berkeley.edu/OpenSees/workshops/OpenSeesDays2011/A6_GeoModels.pdf http://opensees.berkeley.edu/OpenSees/workshops/OpenSeesDays...
unoti 14y ago
You might be interested in Dwarf Fortress. Although it's not exactly what you just asked for, anyone who would phrase a question like that should fire up dwarf fortress at least once.
DanielRibeiro 14y ago
Andrew Price has some amazing tutorials on how to do it with just Blender: http://thenatureacademy.blenderguru.com/sp/7612-the-nature-academy-live-now http://thenatureacademy.blenderguru.com/sp/7612-the-nature-a... It is more on modelling rather than generating though. On procedural generation, we discussed[1] this app written in WebGL: http://creativejs.com/2012/06/snappytree http://creativejs.com/2012/06/snappytree Other peopled did it with Three.js: http://catchvar.com/threejs-procedurally-generated-infinite-terra#more http://catchvar.com/threejs-procedurally-generated-infinite-.... And finally, a really lively discussion[2] turned about The Death of the Level Designer: Procedural Content Generation in Games[3] [1] http://news.ycombinator.com/item?id=4161263 http://news.ycombinator.com/item?id=4161263 [2] http://news.ycombinator.com/item?id=3872615 http://news.ycombinator.com/item?id=3872615 [3] http://roguelikedeveloper.blogspot.com/2008/01/death-of-level-designer-procedural.html http://roguelikedeveloper.blogspot.com/2008/01/death-of-leve...

dexter313 14y ago

Interesting, i thought minecraft had more complicated algorithms. Does anyone have any examples on a more specific 2d terrain generation (side-scroller).

simonh 14y ago
Minecraft also has biomes, which customise the terrain generation to produce regions of a particular type of terrain like forest, desert, sea, etc and some intermediary biome types like beaches. I don't know how it distributes the main biomes, but it may use one noise algorithm for that and another within each biome. Plus applying some rules to handle the borders between biomes. There is a lot more to it that just "It's Perlin noise".
rcfox 14y ago
You can use simple cellular automata to create somewhat natural-looking cave formations: http://rcfox.ca/random-cave-map-generation/ http://rcfox.ca/random-cave-map-generation/
- dexter313 14y ago
  By "set of stairs" do you mean a simple vertical line that cuts trough all of terrain?
  - rcfox 14y ago
    Well, I see the image as top-down view of one level in a cave. Going down stairs would mean generating another level. It's entirely legitimate to see it as a side-view, in which case yes, you'd be cutting through the terrain.
bhickey 14y ago
Not a side-scroller, but here's a screenshot from a terrain generator that I wrote: http://i.imgur.com/HgMWbXe.png http://i.imgur.com/HgMWbXe.png the white dot in the center is a control point that the user can drag around. That point defines a mountain. Height decays exponentially with distance from the control point. The height function is perturbed by an underlying noise function. Edit: It's all done in JS/WebGL using a fragment shader and blatting the output onto static canvas elements. These are then composited for the larger image. It supports scrolling and zooming. I could never get the performance quite to where I wanted it.

donatzsky 14y ago

So, what is the difference between value noise and perlin noise?

stephengillie 14y ago
Yea, the blog shows us what Value Noise would produce, and says this is easily confused with Perlin Noise, but does not show us what Perlin Noise output looks like.
- bionsuba 14y ago
  Here is a good article showing how to implement perlin noise and its outputs: http://freespace.virgin.net/hugo.elias/models/m_perlin.htm http://freespace.virgin.net/hugo.elias/models/m_perlin.htm Also, *yeah.
  - Scaevolus 14y ago
    That's actually not quite Perlin noise either. In Perlin noise, you set each grid point to a unit gradient vector, and then interpolate between them with a specific equation. This gives it useful mathematical properties, like being continuously differentiable, so the surface normals are smooth when you render it. That's not guaranteed with value noise. http://webstaff.itn.liu.se/~stegu/TNM022-2005/perlinnoiselinks/perlin-noise-math-faq.html http://webstaff.itn.liu.se/~stegu/TNM022-2005/perlinnoiselin...
mjn 14y ago
Perlin noise is a kind of gradient noise. The difference is that, in a value-noise generator, you assign a random value (from some distribution) to each grid point, and then interpolate between the values. In a gradient-noise generator, you assign random gradients to each grid point, and then use dot products to produce the actual values from the gradients. There's a StackExchange discussion of the subjective differences here: http://math.stackexchange.com/questions/184121/why-is-gradient-noise-better-quality-than-value-noise http://math.stackexchange.com/questions/184121/why-is-gradie...
14y ago

artursapek 14y ago

This makes me think of how AoE II generated its maps randomly each time you play. They really had it right. It definitely multiplied the longevity of that game.

xentronium 14y ago
I'd wager they had some pre-made pieces that were later slightly modified and stitched together.
- artursapek 14y ago
  One of my earliest memories of "programming" was fucking around with seed files for that map generator. It was very algorithmic, not pre-made.

icegreentea 14y ago

This reminded me all the hours I sunk into playing around with terragen (http://planetside.co.uk/ http://planetside.co.uk/). Definitely remember playing around in photoshop with filters (clouds! and difference clouds!... which I guess is just perlin noise) making height maps.

mjn 14y ago

If you're interested in this kind of stuff, you might like the paper "A survey of procedural methods for terrain modelling": http://www.cg.its.tudelft.nl/~rafa/myPapers/bidarra.3AMIGAS.RS.pdf http://www.cg.its.tudelft.nl/~rafa/myPapers/bidarra.3AMIGAS....

mrcharles 14y ago

If you are interested in a far more terrain like generation, the link casually mentions Diamond-Square at the bottom, but I wrote a post a while back that goes into much deeper detail, after looking at one of Notch's ludum dare entries. http://www.bluh.org/code-the-diamond-square-algorithm/ http://www.bluh.org/code-the-diamond-square-algorithm/

dpiers 14y ago

One of my friends from school wrote a paper on a procedural terrain generation method that allowed simple user inputs to control the generation process. Here's the link: http://larc.unt.edu/ian/research/terrain/ http://larc.unt.edu/ian/research/terrain/

sycren 14y ago

Terragen 2 - Landscape generator http://planetside.co.uk/index.php?option=com_content&view=article&id=32&Itemid=150 http://planetside.co.uk/index.php?option=com_content&vie... 1st version is free to download

baggers 14y ago

If you are interested in generating terrains with caves (or other formations with more that just a height detail) then I recommend following this chap http://procworld.blogspot.co.uk/ http://procworld.blogspot.co.uk/ The technique is based on dual contouring a voxel field and his results are awesome. For info on how he went about it check posts from 2010 (most of it focuses on parallelization using cuda however)

milliams 14y ago

There's an interesting article at http://accidentalnoise.sourceforge.net/minecraftworlds.html http://accidentalnoise.sourceforge.net/minecraftworlds.html about minecraft-like terrain generation. It uses PolyVox (http://www.volumesoffun.com/polyvox-about/ http://www.volumesoffun.com/polyvox-about/) to do the rendering at the end.