[Georg]

Lately I've become interested in random generation in RPG's. Especially in random generating a worldmap (i.e. roughly generating the landscape (sea, mountains etc.), generating rivers, vegetation etc.). Does anyone know how much work is done in this area (like which algorithms to use) and where I can find it?
_________________
Hi, I'm a signature virus. Copy me to your sig-file to help me spread.

[Ninkazu]

I'm not sure if any algorithms exist for such a feat. I would just have map files that have specific patterns that should show up somewhere in the map, and a list of miscellaneous patterns that can be used, and a list of connecting patterns (hallway, valley, etc) that can be used. Then there's the fun problem-solving goodness that comes along with it.

If algoritms do exist and you happen to find information of them, please post them (or preferably links to them) here, for I too am interested.

Basically, I think you just have to define the map's behavior (lots of grass, lots of ruins), or define different patterns as I said above, or something and let your code (which I don't think would take much effort) do the work.

[Rainer Deyke]

There's a lot of material available on that subject, so much that it's hard to even give an overview. On the dungeon level, look up various roguelikes. For outdoors terrain, the standard "plasma" algorithm (recursive subdivision) is a common approach, Perlin noise is another. Overall this is a solved problem in theory, although it'll still take a lot of work to get something that generates maps that are varied but consistently good.

[XMark]

I'm not really well-versed in this subject but I think an idea would be to have certain key points placed on the map (like dungeons and towns and stuff), then generate pathways in between the points, and generate the terrain around those pathways.
_________________
Mark Hall
Abstract Productions
I PLAYS THE MUSIC THAT MAKES THE PEOPLES FALL DOWN!

[janus]

Hugo Elias has a good overview of one method for outdoor areas. (It's intended for 3D, but you should be able to apply the technique to a 2D tiled map if you think hard enough.)

His method only handles land and water, but it should be trivial to do multiple passes of it to create things like grass and forests.

[Georg]

I have thought about this for a short time (and discussed it with Bjorn), but I don't want to do a terrible job compared to what's already done. Probably a lot of people must have studied the problem. I looked at Hugo Elias' site but wasn't satisfied about that. I think to get a more realistic `height map' one would somehow need mountain-ridges and other more realistic concepts than one algorithm to create the entire world. But he has done some very nice things.

Something funny: I went to his section about which books he recommends. About generating landscapes he recommends `The Nature Of Light And Colour In The Open Air', and I thought: `Wait a minute, I have that book (in Dutch), but never looked into it.' :) So now I know what I'm going to read.
_________________
Hi, I'm a signature virus. Copy me to your sig-file to help me spread.

[Georg]

Okay, I've be looking a lot throughout the internet but couldn't find much. Doesn't anyone know where to find algorithms for this? I'm also looking for algorithms for the random generation of dungeons.
_________________
Hi, I'm a signature virus. Copy me to your sig-file to help me spread.

[janus]

[Rainer Deyke]

Just download the source to Rogue/Moria/Angband and look at how they do it.

[white_door]

it really depends on the kind of terrain features that you want..

there are multiple ways of making a hieght map, subdivision is really fast.. but sometimes looks really weird (if you don't do it right you get artifacts)... one of the classic methods is called Diamond-Square. other methods include droping random chunks of dirt on to your map and smoothing it out.. or randomly raising and lowering chunks of the map and smoothing it out.. Whatever method you use... basically the slower method can yield better results most of the time.. smoothing stuff out every frame can help a lot. ;)

so once you have the hieght map, you might want to start thinking about water. generate a rain level map (could just be a hieghtmap, but it doesn't have to look nice, so you can use a fast method for this). let the rain fall on your heightmap... let it flow down.. until it fills up your map up to your ocean level.

Place all your tiles on the map... using the strongest water flows to make the rivers.. and you can use the rain information to decide the terrain types for each tile like plains, forests, and swamps.. mountains are just the peaks of the hieghtmap.. and you get your ocean by flatting off the bottom of the hieghtmap to the ocean level. Finally scan though the map and add your transition tiles.

I think this site covers a lot of the common methods.

http://www.geocities.com/Area51/6902/terrain.html

[biggerUniverse]