Level File Format Improvements #79

New Issue

kirsle · 2022-03-28T01:20:10Z

kirsle commented

2022-03-28 01:20:10 +00:00

The level file format has room for improvement (better compression), currently they are JSON files compressed with gzip and all chunks use the MapAccessor (only chunker implemented) which maps points to palette indexes.

Ideas for improvements:

Add Limits

To get smaller integers/less waste in memory:

Palette can be limited to 256 colors (uint8), maybe 255 to leave a reserved value for 'null' (0xFF)
Chunk sizes can be limited to 256x256 (default is 128 in balance.ChunkSize)
~~Coordinates inside a chunk can therefore be uint8's.~~
- Notes: it was not this way before, even inside a chunk we used absolute world position (64-bit ints), may be hairy to change it now.

Currently: render.Point (X, Y int) are used everywhere, it's 64-bit numbers, this is OK for level coordinates but for in-chunk coordinates moving to uint8's can be an 8X reduction in size.

Chunkers

Improve: MapAccessor

It's a map[render.Point]*Swatch type and in JSON format it becomes a dictionary where keys are X,Y coords like "123,100" and values are integers for palette index. All these numbers are 64-bits in memory so when loaded as Go structs it's at least 24 bytes of memory per pixel.

Possibly can improve the MarshalJSON implementation for better compression. For backwards compatibility, UnmarshalJSON loads into a map[string]int and it could do two passes when decoding a level: unmarshal the new format (not a map[string]int) and if the legacy level doesn't fit that format (returns an error) then load it the old way, but on next re-save, the Marshal function will use the new encoding.

New encoding could possibly be: stream of uint8 bytes, {X, Y, index}, can be a []byte type in Go that automagically encodes as base64 in JSON. Size savings could be:

If X and Y were 3 digit values (100, 120) in the 128x128 chunker
And the palette index was 2 digits (color #10, 11)
"100,120": "10" 9 bytes in digits, 15 with json symbols
0x64 0x78 0x0a 3 bytes hex per pixel.

Done: MapAccessors now serialize to binary using triplets of {varint X, varint Y, uvarint Palette}.

Add: GridAccessor

Planned since the beginning but not added yet, it would be a 2D array for densely packed chunks. Palette index 255 (0xFF) can be the null value since palettes currently index from 0 upwards.

When serializing to JSON use a run-length encoding for higher compression.

Add: UniformAccessor

When a whole entire chunk is filled all in the same color, we could save a LOT of space by having this chunker just treat all of its pixels as the same: Get(x,y) returns the color always. On Set() if the uniformity is going to be broken, switch to a GridAccessor.

Load Rebalance

On level save, the level can choose a new accessor per chunk based on how dense it is (exact balance to be tuned), e.g.

MapAccessor by default, until the len() of points exceeds 75% or so then switch to GridAccessor
GridAccessor may revert back to a MapAccessor if enough null pixels appear again. If the full grid becomes uniform, upgrade to a UniformAccessor.

Runtime Performance

On Chunker.Set() for large rectangles it takes a long time probably because it marks the texture dirty every time, add a way to suspend texture invalidation until done so the whole game doesn't freeze up for seconds.

The level file format has room for improvement (better compression), currently they are JSON files compressed with gzip and all chunks use the MapAccessor (only chunker implemented) which maps points to palette indexes. Ideas for improvements: ## Add Limits To get smaller integers/less waste in memory: * [x] Palette can be limited to 256 colors (uint8), maybe 255 to leave a reserved value for 'null' (0xFF) * [x] Chunk sizes can be limited to 256x256 (default is 128 in balance.ChunkSize) * ~~Coordinates inside a chunk can therefore be uint8's.~~ * Notes: it was not this way before, even inside a chunk we used absolute world position (64-bit ints), may be hairy to change it now. Currently: render.Point (X, Y int) are used everywhere, it's 64-bit numbers, this is OK for level coordinates but for _in-chunk coordinates_ moving to uint8's can be an 8X reduction in size. ## Chunkers ### Improve: MapAccessor It's a `map[render.Point]*Swatch` type and in JSON format it becomes a dictionary where keys are X,Y coords like "123,100" and values are integers for palette index. All these numbers are 64-bits in memory so when loaded as Go structs it's at least 24 bytes of memory per pixel. Possibly can improve the MarshalJSON implementation for better compression. For backwards compatibility, UnmarshalJSON loads into a `map[string]int` and it could do two passes when decoding a level: unmarshal the new format (_not_ a `map[string]int`) and if the legacy level doesn't fit that format (returns an error) then load it the old way, but on next re-save, the Marshal function will use the new encoding. New encoding could possibly be: stream of uint8 bytes, {X, Y, index}, can be a []byte type in Go that automagically encodes as base64 in JSON. Size savings could be: * If X and Y were 3 digit values (100, 120) in the 128x128 chunker * And the palette index was 2 digits (color #10, 11) * `"100,120": "10"` 9 bytes in digits, 15 with json symbols * `0x64 0x78 0x0a` 3 bytes hex per pixel. **Done:** MapAccessors now serialize to binary using triplets of {varint X, varint Y, uvarint Palette}. ### Add: GridAccessor Planned since the beginning but not added yet, it would be a 2D array for densely packed chunks. Palette index 255 (0xFF) can be the null value since palettes currently index from 0 upwards. When serializing to JSON use a run-length encoding for higher compression. ### Add: UniformAccessor When a whole entire chunk is filled all in the same color, we could save a LOT of space by having this chunker just treat all of its pixels as the same: Get(x,y) returns _the_ color always. On Set() if the uniformity is going to be broken, switch to a GridAccessor. ### Load Rebalance On level save, the level can choose a new accessor per chunk based on how dense it is (exact balance to be tuned), e.g. * MapAccessor by default, until the len() of points exceeds 75% or so then switch to GridAccessor * GridAccessor may revert back to a MapAccessor if enough null pixels appear again. If the full grid becomes uniform, upgrade to a UniformAccessor. ## Runtime Performance * On Chunker.Set() for large rectangles it takes a long time probably because it marks the texture dirty every time, add a way to suspend texture invalidation until done so the whole game doesn't freeze up for seconds.

kirsle added the

enhancement

label 2022-03-28 01:20:17 +00:00

Sign in to join this conversation.