28

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.

Ace
  • 1,437
  • 6
  • 28
  • 46

3 Answers3

38

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.

Community
  • 1
  • 1
Ray Hayes
  • 14,896
  • 8
  • 53
  • 78
  • wow thank you , i will definitly take some clooser looks at that blog.. so quickly i've just found the polygon-map-generation from him http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/ i'm wondering if i could use that technique on a 2d tile-based engine. – Ace Aug 15 '12 at 11:17
  • first i've thought about generating IMAGES where each pixel stands for each tile, therefor i could ( actualli i dont know HOW ) just ruffly set some white areas and blur them out ( like a height map ) and then streighten them with contrast ... – Ace Aug 15 '12 at 11:17
  • ..., so all the areas that are white or grey will get white, and the black areas remain black. so i could get a naturally looking area , but the point is that i need mathematical inspiration ^^ – Ace Aug 15 '12 at 11:18
  • Rather than using noise bitmaps, Amit's example of creating random points, turning into Voronoi polygons and then using the neighbours to influence each other seems (to my eyes) to generate much more realistic looking worlds... E.g. less likely to have random mountains and more likely to have mountain ranges. – Ray Hayes Aug 15 '12 at 11:25
  • Of course you can use it to 2D tile maps.. After generating such map, you just have to evenly it up into the some number of even chunks. Split just logically, just inspect the rectangular fragments of the whole map. Then, for each tile, check the characteristics: is the terrain high? is there a water? are there trees? Collect the information, and then, for that map chunk produce a tile that matches that information: a mountain tile with river and a tree, and move to another chunk.. – quetzalcoatl Aug 15 '12 at 11:30
  • That way you will have a great configurable generator that allows you to create maps of specified level of detail. However, it adds another level of complexity. For 2D maps it is probaly easier to get few of the above generators and just generate a few layers directly. – quetzalcoatl Aug 15 '12 at 11:32
  • We used the polygon map generator to create a 2d tile map for Realm of the Mad God, just as quetzalcoatl suggests. First draw the polygons into a bitmap (instead of to the screen), then convert each bitmap pixel into a tile using the characteristics (elevation, moisture, water), then sprinkle monsters on top (species depends on elevation/moisture). – amitp Aug 18 '12 at 17:56
4

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

Mizipzor
  • 51,151
  • 22
  • 97
  • 138
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!

quetzalcoatl
  • 32,194
  • 8
  • 68
  • 107
  • yes that is the way i was thinking about , i get the idea when i lookes at this little tutorial... http://www.patrickmatte.com/stuff/physicsLiquid/ – Ace Aug 15 '12 at 11:23