Random 2D Tile-Map Generating Algorithm
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
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.