Level Radius

Home --> Programming Projects --> Fractal Block Engine --> Coordinate Systems

When Most Chunks are Added and Removed from the Active Chunk Tree

In this page we will describe when chunks get added to and removed from the active chunk tree.

By the distance between two chunks (on the same level) we always mean the L_infinity distance. So, the distance from chunk at VCP (0,0,0) to the chunk at VCP (1,2,3) is 3.

Each level has a radius R (when the viewer changes level, these level radii may change).

Chunks that are distance ≤ R to the center chunk should be added to the main chunk tree.

Chunks that are ≥ R+2 to the center chunk should be removed.

What happens to chunks that are exactly R+1 to the center chunk is more involved. We will sometimes talk about the "block type" of a chunk. That is the type of the block that occupies the same exact space as the chunk.

The Problem with Removing all Chunks that are ≥ R+1 Away: Thrashing

Consider the level of the viewer, where the level radius is R. Suppose we had a system where chunks on this level are added if they are ≤ R chunks from the center and are removed if they are ≥ R+1 from the center chunk.

Then if the viewer is right on the edge of his viewer chunk and quickly moves back and forth across the boundary, then this will cause "thrashing".

The same chunks will be quickly created and then destroyed again and again.

To avoid this problem, chunks should usually be created only when they are ≤ R from the center chunk, and they should be usually destroyed only when ≥ R+2 from the center chunk. Like a thermostat that turns on at 60 degrees and turns off at 62 degrees.

In the system described in this page, it IS STILL possible for some kind of thrashing to occur, but it is quite unlikely that the user would ever find themselves in that situation.

The Problem With a Level Radius of Zero

For a level of radius 0, we CANNOT remove all chunks that are ≥ 1 away from the center. If we did, the player would not be able to leave that center chunk! Let us dig deeper.

We are assuming that each level radius is ≤ 14. If this is not the case, the description in this page should be changed slightly. We are going to treat levels with radius 0 differently from levels with radius ≥ 1. The idea is the majority of the levels in the chunk tree will have radius 0 and we want a maximum of 8 chunks on those levels (to save memory).

Most of the levels with radius 0 will have only 1 or 2 chunks on them.

Important: when a chunk is created, the procedural chunk generation code for that chunk is allowed access to the block types of the chunks in the 5x5x5 surrounding region of the chunk. So if a level has radius R, then to create chunks on that level, we need access to the block types of chunks that are ≤ R+2 away from the center chunk.

So if we want to create a chunk C on level L+1, then all blocks within the 5x5x5 surrounding region of C must be inside chunks that exist within level L. This leads us to the next section.

The "Envelope" of a Level

Let's say that given a chunk C with VCP (x,y,z) and given a nonnegative integer R, the "ball of radius R centered at C" is the region of chunks with VCPS from (x-R,y-R,z-R) at the left back down to (x+R,y+R,z+R) at the right front up.

Consider a level with level radius R. The envelope radius of the level is either 3 if R is 0, or it is R+2 if R is > 0. That is, the envelope radius is the max of 3 and R+2.

The envelope of the level is the ball centered at the center chunk whose radius is the envelope radius.

The idea is that for any chunk to be created on a level (assuming the viewer does not move), the only chunks in the level whose block type will need to be queried will be inside the envelope.

So consider level L > 0. On the next coarsest level (level L-1), only chunks which intersect the envelope of level L will need to be created for the required block information to create chunks on level L. Because we are assuming the level radius of level L is ≤ 14, then on level L-1 only chunks that are ≤ 1 away from the center chunk need to be created to provide this needed block information. Now the level radius of level L-1 might be 0, and that gives us the only situation where we would create a chunk that is strictly more than the level radius away from the center chunk. Also note in this same situation that the envelope radius of level L-1 is 3.

Summary: When we Add a Chunk

Let us be specific: there are only 2 ways for chunks to be added to level L of the active chunk tree: one normal and one strange.

Summary: When we Remove a Chunk

Let us be specific: there are only 2 ways for chunks to be removed from level L of the main chunk tree:

Setting Level Radii in Fractal Block World

You can set the radius of each level before the program starts by modifying Input/Scripts/program_startup.txt and changing the environment variables that start with "engine.exploration.level_radii." The radius of the viewer level is "engine.exploration.level_radii.0". The radius of viewer level - 1 is "engine.exploration.level_radii.", etc."

Making these radii too small trivializes speed runs in which there are monsters. So we propose that a valid speed run needs to have radii of values at least 3,3,2,1,0,0,0,0... These are the default radii values for the 2020 version of the game.

Programming

Given a level, sometimes we recompute the list of "good vcps" (vcp = viewer centric position) and "bad vcps". Good vcps are places on the level where we should create chunks (if they are not there already), and bad vcps are places on the level where chunks should be collapsed into blocks (if they have not been already).

Note that some vcps may be neither good nor bad. Given a level, when should we recompute the lists of that level's good and bad vcps?

Consider level L. The following are the only times when we need to recompute the lists of good and bad vcps of level L:

Clearing the Depth Buffer Issue

Note that in this engine, we render each level starting from the coarsest and going to the finest. After rendering a level, we clear the depth buffer. So, if we render something from level L+1 behind something from level L, this will look wrong. So, when expanding blocks into chunks, we should do this in a certain order. We first want to expand the block whose VCP has the smallest norm (in the taxi cab metric). A similar comment applies to when we want to collapse chunks into blocks, but this is not as much of an issue.

This issue is discussed more here.