Tweaking Chunk Storage

[Panserbjoern]

I guess it could be set up so that the arrays themselves are obtained, which helps for any batch operations (many reads/writes) - although the loss of encapsulation would be a worry.

I absolutely agree! Obtaining the arrays themselves would be nice for performance. Though the loss of encapsulation is a problem. Think about liquids for example.

    public boolean setBlock(int x, int y, int z, Block newBlock, Block oldBlock) {
        if (newBlock != oldBlock) {
            if (blocks.set(x, y, z, newBlock.getId(), oldBlock.getId())) {
                if (!newBlock.isLiquid()) {
                    setLiquid(x, y, z, new LiquidData());
                }
                return true;
            }
        }
        return false;
    }

The above method is from the chunk class. Every time a block is changed, it is necessary to check, whether the new block type is liquid or solid. If the new block is solid it is necessary to clear the liquid data.

But the problem is not only about liquids! In the thread about block dynamics Cervator is talking about general extra-data per block, whose meaning and interpretation would be specific to the type of the block. This makes it necessary that block and extra data are tightly encapsulated. Every block type needs to specify whether it requires extra data and it needs to specify a default value for the extra data. (For debuging purposes the blocks might even specify the exact range of valid extra data values. This would allow to validate the extra data and would certainly make it easier to find bugs. It would also be possible to throw an exception if invalid extra data values are set.)

Generalized for extra data, the above method might look like this:

    public boolean setBlock(int x, int y, int z, Block newBlock, Block oldBlock) {
        if (newBlock != oldBlock) {
            if (blocks.set(x, y, z, newBlock.getId(), oldBlock.getId())) {
                if (newBlock.needsExtraData()) {
                    setExtra(x, y, z, newBlock.getDefaultExtraData());
                } else {
                    setExtra(x, y, z, 0); // could be omitted... ???
                }
                return true;
            }
        }
        return false;
    }

And there might be an additional setBlock() method which allows to pass extra data:

    public boolean setBlock(int x, int y, int z, Block newBlock, byte extra, Block oldBlock) {
        if (newBlock != oldBlock) {
            if (blocks.set(x, y, z, newBlock.getId(), oldBlock.getId())) {
                setExtra(x, y, z, extra);
                return true;
            }
        }
        return false;
    }

The extra data could be larger than just one byte if necessary. Maybe using a 16-bit value would be desireable...

Probably some way to provide views which work within the locks.

I was thinking about that too. I would like it to solve the encapsulation problem through views because they would allow lots of cool stuff:

• Views which allow direct access without encapsulation.
• Views which span multiple chunks.
• Read-Only views! That allows to extend the simple lock into a read/write lock. Good for performance!
• Blocking views: They would block until the chunk is ready/available. Or maybe that could be an integral part of every view. It would simplify the implementation of algorithms which require multiple chunks to be fully ready and available. Very useful for vertical chunks, i guess...
• e.t.c.

But each tera array could implement methods to serialize/deserialize to a raw byte stream...

I have just read more about protobuf. Its features are very cool! I will implement serialization to raw byte streams. I don't have any experience with protobuf though. What do you say about something like that? Would that work with protobuf?

    public void serialize(DataOutputStream out) throws IOException {
        ...
    }
 
    public void deserialize(DataInputStream in) throws IOException, ClassNotFoundException {
        ...
    }

Well, its late again in switzerland... Good night!

 

[Immortius]

I would suggest OutputSteam/InputStream rather than DataXStreams for the interface. The use of the DataXStreams is a serialization implementation concern, not a concern for the caller. You can wrap those with DataXStreams within the implementation if desired. When serializing into a protobuf object, protobuf's ByteString class would be used, and that only provides InputStream and OutputStream.

I'm not sure why ClassNotFoundExceptions would be possible, as you would already need to have found the correct TeraArray class to call deserialize, and you shouldn't be doing any java object serialization (that's the can of worms we're trying to move away from). I'ld also tend to think that deserialization should be a factory method that produces a new TeraArray - this would suggest serialization may be best done as a separate class (likely an inner static class on top of a private constructor). That way you can save some of the cost of constructing the arrays. Perhaps conforming to a common interface like:

public interface TeraArraySerializationHandler<T extends TeraArray> {
    void serialize(T array, OutputStream out) throws IOException;
    T deserialize(InputStream in) throws IOException;
}

The TeraArrayFactory (or whatever) could then keep a mapping of TeraArray implementation to serialization handler, and a mapping of id to TeraArray class, so when given the protobuf object containing a serialized TeraArray it can find the correct handler. Alternatively deserialization could be a static method hooked up by reflection or byte code manipulation, but that probably isn't worth the additional complexity.

 

[Cervator]

For what it is worth my nefarious plot to add another per-block data value was planned to take effect for all blocks, not conditionally on the block type. I was attaching 3-4 different systems, admittedly, where the secondary value would mean different things depending on what the block is - but it would always be present. Really at first it was more of a stab at upgrading/augmenting the existing per-block variables to be used more efficiently, even bit-wise if better done that way.

Real brief my latest thoughts (from a while back) had a single short value meaning under different circumstances something like this:

• Solid block = "integrity" - as in, how well supported the block was, starting at max value at "bedrock" then dropping the higher a column of block goes also modified on the exact type of block (sand would not maintain support well, rock would)
• Liquid block = "pressure" - how compressed is the liquid and if given an outlet with how much force would it expand to how much volume. Could possibly replace the existing liquid variable with a low end (0-15?) being natural liquid height and any value above that being pressure
• Hybrid block = "moisture" - for semi-solid blocks that could serve as aquifers, plants, stuff like that. Would not
• Air / gas block potentially again a pressure or force value for weather, impact of gas explosions, fun stuff like that

It would be nice to either split all that out into separate systems, even separate storage, if that makes sense processor/memory-wise. Or integrate with a few fundamental values that'll be in core and always present (like right now the liquid variable is useless in non-liquid blocks). I'm sure the idea is full of holes, so feel free to start poking them and suggesting better approaches, at least as far as storage goes in this thread, maybe better to keep bigger design notes in its own thread

 

[Panserbjoern]

Immortius

Hm... I am currently experimenting with the implementation of serialization handlers for tera arrays. I have already implemented handlers for every array type. They are using a similiar interface like you suggested it above. Internally they use DataOutputStream/DataInputStream.

There is only one big problem though. I have implemented benchmarks for the new serialization handlers as well as for the current object serialization code.

It looks like object serialization is about 6 times faster than using Data*Streams...

I will soon commit the most recent changes to my simple-sparse-chunk branch. Maybe you want to take a look at it?

Next i will do some experiments with NIO classes. There is some interesting stuff there with Buffers. Maybe they will be faster.

How is protobuf working internally? Streams only, i guess?

 

[Immortius]

I will have a look at it, sure.

I still feel you should just have a go of using protobuf for the Tera Arrays - write a protobuf message description for each one, generate the java classes for it using the protobuf compiler, and then just need to use those classes to generate the bytes to write to the stream and get it back afterwards.

I don't know the implementation details of protobuf, but believe it likely uses NIO internally at some level. It certainly has it's own stream implementation. It only exposes streams and byte arrays in the interfaces though, probably for compatibility with old JVM versions.

 

[Panserbjoern]

Well, the good news is, with NIO the serialization would be as fast as java object serialization!
Now i will take a look at protobuf and try to implement it that way. Lets find out how fast protobuf is!

 

[Panserbjoern]

Hi. It took me a while to implement tera array serialization, but now it's working and it's FAST!

1. I studied the documentation of protobuf and the generated java code. Protobuf supports only one way to handle large messages. That's through ByteString, which essentially encapsulates an array of bytes. Protobuf cannot efficiently handle large structures like tera arrays, which are composed of tens of thousands of elements. So there is just no way around home grown serialization of tera arrays and chunks if we don't want to use java object serialization.
2. I have implemented serialization and deserialization for all supported tera array types. The implementation uses NIO ByteBuffers, which makes it blazingly fast and compatible to protobuf since protobuf's ByteString can handle NIO ByteBuffers.
3. The implementation supports the transformation of tera arrays into protobuf messages and back through TeraArrays.encode() and TeraArrays.decode().
4. I have added some benchmarks to compare different mechanisms/strategies for serialization.

The following features/enhancements are planned:

1. Encoding entire chunks into protobuf messages and back.
2. Make encoding/decoding threadsafe.
3. Better management of ByteBuffers for increased performance.
4. Use protobuf in chunk stores for caching.
5. Use protobuf to store entire worlds to disk.

Have a look at it in my branch simple-sparse-chunk at GitHub:
https://github.com/mbrotz/Terasology/tree/simple-sparse-chunk


Good night!

 

[Cervator]

Nice work! Have a badge upgrade, keep it up!

 

[Immortius]

Looks good. I'ld suggest a comment above the serializer for each TeraArray just briefly outlining the structure for each, for reference by anyone working in a different language. I would also suggest making the x/y/z coords in the chunk messages optional - it is generally best to lean towards optional elements in Protobuf (required is forever), and there are some use cases where coords may not make sense (block vehicles). Also note that the first 14 ids in a protobuf message are "special" - these use the least space so if there are any elements you think are temporary or less common consider setting their ids 15 and above (don't know if there are any).

1. I studied the documentation of protobuf and the generated java code. Protobuf supports only one way to handle large messages. That's through ByteString, which essentially encapsulates an array of bytes. Protobuf cannot efficiently handle large structures like tera arrays, which are composed of tens of thousands of elements. So there is just no way around home grown serialization of tera arrays and chunks if we don't want to use java object serialization.

I absolutely agree that the arrays in TeraArrays need to be byte strings, but that doesn't mean everything has to be. The intermediate I had in mind was more around having messages reflecting the structure - for your sparse arrays for instance you could have a message consisting of the inflated arrays (as a single byte string), the deflated array (another byte string), fill (int16 I guess), and the sizes (int16 each). That is less than a dozen elements. In this way you gain the benefits of protobuf around versioning/change handling, while still having efficiency around storage of the big data blocks.

Probably not that big a deal, can always switch to that technique the first time there is a breaking change to a TeraArray's serialization (if ever).

 

[Panserbjoern]

Jippie, got an architect badge!
Thanks!

 

[Panserbjoern]

Immortius, i will add the comments describing the byte sequences for the serialized arrays. All the fields in the protobuf messages are now optional.

The intermediate I had in mind was more around having messages reflecting the structure - for your sparse arrays for instance you could have a message consisting of the inflated arrays (as a single byte string), the deflated array (another byte string), fill (int16 I guess), and the sizes (int16 each).

Hm... I understand your thoughts. The reason why i didn't implement it that way, is, that i wanted to make it as simple as possible for mod developers to introduce their own tera array implementations. If we reflect the structure of the arrays in the protobuf messages it would be necessary for both mod developers and ourselves to extend the protobuf messages for every new tera array implementation. But in my opinion, the tera arrays shouldn't have to expose their inner structure for serialization. New implementations might be entirely different to the existing ones and they would have to implement the whole handling of protobuf messages themselves... And because the core tera arrays are quite simple structures, i think there will never be breaking changes in the serialization format.

But if i am wrong and it turns out it would be better to have more complex protobuf messages, i will change the implementation.

Are you ok with this?

 

[Immortius]

I'm fine with that.

 

[Panserbjoern]

For those who might be interested, i have pushed a new branch to my fork.

https://github.com/mbrotz/Terasology/tree/chunk-visualizer

It contains a very simple and dirty implementation of a chunk visualizer. When you start the game, it opens a second window in the background. Don't close it, you can't make it visible again until you restart the game.

The visualizer window is black when you start the game. As soon as you load or create a world it will display the chunks as they are created. When you move through the world the visualizer is updated with the new loaded/created chunks. This is not intended to be a minimap! It's purpose was to help me understand what's happening in the background with all those chunks. Every chunk is just displayed as a small square and it's color indicates its internal state.

The states and colors are as follows:

ADJACENCY_GENERATION_PENDING => light gray
FULL_LIGHT_CONNECTIVITY_PENDING => cyan
LIGHT_PROPAGATION_PENDING => magenta
INTERNAL_LIGHT_GENERATION_PENDING => orange
COMPLETE => green

 

[Panserbjoern]

I am thinking a lot about how to implement vertical chunks, but i'm not sure how to proceed... There are lots of thoughts buzzing in my head.

These are the main goals i have currently in mind:

1. Allow chunks to be encoded into protobuf messages (and decoded again)
2. Prepare everything to allow mods to request additional per block storage (like blocks, sunlight, light, liquid)
3. Switch to views of chunks instead of directly accessing chunks. This includes:
   1. Get rid of all data accessor functions on chunk level (getBlock(), setBlock(), getLight(), etc)
   2. Adapt/rewrite existing algorithms such as terrain generators, decorators, light propagation and liquid simulation to use the new views
4. Implement vertical stacking of chunks. This includes:
   1. Adapt/rewrite LocalChunkProvider to handle vertical chunks
   2. Adapt/reimplement existing algorithms (terrain, deco, light, liquid) to work with vertical chunks. (I don't want to implement/invent new algorithms for worlds without height limit, i will use a "virtual height limit" instead)
5. Switch from java object serialization to protobuf to store worlds on disk. That includes:
   1. Implement actual unloading of far away chunks.
   2. Store chunks in multiple files instead of just one big file.

All that stuff will require lots of changes which will probably break Immortius multiplayer arc and the work of others anyway. So i thought, it would make sense to rewrite the classes Chunk and LocalChunkProvider from scratch to suit the needs of the above ideas. They could be named VerticalChunk and VerticalChunkProvider.

What do you guys think about that? Any objections, suggestions, ideas.... ???

Sleep well!

 

[Immortius]

1. Switch to views of chunks instead of directly accessing chunks. This includes:
   1. Get rid of all data accessor functions on chunk level (getBlock(), setBlock(), getLight(), etc)
   2. Adapt/rewrite existing algorithms such as terrain generators, decorators, light propagation and liquid simulation to use the new views

Just about nothing directly accesses chunks anyway, except the very early stages of chunk generation (where the chunk is built in isolation). All game logic that changes the world should be working through the world provider, and the world provider and propagation algorithms work against WorldView, not chunks themselves. So already done?

But I can see where you are coming from. You want to change chunks so they hold a number of data items, and that to work with them you request out a View or Accessor over that data item to work on it. These Accessors need respect the chunk's lock and any logic around changing those values. This is sensible.

I would suggest that the amount of logic around changes at a chunk level will be minimal. They will be only for changes that occur within a position - never adjacent positions as those are handled at a higher level to deal with chunk boundaries. Perhaps the ability to have a type of block data subscribe to changes to another type, in order to enact simple changes would suffice? The Accessors need to trigger these interceptors appropriately in that case.

So, working above the level of a chunk. Early chunk generation should just work directly through the Accessors, the chunks haven't been attached to the world yet and the generators need to make huge changes. For everything else, I would suggest changing (or creating a variant of) WorldView that instead of sitting on a set of chunks, sits on the Accessors of a specific data item from a set of chunks. All the propagators, and the WorldProvider will continue to work against world views (as they allow seamless working over multiple chunks), but will get the world views for the specific data item they work against.

The main game logic will continue to work against the WorldProvider, but with some ability to get read-only world views on different data items, or get the value of any data item (for non-batch operations).

The current liquid system is pretty bad and shouldn't be used as an example of how things should work - I got to a half-way state between liquids being a type of block, and liquids being independent of block (which I think is the way to go) and stopped.

1. Implement vertical stacking of chunks. This includes:
   1. Adapt/rewrite LocalChunkProvider to handle vertical chunks
   2. Adapt/reimplement existing algorithms (terrain, deco, light, liquid) to work with vertical chunks. (I don't want to implement/invent new algorithms for worlds without height limit, i will use a "virtual height limit" instead)

The API for chunk provider/world/world view should already support vertical chunks. The work that needs to be done is

• Change some TeraMath methods to no longer ignore Y values
• Change the LocalChunkProvider to consider the vertical (set LOCAL_REGION_EXTENTS.y to 1, change various other vectors to have a Y value)
• Change the relevance regions to have a vertical element
• Ensure WorldView works with vertical chunks, updating it as necessary.
• Update lighting and world gen algorithms - this is the major point of work, particularly sunlight handling as it needs to regenerate over vertical distance when above the world's "surface". Having a full byte for lighting data under the new sparse implementation will help here.
• I think that is about it

All that stuff will require lots of changes which will probably break Immortius multiplayer arc and the work of others anyway. So i thought, it would make sense to rewrite the classes Chunk and LocalChunkProvider from scratch to suit the needs of the above ideas. They could be named VerticalChunk and VerticalChunkProvider.

What do you guys think about that? Any objections, suggestions, ideas.... ???

Sleep well!

I'm looking forward to being able to use the new sparse arrays in multiplayer, so if you could prioritise finishing off work around serializing chunks using them that would be great.

There should only be a small number of changes needed to LocalChunkProvider, I wouldn't bother making a new chunk provider. You should absolutely not need a new chunk class, it doesn't care about its position or relative chunks and it should stay that way.

 

[Cervator]

For those who might be interested, i have pushed a new branch to my fork.

https://github.com/mbrotz/Terasology/tree/chunk-visualizer

It contains a very simple and dirty implementation of a chunk visualizer. When you start the game, it opens a second window in the background. Don't close it, you can't make it visible again until you restart the game.

The visualizer window is black when you start the game. As soon as you load or create a world it will display the chunks as they are created. When you move through the world the visualizer is updated with the new loaded/created chunks. This is not intended to be a minimap! It's purpose was to help me understand what's happening in the background with all those chunks. Every chunk is just displayed as a small square and it's color indicates its internal state.

The states and colors are as follows:

ADJACENCY_GENERATION_PENDING => light gray
FULL_LIGHT_CONNECTIVITY_PENDING => cyan
LIGHT_PROPAGATION_PENDING => magenta
INTERNAL_LIGHT_GENERATION_PENDING => orange
COMPLETE => green

That looks really neat and useful - thank you! I think that would be a really cool debug option to add a little polish to (labels? Spawn from main menu as an option?) and keep in the game permanently. Seems like it would both be a very educational way to learn about chunks as well as a great way to help develop liquid simulation, cache options, etc

Sample:

I'm going to take a wild guess and theorize the gray chunks on the side manage to load in the very first few moments of a game loading, maybe before something related to the player loads?

 

[Panserbjoern]

That looks really neat and useful - thank you! I think that would be a really cool debug option to add a little polish to (labels? Spawn from main menu as an option?) and keep in the game permanently. Seems like it would both be a very educational way to learn about chunks as well as a great way to help develop liquid simulation, cache options, etc

Sample:

View attachment 764

I'm going to take a wild guess and theorize the gray chunks on the side manage to load in the very first few moments of a game loading, maybe before something related to the player loads?

Thanks! I want to add some polishing later. I am not sure though how to extend this once vertical chunks are available...

About the sample, currently the view does not get updated correctly when you load/create more than one world per session. Maybe its because of that?

 

[dei]

Cool idea this additional debug-Window!

For vertical Chunks: You simply render it in 3D .
No, seriously, we could make two step-buttons to step through the vertical layers.
To fine-tune the compressing algorithm it would be ideal to be able to click on a chunk and get some statistics about the three most used block types with their occurence, its compression rate.
(Reviewing your code I thought of allowing a compression if a row only has one or two differing block-type that could increase compression rate substantially, with certain distributions)

I will look into your branch this weekend and try to implement my propositions by myself. (will send you a patch/pull request if I'm successful)

 

[Panserbjoern]

Hi dei, i thought about stepping through the vertical layers too. First we need vertical chunks, though!

If you want to improve runtime compression just extend TeraArray and implement your own special version. Then you can add a method to TeraVisitingDeflator and implement that method in TeraStandardDeflator.

Keep in mind, though, that your array needs to support write access, even for compressed rows!

 

[Panserbjoern]

Hi Immortius

Just about nothing directly accesses chunks anyway, except the very early stages of chunk generation (where the chunk is built in isolation). All game logic that changes the world should be working through the world provider, and the world provider and propagation algorithms work against WorldView, not chunks themselves. So already done?

Hm... Well, i think the WorldView is a good starting point that can be refined... For example, in my opinion, the chunks should not bother about encapsulation at all. There should be no get/set methods for data on the chunks themselves. They only need to have getters to retrieve the arrays. The views can implement encapsulation. If we distinguish between read/write and read-only access we can also refine the locking mechanism into a read/write lock.

I would suggest that the amount of logic around changes at a chunk level will be minimal. They will be only for changes that occur within a position - never adjacent positions as those are handled at a higher level to deal with chunk boundaries. Perhaps the ability to have a type of block data subscribe to changes to another type, in order to enact simple changes would suffice? The Accessors need to trigger these interceptors appropriately in that case.

The idea of some kind of change subscription is interesting. The only problem i can see here is with performance... But i will do some investigation into that topic later.

So, working above the level of a chunk. Early chunk generation should just work directly through the Accessors, the chunks haven't been attached to the world yet and the generators need to make huge changes. For everything else, I would suggest changing (or creating a variant of) WorldView that instead of sitting on a set of chunks, sits on the Accessors of a specific data item from a set of chunks. All the propagators, and the WorldProvider will continue to work against world views (as they allow seamless working over multiple chunks), but will get the world views for the specific data item they work against.

I can fully agree with that.

The API for chunk provider/world/world view should already support vertical chunks. The work that needs to be done is

• Change some TeraMath methods to no longer ignore Y values
• Change the LocalChunkProvider to consider the vertical (set LOCAL_REGION_EXTENTS.y to 1, change various other vectors to have a Y value)
• Change the relevance regions to have a vertical element
• Ensure WorldView works with vertical chunks, updating it as necessary.
• Update lighting and world gen algorithms - this is the major point of work, particularly sunlight handling as it needs to regenerate over vertical distance when above the world's "surface". Having a full byte for lighting data under the new sparse implementation will help here.
• I think that is about it

I was thinking about some kind of "virtual height limit", so the existing terrain generators and light propagation wouldn't have to be changed right now. (Would be easier for me... ) Lets say we have chunks of size 16x16x16. I would then simply generate 16 chunks vertically stacked and have the terrain and light algos work on them through a world view. The algos wouldn't have to know about the internal chunk size, they would just continue to work as always. The virtual height limit could be made configurable through the "create world" dialog.

The LocalChunkProvider would be aware of the virtual height limit and create the chunks accordingly. Above and below the virtual height limit it would just create chunks on demand. Above the limit the chunks would just be filled with air, below they would be filled with stone.

Later we (or you ? ) can reimplement terrain generation and lighting to actually work with vertically stacked chunks...

I'm looking forward to being able to use the new sparse arrays in multiplayer, so if you could prioritise finishing off work around serializing chunks using them that would be great.

No problem! I will finish it as soon as possible!


Conclusions: After chunk serialization is finished i will start working on vertical chunks. I will try to work on top of existing code as much as possible, adding new stuff only where necessary. Existing classes, such as WorldView, will be adapted to keep them behave as they do now.