Can we reduce (faceted) worldgen api complexity?

[oniatus]

I want to put some thoughts on the worldgen for discussion:

1. I went through some of the interfaces and there seem to be a lot of interfaces which are completely tied to facetedWorldGeneration:
The WorldGenerator contains a method getWorld(), which is basically getSeaLevel + stuff for faceted generation (World). The term "World" seems to be wrong to me too: Why do i have to create chunks but also have to know how to create a "World"?
->(a) We could probably replace the method with getSeaLevel and put all the faceted stuff in the faceted provider.

2. The generator has to place the blocks in the chunk, means there is a likely some converting required, from world to local coordinates.
->(b) Can we rewrite the api in a way, that world generation depends only on world coordinates? It could still be something like: generate(AnyRegion region) but region could have only a .setSomething(Vector3i worldPosition, Something) and encapsulate the internal storage and world->local converting.

3. Facets and borders can get really confusing:
Take a facet with a noise-based distribution of spawnpoints as example. If the spawned structure can raise over chunk borders, you need to extend the chunk facet region.
Now for to Chunks A and B, each chunk will generate the same noise for the region, both may have an overlapping spawnpoint near their border and each chunk will generate only the blocks included in its region. Most of the time with stuff like: for each block of the structure -> if the block is in my chunk region -> place block.

This gets even worse for trees, which are generated by L systems.
If a tree covers N chunks, the entire L system is computed N times but only the blocks from the n-th chunk are set.

More fun for 2D-Data like a heightmap: Instead of calculating the heightmap once for each x-z axis, we calculate the heightmap for each x-z-y chunk
Means: If you have two chunks on top of each other, both will generate the same heightmap from the same noise, instead of reusing the data.
->(c) Can we find a way to "inverse" the process and remove all borders and facets from the "per chunk" view? I think we still need a border/max size info per facet, but maybe we can implement a way to reuse/cache the facet data globally instead of per-chunk.

Probably a goode usecase for the last one is a rainforest: Large trees may cover mutliple chunks in any direction and any size (why not have a super rainforest with 10 chunks height ) Trees are generated by a subsystem which is expensive enough to save the data for one tree instead of calculating it again and again.
One Idea how to solve this:
We ask the worldgenerator if there are blocks to place for a tree. The generator checks first the TreeSpawnPointFacet in each direction, covering an area as big as the maximum tree size (to be configured in the facet or somewhere). If the information is not present, the facet is exended by the required chunks. Internally, we can cache the information per-chunk but maybe limited for n chunks or for xyz time intervals.

If there is a tree spawnpoint in a distance that the tree may spawn into the current chunk, the tree is entirely generated and the blocks are put into a cache - also per chunk - (imaginary data structure, like a facet but with a different caching mechanism).
Afterwards, the rasterizer picks the blocks from the cache and places them (likely we can clear the cache for this chunk afterwards).
If we now go to the next chunk, there is already the cache calculated for the tree on the spawn position. We may resolve other trees (and probably need a merge strategy with conflicting blocks in the cache) but if we raster the trees in the chunk, we can use the existing blocks.

If world generation is paused and the game is restarted while a tree is only generated to 50%, the next time parts of it are required, we regenerate the cache for all not-generated chunks.

This would also enable to cache 2D data like heightmaps in a different/more efficient way than 3d-Data like spawn positions for object.


I did no proof-of-concept implementation so far but wanted to discuss the ideas first.
Thanks for any replies/ideas/stuff i missed

 

[Skaldarnar]

Thanks for bringing that topic up, there is likely a lot potential for good discussions!

re (1): Hm, getSeaLevel seems to be there of historical reasons. As stated in the Javadoc, the sea level value is used for adding reflection to the water surface (shader magic) - that should probably apply to all water bodies, regardless of their position. Cleaning up the interfaces and naming sounds like a good thing. Probably we can take any thoughts by GCI students into account (ask them what they _think_ the classes/interfaces are about, what they expected to get, etc.).

re (2): IMO, such a change would make sense. It's more about default behavior of the methods. A reasonable default would be to encapsulate conversions automatically, and only allow direct control through additional methods, e.g., automatically convert worldPos -> chunkPos and still have a setAtChunkPos(pos, ...) available.

re (3): IMO, the borders allow to generate chunks in parallel. If you plan to generate a structure over multiple chunks and resue it later, you'll get dependencies between generated chunks. We probably can try to do some clever caching or cue up structure placement over multiple regions somehow, but we should figure out first if that actually is a bottleneck here.
Overall, the idea should be to "not care" about the extra work performed by the system. You have a facet and borders, describe what it does/generates, and everything else works out automagically. I agree that we should clarify the use and purpose of everything here - need more images and diagrams.

Your closing ideas seem to match what I have in mind. However, I'm not sure about the complexity involved there, and if it is actually needed at this point. We probably should try to implemented that GiantRainForest for testing purpose, with over-the-top generators for trees and other structures. If the generators still perform reasonably well, there's probably no need for optimizations (yet).

 

[Cervator]

Definitely could use some more sketches and diagrams on this topic and in the world gen tutorial

Trees might almost be a bad example for "super structures" as they tend to be tall, and our chunks are tall anyway, so in the end not that many chunks are likely needed (a 10 chunk tall tree would be over half a kilometer high! Nearly as high as the Burj Khalifa). Maybe it would be easier to test with a large maze structure (and we actually have a maze generating tool used to test out Pathfinding stuff)

Related threads:

• http://forum.terasology.org/threads/gestalt-worldgen.1602/ and @chapp007 who was curious to extract our world gen system for use elsewhere (although on second thought it probably wouldn't be part of Gestalt as that's too voxel centric where the world gen like NUI would have potential elsewhere as well)
• http://forum.terasology.org/threads/new-conceptual-layer-sector-plus-musings-on-multi-world-node.1420/ is my usual plug, and maybe a good thing to try hitting if we do another world gen overhaul (especially if we also extract the framework). I talked to barteks2x on IRC who wrote a Cubic Chunks mod for MC and he used a similar Cube/Column approach including storing details that are above the chunk level (like surface details or heightmaps) in said Cube/Column objects. Maybe we can find a way to store/cache facet data in Sectors? They might be semi-ephemeral - one approach would be to serialize mostly everything via chunks with just a few things at a higher level (possibly even stored at the world level) then load up sectors dynamically based on what chunks are needed, with some overlap along sector edges. So with that setup caching would fit right in.

 

[xTimPugz]

Hello

I have noticed how you guys could optimize a few things. First of all, take a look:
https://github.com/Terasology/TutorialWorldGeneration/blob/master/src/main/java/org/terasology/tutorialWorldGeneration/HouseRasterizer.java
Ya see the funky stuff? Well, allow me to explain. Basically it asks for ALL of the facets EACH time a chunk generates. This doesn't seem extremely logical to me. Let's say you have a pyramid, with a size of 16,16,16 and the chunk you're currently generating starts at (0,0,0). It doesn't make much sense looking at facets far away, for instance at coords (5000,5000,5000).
Image to make it more clear:

http://prntscr.com/dubba1
Link there if image doesn't load. As you can see, from the top view, you only need to check between 2 points, which are (chunkMinX - X-size building, chunkMinZ - Z-size building) and (chunkMaxX + X-size building, chunkMaxZ + Z-size building). The square shape formed by these 2 points contains ALL of the possible Facets for THAT chunk. To make this more simple: you can just add the size of the structure to the chunk's max coords and subtract it from the chunk's min coords, making a region for that, and then checking in THAT region for facets. For the example above that'd mean that you get a 2D Rectangle made by using the 'forumula' I mentioned above; -16, -16, 80, 80, and then using that rectangle to get the World facets which are within this location.

I'd guess that there might be an issue here however: If you store Facets in a map of some sort, you'd have to loop through them anyway. Solution to this could be changing it a bit by making a new HashMap<Chunk, List<Facet>>();? (or something like that this was just a thought ).


Any thoughts?

Thanks

 

[oniatus]

The facet is a new instance per chunk:

HouseFacet houseFacet = chunkRegion.getFacet(HouseFacet.class);

E.g. for a chunk with the region Min: (-64, -128, -32), Size: (32, 64, 32))
you get a facet with Min: (-68, -136, -36) and Size: (40, 72, 40), because the HouseProvider requires the border extended by 4 units.

 

[xTimPugz]

So what you're saying is, that getWorldEntries does NOT send back all of the entries in the world? But rather the ones IN the chunk with the BORDERS added to them? I'd say that's a really funky name for a method.

 

[Josharias]

Hey all, I am very late to this party...

@xTimPugz: The "world" part of "getWorldEntries" is communicating that it is world relative positions, not chunk relative positions. It has been the common naming convention among the rest of the facet methods. But you are right, it does infer that it gets all the items for the entire world.

@oniatus: While caching could save some CPU cycles, it will also add complexity and memory usage. I think the design choice for limiting this facet data to a single chunk was to keep memory usage from ballooning. Consider what would happen if there were multiple players on a server in different sectors of the world. The server could potentially start keeping vast amounts of cached data, specially if each player is actively exploring the world. I would suggest that if caching was to happen, it would be only very short lived, like maybe only for a second.
Additionally I think you may find that world gen is not usually the bottleneck when it comes to loading chunks. Light propagation is currently the most limiting factor, not only in CPU cycles, but in memory usage. This in addition to the mostly single threaded behavior of light propagation. I put in some effort a while back to make light propagation more multithreaded. It caused a ridiculous improvement in load time for chunks, but there is some cross threading issues that I could not resolve in the time I had.

Re: Multi chunk structures
The L Tree system is probably the worst case scenario for performance with the facet system because the blocks are determined by a lengthy iterative algorithm. If we made trees predefined block "models" we could optimize this a fair amount by caching each tree variation globally (the Asset system should do this naturally) and then selecting a 3d region of the "model" for the chunk area we are rasterizing.
That said, mstieger did an excellent job of caching metadata of the world in PolyWorld. That may be a useful resource. Just keep in mind, that this was ported over to use facets after it was already a working generator, so there are probably places that could be optimized/simplified further in a new greenfield generator.