Height Limit

[Nym Traveel]

Proceed with caution, weird thoughts of a mathematician below...


Ok, so you ignored my warning, never mind.


I thought about the height limit in Terasology.
Basically: what is a chunk primarily?
As of now it's a TeraArray filled with blockIds and a TeraArray is a class with an Array which is indexed to serve as a fake 3d array.

This is, however, not capable of handeling giant or infinite height levels.
Big heights would lead into a massive array which basically is nearly "empty" - meaning filled with air (some big mountains but most of it is air).
So, I have 2 ideas to present:

First (not really concerning height problems)​

What about breaking up the inner structure of chunks? Instead of making a 3d array, we make a 2d array filled with pillars! Each pillar holds the values of the blocks in it and some special values like temperature, humidity and so on. This way, we'd have some more values per x-z coordinate but would save looking up the initial noise when we need the values.​

​

Second (now it's getting seriously freaky)​

I thought about the very high heights.​

Basically, I would suggest a hardlimit for Terrain generated by the game itself. We could also make some exponential falling of the expected height but I think this would lead to some serious artefacts.​

For the infinite height we have to use lists in some way.​

Using a list for the complete pillar would expectably be very slow...​

So, we have to somehow combine arrays and lists. Here is very much potential for discussions, I thought of the following possibilities:​

- have an array until some heigth, maybe oceanlevel + 30 or sth similar and proceed with the list​

- have an array until the highest point of this pillar and save everything beyond in a list​

- make basically the same as one above but on unloading the chunk rewrite the array if necessary to the new maxheight (also possibly smaller array)​

​

Ok, I'm ready and geared up, waiting for the criticism
so long,
Nym

 

[Perdemot]

if we would make pillars wouldn't the temperature change depending how high a block is placed in the it?
Because of this i would give just the lower part of the pillar the temperature and humidity settings, so the game can calculate how it would be in higher regions.

 

[Nym Traveel]

As of now, temperature is 2d, but we could make a gradient, yes. So one base temperature is saved and the rest is calculated.

My main concern right now is, if this whole setting is feasible, performancewise

 

[Immortius]

The 3D arrays are a big performance thing - basically java can pack all the bytes together when they're in an array. As you split it into separate structures for pillars or whatnot, overhead is introduced. Lists of primitives are particularly bad, as the primitives each get boxed into an object which adds even more overhead.

The theory (although we haven't acted on it at this point) is we should go from a 2D grid of 16x256x16 chunks, to a 3D grid of 16xNx16 chunks (where N may be as little as 16). We could accent this with chunks tracking the number of non-air blocks they contain and freeing up most of their memory when it reaches a lower threshold - which would be typical of sky chunks.

The big issue is how to handle sunlight propagation with infinite height, as the current algorithm needs to know the entire vertical column to work. Some sort of sunlight cut off point, after which it fades to darkness like normal light would probably be required at the least, although it wouldn't help with something like a space platform a few kilometres up.

 

[x3ro]

While (and because) my knowledge on Java performance implications is limited, wouldn't it be feasible to code up an actual "benchmark" comparing different chunk storage forms. For this to work we'd need to gather information on how the data is actually used (i.e. how it is accessed [sequentially, randomly]) what properties we need it to have (e.g. as Immortius states, we currently need to know an entire vertical column) etc.
Using that information and a little benchmark we could experiment with different storage mechanisms in addition to speculating on performance implications

 

[Cervator]

That's pretty much what Terasology\src\dev\java\org\terasology\world\chunks\store\ChunkCachePerformanceTest.java is - we could probably extend off that to test new formats. Kai Kratz prepped that

As for fading sunlight - maybe we can calculate an average "surface" height and then only care about a height band around that? If there are any substantial structures way above the surface maybe it can get its own band and the sunlight refreshes way below to not cast weird shadows.

 

[mkalb]

I am working on an other solution: "Cubes"

1. A main cube with the edge length of the maximum height (for example 1024)
It manages all the cubes and blocks within it.
Contains the biome data (2D; x*z)

2. CompositeCubes
Contains 8 child cubes.
A Cube with edge length 128 has 8 child cubes with edge length 64.
Contains a default blockId (and other default values like light).
Contains a child status byte (8 Bit: One for every child cube). Status: Child exists/not exists.
If a child doesn't exist, the default values are used. This is very useful for large areas with the air block.

3. BlockCubes
Edge length maybe 8 or 16
Contains block values (saved into byte arrays like the current Chunk)

What do you think of this solution?

 

[Immortius]

What problem are we actually trying to solve here? Is there a particular performance issue of concern? Memory usage? Or is this just about increasing available height?

mkalb - I think your suggestion is similar to mine around the empty sky-chunks, and perhaps my suggestion in a different thread around having chunks more actively track the types of blocks that occur in them for switching between different internal representations. The main difference is I feel that it would be better handled by chunks managing their internal representation based on their content, rather than introducing outer levels to do that management. Possible internal representations would be uniform/sparse/byte array/short array modes. The outward interface is always the same, and the internal representation would be invisible except for persistence/network serialization.

Basically a world composed of 16x16x16 chunks (wouldn't want to go below 16, due to light propagation reasons - light propagates 15 units, so it is guaranteed that only a chunk and its adjacent chunks are needed to process a lighting change. 8x8x8 chunks would require obtaining a bunch more chunks which makes things more complicated). Keeping chunks as the only grouping level means we can be much more flexible with loading and unloading - having "main cubes" of size 1024x1024x1024 sets a hard limit on the minimum that can be loaded at a time, while we can keep the minimum loaded to a much tighter value with just chunks. We could even have "spherical" areas loaded if we want to cut corners.

I have experimented with the use of octrees before - the problem I found was they were simply too slow for random access - having to drill down through repeated layers, recalculating the indices for each layer. And then there is all the management of folding sub-trees together or splitting them apart with changes. Less layers is more performance.

On biome data, I don't really see any need to store it - sampling the procedural source is reasonably cheap and extremely space efficient. Are there some metrics suggesting it is a problem at the moment? Or if you want to have some other source for biome data that can be done too by having an alternate BiomeProvider- it is distinct from chunks themselves.

 

[Nym Traveel]

It's about increasing the height in first place and in second place it's about saving resources regardless of memory issues. I have no memory issues atm, but i can think of some other pc's who'd like to crank up their settings without trouble.

concerning the biome data:
I just thought that the frequent access to the procedural generation of the biomes would be fairly expensive. But you're the architect, I thrust you

The 16³ Cubes sound quite nice but I see one problem with the crrent way chunks are generated:
Currently, chunks are build top-down, so the iteration starts at y=256 and goes down to y=0. By this we can determine what the first block with something not equal to air is. This is essential for the distribution of the different materials; dirt, stone, etc (dirt always on top, etc). This would be more difficult with the smaller cubes.
One way would be to use the noise value directly, have to sleep over this idea

 

[Immortius]

If we're introducing infinite height then the algorithm needs to change regardless. But yeah, ideally the world generation should be able work out the value for any area of blocks without having to generate swathes of surrounding blocks - still might be best to have a higher Y span in a chunk. This would be a little interesting for trees and other structures - the simple way would be to detect whether a tree or structure may intersect the chunk, generate the entire structure and add the blocks that do intersect the chunk, then throw away the structure. This may be optimised through some caching of the structures. The key is that all world features should be fully deterministic based on the world seed and the block positions. Voronoi algorithm should be able to help with deterministic feature placement.

Should be noted that the current tree generation relies on a special generate phases where all adjacent chunks are available, and if the tree can't fit in that set of chunks it gets cropped (resulting in the occasional flattened tree foliage). Ideally that phase could be removed in the future.

 

[Nym Traveel]

Why throw away the structure? As terrain generation and building/tree generation are seperate anyway we could just calculate the adjascent chunks terrain with leaves/tree parts in it but prevent it from generating trees/structures of his own. By this we prevent chain reaction chunk loading. Maybe a little boolean flag on the chunk object which tells whether it's true loaded or not.
As the chunk is really loaded and structures are generated we'd need some rules what block can replace other blocks. E.g.: chunk a generates a tree which expands into chunk b. As chunk b's generation is in progress a house is generated which needs to cut the tree. The other way round if the tree is generated after the house it coudn't replace it.
This also would work for bigger structures like halls or temples or whatnot. Just place the terrain and mark them

(This is of course a naive first thought approach )

 

[Immortius]

The structure is a duplication of what is actually in the world, there's no need to keep it. Especially once all the involved chucks have been populated with the structure. The structures should also be deterministic, so they can just be regenerated. Although it is probably best to try and design generators so they don't need to generate whole structures - you wouldn't want to have to generate an entire city all at once. A city may cover thousands of chunks. Better to set things up so that you can generate as close to individual chunks of the city at a time.

The way the system works at the moment chunks are provided to the generators to be populated, rather than the generators requesting chunks. This is done in a series of phases, and a chunk isn't ready for use until it has passed all the phases. This allows the chunk manager to keep a tight reign on loaded chunks.

I think... I think what might help is if the generators were kept as a stack, with each generator being able to ask the generators under it what a given block is. The main terrain generator would be at the bottom, with other generators stacked on top in order of precedence. This will allow generators to sample a wider area of the world than just the already generated chunks. It also means the generators are sampling the unaltered world, which makes sense. Done this way, you wouldn't even need to pass the chunks into the generators necessarily.

 

[Skaldarnar]

My approach for building generation will be based on the biome, position, dimension and functionality of the building. As far as I know the city itself will be parted into different parcels for the actual buildings.
I am not sure wether its better to control the structure generation by one "control unit" or using the stack approach. But I can see some issues using the stacks, first of all the different generators would be dependend on each other and it would be a pain in the *** to change the generator system (what if the building generation comes before/after tree generation,...).
Using parcels and dimensions for tree generation as well could avoid the building-tree-issue, and maybe the city generator could mark parcels as tree-parcel which will later be generated by the respective generator.
The control unit should transform logical structures like buildings/cities and trees into the "physical" block representation. Due to that, new generators could easily be integrated in the control unit (only change one file), independent from the stack...

 

[Immortius]

I think you're right. The different generators are probably too inter-related to be fully separated for the most part. A stack structure on top of the main generator may be good for simple extensions though (like if someone mods in underground treasure rooms) - although perhaps the main generator should itself have extension points in its different areas (houses, trees, mineral veins, etc). But I guess my central point is a generator is essentially a process of taking an abstract, noise-based-or-otherwise world and pulling out the block for each location.

One thing that would be good is to change the world generator from depending on specific blocks all the time to selecting them from block metadata - for instance, instead of a house being made of brick + planks, maybe select from any available building material and wood material (to use for the entire house). That sort of thing. Just makes getting new blocks into the world easier. We probably need to add more metadata for this to work, like block categories.

 

[Cervator]

Block categories like that would be super important to get nice geology going too - good ole DF mineral layering

 

[Skaldarnar]

Yeah, block categories have to be on the todo-list absolutely.
I am trying to keep the building generator easy extensible by using grammars as basis, and I think underground structures (like mines or treasure rooms) and fortresses and castle would be some kind of special city generation...(okay, we still have the problem on how to add "new" custom generators...).

 

[Aperion]

I came here to ask a simple question that probably has a complex answer: Why are chunks 16x16x256? I think Immortius explanation of light propagation to be to be the best explanation I've heard so far. But that explanation just begs for a follow up question, why does light propagate 16 cubes? If chunks are changed to cubes why consider 16x16x16? why not 32x32x32? or 32x32x64? 64x64x16?

I'm not that familiar with the reason for one size over the other, but I do know part of the reasons for chunks is to reduce the amount of data loaded.16x16x256 is 0x10000 or 65,536 blocks. I also note that is a nice round (hex) number, you can fit two chunk locations in a single integer and thus no wasted space. But then again, so is 32x32x64 and 64x64x16, they both also contain the same number of blocks: 65,536 blocks.

a 64x64x16 chunk with light propagation of 15 would mean most of chunks would not need to load adjacent chunks to check for lighting, except for perhaps in the Z direction. With a 64x64x16 chunk size wouldn't the chunks be loading in the direction a user primarily moves and sees? When standing on solid ground most of a 16x16x256 chunk can't be seen as it is below the user.

I'd really like to get smart on this. I've only ever seen chunks mentioned as 16x16xN where N is a multiple of 16. So I am unsure if there is a technical reason for this, or just because of tradition.


I am interested in removing height/depth limits so that large scale natural formations could be generated such as sink holes, canyons, I also have some fantasy terrain ideas that would not work that well with a height of only 256 from bed rock to sky

 

[Immortius]

I came here to ask a simple question that probably has a complex answer: Why are chunks 16x16x256? I think Immortius explanation of light propagation to be to be the best explanation I've heard so far. But that explanation just begs for a follow up question, why does light propagate 16 cubes? If chunks are changed to cubes why consider 16x16x16? why not 32x32x32? or 32x32x64? 64x64x16?

I'm not that familiar with the reason for one size over the other, but I do know part of the reasons for chunks is to reduce the amount of data loaded.16x16x256 is 0x10000 or 65,536 blocks. I also note that is a nice round (hex) number, you can fit two chunk locations in a single integer and thus no wasted space. But then again, so is 32x32x64 and 64x64x16, they both also contain the same number of blocks: 65,536 blocks.

a 64x64x16 chunk with light propagation of 15 would mean most of chunks would not need to load adjacent chunks to check for lighting, except for perhaps in the Z direction. With a 64x64x16 chunk size wouldn't the chunks be loading in the direction a user primarily moves and sees? When standing on solid ground most of a 16x16x256 chunk can't be seen as it is below the user.

I'd really like to get smart on this. I've only ever seen chunks mentioned as 16x16xN where N is a multiple of 16. So I am unsure if there is a technical reason for this, or just because of tradition.


I am interested in removing height/depth limits so that large scale natural formations could be generated such as sink holes, canyons, I also have some fantasy terrain ideas that would not work that well with a height of only 256 from bed rock to sky

• The vertical axis is he middle one in Terasology, so chunks are 16x256x16.
• Sunlight doesn't attenuate when propagating downwards at the moment, so the complete vertical stack is required to calculate sun light. This is the primary reason chunks are 16x256x16 at the moment I believe.
• Need to work out how to ensure they player can generally see the ground from a mountain (empty chunks and extending relevance downwards when they are encountered would help with this)
• One of the reasons small chunks are nice is mesh size limits. If we were to use 16 bit indices, then worst case scenario for a 16x16x16 chunk is every second block being solid (3D checkerboard), with 4 vertices per side, 6 sides per solid cube = 49152, which is less than the 64k limit for 16 bit indices. We're probably using 32 bit indices at the moment anyway though. This can also be handled by generating more mesh as needed, so not a big deal.
• Having chunks with 65,536 blocks is also nice as it means that we can map all the types of blocks a particular chunk contains with shorts in a worse-case scenario.
• It doesn't matter how big a chunk is horizontally, adjacent chunks are still needed to calculate light propagation when the light changes happen towards the edge.
• I think that's about it? Using multiples of 2 is useful so that bitshifts and filters can be used when resolving blocks. Something like 32x64x32 chunks may work well.
• Any thoughts, begla ?

 

[Cervator]

Bump! This has been idling for a little while but came up on IRC/Mumble on Saturday and probably needs to get kicked back into gear.

Key part from the discussion might be the potential solution for sunlight propagation with potentially infinite height (chunks get stacked vertically) - early in the world generation process we create a height map and each pixel/value determines the average height in the chunk column that later becomes (that's a rough description, details may change). Persist that height value in the world map so it can be queried (and changed, important!) later on.

When we reach the terrain generation stage we are dealing with chunks that now are something like 16x16x16 or 32x32x32 or so. I figure there's some benefit to them being cubic, and 32^3 = 32,768 so an array of shorts would take 65,536 bytes, useful? To save space on height we could make the value stored in the heightmap be a byte (256 values) but be multiplied by a static value to get the actual in-world average height of the surface in that chunk column. I'm not sure how useful that is, but using an exact height from 0-256 isn't enough. Maybe multiply by 16 or 32 to get the real height in the world?

That would also be the minimum height difference between two pixels on the height map (although the actual terrain stored in chunks would be able to smooth that out) and give us a max height for an "Overworld" part of the world. 16 x 256 = 4096 = 4 km to play with mountains. I don't think sub-ocean would care about sunlight, and sub-ocean level chunks could be counted as "Underworld" and by convention use the sunlight variable for something else. We could even do a "Skyworld" above 4 km where you could have floating islands and space platforms that do not block sunlight, or at least do so in a vastly simplified fashion?

Around the average surface height we care about sunlight calculations in a set vertical band, like 256 blocks. Anything below that is considered devoid of sunlight (and that value could be used for something else) and anything above is always the max possible light value as per time of day (so again we can use the value for something else)

The difficulty comes in a few ways:

1. Player modifies the terrain drastically so the average height value changes - the world map storage for height values must be able to change after initial generation
2. Player outright does something obnoxious, like fill one side of a chunk column with blocks and clear the other side Where does the sunlight go, as simply averaging a chunk column could leave the average value hundreds below the top solid block?
3. Floating space platform scenario. Essentially you've now got two surfaces, as something sufficiently small / high up in the air should not block sunlight hitting the true surface, yet it needs shade on its bottom anyway. It sounds like trying to do an exception to calculate two bands of sunlight would be too much hassle, yet it still just looks goofy to have a perfect column of darkness, especially if the sun isn't even directly overhead but off to the side. Could involving the sun's angle help fix this and create more realistic shadows? That sounds like another big hassle. And imagine a world with multiple suns...

 

[Josh]

And imagine a world with multiple suns...

Nobody said Terasology had to be exactly like earth, why couldn't it have multiple suns? It may be Super Super weird and misleading but it's possible, kind of... Not in reality but, in a game, anything is possible. Other than that, good explanation, you did a good job explaining your point.