Skip to main content

Blog Archive

Using Run Length Encoding (RLE) to Compress ROBLOX Terrain

June

13, 2012

by Lord Rugdumph


Archive

Terrain-based ROBLOX IslandROBLOX released its high-performance terrain feature late in 2011, allowing users to create and play games significantly larger than anything previously seen on the platform. Many ROBLOX users have since taken advantage of terrain, particularly to facilitate expansive games with fast vehicles. Currently, the ROBLOX Content Team is pushing the feature further than ever before with a new game that procedurally generates destructible, cliff- and gold-ridden terrain each round (we’ll have more on that soon).

Terrain can be up to 2048 x 256 x 2048 studs in dimension, containing up to 16 million 4 x 4 x 4 terrain cells, with no graphics slow-down. One of the supporting techniques we use to make terrain so scalable and efficient is Run Length Encoding. Run Length Encoding makes the file sizes of terrain places a small fraction of what it would be with normal parts.

Run Length Encoding

Every published ROBLOX game is hosted on Roblox.com, so one of the keys to efficient terrain on our platform is saving the data in a cost-effective way. To that end, we use Run Length Encoding, or RLE. RLE is a method of storing a sequence of duplicates. Rather than store each duplicate item individually, RLE creates a count of the duplicates.

Let’s say we’re saving a small piece of terrain that consists of eight grass cells. You could store each grass cell individually – in this case, you would use five letters for each cell, for a total of 40 letters.

Grass Grass Grass Grass Grass Grass Grass Grass

Using RLE, we can store the small piece of terrain much more efficiently. Using only seven letters, we reduce the overhead by more than five times.

8xgrass

RLE doesn’t always save space because it’s dependent on there being a sequence of duplicates. For example, suppose you have alternating solid and empty spaces in a voxel grid. Again, you could store each cell individually.

solid empty solid empty solid empty

But using RLE would actually increase the data you’re storing by 12 characters, or about 40%.

1xsolid 1xempty 1xsolid 1xempty 1xsolid 1xempty

Duplicate Terrain Cells (Bottom view)

ROBLOX terrain is usually composed of a sequence of duplicates. As you can see in this screenshot of the bottom side of a common terrain formation, there are a lot of repeated cells.

A Practical Example

For a more practical example, consider two 15 x 15 x 15 structures, one made of standard ROBLOX parts and one built with terrain cells. Here’s a comparison of the amount of data stored with and without compression.

Regular ROBLOX parts Regular ROBLOX parts (Zipped) Terrain Terrain with RLE Terrain with RLE (Zipped)
8245 KB 83 KB 32768 KB 44 KB 3 KB

The unencoded, uncompressed terrain structure is actually more data intensive than the structure made with parts, but RLE and compression make the terrain structure much more efficient. Terrain with RLE and compression is 27 times smaller than compressed regular ROBLOX parts, 14 times smaller than terrain with RLE but no compression, and about 11,000 times smaller than standard terrain. ROBLOX uses zipped RLE terrain in practice.

Using these ratios, if you built a maximum-size terrain out of regular ROBLOX parts, the game file, even with compression, would already be around 380 MB.

We should note that much of the data for terrain is implicit; each cell’s position is implied by its terrain coordinate. That means we don’t need to save its position in the file. Parts, on the other hand, are physically simulated, so their starting position needs to be recorded and updated during the simulation.

Alternatives to RLE

There are many alternate compression techniques. Variations of RLE are commonly used for applications where speed to compress and speed to decompress are more important than average compression ratio. For example, Snappy, Google’s compression/decompression library, does not aim for maximum compression, but very high speeds and reasonable compression. At its core, Snappy uses RLE, with a few other techniques layered on top to further improve compression and decompression.

But standard RLE is a good fit for ROBLOX, and one of the key reasons why terrain, despite its expanse, doesn’t slow down the user experience.