Author Topic: Let's talk a bit about world map generation!  (Read 31916 times)

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Let's talk a bit about world map generation!
« Reply #30 on: July 10, 2013, 02:54:25 PM »
World generation won't happen very often, so as long as it doesn't take long and as long as there's some kind of indication of progress, that's not a problem. Perlin and Simplex noise are more popular choices for heightmap generation at the moment, but they suffer from the same problem of geological implausibility. Libtcod has a very efficient erosion algorithm
If you want to do crazy-efficient erosion in real time (on a graphics card), you can take a look at Florian Boesch's craftscape demo: http://codeflow.org/entries/2011/nov/10/webgl-gpu-landscaping-and-erosion/

miki151

  • Rogueliker
  • ***
  • Posts: 264
  • Karma: +0/-0
    • View Profile
Re: Let's talk a bit about world map generation!
« Reply #31 on: July 10, 2013, 03:45:26 PM »
I'll have a look at libtcod. Is their algorithm documented anywhere? It doesn't have to incredibly efficient, but I'm trying to keep start up time below ~5 seconds. The terrain size is in the range of 1000x1000, so something linear would be great. I'm also afraid that the algorithm would do implausible things, like digging out straight lines to the nearest lower point. What's your experience?

Ideally I'd implement something that generates mountains in one step, surely there must be an algorithm.
KeeperRL, Dungeon Keeper in roguelike style:
http://keeperrl.com

Endorya

  • Rogueliker
  • ***
  • Posts: 513
  • Karma: +0/-0
  • The non-purist roguelike lover
    • View Profile
    • Email
Re: Let's talk a bit about world map generation!
« Reply #32 on: July 10, 2013, 03:53:58 PM »
I've been following your work for some time now, since the time your project was still about medieval fantasy. Yeah I did fight some trolls back then! Though I feel sad you discarded the fantasy setting, I'm still looking forward to play it!

Regarding the your map generating algorithm. It is the most beautiful, easy to ready and believable pseudo-ASCII map generator I've seen so far. Really, I got pretty amazing with it. Your clean overall design of the whole game is without a doubt the best experience I had so far in the rogue-like world.

EXCELLENT WORK!
"You are never alone. Death is always near watching you."

miki151

  • Rogueliker
  • ***
  • Posts: 264
  • Karma: +0/-0
    • View Profile
Re: Let's talk a bit about world map generation!
« Reply #33 on: July 11, 2013, 12:59:16 PM »
I had a look at libtcod's height map generation. It looks like the main elements are placing a hill, which is a part of a spheroid and rain erosion, which simulates rain drops that roll down and take soil with them. What to do with it is left to the user. I'm not sure if this is enough to generate really good terrain, does any one have any experience?

By the way, I'm specifically looking for an algorithm that generates terrain without local minima, just like (mostly) in reality. This will let me generate a nice river system almost for free.
KeeperRL, Dungeon Keeper in roguelike style:
http://keeperrl.com

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Let's talk a bit about world map generation!
« Reply #34 on: July 11, 2013, 01:20:30 PM »
Libtcod's heightmap generation is a lot more flexible than that. The "hmtool" included with the library lets you add r multiply by FBM noise, add hills, divide into a voronoi diagram, smooth the landscape, simulate rain erosion, and normalise the result. Once you find a sequence of operations that generates a suitable map, you can use that algorithm with different seeds to get similar-but-different maps.

miki151

  • Rogueliker
  • ***
  • Posts: 264
  • Karma: +0/-0
    • View Profile
Re: Let's talk a bit about world map generation!
« Reply #35 on: July 11, 2013, 02:05:03 PM »
Do you know what the Voronoi diagram thing does? (I know what a Voronoi diagram is, just don't know how it can be used for terrain generation)
KeeperRL, Dungeon Keeper in roguelike style:
http://keeperrl.com

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Let's talk a bit about world map generation!
« Reply #36 on: July 11, 2013, 02:56:58 PM »
Why not see for yourself? Load the hmtool executable from the libtcod download and click on the voronoi button.

AgingMinotaur

  • Rogueliker
  • ***
  • Posts: 805
  • Karma: +2/-0
  • Original Discriminating Buffalo Man
    • View Profile
    • Land of Strangers
Re: Let's talk a bit about world map generation!
« Reply #37 on: July 12, 2013, 10:12:59 PM »
Here is a pretty cool article about Voronoi diagrams and such: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/

As always,
Minotauros
This matir, as laborintus, Dedalus hous, hath many halkes and hurnes ... wyndynges and wrynkelynges.

miki151

  • Rogueliker
  • ***
  • Posts: 264
  • Karma: +0/-0
    • View Profile
Re: Let's talk a bit about world map generation!
« Reply #38 on: July 13, 2013, 09:35:05 AM »
Yup, I've read it a few days ago. It's the first algorithm that I've found that guarantees a "no-local-minima" level. It gave me the idea to start generation with a river system, and then generate a height map, such that the farther away from water, the higher. I'll try it out soon.
KeeperRL, Dungeon Keeper in roguelike style:
http://keeperrl.com

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Let's talk a bit about world map generation!
« Reply #39 on: July 13, 2013, 02:12:55 PM »
That might not make a very realistic river system - real rivers don't tend to form loops.

guest509

  • Guest
Re: Let's talk a bit about world map generation!
« Reply #40 on: July 14, 2013, 04:43:29 AM »
  Dunno if relevant, but I have been imagining an overworld where the x axis corresponds to wetness and the y axis corresponds to heat. With mountains and rivers flowing through.

So the very bottom right is the hottest and wettest, so it's basically tropical ocean. The top right is iceberg ocean. The top left is coldest and driest, so tundra. The bottom left is hottest and driest, so it's mostly desert.

That was how I was going to create my often attempted and often failed Zelda Opus roguelike.