Trees and sand

Now that this blog is up and running, I was able to return full time to working on Terra Diem. This week is was all about trees and sand simulation.

Trees

What is a tree?

There are two primary aspects I was considering when choosing how to make trees:

1. How are trees represented from a simulation and gameplay perspective
2. How are trees visually represented in the world.

Unlike general materials that make up the world (rock, dirt, water, etc), a tree is a recognizable wholistic thing on its own. Trees are also quite big (certainly bigger than a cubic meter block!), and have significant variety between instances.

One approach would be to leave trees as a problem solely for the generator. It could create a tree that looks tree-ish up front and then in the game it is just blocks of terrain like everything else. However, I wanted to retain this “tree-ness” quality even after initial generation. There are benefits to this that I think will make the game feel more alive:

• Trees could grow over time, instead of always being fully grown and static.
• If a tree trunk or branch is cut or broken, the game can respond appropriately (for instance, chopping down a whole tree or part of one).

A different approach I considered was making trees its own separate thing, different from terrain. The generator would simply place a tree (with appropriate tree parameters), and then trees could be managed and rendered as a whole. This is basically what is planned for objects (a subject of a future post). However, this has several drawbacks over the “turn trees into terrain” approach:

• Trees can be quite large, and may be densely packed (as in a forest). Dealing with tree/tree intersection, player and object collision, lighting, etc. all requires a separate system and custom support.
• Trees are quite complex (or I wanted them to be). They can have many branches, and of course lots of leaves. All of this needs to be stored separately as it would not be in the underlying terrain.
• Trees can cross chunk boundaries (see Terrain article for what a chunk is). This greatly complicates terrain generation, as chunks may be built independently and trees shouldn’t do silly things like grow into solid rock.

This did not seem like a good trade off. So what I’ve ended up with is as follows:

• Trees are composed entirely of independent terrain blocks (like the first approach).
• However, tree blocks store a relationship to neighboring blocks. From any tree block, the entire tree can be discovered by following these connections.
• Trees are defined soley by their branch structure. Trees cannot intersect and each block is part of a unique and separate tree.
• Leaves are deterministically implied by the branch structure. However leaves are not necessarily unique to a single tree. Leaves between trees are merged.

Tree structure

Trees are composed of “tree” terrain blocks, which represent the solid (aka trunk or branch) part of the tree. Each tree block has a root and one to three ends. The root and each end are defined by a position and size:

• Position: There are 27 possible positions in a block: cube corners, cube edge midpoints, cube face midpoints, and the cube center.
• Size: This varies from 1 to 8 and represents the diameter of the root/end, with 8 being almost the full width of the block, and 1 being 1/8th of a block. For the initial tree generator, this also implies the total length of a branch, although that is not required generally.

The cube center position is reserved for the terminal end, which indicates there is not a further branch. For the initial tree generator, this also results in a “leaf ball” (more on this later). It is possible to have both a terminal end and a non-terminal end in the same block. Really, the terminal end is only meaninful for rendering an “end” to a branch and for leaf generation.

The position of a root or end also determines what block the next part of the tree will be in. For instance, a root or end in the middle of a face indicates the connecting block is through that face to the next block. Edge and corner ends similarly indicate diagonal connections through the edge or corner). This works out quite well in practice, as you can always traverse the tree in any direction (from end-to-root or root-to-end).

Tree structure rendering

Terra Diem terrain has a definite visual style which is really about supporting 45 degree angles. This gives nice features like the octagonal tower. I wanted to leverage this, staying with a low-polygon look but being more than just cubes. The obvious choice here for a branch was an octagonal prism, and that is precisely what I did. Terminal ends come to a point in the center of a block, and the starting and ending positions define an octagon which I just connect as a (potentially warped) prism.

Warping happens when the orientation of one end does not match the other, so it kind of gets squished. The more radical the angle difference, the more radical the warping. I spent some time thinking about how to eliminate this, but it is surprisingly non-trival as it does not compose easily within and between blocks (resulting in cracks or protrusions). In the end, the warping is not that bad if the angle is limited, and it actually looks quite good for branches growing out of the trunk.

When deleting a tree block, it exposes the now-orphaned branch ends with tree rings. Keeping the texture size consistent, this naturally ends up with less tree rings for smaller branches, which is a nice side effect. This next picture shows what happens if I delete a tree block that has a root and two ends (the space highlighted with a white box). When the block was there it would have two prisms that connected the ends at the cube corners to the root on the bottom.

What happens in the game if you chop out the middle of a tree? Good question… I’m still mulling this one over. Personally, I’m not a fan of floating terrain. My preference is to have the orphaned bits of tree fall, but as always there are complications. For now, it will float as you see here – but that will almost certainly change in the future. The advantage of the chosen representation is that there are options later.

Leaves

There are many possible ways to adorn trees with leaves. Ultimately, both the branch and leaf generation will be different based on the type of tree. However, the basics will be the same for all trees – a core tree structure with leaves added to fill out the shape.

The first type of tree I wanted was a typical full and leafy tree. My first thought was to leverage the game’s ability to render sloped mesh to add a small ball of leaves at every terminating end. If leaf balls intersect, they would merge together.

I was pretty excited about this, but I wanted to do better. For one, the leaf balls just were not big enough… at least not all the time. It seemed ok for the smaller 3-ball tree above, but the thick trunk looked inadequate with a small leaf ball. Also, the huge tree with all the branches looked kind of cool it its own way, but was just was too exposed. I decided to make two changes:

1. In the first approach, a terrain block could only have a branch or leaves, not both. You can see some of the weird artifacts in the picture above, if you look closely. However, Terra Diem terrain blocks support multiple instances, so I could support the branches and leaves in the same block.
2. I clearly needed bigger leaf balls – but not always. I decided to make four sizes of leaf balls, and then generate that based on the size of the branch (for the current tree generation, the diameter and length of a given branch are correlated).

Forests

The final piece was getting the light to filter through the trees correctly and to allow trees to “grow” through the leaves of other trees. This allows for dense forests which can have a continuous canopy which the player (or monsters and npcs) can wander through.

Sand and snow

The other big thing I’ve been working on this week is flow simulation for loose materials like sand and snow, and liquids like lava and water. Loose and Liquid material already have a well defined terrain specification (see Terrain article for details). But what wasn’t defined or implemented is how it behaves.

Simulation algorithm

This was the first time simulation was getting added into the game, and I decided to keep it as a separate system that modifies the static world just like the player would do with a pickaxe or shovel. Whenever a block containing loose or liquid material is modified, it is added into a queue to be simulated in the next frame. If that simulation modifies other blocks, then those will be queued for simulation in the subsequent frame after that.

Simulation of a block is pretty simple at its core. Each block may contain up to 64 bits of material, including loose and liquid material. Loose and liquid material can do two things:

1. Move to the block below, if there is room: Material always moves down, if it can – because of gravity.
2. Spread out to the surrounding blocks: Any remaining material may disperse to surrounding blocks slowly (1 bit to each neighbor per simulation tick). This happens if the material is piled higher in the current block thatn the surrounding block based on the material’s piling value.

The piling value for a material is different for loose material (like sand and snow) than it is for liquid. Loose material only spreads out if the height differential is greater than 1/8th of a block. By contrast, liquid material tolerates only a 1/64th of a block differential. Note that this does mean that liquids pile up, but very very slowly.

Trying it out

Because material spreads out slowly horizontally, this generates a really nice animation based on the simulation tick. I started out with a simulation tick of four times a second, and a spread to all neighboring blocks (both directly adjacent and diagonally adjacent).

When I tried it out… it just worked! I hadn’t addressed the graphical issues yet, as partial material being rendered over partial material looks really weird. However, I was so excited I started a YouTube channel and made my first video to show how it works (like and subscribe!)

So I’m done?

I actually hid some significant problems in that first video, which I spent time fixing this week:

• Material actually flowed through blocks that were not entirely solid as if they were air. For instance, sand would actually flow through the diagonal walls of the tower, as they are slope blocks that are half-rock, half-air.
• Multiple loose materials combined (for instance snow on top of sand) didn’t work right yet. There is an ordering to materials, and the top material should flow out first.
• Liquids didn’t work at all yet. This complicates things a lot more as liquids have a different piling value, but may coexist in the same block with loose materials.

The second set of issues were apparent in the video:

• Material flowing down is disconnected and broken up. The simple solution is to just make the lower material artifically render as a full block – which actually looks ok (I wish I had waited to get this in before shooting the video).
• Material flows out in entirely too much of a square shape. This is because it flowed to diagonal neighbors at the same rate as adjacent neighbors. Again the simple solution here is to only flow out in the cardinal directions (north, south, east, and west). And again, this worked quite well. It slows the flow by 2, but I simply increased the simulation rate to 10 times a second.

And after all that, I’m still not done. There are lot of graphical polish issues related to solid transparent materials holding loose materials, translucent liquids (aka water). Also, I need to resolve what (if anything) I want to do about running water (like rivers) and infinite water (like oceans).

Anyway, that’s it for now. Stay tuned next week for what will surely be more liquid and loose material simulation.