Developing a world generation algorithm

[mughinn]

So, in the makings of a roguelike, I'm trying to develop a somewhat good world generation algorithm, as of now I'm trying to get my own ideas and try them. This one is the one that I liked the most for now, and I somewhat made it.

I'll explain a bit the algorithm, and I'd like some criticism on it, and honest answers, if you think it's not a good idea just tell me, I wouldn't like to waste my time

First set a max width and height of a map, and get a good amount of random points(16 now) in it. Then i create a Voronoi diagram (https://en.wikipedia.org/wiki/Voronoi_diagram).

Having that, I abstract them into Plate tectonics, and "move" them into a random direction, overlaping them in some points.

Then i finally make the map, where the movement left no "land", i put water, when they overlap, i make mountains, and in the rest i make normal ground.

Please also keep in mind i haven't finished working on it, I know these aren't pretty, but i think it has potential.

Some generated maps (should work):

http://www.freeimagehosting.net/n9tmw
http://www.freeimagehosting.net/bo7tp
http://www.freeimagehosting.net/8gdhm
http://www.freeimagehosting.net/tfjze

Okay, editing before anyone posts, I managed to make it look a bit better by making 50 random points instead of 16.

http://www.freeimagehosting.net/ndqh1

[guest509]

  Looks pretty neat. Hard to know unless we know what kind of game. Is this a wander around and find the dungeons game? Or will it all take place on the surface? Is this the resolution of the map, or will game play be zoomed in?

[mughinn]

I'm currently brainstorming a lot while programming the ground of the game, the basic idea is to have a surface, with possible quests, events, with some small catacombs or towers, and then a final, big dungeon.

It's probably too big, and won't en up there, but surface seems important.

This is mostly a small demo to see if it works or if it could work, probably after making a map like this I would create a "true map", that, for example, would be scaled so that each of the example tiles be a 50x50 or more tiles in the real game.

Though some ideas for it would be nice too.

[naughty]

I think the areas created by the overlaps look a little unnatural (even with 50 points), you could smooth them with cellular automata or a blur filter though.

I'm currently looking into voronoi diagrams for a graph based 2D roguelike and there's some great ideas in this polygonal island generation article. Instead of the overlapping you could pick a path along the edges of the diagram and widen it into a river. If you're using more points you could also combine some areas into lakes and just smooth out the shore lines.

As a side note by far the fastest and most robust implementation of voronoi I've found is in the boost polygon library but it's in C++.

You're definitely on an interesting track though.

[Quendus]

I think it's a great idea - standard FBM noise makes very unnatural-looking continents and islands, with highest points on average in the middle of blobs rather than along coasts like real continents. This person tried the same thing, with very nice results: http://www.cartographersguild.com/regional-world-mapping/4737-tectonic-plate-fakery.html unfortunately they didn't share their code.

Two suggestions:
1. More flexible plate boundaries, and land boundaries within the plate. The beach isn't a tectonic fault - that will be further out to sea. If the individual cells have their own height values which can change according to the relative motion at faults (converging plates causing areas of land to rise, etc.) then you'll get much more natural looking coastlines and mountains
2. Oceanic plates. That way you can get much larger regions of ocean, and mountain ridges parallel to the coast.

[Krice]

Another way to approach this is not with algorithms but simply faking it and creating areas with much simpler routines. It certainly gives less predictable results which can lead to problems, but in world map they are usually not that critical. Just make sure the map can be travelled from important points to another.

[mughinn]

Thanks for the ideas, I'll be working on this for a while.

I'll keep reading stuff to get hints at more natural looking worlds.

So here are some more example following the easiest advice I got, random ocean plates.

Here are 2, made on 200 plates, the first one with 50 plates made into ocean plates, and the second one with 100.
Also, this plates are made with manhattan distance instead of normal, direct one.

http://www.freeimagehosting.net/ddwda
http://www.freeimagehosting.net/1whu9

This ones are respectively the same, with direct distance calculated instead of manhattan distance.

http://www.freeimagehosting.net/qnouz
http://www.freeimagehosting.net/ar1cu

There's still some smoothing to do, but i think they're going nicely. Thanks for the help.

[guest509]

  I can see that system being used to make a Dragon Warrior or Warlords style overworld where some land masses are connected by single tile bridges. Do you remember such things from the original Dragon Warrior? Cross the bridge and you are in a new zone with new bad guys. And you die. Horribly. :-)

[Quendus]

I like the two maps with 100/200 oceanic plates. I think they could be improved by keeping the same map size but decreasing the number of plates to something between 8 and 30 - perhaps with more varied plate sizes, and with rougher boundaries between plates.

Voronoi diagrams are nice for dividing space up, but they make unnaturally straight lines and neat corners. An alternative might be a random walk, or thresholded simplex noise.

[mughinn]

I think I'll deal with that with some cellular automata, to also deal with the lonely points, although i got to say that the islands formed are actually, in my opinion, pretty good formed, except for some odd straight lines around there.

I still have to optimize and start using delauney triangulation or some method to make this faster, at the moment I'm taking nearly a minute to make the 100x100 maps.

Unfortunately Jo, I never played the NES, I searched a viedo about the game, and I see what you're talking about.
Seems nice to have difficulty areas, I'll see if i can make t work with my current idea.

One more thing, Manhattan or Euclidean distance? I like both for different things, Manhattan seems to make more straight lines, but I think the islands it makes are much more nicer, but then, Euclidean makes for some realist continents.

[guest509]

  NEVER PLAYED THE NES!!!!!!!!!!!!   

[mughinn]

Yes, I know, i should download an emulator or something, keep in mind I'm pretty young barely 19 since yesterday.

[Quendus]

Build your own canon!

[mughinn]

What do you mean by building my own canon?

[AgingMinotaur]

What do you mean by building my own canon?

Probably that in 10-20 years it's your time to act shocked at the young'uns for not having played the classics from your childhood ("Never owned a PS2!? Get off my lawn!").

As always,
Minotauros