This Week In Veloren 117

This week, we get a deep dive into how world chunks are compressed and sent over the network. We see updates on the packaging front, and some amazing new creatures.

- AngelOnFira, TWiV Editor

Contributor Work

Thanks to this week's contributors, @Slipped, @Sam @xMAC94x, @juliancoffee, @zesterer, @holychowders, @aweinstock, @Pfau, @alfy, @XVar, @Snowram, @James, @Adalovegirls, @ygor.souza, @nwildner, @lboklin, @YuriMomo, and @imbris!

@zesterer added the ability for characters to hold their lantern when their right hand is free (i.e: when not wielding, or when using a single-handed weapon). @Pfau is in the process of remodelling the lanterns so they have a handle. The swinging animation looks surprisingly realistic given that it's entirely 'fake' (no physics is being simulated).

@alfy made some brand-spanking-new block and parry sound, as well as tweaked the wind sound to be a bit more organic. @LunarEclipse made a few improvements to Torvus, most notable is messages from Matrix are now bridged to Veloren in #ingame-chat. A full list of changes is included in the MR description. @juliancoffee fixed off-by-one error in localization tests, so outdated fields are now a more reliable way to check if a translation is up-to-date than before.

@XVar added more player-friendly error handling for network errors caused by client/server version mismatches. You will now get a dialog informing of a version mismatch if a version mismatch is detected and a networking error occurs during login after the server version is fetched. If login does succeed but there is still a client/server mismatch a warning banner is shown on the character select screen.

@Snowram created a new skeleton that will fit big winged creatures. They also made several animations for it and collaborated with @Gemu to make a phoenix model as well as transition the existing cockatrice NPC to the new skeleton. @Snowram also coded a combat AI for those new NPCs with the help of @James. Daytime-specific NPCs spawns were also added.

@juliancoffee fixed the burning debuff icon, which was previously displayed as a question mark on the hotbar. @Christof brought English as a fallback language to the finish line and resumed work on accelerating econsim using arrays.

Packaging Airshipper by @Frinsky

I have kept going with packaging Airshipper. There is now a PPA available for Ubuntu-based distributions: https://launchpad.net/~frinksy/+archive/ubuntu/airshipper. Packages are available for Ubuntu 18.04, 20.04, 20.10, 21.04 and their derived distros.

Additionally, I have made more packages available in my Copr repository (https://copr.fedorainfracloud.org/coprs/frinksy/airshipper/) to support more distributions. There are now builds for Fedora 32/33/34/Rawhide, Mageia 7/8/cauldron and openSUSE Leap 15.2. I am also planning on creating a comprehensive page with installation instructions for each distribution, to help new players get into the game more easily. Finally, I've submitted an Airshipper flatpak for inclusion into the Flathub repository, and it recently got merged and is now available here.

Compression by @aweinstock

I've been working on better compression formats for terrain chunks for sending them over the network. This is intended to help players with poor connections be able to play on servers in the first place, and to allow players with good connections to comfortably set a higher view distance to load more chunks at once. I've already merged a format that reduces the per-chunk space cost by 1.5x lossless, and have a few formats on a branch that can give another 5-9x reduction with some reduction in visual quality (but no cost to gameplay accuracy).

Terrain and lossless compression

Veloren only stores a very coarse heightmap of the world on disk. For a 1024x1024 chunk world, the mapfile is around 16MB, which is only 16 bytes per chunk. Pre-generating this is an expensive step, "worldgen", which simulates geological processes including erosion.

Chunks are generated with 32x32xZ voxels of data when their location comes within a player's view distance (Z varies per chunk). The in-memory structure (a "Chonk") consists of a z-offset for the bottom of the chunk, a vector of subchunks, and two default blocks for above and below the chunk. The subchunks are 32x32x16 slices, and internally deduplicate adjacent blocks of the same kind. These chunks tend to be a few hundred kilobytes each.

Previously, chunks were compressed the same way that most network traffic in Veloren is, with LZ4, achieving around 25% of uncompressed size. LZ-family algorithms accomplish compression by referencing previous occurrences of the data within the same file. This works great for text: the string " the "with spaces included occurs often in English, and a reference to a previous occurrence of the string " the " can save up to 5 bytes if the instruction to do a backreference takes less than 5 bytes. By backreferencing from the current position, you can also compress 200 copies of the same letter/voxel by emitting an instruction like "from 1 position backwards, copy 199 characters".

When I printed out some statistics on frequently occurring byte patterns in Chonks, I noticed that they had long runs of 0 bytes (which is good for LZ4), but sparse positions of other bytes, positioned seemingly randomly in the window size I was using. Since most of those bytes had a few common values, I tried using deflate, achieving around 17% of uncompressed size (with a quality setting that had a similar encoding time to LZ4). Deflate is the algorithm used by zip and gzip, and is a mix of LZ77 and Huffman coding. Huffman coding computes statistics on the input, and uses fewer bits to encode more common symbols. For example, in English text, "e" occurs more frequently than "z", but ASCII encodes both of them as 8 bits. With Huffman coding, it's possible to use fewer than 8 bits for "e" (like 3-4), and more than 8 bits (like 10-11) for "z". Huffman also synergizes nicely with LZ because the backreference instruction doesn't to be given a byte representation manually, it's just another abstract symbol that occurs with some frequency, which can get allocated a bit-sequence by Huffman coding.

Spatial locality and greyscale PNGs

LZ4 and Deflate operate on one-dimensional sequences of bytes. When applied to voxel data, this makes a x-aligned wall compress really well (since it's a run of adjacent bricks of the same kind and color), but a y-aligned wall or z-aligned pillar doesn't correspond to a contiguous run of bytes. LZ4 and Deflate also don't assume much about the statistical model of the data, so they don't compress increasing or decreasing runs of adjacent bytes (e.g. color gradients).

PNGs handles both of these concerns for 2d pixel data losslessly by using delta-encoding with a packing order, such that horizontal gradients get encoded with instructions like "copy left color and add 1" and vertical gradients get encoded with instructions like "copy above color and add 1". This makes the byte stream have contiguous runs of relative positions and offsets, which then compress well with deflate.

Each 32x32x1 slice of a chunk can be treated as an image. Encoding them as separate images per z-level would cost lots of space to image headers, so I pack all the z-levels for a chunk into a single image. Encoding each z-level into a square image, packed next to each other left to right, then packed as rows top to bottom, works well for visualizing what's going on, but wastes space if chunk height isn't a perfect square. Encoding a tall image, with each z-level stacked vertically in the image, doesn't waste any space. Additionally, flipping every odd z-level across the y-axis improves spatial locality, which translates to improved compression ratio and encoding speed in practice.

The gameplay-critical part of terrain (BlockKind data used for collisions, and sprite attributes used for interactable objects like treasure and plants) are stored in greyscale PNGs with 1 byte per voxel. This is around 1-2% of the uncompressed Chonks, and is the best format for it I've made so far, though it might be possible to do slightly better on this part with custom space-filling-curve orderings to improve locality.

Lossy compression for colors

The color data for blocks is much more expensive than the gameplay-critical data. Encoding it in an RGB PNG losslessly gives 16% compression ratio (barely better than deflated chonks).

Currently, the leading techniques for lossy compression of colors are:

• 256-color palette (throws away all the color info except for what's already knowable from the BlockKind, basically free)
• low-quality JPEG (2-3% of uncompressed size, but has horrible artifacting)
• Quarter-resolution PNG (3-5% of uncompressed size, but looks reasonably good, and allows control over artifacting).

For improving the aesthetics of the quarter-resolution PNGs, @LunarEclipse is tuning an implementation of Lanczos interpolation, which sweeps a convolutional filter across the image to upscale it in a way that tends to keep good edges (like road paths) and blur bad edges (like block artifacts).