Minecraft Classic map generation algorithm
Analysis is based on the decompiled source of the classic c0.30_01c client.
Parameters:
- creator's name
- level width
- level depth
- level height
Returns:
- Minecraft level object
Perlin Noise is a noise function where the return value smoothly varies between input values close together https://en.wikipedia.org/wiki/Perlin_noise. It is implemented in a class with a method to create a noise distribution using a given pseudo-random number generator. After being initialised the noise function can be measured with a compute method which takes a 2D coordinate as input and returns a float which varies from -1 to 1 (exclusive) Input can be a float or integer and the compute method will always return the same value given the same inputs.
Octave Noise is the summation of multiple noise functions where each function has differing frequency and amplitude. When computed it produces a series of results with smoothly varying noise at multiple scales, similar to a fractal or real world terrain height-maps. The implementation in Classic Minecraft is a class which takes as argument to its constructor an integer number of Perlin noise functions to compute and sum together. Each successive noise function/octave has twice the amplitude and half the frequency. This means that an Octave noise function of octave 8 will, when computed for a given 2D position, return a value from -128 to 128.
Combined Noise is used in Classic Minecraft to create a noise function where the rate of change of the returned value can vary over the 2D plane, eg. some valleys will be particularly steep while others have gentle slopes. This is achieved by taking one noise function and using its result to modify the arguments to a second noise function. The class prototype takes two noise functions as arguments, either Perlin or Octave noise functions. its compute method returns:
noise1.compute( x + noise2.compute(x,y), y)
Where x, y are the given 2D coords and noise1, noise2 are the two noise functions.
Generation of a Classic Minecraft map, as seen on the sadly defunct browser-embedded version of creative mode that used to be hosted on the main Minecraft site, goes through a sequence of generation steps each time a new map is created:
- choose map size
- create height-map, "Raising..."
- smooth out height-map, "Eroding..."
- create strata, "Soiling..."
- carve out caves, "Carving..."
- create ore veins
- flood fill-water, "Watering..."
- flood fill-lava, "Melting..."
- create surface layer, "Growing..."
- create plants, "Planting..."
The players is prompted to choose from 3 default sizes; small medium or large. Small is 128 by 128 blocks in x,z coordinates (width and depth), medium is 256 by 256 and large is 512 by 512. All of the options have a height of 64 blocks with a water level at height/2 = 32. The entire map is created at once on generation and the edges of the map are impassible with a bedrock seabed two blocks below the water level.
Using:
- heightMap, a 2D array of size width X depth
- waterLevel, a constant of 32
- noise1, a combined noise function with two octave noise functions (of octave 8) as input.
- noise2, a combined noise function with two octave noise functions (of octave 8) as input.
- noise3, an octave noise function (of octave 6)
For each column in the x,z plane assign an elevation value to heightMap computed from:
Let heightLow be noise1.compute( x*1.3, z*1.3) / 6 - 4
Let heightHigh be noise2.compute( x*1.3, z*1.3) / 5 + 6
If noise3.compute(x,z) /8 > 0 {
set heightResult to heightLow
} else {
set heightResult to the maximum of heightLow and heightHigh
}
set heightResult to half its previous value
If heightResult < 0 {
set heightResult to 8/10 its value
}
heightMap(x,z) is then set to the integer component of heightResult + waterLevel.
Using:
- noise1, a combined noise function with two octave noise functions (of octave 8) as input.
- noise2, a combined noise function with two octave noise functions (of octave 8) as input.
For each column in the x,z plane assign a new elevation value to heightMap computed from:
Let a be noise1.compute( x*2, z*2) / 8
Let b be 1 if noise2.compute( x*2, z*2) > 0, otherwise 0
If a > 2 {
heightMap(x,z) is then set to: (int)((heightMap(x,z) - b) / 2) * 2 + b
}
Using:
- blocks, a 3D array of size width x height x depth
- noise, an octave noise function (of octave 8)
For each column in the x,z plane populate blocks in array with stone-to-dirt and dirt-to-air transitions:
Let dirtThickness be noise.compute(x,z) / 24 - 4
Let dirtTransition be heightMap(x,z)
Let stoneTransition be dirtTransition + dirtThickness
for y in height {
Let blockType be AIR
If y equals 0 then blockType is LAVA
else If y <= stoneTransition then blockType is STONE
else If y <= dirtTransition then blockType is DIRT
set block(x,y,z) to blockType
}
By doing so the block array is populated with lava at height 0, stone along with a variable thickness layer of dirt up to the heightMap elevation for that column and then air above.
This step involves creating multiple snaking caves of variable length which vary in direction and radius along their length. The total number of caves is given by width x height x depth / 8192
For each cave:
Let cavePos be a random point (x,y,z) within the (width,height,depth) space.
Let caveLength be floor((randomFloat() + randomFloat()) * 200)
//cave direction is given by two angles and corresponding rate of change in those angles,
//spherical coordinates perhaps?
Let theta be randomFloat() * Pi * 2
Let deltaTheta be 0
Let phi be randomFloat() * Pi * 2
Let deltaPhi be 0
Let caveRadius be randomFloat() * randomFloat()
for len in caveLength {
set cavePos.x to previous value + sin(theta) * cos(phi)
set cavePos.y to previous value + cos(theta) * cos(phi)
set cavePos.z to previous value + sin(phi)
set theta to previous value + deltaTheta * 0.2
set deltaTheta to (previous value * 0.9) + randomFloat() - randomFloat()
set phi to previous value/2 + deltaPhi/4
set deltaPhi to (previous value * 0.75) + randomFloat() - randomFloat()
If randomFloat >= 0.25 {
Let centerPos be a new point with each component equal to
cavePos.n + (randomInteger(4) - 2) * 0.2
// eg. centerPos.x = cavePos.x + (randomInteger(4) - 2) * 0.2
Let radius be (height - centerPos.y) / height
set radius to 1.2 + (previous value * 3.5 + 1) * caveRadius
set radius to previous value * sin(len * Pi / caveLength)
fillOblateSpheroid( centerPos, radius, AIR)
}
}
Where fillOblateSpheroid() is a method which takes a central point, a radius and a fillBlockID to use on the block array.
For each entry (x,y,z) within -radius to +radius in the block array:
dx = x - center.x
dy = y - center.y
dz = z - center.z
If (dx^2 + 2 * dy^2 + dz^2) < radius^2 and point (x,y,z) falls within level bounds {
If block(x,y,z) is STONE then replace block(x,y,z) with fillBlockID
}
Due to the multiplication of dy^2 by 2 this results in spaces which are wider than they are high.
The ore veins of coal, iron and gold are created in a similar manner to the caves, each is given an abundance value which affects the number of veins, vein length and radius of each vein. Abundances are; 0.9 for coal, 0.7 for iron and 0.5 for gold.
Number of veins is given by width x height x depth x abundance / 16384
For each ore vein:
Let veinPos be a random point (x,y,z) within the (width,height,depth) space
Let veinLength be randomFloat() * randomFloat() * 75 * abundance
Let theta be randomFloat() * Pi * 2
Let deltaTheta be 0
Let phi be randomFloat() * Pi * 2
Let deltaPhi be 0
for len in veinLength {
set veinPos.x to previous value + sin(theta) * cos(phi)
set veinPos.y to previous value + cos(theta) * cos(phi)
set veinPos.z to previous value + sin(phi)
set theta to deltaTheta * 0.2
set deltaTheta to (previous value * 0.9) + randomFloat() - randomFloat()
set phi to previous value/2 + deltaPhi/4
// unlike deltaPhi for caves, previous value is multiplied by 0.9 instead of 0.75
set deltaPhi to (previous value * 0.9) + randomFloat() - randomFloat()
// simpler derivation of radius here than for caves
Let radius be abundance * sin(len * Pi / veinLength) + 1
fillOblateSpheroid( veinPos, radius, oreBlockID)
}
Water is flood-filled into the map, spreading horizontally and down vertically, from the x,z edges of the map at a height of water level - 1.
Some underground water sources are then added to the block array to create flooded caves. The number seeded is: width x depth / 8000
For each water source a random x and z coordinate value is chosen and the y coordinate is set to water level - 1, or water level - 2. If this position in the block array is AIR then the water flood-fills out and downwards.
The lowest layer of the block array is always lava, having been set so during strata generation. A few lava flooded caves might form. Only width x height x depth / 20,000 lava sources will be seeded.
For each lava source a random x and z coordinate value is chosen and the y coordinate is set to (water level - 3) x randomFloat() x randomFloat(). If the position is AIR then lava is flood-filled from that point.
Using:
- noise1, an octave noise function (of octave 8)
- noise2, an octave noise function (of octave 8)
For each column in the x,z plane, determine block type of highest point in block array:
Let sandChance be (noise1.compute(x,z) > 8)
Let gravelChance be (noise2.compute(x,z) >12)
Let y be heightMap(x,z)
Let blockAbove be block(x, y+1, z)
If blockAbove is WATER and gravelChance is true {
Set block(x,y,z) to GRAVEL
}
If blockAbove is AIR {
If y <= water level and sandChance is true {
Set block(x,y,z) to SAND
} else {
Set block(x,y,z) to GRASS
}
}
Classic Minecraft maps include flowers on the surface, mushrooms underground and trees with a simple shape.
Flowers are created in patches, the total number of which is set to width x depth / 3000.
For each flower Patch:
Let flowerType be randomly chosen from Dandelion or Rose
Let patchPos be a random point(x,z) in x,z plane
Repeat 10 times {
Let flowerPos equal the patchPos
Repeat 5 times {
Set flowerPos (x,z) to previous values + randomInteger(6) - randomInteger(6)
If flowerPos is within level bounds {
Set flowerPos.y to heightMap( flowerPos ) + 1
Set blockBelow to be block( flowerPos.x, flowerPos.y-1, flowerPos.z )
If block( flowerPos ) is AIR and blockBelow is grass {
Set block( flowerPos ) to flowerType
}
}
}
}
Mushrooms are created in much the same way as flowers except they can be placed underground and not on the surface. There will be width x height x depth / 2000 patches of mushrooms.
For each mushroom patch:
Let mushroomType be randomly chosen from Red or Brown
Let patchPos be be a random point (x,y,z) within the (width,height,depth) space
Repeat 20 times {
Let mushPos equal the patchPos
Repeat 5 times {
Set mushPos (x,z) to previous values + randomInteger(6) - randomInteger(6)
Set mushPos (y) to previous value + randomInteger(2) - randomInteger(2)
If mushPos is within level bounds and mushPos.y < heightMap( mushPos )-1 {
Set blockBelow to be block( mushPos.x, mushPos.y-1, mushPos.z )
if block( mushPos ) is AIR and block( blockBelow ) is STONE {
Set block( mushPos ) to mushroomType
}
}
}
}
Finally trees are added to the map, there will be width x depth / 4000 patches of trees created.
For each tree patch:
Let patchPos be a random point(x,z) in x,z plane
Repeat 20 times {
Set treePos to patchPos
Repeat 20 times {
Set treePos (x,z) to previous values + randomInteger(6) - randomInteger(6)
If treePos is within level bounds and randomFloat <= 0.25 {
Set treePos.y = heightMap( treePos ) + 1
Let treeHeight be randomInteger(3) + 4
If isSpaceForTree( treePos, treeHeight ) is true {
growTree( treePos, treeHeight )
}
}
}
}
Where isSpaceForTree() is a method which checks for an empty region of AIR blocks treeHeight high and with a width and depth of 3 by 3 for the trunk and 5 by 5 for the canopy (the last 3 layers). This position is centered on the given position x,z coordinates and upwards from the y coordinate. It also checks if the block directly below the trees position is a grass block.
If such a space is found then isSpaceForTree() returns true, otherwise false.
growTree() creates a tree of given height upwards from the position given. The highest four x,z layers will contain leaves in the following pattern:
L: max max-1 max-2 max-3
..... ..... %###% %###%
..#.. .%#%. ##### #####
.###. .#O#. ##O## ##O##
..#.. .%#%. ##### #####
..... ..... %###% %###%
Key:
. air
# leaves
O tree trunk
% contains leaves 50% of the time
After this, it creates the rest of the trunk and sets the block below the trunk to dirt.
Once map generation is complete the resulting block array is put into a new Minecraft Level object along with the width, height, depth and water level. The level create time is set to system clock time in milliseconds, the level creator to creator's name and the level name set to the place-holder text "A Nice World".
The Level object is then returned to the object which called the Map generator.
- Frequently Asked Questions
- Setting up a MC Classic Server