World generation
A Minecraft Chunk is a data structure that holds blocks and allows Minecraft to deal with large amounts of blocks as a unit. A chunk is 16x16x128 blocks in size. Minecraft chunks are created on demand by the server. This usually is the result of the player approaching the chunk coordinates. A chunk is generated, filled with terrain, then populated(decorated) in various stages. When the chunk is no longer needed(player left area, chunk loader disabled, etc) then the chunk data will be written to disk and the memory it occupied is freed. When the chunk is approached again Minecraft will check if it exists on disk first and load it instead of recreating it via the generation process.
When Minecraft needs a chunk it requests it from the ChunkProviderGenerate.provideChunk(...) function. If the chunk hasn't been created then ChunkProviderServer.OriginalLoadChunk(...) will create a new chunk and populate it with stone according to the height map and/or terrain build rules for the chunk. Next Chunk::PopulateChunk() checks the chunk layout and populates(adds decorations) if conditions are right. Next the function ChunkProviderServer.populate(...) will run to fill the chunk with ore, trees, etc if the chunk hasn't already been populated.
Finally, once ChunkProviderServer.populate(...) has completed decoration the function GameRegistry.generateWorld(...) will run for mods wishing to capture the event.
There are numerous points in the WorldGen process that generate events for mods that can be exploited to do basically anything. It is not necessary to go over all of them here.
All of the work to do the actual decoration in a single chunk lies in ChunkProviderGenerate.populate(...) function.
PopulateChunkEvent.Pre(...) event is generated for mods.
Generate Structures(if any):
MapGenStronghold.generateStructuresInChunk(...);MapGenVillage.generateStructuresInChunk(...);MapGenMineshaft.generateStructuresInChunk(...);MapGenScatteredFeature.generateStructuresInChunk(...);
Generate Natural Features:
- LAKE -
WorldGenLakes(Blocks.water)).generate(...)//Only if biomegenbase is not a type of desert - LAVA -
WorldGenLakes(Blocks.lava)).generate(...) - DUNGEON -
WorldGenDungeons()).generate(...)
Each biome type in Minecraft(Desert, Jungle, etc.) has it's own BiomeGenerator class derived from the class BiomeGenBase. It determines how the biome will be generated and contains the mob spawning list. The biome type is determined by Minecraft from the coordinates of the chunk:
BiomeGenBase biomegenbase = this.worldObj.getBiomeGenForCoords(...). How the biome is selected is beyond the scope of this document.
The BiomeGenBase::decorate member function will decorate the chunk in the specific style of that Biome. It achieves this by using the theBiomeDecorator member object of class type BiomeDecorator and calling its BiomeDecorator::decorateChunk(...) member function which sets up the decorator on a specific chunk. This decorator object is customized by the BiomeGenerator for it's specific style and needs.
For instance, the BiomeGenForest class sets up the decorator to always create trees if the field is 3(roofed forest).
The decorator object is responsible for all generated content. The heart of the decorator is the BiomeDecorator::genDecorations(...) member function. Here nearly all of the Minecraft content you see is created step by step in this order:
- ORES (via
BiomeDecorator::generateOres(...))- DIRT
- GRAVEL
- COAL
- IRON
- GOLD
- REDSTONE
- DIAMOND
- LAPIS
- Modded Ores(via
OreGenEvent.Post(...))
- SAND
- CLAY
- SAND_PASS2
- TREE This is important for us!
- BIG_SHROOM
- FLOWERS
- GRASS
- DEAD_BUSH
- LILYPAD
- SHROOM
- REED
- PUMPKIN
- CACTUS
- LAKE (Why is this here and also in the populate function?)
Each one of these can be interrupted or overridden by mods. If you are interested in changing how trees are created then the TREE decorate event should targeted. A decorate event can be captured with an event handler like so:
public class DecorateEventHandler { @SubscribeEvent(priority=EventPriority.NORMAL, receiveCanceled=true) public void onEvent(DecorateBiomeEvent.Decorate event) { if(event.type == EventType.TREE){ //Does not affect roofed forests //Make custom trees here or do nothing. event.setResult(Result.DENY); //Result.DENY will prevent vanilla trees from being created } } }
And the event handler can be registered like so:
MinecraftForge.TERRAIN_GEN_BUS.register(new DecorateEventHandler());
After the decorator has finished it's task then the biome generator runs a few more routines to wrap up the creation process:
- ANIMALS (via
SpawnerAnimals.performWorldGenSpawning(...)) - ICE
-
PopulateChunkEvent.Post(...)event is generated for mods
The process of the decorator filling the chunks with goodies and pretties is fairly simple. It picks a random spot in the chunk and replaces the blocks with something else. This works great for ores and flowers and things that take up a single block but what if you are creating a multiblock structure such as a tree? The blocks the tree is composed of can cross the chunk boundry and you can't be sure that there's a chunk there at all! Attempting to create blocks in an uninitialized block can create huge performance issues or worse it can potentially crash the entire game.
One possible solution to this problem is to precheck that the random placement of the whole tree fits comfortably in one chunk and does not cross the boundry into a neighboring chunk. The problem of this approach is that the pattern of trees on the landscape would look unnatural with obvious empty rows going from east to west and north to south. Human pattern recognition is powerful and the results would be noticed immediately even from inside the forest. Another solution is to use hashes for tree placement and just build partial trees that fit into the chunk and count on the rest of the tree being built from the same hash in the neighboring chunk later. This would solve the unnatural placement problem but would mean building the tree potentially four times if it was on the intersectional corners of four chunks. It also adds unecessary complications to the code base.
Yet another solution is to simply check that all 8 of the surrounding chunks exist before we even place a single tree. If all 8 don't exist then flag the chunk as undecorated and refuse to decorate it until they do exist. By confirming that all boundries have valid chunks we can build structures that go over the boundry up to 16 blocks before we potentially encounter an uninitialized chunk. This means we can make some pretty big structures comfortably however this solution is also not without it's problems. We have no idea if trees have already been created in the neighboring chunk. We could be generating trees over existing trees in the neighboring chunks and make terribly broken looking generation. We could solve this by detecting existing trees by checking for key blocks that make up the trees but we are needlessly wasting cycles. We could store all of the tree positions in memory and check that way but it's hard to get around the performance issue caused by this bad design choice. Maybe a solution could be created using hashes and hashmaps but these solutions carry memory space problems and code complexity with them.
The solution that minecraft uses is sort of like the adjacent chunk check previously mentioned with a slight variation to prevent tree collisions. When Minecraft is about to decorate a chunk it checks for existing chunks to the south(z+1),the east(x+1), and the southeast(x+1,z+1). If these conditions are met then Minecraft will decorate the chunk and flag it as decorated, if not then the chunk's decorated flag will remain false until it can be decorated at some other time. Once it has been established that these 3 other chunks exist the tree decorator will offset its 16x16 "build volume" for the trees by +8 blocks on the x and z axis. In a sort of virtual 16x16 chunk that spans between the centers of all 4 chunks there is a safe zone where trees can be built without running the risk of running into uninitialized chunks provided that the trees are sufficiently small. This solves the chunk "overflow" problem.
_Chunk Population Zones: active, lot, arena, and stage. These terms are utter contrivances but should be helpful in describing the layout._
- The active zone is the 16x16 chunk being (potentially) decorated at the moment.
- The lot zone includes all of the surrounding chunks around the active chunk and the active chunk itself.
- The arena zone is the 4 chunks that are made up of the active chunk and it's neighoring chunks to the south, east, and southeast.
- The stage zone is a virtual 16x16 "chunk" that straddles the chunk intersection in the middle of the arena.
All of the chunks that make up the arena must exist before a stage can be created.
Chunk::PopulateChunk() checks the entire lot in 4 steps. At each step it checks for the existance of neighboring chunks that can make up an arena and potentially decorates the stages of up to 4 chunks if those neighbors exist.
| Chunk.PopulateChunk() |
|---|
 |
E: Chunk that will be tested for existence
U: Undecorated chunk that will be decorated if the chunks marked E exist.
Notes: The center chunk was just created and is guaranteed to exist. Whether the existing chunks are decorated or not is of no consequence.
For each of these 4 steps the function ChunkProviderServer.populate(...) will run on the U chunks to fill the chunk with ore, trees, etc if the chunk hasn't already been populated.
So what about trees intersecting with each other? Surely if minecraft is randomly placing trees in the stage then some of them would be built too close together or even in the same place. Why have we not seen this in the world? Minecraft cheats to achieve this. What Minecraft is actually doing is creating a 4x4 grid of tree cells in the stage zone. Each of these cells are 4x4 Minecraft blocks in size for a total of 16 cells per stage zone.
| Chunk Tree Cells |
|---|
 |
The existance and/or type of a single tree in each cell is decided at random depending on the forest density of the biome, the biome type, and the presence of soil at the location. In order to prevent the look of being created in a grid the position of each tree is "jostled" by adding a random small amount(0-2 blocks) on each x and z axis. This amount is not large enough to push it into a neighboring 4x4 tree cell. Viola! Tree trunks can't touch each other. An artifact of this algorithm is that rows 4,8,12, and 16 in every chunk on the x and z axis never generate trees but it's not that noticable.
| Vanilla Tree World Generation |
|---|
 |
- The cells of the stage are populated in this order
- The potential position of trees in each cell
- Some positions are randomly eliminated based on the biome's forest density
- Positions are moved on the x and z axis randomly by 0 to 2. The dotted lines show the allowable range.
- Trees are constructed from logs and leaves if space if available
If you play with the mod Pam's Harvestcraft you'll see what happens when a tree is placed into the world after vanilla tree generation has occured. Harvestcraft trees can spawn directly next to an existing tree or even write over it completely because of the difficulty in detecting existing trees. The modder obviously decided that it's not worth the difficulty of detecting existing trees and just leave it to chance. Large Minecraft trees also follow this rule. Neighboring trees are simply written over. Minecraft tree vertical positioning is done by looking for the highest block in the column of blocks at the decided upon x, z world coordinates. We will also use this method for deciding our vertical(y axis) world position.
There are times when generating a tree could cause it to intersect unaturally with the landscape. In order to prevent this the Minecraft tree building algorithm will inspect the rectangular prism shaped volume for blocks that are not leaves, logs, or air. If the algorithm finds any other block type it will jam and the tree will not be created. This includes jamming on natural blocks like stone and dirt. Leaves and logs are given exception so trees can grow closely together. Right next to each other in fact.
Okay, so now we have a basic understanding of how Minecraft generates trees.
Dynamic Trees are composed of branch blocks that form a branching network. The Rooty Dirt block is tick sensitive and will send a growth signal through the network when ticked. The signal traverses the blocks from the base trunk(also a branch) directly above the Rooty Dirt selecting a single path at branch intersections along the way until it reaches an end branch. When the end branch is reached it will attempt to lengthen the path by one block in a direction decided by the algorithm appropriate for the tree species. If the lengthening is successful the signal will make a return journey back to the Rooty Dirt block and will thicken the branches along the way. The amount of thickening is also determined by the species. Branch intersections are calculated as the Square root of the sums of the cross sectional area of all of the combining branches that are not facing the direction of the Rooty Dirt block in the network. It is important that the tree network follow a few general rules:
- Each tree is it's own branch network
- There must be one and only one Rooty Dirt block per tree network
- Signals originate from the root node(Rooty Dirt Block) and nowhere else
- Tree branch blocks must be connected in order for signals to propogate
- Two or more tree networks must not be connected to each other
If we used the tree generation tactic employed by Minecraft worldgen then we quickly run into a big problems. The first and most obvious problem is that Dynamic trees are much larger than Vanilla trees. Inspecting the build volume for the placement of a potential tree will turn up many hits for tree jamming blocks making suitable locations rare. Plus a larger volume means more wasted processing trying to inspect all of the blocks for jammers. Placing the trees in a 4x4 cell(like Vanilla) will quicky lead to intersecting dynamic trees and colliding branch networks which violate the network rules. Violating the network rules make nonfunctional or unconvincing looking tree structures. Let's avoid that somehow.
We have three problems that need to be addressed for the placement of new trees:
- How to do this without inspecting the entire placement volume for jammer blocks(CPU intensive)
- How to place our tree models into the world without running into other trees and causing a network collision.
- How the location and shape of new trees are decided to make the environment look natural
One solution that could produce the best looking results is also the most impractical. One could simply program the decorator to plant dynamic saplings like a player would plant a seed and then "age" the chunk by pulsing the grow signal on all of the rooty dirt blocks in the stage a number of times or until they all run out of soil fertility. The Vanilla method of a 4x4 grid of 4x4 block tree cells would work just fine for this approach. The networks are created naturally and since the branch growth logic is constantly inpecting neighboring blocks for collisions everything will grow perfectly and look great. So what's the problem? Chunk generation performance is completely destroyed. Individual chunks could take up to a full minute to decorate. This is obviously unacceptable if we want to actually play the game. We could plant the saplings and then move on.. not growing the network at all. This would be very fast. But there would be no forests unless you waited around for days for them to grow. Not fun. It would seem that if we want WorldGen to actually function we would have to make pregrown tree models and load them from a file on startup. Fine, it's doable. But the placement problem still exists.
Let's solve the jammer inspection problem first. If we code the model as a series of runs, turns and divergent forks then we can draw the model from the root node and trace out each branch until it hits a non-air block. When a non-air block is jamming the path then backtrack to the latest divergent point in the network and continue with the rest of the model. If this method is used then we can draw partial models and not worry about inspecting the entire axis aligned bounding volume. It also gives us a chance to terminate early on a bad path, which can improve performance and appearance. Once the network is created a signal can be sent to "inflate" the tree. The inflate signal can traverse the branches and calculate their proper thickness. When the signal reaches an end run of a branch it can create leaf clusters around it with a 3d "stamp" of what a cluster of leaves looks like for that particular tree. We can also keep track of where the leaves and branches are created and "age" them with a few artificial ticks to make sure that doomed blocks(such as leaves without adequate light) are destroyed before they are loaded. This works well enough and there's room for optimization. Plus if the model can be encoded as a string we could have a portable method for storing, sharing, and creating tree shapes.
Now let's solve the network collision problem. Using the branch model mentioned above is less useful since we would have to check every single block surrounding each new block for other branches. Again this is a performance issue. Fortunately it makes no sense to have tree networks close together as they would smother each other and wouldn't have grown in that way anyway. So all we need to do is make sure that each model has a boundry that can't be crossed by the boundry of another tree network. Since the physical structure of a tree can be approximated with a cylinder(circle on a 2d map) we'll just use a circle as a boundary. Checking if 2 circles intersect is mathmatically trivial. We will store a circular boundary in memory for any tree that is built and test it with the boundary of a potential tree. If the boundries intersect then we won't create the new tree and thus no collision will be created. The boundries will be stored with the pregrown tree model and will be sized to fit it's branches(ignoring the leaves) with a +1 block buffer ring. The center of the circle will be the rooty dirt block. We can store the boundary circles in the NBT data of the chunk. So if an adjacent chunk is created at a later time it won't attempt to create a tree too close to an existing one. Implementing a system like this would make it impossible to introduce colliding networks. That's good!
One more problem to solve and it's a huge one. How do we know where to put the tree to begin with? The Vanilla 4x4 grid method doesn't help us because the cells are too small and our trees have varying sizes. We could simply scatter shot the stage with random points checking for boundary intersections with existing trees and creating a tree where no such intersection exists. We could do this and terminate after a decided upon number of failures(Example). We could even test several scenarios for the placements to see which one maximizes the amount of trees that could be placed. This could work but there's more efficient ways to find locations without constantly throwing darts to see which ones stick. What we want is to maximize the scenery by packing the trees closely together at their boundries. We also want to take into account the varying boundary sizes for each prospective model so we can make denser forests with trees of varying sizes. In addition to all of that we want to select tree sizes that are smaller(tall and narrow) for dense forests and bigger(short and wide) in open areas. In other words we need to pack circles, and pack them tightly.
Then hidden concept of what we are trying to achieve has been largely solved by image dithering algorithms. If the optimal placement for a black pixel in a sea of white pixels can be determined from a greyscale image in such a way that the result is still recognizable as the original picture then the degree to which it matches the original is representative of the quality of the dithering algorithm. A quality dithering algorithm will space black pixels uniformely on a canvas in a way that prevents patterns from emerging and pixels from touching if possible. There are several algorithms in the wild but the one that is most relevant to our needs is called Adaptive Incremental Stippling. This algorithm uses circular boundaries to determine pixel placement. Circles are not permitted to intersect. Darker areas from the source image will create circles with smaller radii so they can pack closer together. Light areas select larger boundried circles that force other black pixels farther away. New circle locations are created tangentially to an existing circle. If two tangential circles already exist then the circle is created tangentially to both. If no circles exist then a "seed" circle location is chosen at random. The process continues until there is no room left for any additional circles. Several optimization are employed to speed up the process and help determine the next circle location. One of which is that each circle has a mask on it's circumference that determines where a neighboring circle is already occluding. When a new circle is joined to a neighbor they are mutually masked off from each other. When all of the circles have no more room on it's boundary for a new circle then the algorithm is finished. This sounds exactly like what we need. There's plenty of information on Adaptive Incremental Stippling on the web as well as numerous javascript demos to view if you need more information.
We will be using Adaptive Incremental Stippling(AIS) using the PoissonDisk Distribution but we will be simplifying it and modifying it for our needs. We can use AIS to determine the placement of new trees(pixels) and boundaries(circles) for them. The radius of each tree boundary can be derived from a sample on a 2d perlin noise map on the x and z axis. Just like perlin noise can be used to represent terrain height at a location we will use it to represent forest density. The density will be modulated by the biome.theBiomeDecorator.treesPerChunk value from the Minecraft biome. This will allow for more trees in forests and fewer on plains.
We will use preconstructed blocky circles that are appropriate for Minecraft's blocky environment. We will need to store the circles in their respective chunks in case chunk generation needs to continue from where we left off. We need only store the chunk circles in some kind of list and store that list in a chunk coordinate keyed hashmap. The NBT data of the chunk can be used to store the circle data on disk when the chunk is saved or loaded. Circle data is simple and can be described with 3 terms: x axis, z axis, and radius. We should make the minumum boundary radius 2 since anything smaller won't hold any structure that would look like a tree anyway. We don't need very large circles either. In fact if we keep the radius 8 or smaller we can prevent the tree from flowing over outside of the arena because the boundries will always be in the arena, no matter where the tree center is in the stage.
| Safe Boundaries |
|---|
 |
The largest circle placed at the furthest extent in the stage can not flow outside of the arena and is thus safe. This is true for all 4 corners and the edges.
Since we are dealing with blocky circles we will need to find a way to make these circles pack tightly with the most amount of edge contact and try to minimize no contact or corner contact when possible. A lookup table can be precalculated and employed for all of the angle cases between 2 circles of predicted integer radii and positions. The lookup table I created for all circles radius 2-8 can be found here. We can also use a 32bit mask to represent the border mask with 11.25 degrees of resolution which should be adaquate for our application.
| The circles |
|---|
 |
The chosen set of circles and their blocky boundaries. The approximate diameter of each block circle is R*2+1
| 2nd Circle Algorithm | 3rd Circle Algorithm | ||
|---|---|---|---|
 |
Start with an existing unmasked circle that was created in a random location with a radius derived from a 2d perlin noise map at that location. |  |
A partially masked circle is selected at random from the selection of existing circles. Here the R8 circle is selected as master and the R6 circle is ignored for the moment. |
 |
A random angle is selected and is rounded to the nearest angle used in the fast lookup table. |  |
The master circle's arc mask is inspected for a transition from high to low bit. Where this transition occurs is rounded to the nearest angle used in the fast lookup table. |
 |
A Perlin density function is read for the relative coordinates at [sin(θ)*1.5r8,cos(θ)*1.5r8] to determine the radius of the new circle. In the case shown the radius is 6. |  |
A Perlin density function is read for the relative coordinates at [sin(θ)*1.5r8,cos(θ)*1.5r8] to determine the radius of the new circle. In the case shown the radius is 5. |
 |
A fast lookup table is used to find best x,y fit for the angle and the radii of the 2 circles. In this case we will choose the closest angle from the table that maximizes edge contact of the blocks. |  |
A fast lookup table is used to find best x,y fit for the angle and the radii of the new circle and the master circle. |
 |
Tangent angles are calculated mutually between the 2 circles. |  |
If the new circle is intersecting with any other circles then the one with the greatest overlap is chosen as a slave circle. In the case shown the R6 becomes the slave circle. The cross product of the positions is used to determine the handedness of the new position. |
 |
Arc masks are generated from tangent angles. |  |
The new circle is optimally repositioned by using the same fast lookup table and cross referencing for the master and slave circles. |
| From this point on the 3rd Circle Algorithm will be employed since we will always have 2 or more circles to work with. |  |
Tangent angles are calculated mutually between the 3 circles. | |
 |
Arc masks are generated from tangent angles and the process is complete. | ||
 |
However in the case that the new circle in it's adapted position is still overlapping an existing circle then the new circle is deleted but the modified masks on the remaining circles remain intact. | ||
The radius range for our circles is 2-8 blocks or 7 values. We can store 7 values in 3 bits with 0 reserved as a special case. We can use small numbers for each term if we store each circle as an offset from the chunk's world position. That means we would need 8 bits to store the position in the chunk(16x16=256=2^8). That's 8 bits for the position and 3 bits for the radius for a total of 11 bits for each circle.. seems akward. We could do better.
If we take a page from Minecraft's playbook and make a 4x4 grid of cells out of the stage with each cell being 4x4 blocks we can pack it even more elegantly. Each 4x4 cell can only hold one of the smallest radius tree. Even on the opposite corners the small circles will intersect. That means that no cell can have more than one circle. And since each cell is only 4x4 we can store the offset from the cell corner in 4 bits(2 bits for x, 2 bits for z). If we take the 3 bits for the circle radius and 4 bits for the cell offset we get 7 bits to describe any circle at any position within a cell. With one extra reserved bit we can represent it in a single respectable byte. For empty cells a radius of zero will represent no circle. With an array of 16 bytes we can describe the layout of any arrangement of circles(with radius 2-8 blocks) that could be possible for the chunk. Not bad. A small static sized array will help us manage memory a little better rather than pushing circle objects into a list. Since the active chunk and the stage for it are offset by +8 blocks on the x and y axis then those units will need to be added to the final position of the circle before it's used.
| Cells |
|---|
 |
An array of 16 bytes to define the circle layout for a stage
| Cell Encoding |
|---|
 |
Each of the 16 cells are encoded as a single byte.
- X: The X offset of the circle center within the cell. (0-3)
- Z: The Z offset of the circle center within the cell. (0-3)
- Radius: The radius of the circle - 1. (0-7) Zero means no circle, any other value will have 1 added to it before use to make the radius 2-8.
- Rs:Reserved bit.
The above method is what we have chosen to use but it's not without it's caveats. Here I will outline some issues and their workarounds.
Firstly, we need to know when to stop generating circles. Since the minecraft world is absolutely massive on it's x and z axis we should limit where the circles stop. A lot is a good limiting scope. When a stage is to be decorated it should not yet contain any circle centers. We will pull all of the existing circles stored in the surrounding chunks(the lot) and build the new circles off of them using the 3rd circle algorithm until none of the circles in the entire lot have any more free arc mask. In the case where there are no circles in the lot we will create a new circle at a random position in the stage and start the process with the 2nd circle algorithm. But what if we end up creating new circles that are located in a chunk that doesn't exist? We can solve that by providing each new circle that's temporarily generated with a "real" flag. We will only store the real circles in the chunk when we are done. The only circles flagged as "real" will be those that have their center block inside of the stage. All other (non-real)circles will be discarded as a sort of scaffolding when the algorithm completes. These outlying circles in the lot that are not in the stage will also have their arc masks treated differently. When a "non-real" circle is created it's arc mask will be masked off in the directions facing away from the arena. This will prevent new circles from being created outside of the lot and limit the circle creation to where it counts.
The second problem is that if we are sampling a particularly dense or sparse area we could end up with circles that are either all 2 or 8 in radius. This can lead to the circle packing algorithm making gridlike patterns which is to be avoided when possible. A simple working solution is to "jostle" the circle radius that is sampled from the perlin map by a unit or two at random. This slight variation of radii will cause the packing algorithm to find positions that look more natural.
A third problem is how to deal with areas that are particularly sparse, such as a savanna biome. The maximum distance we can space circles apart is 17(R8+R8+1) blocks between centers. This is actually too close and looks weird when there's a tree at every possible circle with a radius of 8. A simple solution that seems to work well is to discard some of the tree build operation in radius 8 circles. This discard is done with a weight that depends on the biome density in the build area.
With these additions the circle generation algorithm is adapted to life in a chunk environment and is ready for use.
We can devise a simple bytecode "script" for drawing a tree. The only commands we need are to go forward by a specified amount, turn in 1 of 6 directions, fork a path and return to a previously forked path point. Fairly uncomplicated. In my implementation I have decided to use a nybble(4 bits) to hold 16 commands which I've outlined below.
| Value | Action |
|---|---|
| 0 | Do Nothing |
| 1 | Go Forward 1 |
| 2 | Go Forward 2 |
| 3 | Go Forward 3 |
| 4 | Go Forward 4 |
| 5 | Go Forward 5 |
| 6 | Go Forward 6 |
| 7 | Go Forward 7 |
| 8 | Turn Down |
| 9 | Turn Up |
| A | Turn North |
| B | Turn South |
| C | Turn West |
| D | Turn East |
| E | Fork |
| F | Return to Fork |
Being able to represent 2 commands per byte is pretty tidy. If we happen to have an odd number of commands the last nybble can be 0 without affecting the output. The turn command directions are ordered per the Minecraft standard. When the interpreter runs out of commands or a return to fork command is issued when there are no forks on the stack the script is complete. The code could be represented in hexidecimal but in an attempt to compress the string for convenience we will base64 encode the string, padding it with zeros to make it fit the encoding scheme. By encoding it with base64 we can ensure it's portability as an easily copyable/pastable string. Below is an example script and it's base64 encoding.
| Hex | Description | Base64 |
|---|---|---|
| 4 | Go 4 | TqKR |
| E | Fork | |
| A | Turn North | |
| 2 | Go 2 | |
| 9 | Turn Up | |
| 1 | Go 1 | |
| F | Return to Fork | 8tKR |
| 2 | Go 2 | |
| D | Turn East | |
| 2 | Go 2 | |
| 9 | Turn Up | |
| 1 | Go 1 |
The Hexidecimal number 4EA291F2D291 can be base64 encoded to "TqKR8tKR". Each 6 hex digits become 4 base64 characters.
I've taken to calling these base64 encoded models "JoCodes". Because of the way the trees grow the encoded string normally starts with "Jo". These JoCodes are the strings we store in the database to be selected and drawn during worldgen. We only need to make a sizable number of these codes that represent variations in tree structures with differing bounding radii. We need many so the repeating structures are less noticable. We'll also rotate the trees in different directions to increase the look of natural variation.
All we should need to do to produce the models is create approximated cylindrical growing chambers with opaque block walls in the game and let the trees grow. Once the tree has depleted the fertility of the root node the model code can be derived from the tree shape and stored in a look up table along with the radius of the grow chamber for later use by world generation. This process can be automated through a block I've created in the mod for creative mode only called the "dendrocoil". This block is usable with computercraft to script advanced features like rapidly growing trees, pulling JoCodes, planting saplings, etc. This has a huge advantage over hand creating the models and their codes.
| Denrocoil |
|---|
 |
 |
The creative only dendrocoil block for automated tree manipulation.
I created a set of 7 growing chambers in creative mode, one for each radius size. Each chamber features a dendrocoil at it's center and a touch screen activated program for automating growth. The computercraft program pulses a grow signal to the entire chamber to force it to grow many times faster than normal. When the program detects that the soil fertility is zero it then reads the tree's JoCode and sends it to my webserver where it is stored in a database. Once the code is safely stored away the tree is killed and a new one planted with full fertility and the process repeats. My goal was to have 16 variations for each radius of each tree species for worldgen.
| Growing Chambers |
|---|
|
My solution for automating tree growth.
Note that in the pictures above the sides of the chambers are solid blocks so that the only light available to the tree is from directly above.
I've used wool blocks to mark the circle locations for demonstration purposes. The algorithm keeps up faily well while walking through the world. Notice that circles are generated everywhere, even over the ocean.
 |
 |
 |
 |