Paul's picture

I have been writting articles explaining some of the details of how to implement a block engine. But it occurred to me that maybe I need to take it one step back and talk about the big picture. I am so close to this tree that might have taken for granted the fact that there was a forrest around me.

So in this article, I am just going to talk about the big picture of the lifecycle of chunks. How do we get from a seed (random string typically provided by user) to triangles in your screen from a 10000 mile high POV.

The earth took billions of years to form. If you are a christian, then you would say it took 7 days to create the earth. If you are making a block engine, you need to be a hell of a lot better than that, try a few seconds. And you want to make it interesting with mountains, trees, caves, seas, etc... 

So how can you optimize Genesys down to a few seconds?

The first thing to notice, is that you do not have to create the whole world at once. The player can only see so far, so all you really need to create are chunks that are close to the player. A world object then needs to watch the player, and load and unload chunks as they become visible. This is similar to something multiplayer games do called Region-based Interest Management system (If there is interest, I will write an article on that).

As the world loads chunks, the chunks go through the following life cycle:

Prioritize -> Generate -> Physics -> Light -> Render -> Dispose

Prioritize

First, determine which chunks need to be generated. It is also important to determine in which order. You want the chunks that are closest to the player to be done first, and then the chunks that are far from the player. 

So you loop through the coordinates of the chunks within an area of the player, and place them in a PriorityQueue ordered by the distance to the player. The closest chunks towards the top of the the list. You could come up with better algorithms to sort the chunks, but the fact is that it does not matter since we are talking about just a few dozen chunks.

Then for each chunk that needs to be generated, you go throgh the rest of the process.

Generate

Before generation, there is nothing, just thin air. Generation consists of creating the chunk as the 3d array of blocks, and start filling it up with actual blocks based on a seed.

The heart of this process is the simplex noise function (perlin noise also works). Without going into all the nitty gritty details, the simplex noise function receives a coordinate in 3d (any dimension really) and returns a float number from -1 to 1. The important part is that this number is always the same for the same coordinate, it is smooth, and appears random. 

Then you combine this noise function with different frequencies and different amplitudes to determine wether a particular block is air or solid and what kind it is.

Physics

Once you initialize the chunk, you might need to run some physics, like water flow. Note I have not done that yet in my engine. You essentially loop through all the blocks that you generated, and determine if there is some action that needs to be taken for it. For example, if you see a water block, check its neighbors, if neighbors are air, then change neighbor to have some water.

Light

Essentially you perform a flood fill, where a block with light, throws some light to its neighbor blocks, and then you repeat the process for the neighbor blocks until you run out of light.

Render

Once light is calculated, you are ready to start producing triangles. This step consists of looping through the blocks, and produce triangles for each visible one. See my previous article for very basic information on how to do this.

Dispose

Once the player walks away, the chunk needs to be discarded, otherwise you would run out of memory quickly. You might need to save the chunk to persistent storage at this point.

 

From this process, the slowest step by far is Generate. It heavily depends on how complex you want your terrain to be, how many times you call the noise function.

Note that if the player changes the world, then you essentially need to rerun physics, light and render. The good part is that you can skip generation completelly which is the expensive part. So this can be done very quickly.

I can elaborate on any one of these steps but I will require from you the reader to request which one you would like to know more about.

Update

Charles Barros has taken it upon himself to proof that I am not just talking nonsense.  He has generously implemented a block engine based on some of the things I wrote about and made it open source.

If you don't want to start from scratch,  you could get that, and work your way up.