Let's talk a bit about world map generation!

[UltimaRatioRegum]

I like the custom ASCII-esque tiles you're using.  As a fellow Python RL developer, I'm curious to know what library you're using to display both standard ASCII characters and custom characters side-by-side.  

Mmh, I think it's libtcod.  

I made all of the custom tiles myself, and also actually changed quite a bit of the default fonts, but I am indeed using libtcod

[Leaf]

Would you be willing to share more details of how you're doing the world map generation?

I've been working on procedurally (rather than randomly) generating worlds, given a seed value, so that I can zoom in and generate the areas needed as the player enters them, instead of having to spend a bunch of time at the beginning generating a world randomly.

I'm generating the base terrain using fractional browning motion running on top of a procedural perlin noise function that feeds a seed and a set of coordinates through a fast murmur hash function to generate values.  Once I've drilled down to the resolution I want, I pull out a square of terrain, plus some buffer area on the edges, and run a hydraulic erosion loop on it for a while.  It seems to work pretty well, but....

Rivers are troublesome.  I can get them to form if I run many many iterations that evaporate and deposit small amounts of water, but that takes quite a long time.  Pleasant but fast results are achieved if I dump a whole bunch of water in relatively few iterations, but rivers don't form that way....

I haven't even begun to think about biomes yet.......

How are you running your rivers?  What methods are you using to form your biomes?  Would any of these methods be usable with as-needed procedural generation rather than pre-generated random worlds?

[eclectocrat]

This is great, I love procedural/random map generation, but it's so darn difficult! Is there a place for best practices having to do with such things? I know of the procedural content generation WIKI, but that's about algorithms and not code. Perhaps it's time to start a page on roguebasin...

EDIT:
This represents my solution to making level generation algorithms that can be used flexibly. I'm interested in peoples opinions, and I'd really love to start some kind of library project, although that might be a little ambitious.
http://roguebasin.roguelikedevelopment.org/index.php/Designing_Flexible,_Reusable_Algorithms

[Leaf]

I've thought about starting a blog to post code snippets and screenies as I work on stuff...

Some of the code is too long to be spamming up these forums with. <_<

Here's a great article on polygonal map generation: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/

I don't know why I didn't think of using a table like that to figure out biomes myself, lol....

[Leaf]

Here's a pretty good paper on river generation.  Probably wouldn't work for a truly procedural world though...

http://www.cs.sjsu.edu/~teoh/research/papers/CGVR08_terrain.pdf

[UltimaRatioRegum]

Would you be willing to share more details of how you're doing the world map generation?

I've been working on procedurally (rather than randomly) generating worlds, given a seed value, so that I can zoom in and generate the areas needed as the player enters them, instead of having to spend a bunch of time at the beginning generating a world randomly.

I'm generating the base terrain using fractional browning motion running on top of a procedural perlin noise function that feeds a seed and a set of coordinates through a fast murmur hash function to generate values.  Once I've drilled down to the resolution I want, I pull out a square of terrain, plus some buffer area on the edges, and run a hydraulic erosion loop on it for a while.  It seems to work pretty well, but....

Rivers are troublesome.  I can get them to form if I run many many iterations that evaporate and deposit small amounts of water, but that takes quite a long time.  Pleasant but fast results are achieved if I dump a whole bunch of water in relatively few iterations, but rivers don't form that way....

I haven't even begun to think about biomes yet.......

How are you running your rivers?  What methods are you using to form your biomes?  Would any of these methods be usable with as-needed procedural generation rather than pre-generated random worlds?

Certainly .

Ah, that's a nice idea. I've been considering using a seed value, but I've decided not to go that route for now. I'm the same in a way, though, since parts of the 'local' map - ie the scale the player walks around on - aren't generated until you first step foot in them.

I also found rivers by far the toughest part. If I split my workgen into various parts - land, terrain, height, mountains, forests, gorges, volcanoes, and rivers, rivers take more time than all the others combined, and it's about as efficient as I can find a way to make it at the moment.

Biomes are currently based primarily upon latitude, with a small height component, though I plan to make this slightly more complex in the future.

As for rivers, my latest devblog entry is on just them!

http://www.ultimaratioregum.co.uk/game/2011/12/19/the-case-of-the-penrose-river-2/

Here's how rivers look at the moment (without any current or indicator of flow shown, currently):



Let me know what you think, or if the explanation I give there isn't clear enough : )

This is great, I love procedural/random map generation, but it's so darn difficult! Is there a place for best practices having to do with such things? I know of the procedural content generation WIKI, but that's about algorithms and not code. Perhaps it's time to start a page on roguebasin...

EDIT:
This represents my solution to making level generation algorithms that can be used flexibly. I'm interested in peoples opinions, and I'd really love to start some kind of library project, although that might be a little ambitious.
http://roguebasin.roguelikedevelopment.org/index.php/Designing_Flexible,_Reusable_Algorithms

I know what you mean - starting a library project seems like a huge undertaking! I'm trying to get a flexible generation system that can be used for dungeons, but since the focus of URR is on large-scale army combat, dungeons aren't actually that common. So while it's important, getting the outside world looking good is significantly more vital. Really interesting article, though, and has given me a few ideas...

I've thought about starting a blog to post code snippets and screenies as I work on stuff...

Some of the code is too long to be spamming up these forums with. <_<

Here's a great article on polygonal map generation: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/

I don't know why I didn't think of using a table like that to figure out biomes myself, lol....

I've come across that article before - it's fascinating, and gave me quite a few ideas for my system. In the end, though, I think how the map looks is more crucial than how it's constructed; which is to say, if you use a simpler method but the end result is no different, I think one should err on the side of the simpler method. My system is not quite as complex, but I think (at the moment) the map is sufficiently complex : )

Here's a pretty good paper on river generation.  Probably wouldn't work for a truly procedural world though...

http://www.cs.sjsu.edu/~teoh/research/papers/CGVR08_terrain.pdf

Wow - that's much more detailed than anything I'm going after. As you say, though, I think that could only be used in certain areas, and I'm not sure I have the skills to program that in myself anyway!

[UltimaRatioRegum]

I've gone back a bit and added a heightmap in, properly, to the world map. This is enabling hills, more interesting coastlines, and all kinds of other funky stuff.

For instance, a comparison of the same area on the minimap looks like this:



I've uploaded a load of new screenshots and looks at the world in today's devblog entry @ http://www.ultimaratioregum.co.uk/game/2011/12/26/winter-screenshot-update/ - how does everyone think it's looking?

[Z]

The rightmost lake  (3 down, 6 right) from X looks quite steep. Height 4 on western and height 0 on eastern coast.

[Kyzrati]

- how does everyone think it's looking?

I think it's looking pretty awesome. The "lakefall" Z mentions could theoretically just be a lake adjacent to towering cliffs.

[UltimaRatioRegum]

The rightmost lake  (3 down, 6 right) from X looks quite steep. Height 4 on western and height 0 on eastern coast.

Yep; but I decided to allow that. Cliffs don't form (both because in the real world, they are actually pretty rare, and they don't stick with the wide-scale 'open' combat theme of the game) so it's a very, very steep incline instead.

I think it's looking pretty awesome. The "lakefall" Z mentions could theoretically just be a lake adjacent to towering cliffs.

Cheers! It is largely thus, though as I say, more of a very steep slope. Lakes often have different heights on different sides from that, whereas normal terrain is (generally) a lot smoother . That screenshot is actually fractionally out of date; in actual fact, on land, squares can only go up or down by 1 in adjacent squares. Again, stops cliffs, keeps things a lot smoother for large battles, and also (I confess) makes the whole thing easier to draw on the human scale!

[guest509]

  I would assume the level of the lake is the same as the level of the lowest land adjacent to the lake. Or the lake would just sort of run out. Right? :-)
  Cliffs are fun to throw evil off of. And to jump down to escape the cowardly mooks that dare not follow you. You are probably wanting to make a realistic world with fewer cliffs. But in heroic fiction there is always plenty around.

[getter77]

http://swordofahkranox.blogspot.com/2011/12/new-year-comes-with-new-features.html

A bit tangential perhaps to the goings on afoot here directly, but these folks are definitely figuring some stuff out bit by bit at a good clip as far as these sorts of things go.

[Z]

I have written a terrain/river generation program a long time ago, and the algorithm was simply something like "start river in a random point; while river has not reached the ocean, find the lowest pixel next to the river, and add it to the river". This algorithm did not generate meanders or deltas, but it did generate nice lakes (if the river falls into a local minimum, it fills all the land around it, until it breaks the wall). I am not an expert on rivers, but I have a feeling that flat lakes and rivers going strictly downwards are more natural (don't rivers carving through hills, subterranean rivers, canyons, and lakes with towering cliffs form simply because there is a kind of rock (limestone) which is very poor at blocking the water, effectively making the river generation algorithm treat it like air?). Anyway this was intended as just a fun simulation, not a game.

[UltimaRatioRegum]

  I would assume the level of the lake is the same as the level of the lowest land adjacent to the lake. Or the lake would just sort of run out. Right? :-)
  Cliffs are fun to throw evil off of. And to jump down to escape the cowardly mooks that dare not follow you. You are probably wanting to make a realistic world with fewer cliffs. But in heroic fiction there is always plenty around.

Correcto; lowest level (almost always sea level) is the level for lakes. And there are some steep areas, but still no absolute cliffs; though you will be able to knock creatures off towers, bridges, ramparts, and similar areas instead!

http://swordofahkranox.blogspot.com/2011/12/new-year-comes-with-new-features.html

A bit tangential perhaps to the goings on afoot here directly, but these folks are definitely figuring some stuff out bit by bit at a good clip as far as these sorts of things go.

Most interesting - an infinite world? I'll be keeping an eye on that project...

I have written a terrain/river generation program a long time ago, and the algorithm was simply something like "start river in a random point; while river has not reached the ocean, find the lowest pixel next to the river, and add it to the river". This algorithm did not generate meanders or deltas, but it did generate nice lakes (if the river falls into a local minimum, it fills all the land around it, until it breaks the wall). I am not an expert on rivers, but I have a feeling that flat lakes and rivers going strictly downwards are more natural (don't rivers carving through hills, subterranean rivers, canyons, and lakes with towering cliffs form simply because there is a kind of rock (limestone) which is very poor at blocking the water, effectively making the river generation algorithm treat it like air?). Anyway this was intended as just a fun simulation, not a game.

That description is very, very close to how rivers form in URR. They can carve valleys, but not that often, and they obviously head down-hill by default. Lakes form when a river cannot find an exit into a gorge, or an ocean square, and their depth is determined by a bunch of factors. Though, since swimming will hardly be a focus of the alpha, their depth and other factors will come much more into play later.

[miki151]

I'll revive this old thread. I've played around with height map generation, namely this algorithm: http://en.wikipedia.org/wiki/Diamond-square_algorithm. The terrain it makes is very unnatural though, as there are no valleys. Normally every point on the map should have a path to the ocean that's only going down. This will allow nice looking rivers. I was thinking of enforcing this as a second step (kind of "erosion"), but it would be computationally costly, and not necessarily give nice looking results. An algorithm that generates realistic mountains in one step would be much better. Ideas?