Randomization of biomes

You know how in Minecraft, the World is ever-expanding and all the biomes are randomized?

My generalized question is: In relation to a space simulation that is also ever-expanding as the player moves about the world, how would one go about programming this randomization in Java?

My real question is: Could I get a simplified example broken down into these example classes:

astroids (This would include how many astroids there are, their positioning in space, their size, how often the larger astroids occur, how close they are to each other, the limitations of how many of the large asteroids can be in one field, how often astroid fields are generated, etc.)
star-types (size, color, type, how often they occur, where hey occur, etc.)
inhabitable-planets (size, positioning, how often they’re generated, where they are generated, etc.)

This would be very helpful currently since I wish to make a simplified version of such a program.

Minecraft Example
Biomes in minecraft are not directly determined; a biome is selected based on the local temperature and humidity (for example a hot dry biome ends up as desert, a hot wet biome ends up as rain forest, for the whole graph see http://www.minecraftwiki.net/wiki/File:BiomesGraph.png [Note this graph is outdated but the concept is still current]).

Now you could simply choose the temperature and humidity randomly; but that would lead to each block having a different biome (really really stupid) or you could still choose randomly but on a larger scale; this would lead to horrible sharp edges and biomes that shouldn’t be next to each other. For example desert could be next to arctic tundra (still quite stupid).

Naive solutions i.e. don’t do this
A method that would solve this problem would be to stop choosing the temperature and humidity randomly but start choosing the change in temperature and humidity randomly. Initially this seems really nice, but because the player can walk through the world in any manor you end up with problems when the world curves back around on itself; you get nasty joins. Even if you create rules such as the world is created outward from the origin irrespective of walk direction you still have to make parts of the world the player hasn’t explored yet. I.e. walk 100m North, then 10,000m East, then 200m South. Suddenly and all at once you need the “other 10,000m East” that you didn’t walk down to work out what the new block is going to be like.

Perlin Noise (and its more efficient cousin simplex noise)
Perlin noise takes the position co-ordinates as an input (as well as a main seed) and outputs a value between -1 and +1 that is both random and slowly changing as your co-ordinate changes. It achieves this by sampling random numbers on several length scales. For example, the point at (1100, 0) will sample:
(1088,0)[-16 (rounded)]
(1120,0)[+16 (rounded)]
(1096,0)[-8 (rounded)]
(1012,0)[+8 (rounded)]
…
(1100,0)[+0]

NB by rounded I mean that (for example) at the +-16 level the sampling point is moved to the nearest value divisible exactly by 16, so (1100, 0) (1101, 0) (1102, 0) and similar will all sample (1088,0) as their -16 point

And will sum them, the weighting will determine how quickly the value changes, high weighting for the large scale will create slow undulations, high weighting for small scales will create more jagged quickly changing values.

A point next to it (1101, 0) will sample the same higher level point but the lowest level point will be different so it changes only slowly (the weighting of the higher points will also change). (1109, 0) will only have the very high level points in common.

This means that to calculate (1100, 0) you don’t need to know any other point, your can generate them as and when and they will just “end up” being gradually changing.

Note that simplex noise is considerable faster than perlin noise as well as better in several more technical ways; however the maths is considerably more complex (which is amusing given the name)

Conclusion
If you just want true randomness (i.e. looks like static) just use java’s inbuild random functions. If you want random but slowly changing noise (i.e. looks like mountains) use Perlin or Simplex noise. Perlin and Simplex noises are available for any dimension but perlin noise gets very inefficient for high dimensions whereas simplex noise only slowly grows in complexity with dimension.

References:
Explanation of perlin noise
Java implimentation of perlin noise

Filed under: softwareengineering - @ 01:17

Thẻ: algorithms, random

Thiết kế website giá rẻ

Danh mục

Randomization of biomes