Ask HN: How to generate random terrain

#1

Post by alaricsp » Mon, Sep 14, 2009, 1:02 PM UTC

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!

Re: Ask HN: How to generate random terrain

#2

Post by jacquesm » Mon, Sep 14, 2009, 2:10 PM UTC

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

Re: Ask HN: How to generate random terrain

#3

Post by jules » Mon, Sep 14, 2009, 2:48 PM UTC

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

Re: Ask HN: How to generate random terrain

#4

Post by bendotc » Mon, Sep 14, 2009, 2:53 PM UTC

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.

Re: Ask HN: How to generate random terrain

#5

Post by alex_c » Mon, Sep 14, 2009, 2:55 PM UTC

bendotc wrote: post #4

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.

Did you actually read his entire question, or just the title?

Re: Ask HN: How to generate random terrain

#6

Post by slmbrhrt » Mon, Sep 14, 2009, 2:56 PM UTC

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=C...

Re: Ask HN: How to generate random terrain

#7

Post by bendotc » Mon, Sep 14, 2009, 3:01 PM UTC

alex_c wrote: post #5

bendotc wrote: post #4

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.

Did you actually read his entire question, or just the title?

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.

Re: Ask HN: How to generate random terrain

#8

Post by zeckalpha » Mon, Sep 14, 2009, 3:08 PM UTC

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

Re: Ask HN: How to generate random terrain

#9

Post by jharsman » Mon, Sep 14, 2009, 3:10 PM UTC

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.

Re: Ask HN: How to generate random terrain

#10

Post by afiske » Mon, Sep 14, 2009, 3:16 PM UTC

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