7 ms·

Ask HN: How to generate random terrain

31 points by alaricsp 17y ago

When I was a kid in the 1980s, I read a library book on the topic of writing military strategy sim games, and it had an entire chapter on producing random terrain. It started with the usual fractal techniques for producing contours, but then it went on to use weighted random walks to produce roads and rivers, lakes, bridges, and cities. I've tried recreating the algorithms from what little I remember of them, but they never produce anything that looks very good. Online I've found plenty of references to ways of generating the contours, but never realistic-looking roads, rails, and waterways... Does anybody know an online reference to that sort of thing? Thanks!

jacquesm 17y ago
Search for 'Mandelbrot' or 'Peitgen' and 'fractal landscape'.
jules 17y ago
For waterways you could try to place random water sources and follow the gradient from there.
bendotc 17y ago
http://lmgtfy.com/?q=terrain+generation&l=1 http://lmgtfy.com/?q=terrain+generation&l=1 Seriously, I'm all for discussion of particular techniques, but your question is way too broad right now. Go read some papers or even just online tutorials or descriptions of how other software does it, and then lets have a discussion.
- alex_c 17y ago
  Did you actually read his entire question, or just the title?
  - bendotc 17y ago
    I read the entire question, and there are plenty of great resources out there for rivers, as well as human settlements, roads, railroads, etc. Even a "I've tried method X and had problems Y and Z with the output" could produce interesting discussion, but this is just asking for links when a minute or two of Googling does a pretty good job of turning things up.
    - alaricsp 17y ago
      True, I glossed over my previous research; I didn't think it'd interest people, but you're right, it's wise to show some evidence of your previous attempts before asking for tips... My googling always just found me more and more ways of generating the height-field data - it's the roads and so on that interest me. I tried tinkering with weighted random walks (eg, given the desire to continue a road from a given point, pick an adjoining cell with a weighting that prioritises having the same altitude and being closest to continuing the existing direction), but this fails to capture things like the fact that roads tend to run along valleys and mountain passes - the hard part, it seems, is in choosing initial points. Likewise, a river can be continued by finding the most downhill adjacent cell, until you find a minimum then starting a flood-fill algorithm to create a lake, until you reach a boundary pixel that "goes downhill", whereupon you can start a new river going down from there - but this fails to realistically account for the widths of rivers (you can just make the river wider as you go down, and sum the width of rivers that meet, but that simple model looks wrong: real rivers are deeper when in narrow canyons and the like).
slmbrhrt 17y ago
For generating roads or waterways, try coming up with rules similar to the way they're created in real life. For example, water flows downhill and pools when it finds a local minimum. Roads, on the other hand, tend to avoid steep grades when they can, typically moving straight and branching at right angles at regular intervals. Read up on L-Systems, too. They're great for creating organic structures, be they leaves, trees, or river-tributary systems. Oh and this may be useful: http://roguebasin.roguelikedevelopment.org/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels http://roguebasin.roguelikedevelopment.org/index.php?title=C...
- alaricsp 17y ago
  That rogue-like cave generation algorithm isn't the kind of terrain I'm after, but is nonetheless quite awesome in its results. I'm now wondering if I can find an excuse to involve caverns in my game ;-)
zeckalpha 17y ago
Perchance recall the book? I'm semi-interested in retro approaches to the problem.
- alaricsp 17y ago
  I'd love to find the book again... I bet it's out of print, though. It had lots of detail on modelling damage to tanks, and creating terrain, and working out things like line-of-sight in complex worlds, and I think some basic AI, but had nothing to say about snazzy graphics whatsoever; I think it made some reference to vector displays or something like that ;-)
  - zeckalpha 17y ago
    Any of this look familiar? http://books.google.com/books?q=AI+computer+simulation+military+strategy+tanks+damage http://books.google.com/books?q=AI+computer+simulation+milit...
    - alaricsp 17y ago
      Alas, no :-)
  - plinkplonk 17y ago
    "I'd love to find the book again... I bet it's out of print, though. It had lots of detail on modelling damage to tanks, and creating terrain, and working out things like line-of-sight in complex worlds, and I think some basic AI, but had nothing to say about snazzy graphics whatsoever; I think it made some reference to vector displays or something like that ;-)" This is an interesting search problem. The fact that a description like this still doesn't help in locating a book (when you think about it the set of all books published is a small one compared to say the domain of web pages on the internet), shows how much work still remians to be done in search.
jharsman 17y ago
For waterways, just simulate rain and erosion. Let's say you model your terrain as a height field. 1. Add rain in random locations 2. Have the rain absorb some of the soil from the square it starts in. 3. Let the water flow in the direction of the gradient. 4. Deposit som e of the picked up soil (maybe only with some probability based on the flow velocity?) 5. Repeat If you just want rivers and lakes you can skip the erosion step and just simulate the water flowing. If you wanted you could add sources manually and have water always flow from there.
afiske 17y ago
Here's an article on adding rivers to procedurally generated terrain - http://www.gamedev.net/reference/programming/features/randomriver/ http://www.gamedev.net/reference/programming/features/random.... Searches for "procedurally generated [roads/rivers/waterways/etc] seemed to be the most promising.
wlievens 17y ago
What kind of scale of terrain are you looking for? Continent maps or battlefield scale? I got some stuff I rolled here http://flywheel.be/examples/ http://flywheel.be/examples/ All random generated. But probably not what you're looking for.
- allenp 17y ago
  These look great - what method did you use to define the borders on the risk-like map?
  - wlievens 17y ago
    You mean the border between the hued territories? Roughly: 1) Randomly pick center points of territories, guarantee a minimum distance for best looks 2) Compute the Voronoi raster, i.e. for each pixel find the nearest territory center 3) Figure out which territories border which, based on the Voronoi raster 4) Compute borders for each territory by taking the midpoints of edges in the territory neighborhood graph. Use a couple special tricks for coastal territories. 5) Split up those borders into finer segments 6) Add noise to the border segments 7) Fill in the pixels according to the borders
    - allenp 17y ago
      Thank you so much for the detailed response!
- wlievens 17y ago
  I also have these: http://flywheel.be/wouter/maps/ http://flywheel.be/wouter/maps/ For more discrete-looking maps.
jwecker 17y ago
google erosion simulation algorithms (or derivations)- some brilliant stuff mostly developed for geography simulations that would make absolutely amazing terrains.
bigsassy 17y ago
Game development websites are a good place to look. Try these links: http://www.gamedev.net/reference/list.asp?categoryid=45#188 http://www.gamedev.net/reference/list.asp?categoryid=45#188 http://www.gamasutra.com/search/index.php?search_text=terrain+roads&submit=Search http://www.gamasutra.com/search/index.php?search_text=terrai...
allenp 17y ago
If you have a heightmap, the roads should be fairly easy. Pick start and end points (cities?) and use a pathfinding method like A* to plot the road. If you want something more stylized, you could select a handful of points from that method and then use beizer curves or something between them.
- wlievens 17y ago
  And finally, add noise. Adding noise using midpoint displacement for instance greatly increases believability for very little effort. But you need to tune things carefully.
dovyski 17y ago
You can take a look at my master thesis (Charack: Pseudo-infinite 3D virtual world generation). It's in a pre-alpha stage, but I think you can find something useful (besides the wide range of similar tools and works I found during my research). Project link: http://code.google.com/p/charack/ http://code.google.com/p/charack/
- alaricsp 17y ago
  Oooh, beautiful...
  - dovyski 17y ago
    Thanks! :)
- daigidan 17y ago
  This really is a wealth of knowledge and practical code. I know what I'll be spending my evening reading now. ;-] Thanks!
  - dovyski 17y ago
    Thank you for the nice words. About the reading, at http://charack.googlecode.com/svn/ http://charack.googlecode.com/svn/ you can find my thesis text and a full paper. Unfortunately the master thesis is available in Brazilian Portuguese only (I really had no time to translate it to English), but the paper is written in English ;)
stevejohnson 17y ago
I did some work on random terrain once. You can see the results here: http://steveasleep.appspot.com/pyworldgen http://steveasleep.appspot.com/pyworldgen If this is what you're looking for, I can try to explain it.
- wlievens 17y ago
  Cool. I made these: http://flywheel.be/wouter/maps/ http://flywheel.be/wouter/maps/ Similar in concept, I guess. What technique are you using? I always start from fractal + voronoi but I think that's fundamentally flawed; going from raster to vector is silly when you could have gone straight to vector.
  - stevejohnson 17y ago
    I'm starting with a triangle and expanding random sides with triangles or trapezoids, filling in tightly acute angles as well.
elcron 17y ago
The freeciv map generator is pretty good if your looking for sample code for a world scale map.

31 points by alaricsp 17y ago

jacquesm 17y ago

Search for 'Mandelbrot' or 'Peitgen' and 'fractal landscape'.

jules 17y ago

For waterways you could try to place random water sources and follow the gradient from there.

bendotc 17y ago

http://lmgtfy.com/?q=terrain+generation&l=1 http://lmgtfy.com/?q=terrain+generation&l=1 Seriously, I'm all for discussion of particular techniques, but your question is way too broad right now. Go read some papers or even just online tutorials or descriptions of how other software does it, and then lets have a discussion.

alex_c 17y ago
Did you actually read his entire question, or just the title?
- bendotc 17y ago
  I read the entire question, and there are plenty of great resources out there for rivers, as well as human settlements, roads, railroads, etc. Even a "I've tried method X and had problems Y and Z with the output" could produce interesting discussion, but this is just asking for links when a minute or two of Googling does a pretty good job of turning things up.
  - alaricsp 17y ago
    True, I glossed over my previous research; I didn't think it'd interest people, but you're right, it's wise to show some evidence of your previous attempts before asking for tips... My googling always just found me more and more ways of generating the height-field data - it's the roads and so on that interest me. I tried tinkering with weighted random walks (eg, given the desire to continue a road from a given point, pick an adjoining cell with a weighting that prioritises having the same altitude and being closest to continuing the existing direction), but this fails to capture things like the fact that roads tend to run along valleys and mountain passes - the hard part, it seems, is in choosing initial points. Likewise, a river can be continued by finding the most downhill adjacent cell, until you find a minimum then starting a flood-fill algorithm to create a lake, until you reach a boundary pixel that "goes downhill", whereupon you can start a new river going down from there - but this fails to realistically account for the widths of rivers (you can just make the river wider as you go down, and sum the width of rivers that meet, but that simple model looks wrong: real rivers are deeper when in narrow canyons and the like).

slmbrhrt 17y ago

For generating roads or waterways, try coming up with rules similar to the way they're created in real life. For example, water flows downhill and pools when it finds a local minimum. Roads, on the other hand, tend to avoid steep grades when they can, typically moving straight and branching at right angles at regular intervals. Read up on L-Systems, too. They're great for creating organic structures, be they leaves, trees, or river-tributary systems. Oh and this may be useful: http://roguebasin.roguelikedevelopment.org/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels http://roguebasin.roguelikedevelopment.org/index.php?title=C...

alaricsp 17y ago
That rogue-like cave generation algorithm isn't the kind of terrain I'm after, but is nonetheless quite awesome in its results. I'm now wondering if I can find an excuse to involve caverns in my game ;-)

zeckalpha 17y ago

Perchance recall the book? I'm semi-interested in retro approaches to the problem.

alaricsp 17y ago
I'd love to find the book again... I bet it's out of print, though. It had lots of detail on modelling damage to tanks, and creating terrain, and working out things like line-of-sight in complex worlds, and I think some basic AI, but had nothing to say about snazzy graphics whatsoever; I think it made some reference to vector displays or something like that ;-)
- zeckalpha 17y ago
  Any of this look familiar? http://books.google.com/books?q=AI+computer+simulation+military+strategy+tanks+damage http://books.google.com/books?q=AI+computer+simulation+milit...
  - alaricsp 17y ago
    Alas, no :-)
- plinkplonk 17y ago
  "I'd love to find the book again... I bet it's out of print, though. It had lots of detail on modelling damage to tanks, and creating terrain, and working out things like line-of-sight in complex worlds, and I think some basic AI, but had nothing to say about snazzy graphics whatsoever; I think it made some reference to vector displays or something like that ;-)" This is an interesting search problem. The fact that a description like this still doesn't help in locating a book (when you think about it the set of all books published is a small one compared to say the domain of web pages on the internet), shows how much work still remians to be done in search.

jharsman 17y ago

For waterways, just simulate rain and erosion. Let's say you model your terrain as a height field. 1. Add rain in random locations 2. Have the rain absorb some of the soil from the square it starts in. 3. Let the water flow in the direction of the gradient. 4. Deposit som e of the picked up soil (maybe only with some probability based on the flow velocity?) 5. Repeat If you just want rivers and lakes you can skip the erosion step and just simulate the water flowing. If you wanted you could add sources manually and have water always flow from there.

afiske 17y ago

Here's an article on adding rivers to procedurally generated terrain - http://www.gamedev.net/reference/programming/features/randomriver/ http://www.gamedev.net/reference/programming/features/random.... Searches for "procedurally generated [roads/rivers/waterways/etc] seemed to be the most promising.

wlievens 17y ago

What kind of scale of terrain are you looking for? Continent maps or battlefield scale? I got some stuff I rolled here http://flywheel.be/examples/ http://flywheel.be/examples/ All random generated. But probably not what you're looking for.

allenp 17y ago
These look great - what method did you use to define the borders on the risk-like map?
- wlievens 17y ago
  You mean the border between the hued territories? Roughly: 1) Randomly pick center points of territories, guarantee a minimum distance for best looks 2) Compute the Voronoi raster, i.e. for each pixel find the nearest territory center 3) Figure out which territories border which, based on the Voronoi raster 4) Compute borders for each territory by taking the midpoints of edges in the territory neighborhood graph. Use a couple special tricks for coastal territories. 5) Split up those borders into finer segments 6) Add noise to the border segments 7) Fill in the pixels according to the borders
  - allenp 17y ago
    Thank you so much for the detailed response!
wlievens 17y ago
I also have these: http://flywheel.be/wouter/maps/ http://flywheel.be/wouter/maps/ For more discrete-looking maps.

jwecker 17y ago

google erosion simulation algorithms (or derivations)- some brilliant stuff mostly developed for geography simulations that would make absolutely amazing terrains.

bigsassy 17y ago

Game development websites are a good place to look. Try these links: http://www.gamedev.net/reference/list.asp?categoryid=45#188 http://www.gamedev.net/reference/list.asp?categoryid=45#188 http://www.gamasutra.com/search/index.php?search_text=terrain+roads&submit=Search http://www.gamasutra.com/search/index.php?search_text=terrai...

allenp 17y ago

If you have a heightmap, the roads should be fairly easy. Pick start and end points (cities?) and use a pathfinding method like A* to plot the road. If you want something more stylized, you could select a handful of points from that method and then use beizer curves or something between them.

wlievens 17y ago
And finally, add noise. Adding noise using midpoint displacement for instance greatly increases believability for very little effort. But you need to tune things carefully.

dovyski 17y ago

You can take a look at my master thesis (Charack: Pseudo-infinite 3D virtual world generation). It's in a pre-alpha stage, but I think you can find something useful (besides the wide range of similar tools and works I found during my research). Project link: http://code.google.com/p/charack/ http://code.google.com/p/charack/

alaricsp 17y ago
Oooh, beautiful...
- dovyski 17y ago
  Thanks! :)
daigidan 17y ago
This really is a wealth of knowledge and practical code. I know what I'll be spending my evening reading now. ;-] Thanks!
- dovyski 17y ago
  Thank you for the nice words. About the reading, at http://charack.googlecode.com/svn/ http://charack.googlecode.com/svn/ you can find my thesis text and a full paper. Unfortunately the master thesis is available in Brazilian Portuguese only (I really had no time to translate it to English), but the paper is written in English ;)

stevejohnson 17y ago

I did some work on random terrain once. You can see the results here: http://steveasleep.appspot.com/pyworldgen http://steveasleep.appspot.com/pyworldgen If this is what you're looking for, I can try to explain it.

wlievens 17y ago
Cool. I made these: http://flywheel.be/wouter/maps/ http://flywheel.be/wouter/maps/ Similar in concept, I guess. What technique are you using? I always start from fractal + voronoi but I think that's fundamentally flawed; going from raster to vector is silly when you could have gone straight to vector.
- stevejohnson 17y ago
  I'm starting with a triangle and expanding random sides with triangles or trapezoids, filling in tightly acute angles as well.

elcron 17y ago

The freeciv map generator is pretty good if your looking for sample code for a world scale map.