Work in progress Minecraft-like. This project intends to serve as a base to experiment with procedural generation a bit more than what is usually done in Minecraft-likes. This page will only present what is already implemented and will not focus of the future of this project (for which I have so many ideas).

GitHub repository

Features

• Infinite world in all directions including up and down, thanks to cubic chunks.
• Chunk meshing with covered face culling and ambiant occlusion trick.
• Palette compression for chunk blocks (with palette indices being stored on as few bits as possible).
• Multiple procedural terrain generators. Some use a custom structure generation engine that is fast and can handle large structures while keeping the world independent from chunk loading order (see the generator structures-links-smooth).
• Home made N-dimensional noise computation (more optimized than the noizebra implementation).
• Optimized chunk loading order that culls away covered and inaccessible chunks and prioritizes terrain over air.
• Blocks can be placed and removed.
• Blocks can also be thrown.
• Saving/loading to/from disk, named saves.
• AABB vs voxels simple but working collision resolution for the player and entities.
• Entities that are rendered fast (instanced rendering, with per-instance texturing/coloring by indexing in a texture mapping and coloring table), saved/loaded/generated without loss or duplication. Blocks being thrown are entities. There are also tiny rolling balls with eyes (that are generated by the world generation, even the structure generation can place entities).
• Procedurally generated skybox texture.
• Threadpool for terrain generation, meshing and skybox texture generation.
• Dynamic shadows by cascading shadow mapping.
• Fog effect (blocks in the distance fading in the skybox).
• Procedurally generated block textures (see the generator structures-generated-blocks).
• Configurable controls for most controls.
• Custom widget tree for the interface.
• Grounds for a statically typed stripting language.
• Configurable chunk size at launch time. (Actually useful as this parameter influences the performance of the generation, gameloop and memory usage in complex ways and the best value that optimizes for what a given user prefers on a given machine may be different from one another, and it doesn’t cost anything to make this a parameter.)

Gallery

A video:

Also a video:

WIP entities that are not blocks:

On interesting and fast terrain generation

Using noise

There are multiple world generators available, most of which generate terrain by manipulating 2D and 3D noise.

Nice properties

We want terrain that generates in a way that does not depend:

• on the order in which the chunks generate,
• nor on the size of the chunks,
• nor on the offset of the chunk grid (the placing of the chunk edges).

These constraints allow to consider that the world would always generate in the same way not matter the other settings or implementation details, instead of a generation that is influenced by the player’s actions. Most people would not care about these properties but I want to see the worlds of Qwy3 as exisiting independently from the player’s actions.

Using transformed noise to generate each block of the world guarentees that the terrain generation has these properties because the generator can be expressed as a function that maps block coordinates to a block type. The generation of each block is independant from the generation of all the other blocks, no matter the size, position and loading order of the chunks.

Only one step

Also why not wanting chunks to generate in only one step? Some world generators of other voxel games (and also Qwy2’s generation) would have each chunk generate in multiple steps, each step requiring the completion of the previous step for all the neighboring chunks. A problem with such technique is that we end up with a large number of partially generated chunks on the edge of the generated area which we cannot mesh and render to the player because their last generation step cannot be done because it would require to extend the generated area a chunk further and if we do that then we just moved this problem a chunk further. All these generation steps use precious time that is not spent on directly generating the chunks that end up visible to the player, and also use more memory.

Qwy3 generates each chunk in one step, meaning from nothing to block data to meshing without the need for neighboring chunks to even exist (although the meshing is done again when neighboring chunks are generated to make sure that the ambiant occlusion and face culling on the edges of the chunk take into account neighboring blocks from the neighboring chunks). This happens to not be a problem for structure generation, which is explained further below.

What can we do with noise

Using N-dimensional noise and transforming it in original ways can make for interesting terrain that break the monotony of 2D height map style terrain. For starters, 3D noise allows for overhangs to appear which doesn’t happen with 2D height maps. It also allows for floating islands (which can be desirable or not depending on the feel we aim for the game). But it can allow for so much more!

Here is an example of multiple 3D noises being used to generate curved lines in 3D, could be used as a base for the generation of some future aerial biomes (when biomes will be implemented):

This is a matter of discovering interesting ways to transform and combine noises and keeping the ones that happen to fit the desired feel of the game. Some terrains like the lines above were not foud by chance but by an intuition about how to get line-like shapes to generate in 3D; however there is no reason to not try random noise manipulations as these sometimes turn out interesting enough.

Structures

Transformed 3D noise is not enough! Blocks are related to eachother only by proximity in the noise sampling. How to generate trees this way? It may be possible by carefully tweaking impossibly complex noise transformations for weeks or even months, but I would not resort to such cumbersome way.

We want to be able to describe structure generation as a sequential algorithm, using operations such as “place a block there”, “fill a sphere of such radius there”, etc.

The chunk edge problem

But what to do when a tree decides to generate near the edge of a chunk and is cut by the edge?

A few solutions that were not applied:

• Having multiple generation steps and structures smaller than a chunk is a simple solution, that was not applied to Qwy3 because:
  • a constraint on structure sizes that depend on the chunk size means that the world generation is indirectly influenced by the size of chunks, and as said above I refuse to let that parameter limit the generation,
  • as also said above, having a single generation step for chunks is a great advantage that is not to be given up so easily.
• Having the tree be generated anyway by the chunk in which it decided to appear, allowing the tree generation to place blocks outside of the chunk, editing chunks already generated and saving the blocks that are placed on non-generated chunks to be applied on them when they generate is also a solution. It was not applied to Qwy3 because:
  • it is harder to do it in a thread-safe way, as the generation of each chunk is done in a separate thread,
  • it allows large structures but generating a large structure (that spans over many chunks) will require the edition of many chunks both for already-generated chunks and for to-be-generated chunks, all that for each chunk that generates a large structure,
  • and if it allows large structures then a sufficiently large structure that is generated by a chunk far away from the player may generate blocks near or on the player; we want the generation to generate a chunk and be done with it, not comming back to already generated chunks to edit them potentially plenty of times.
• Having structures smaller than a chunk and that are generated in a way that makes it so that they do not cross the chunk edges. This solution was not applied to Qwy3 because:
  • again, structure sizes shall not be limited by chunk sizes for reasons stated above,
  • and the world generation shall not be influenced by the chunk grid offet (placing of the chunk edges).

The chunk edge solution

Considering two adjacent chunks that must both generate different parts of the same tree, how can they agree on what to generate so that it matches perfectly at the shared edge that cuts the tree? How can they even know that they must agree on a shared tree?

The way noise-induced terrain works fine across chunk edges is because both chunks sample the same noise functions that happen to be spatially coherent. This coherency can be reproduced for structures. Noise sampling is not limited to floating point parameters and can be done with integer parameters. This allows to map noise values to cells of a cubic lattice (that has a scale that does not depend on the size of chunks). Chunks can now check which cells of the lattice they overlap with and use the noise values from these cells (that are shared with the other chuncks as per the fact that a noise function is deterministic (pure)) to generate parts of structures that occupy these cells. Each chunk generates all the structures that might overlap with it and only keeps the parts that actually overlap with it; structures that might span over multiple chunks are “generated” multiple times, but always at the exact same position and in the exact same way (always seeded by the same noise values) so that all the parts overlaping different chunks match up perfectly.

Here is an example of this technique being used to generate balls. As opposed to terrain generated by transforming some noise, here the noise is simply used to allow chunks to share values in cells of a lattice so that the chunks can agree on what structures can be generated (here, just balls at different positions in the cells of the lattice) so that said structures can cross chunk edges without issue.

Then noise transofmration can be used again to shape such structures to more natural-looking terrain.

Expanding on the idea

The fact that the position and properties of all the stcuture is decided by noise values and queryable by their position means that a structure can be made aware of its neighboring structures and decide to generate accordingly. For example, the structures can link themselves by generating a bridge, both of the two linked structures generating its half of the bridge.

Here is an example of the balls from earlier, all linked together in one direction:

Two structures can also decide to agree on some properties together, for example two structures can agree to link themselves or not (which is important if we want to generate structures that are not always linked together, if a pair does not agree on being linked or not then one might generate half a bridge and the other not and the bridge may stop awkwardly, which might look bad if such behavior was not intended). For two structures to agree on some properties, they can use noise again, as the (home made) noise used in Qwy3 is N-dimensional it can be sampled in a 6D space at both the coordinates of the structures origins for example, in both order, and combine both noise values in an order-independant way (the mean of two values for example) to get a noise value associated to the pair of structures that they will both agree on (both structures will associate the same noise value to the other of their pair, for each pair).

Here is the example of the balls again, but now they can be linked with all of their 6 direct lattice cell neighbors, they decide to link only sometimes, the bridges have a flat top and the generated shapes are also piped in some noise transofmration to make the bridges look more natural (as far as a lattice of bridges in an alien sky go anyway, the whole concept way not be very natural but if it was natural then it may look like this more than if it was not transformed using noise):

One more strange-looking take on the idea:

Note: To compare these structure-using generators to the noise-using line generator mentioned above that generates lines of land in the sky, it appears that:

• the structure-using one is harder to implement,
• but once implemented the structure-using generator is way easier to control and tweak to get it to generate what we want than the noise-using generator,
• and the structure-using generator expands what is actually possible, for example large lines with a circular cut is not really possible with the noise-using technique.

More structures!

Until now was discussed a technique that allows for one structure per lattice cell that is not allowed to cross lattice cell edges. We want more structures and structures that can cross lattice cell edges.

What is important is that a chunk that generates knows what structures might overlap with itself (the chunk) to generate them (and only them) so that any parts of these structures that overlap with itself (the chunk) are generated now (as we only allow ourselves this one and only occasion to generate all of the chunk’s content) or even to check weather a given structure will not overlap with itself (the chunk) to discard only what does not overlap.

Allowing multiple structures per lattice cells is as easy as deciding to do so. To allow for a variable number of structures per lattice cell, we can decide on the number of structures in one given lattice cell by getting a noise value N from the cell, and then for-looping to get new noise values to seed N structures and placing them in the cell.

Allowing lattice-cells-edges-crossing structures can be done as follows: We decide ahead-of-time on a size constraint for all the structures of the world. That gives a bounding box around a structure origin coordinates that is the only area in which that structure’s generation is allowed to place blocks. Now, for a given chunk that generates, the chunk can list all the lattice cells that might generate structures that might overlap with itself (the chunk) by extending itself (the chunk) with margins as wide as the already known structure bounding box radius and that gives the area in which structure origins might generatate blocks that overlap with itself (the chunk we are generating). Now, the chunk asks all these lattice cells for their structure origins, and can discard the ones that fall just ouside of the area in which structure origins might generate to overlap with itself (the chunk). All the remaining structure origins are to be generated, discarding every bit of generation that falls outside of the chunk we are generating.

Structure generation can now be defined by a program that uses generation primitives like “placing a block there”, “placing a radius there”, etc. with these primitives handling the fact that if these shapes or blocks are placed outside of the chunk we are generating then they are discarded. The structure generation program can also querry the terrain with generation primitives such as “what is the terrain block there” (which simply makes the calculations done by the generation of the terrain for the whole chunk, but only for one block this time) to generate structures in a way that takes the terrain into account, this can be useful for example by structures that want to generate on the ground, as they first have to find the ground (because structure origins are generated uniformly in all the 3D space, and are not bound to generate from their origin coordinates but can actually use any part of their bounding box).

Here are trees generated this way:

This may seem like a lot of work for each chunk, and each structure is generated plenty of times (as many times as there are chunks that it could have placed blocks in if it wanted). In practice, this happens to not be the bottleneck at all, if structure origins are not too densly generated and if structures keep their generation at least reasonably fast (in practice, it was a problem once and was fixed immediately without compromising on the look of the generated structures). After all, if chunks are 24x24x24 blocks then each chunk must generate the terrain on each of its blocks, that is 13824 blocks, each terrain block being generated by transforming some noise that takes time to be computed (and was optimized a bit but could be optimized way more with more effort in the future); the structures happen to not slow down the generation of each chunk so much that it was noticeable.

This way of placing and generating structures offers some parameters to tweak to achieve different results, like the lattice cell size, the range of number of structure origins per lattice cell, or the structure generation bounding box size.

Large bounding boxes allows for large structures (much larger that a chunk):

Seeding the structure origins with different structure types allows for, well, different structure types (dispatching the generation to the generation program that corresponds to the structure typed that was decided for each structure). Here are trees and boulders, both using a different gereration program:

The bounding box is only about modifying the world, not about querrying information, there is no reason to limit the range in which the generation of a structure can access information. Structures can still access the position of other structures, even other structures whose origins are outside of the bounding box of the structure we are generating. Two structures whose bounding box touch eachother can decide to generate a bridge between them for example, in the same way as described further above:

That does it for structures.

Chunk culling and loading order

Loading a chunks means either generating its blocks or read them from the disk (the saving to/reading from the disk it not yet implemented), making the blocks of a chunk availavle in RAM. This allows to interact with the blocks but also to mesh them to render them to the screen.

A setting of the game is the radius of a spherical area around the player in which the world is to be loaded and displayed. When the game is launched, the whole area is to be loaded as fast as possible, and when the player moves then unloaded chunks enter the sphere and creates an area (that can be large if the player moves fast) to generate. We often have to generate a large amount of chunks, and make it faster somehow. Any compromise on the generator’s quality of work is out of the question, making the generator faster is somewhat discussed above and making reading from disk faster may be discussed after it is implemented in the future. What can we tweak ?

Loading and ignoring the right chunks to load, and loading the chunks in the right order, instead of naively loading chunks closer to the player until the whole spherical desired area is loaded. Loading chunks in the right order makes for a faster meshing and rendering of the chunks that actually have a mesh to render and that the player will actually see, and ignoring chunks that the player has no chance to see or even to interact with allows to spend the constant amount of compute we have on the intresting chunks.

Note: Avoiding loading useless chunks also allows to have fewer chunks loaded for the same player experience, which cuts on memory usage and chunk management time in the gameloop.

Loading front (culling)

The chunks containing and around the player are to be loaded, that we know for sure. How about working from there?

Let us consider a set of chunks that we call the front. The front are the chunks that we actually consider for loading. The chunks containing and around the player are put in the front for starters. The chunks in the front that were not loaded yet are flagged for loading. Once loaded, a chunk propagates the front to adjacent chunks that were not loaded yet, and removes itself from the front. That way, the front represents a surface of chunks that expands the loaded area (behind it) as it moves forward, eating the unloaded area.

Working with a propagating front allows for the following optimization: making a chunk C not propagate the front to an adjacent chunk A if its face (the blocks on the face of C that touches A) is made of only opaque blocks. This makes the front fail to propagate through walls that happen to contain whole chunks faces, but also to fail to propagate underground or even inside large masses of solid blocks that lack holes. Given a world that has a surface with only rock underground and air above, then the front will not penertate the underground area and only half of the spherical area will be loaded (thus in half the time!), and this generalizes to any ladmass configuration, no matter its shapes in 3D (given that the masses are large and lack holes).

In a flat world, the loaded area only makes half the full spherical area:

Loading priorities (order)

Left at that, the above optimization would still make the loading spend most of its time loading huge volumes of air. Air is fine, and must be loaded just in case it actually contains something worthy of notice (like blocks to be meshed that we failed to predict), and even if it turned out to be just air as predicted then having confirmed that it is air is also valuable information that is needed by gameplay (what if the player or an other entity (yet to be added) flies or falls through that air? Having confirmed that it is indeed air allows for the flying or falling to happend quickly without having to hastily load these chunks). But if we suspect a non-loaded chunk to be air, the loading’s efforts may be better spent on an other chunk that we suspect to be part air and part blocks to be meshed. Loading the likely-to-be air after the likely-to-be intresting chunks is a good idea.

That can be done by having two levels of priority in the front. The loaded chunks that propagate the front on adjacent chunks now also check for only-air-blocks faces, and put the corresponding adjacent chunks in the low priority font instead of putting them in the hight priority front for the others. A chunk containing the surface between the air and the undergorund (thus containing the ground) shall thus put the chunk above it in low priority if its top face is nothing but air, and this generalizes to any shape that takes the surface between solid blocks and air.

Still in a flat world, the loaded area prioritizes the ground first:

Low priority front chunks generate with a much lower probability than hight priority chunks (so as to have a chance to stumble early of land that was predicted as air). Once there is no high priority front to load anymore, all the low priority front chunks are moved to the hight priority, so that one layer of air is now to load, and then the next, etc. as can be seen here: