Random 2D Tile-Map Generating Algorithm

Question

Can anyone tell me a way to generate island structures or hill structures like in minecraft?

I'm just searching for a proper THEORY for that random-shape generating, but it should keep a defined base pattern..

like: islands schould be rounded but variate in shape and scale ( min/max width & height ).

or: rivers schould not be straight lines, they should have curves and a random width.

or even: generating some sort of forest, where trees are placed in a way that the user can still walk through the forest (that's a simple one I think, just say that some blocks around a tree should remain blank, if code tries to put more trees around the last one )

What kind of math can I use to do such things?

I would be glad for some links for tutorials or references. I've searches all around the web for hours, but all I could find was some books to buy like "game mathematics" or something, but my budget is set to zero.

EDIT:

First of all, I'm sorry for my bad englisch.

Secondary I want to thank all of you for your answers. These are great references and I'll spend much time to go deeper in that.

Answer 1

I strongly recommend looking at Amit’s Game Programming Information and other blog posts by him. He had a whole series on creating realistic looking maps with rivers, coastlines, etc.

Building Worlds

Although procedural map generation can be applied to non-grid worlds, it’s most often used with grids. Viewed at a single point in time, generated game maps are rarely as nice as hand-crafted worlds. However, they have three advantages: (1) lower cost per world if there are many worlds to be made, (2) more replay value because the next time through the world is different, and (3) potential for the world evolving while the game progresses.

• Amit’s World Map Generator
• Procedural Content Generation: generating terrain, cities, buildings
• Dungeon generation in Unangband
• Generating game worlds with a lock-and-key structure so that certain rooms require objects from other rooms
• Algorithm for building rivers
• Adding rivers to randomly generated terrain
• The original Rogue algorithm for generating dungeons
• 11 Maze Generating Algorithms with demos and code
• Using noise functions to generate caverns such as those in Terraria and Minecraft
• Irregular shaped rooms, simple algorithm
• Resizable interior room regions
• Tunneler algorithm for digging dungeons in DungeonMaker
• Guide to random Terrain Generation techniques
• Wiki guide to procedural content generation
• Simulating Large Virtual Worlds

Amit's Polygonal Map Generation for Games (first item in list) is a hugely impressive article that talks about the logic of generating sensible shaped coastlines, islands, rivers, mountains, etc. Hugely impressive bit of work!

A Method For 'Growing' Rivers In A Randomly Generated World [included in above list] fairly simple algorithm for generating a river's path based upon the other 'tiles' in the map, e.g. their type and elevation.

Answer 2

I once found a great site for the theory when I made a rougelike. Have a look.

Answer 3

Quite often the maps are being logically split into layers/overlays like "base terrain height", "water level", "highlands", "trees", "housing" etc.

Then for each layer a different kind of generator is run. Very often fractals are used because they tend to generate interesting and hard to predict shapes. But only a part of the fractal is used. Using whole one would instantly expose the structure (on the top-level fractals are very repetitive) and viewers would notice it. So, the generated fractal is then distorted/modified/filtered/cut so that will not be obvious. For example, you may generate the base terrain level with some simple X-Y trigonometric oscillator, and then sum it up with a part your fractal image, limited to some min-max values, and you'd get an uneven terrain with noticeable hills and drops..

For all other layers, you usually cannot "sum up", because the layers other than terrain are not about "height" or "density" but rather they are 0/1 - place the tree here or not to place the tree here? But again, you perform it similarly: you generate some image (maybe a fractal again), then inspect the numbers and set a threshold value: everywhere when the number is higher/lower than X, you place/notplace the thing. You may additionally filter or branch it: for example if a tree would hit an under-water position, place a fish there or not place the tree at all.

I am surprosed you couldnt find resources on it. Few years ago googling for "terrain generation algorithms" would return many hits!