Voxel Data Compression

[redpepperdoc2006 (PETPWER)]

Introduction
Hello! Recently, I started a Voxel Sandbox game! I want to make Bandwidth Optimizations to my code. The chunks that are generated on the server are sent to the client. I’ve made many optimizations to my code like making each part of a coordinate into having its own table.

Code

for x = 1,16 do
	grid[x] = {}
	for z = 1,16 do
		local height = 32 + math.floor((math.noise(x/16, z/16) * 4) + 0.5)
		grid[x][z] = {}

		for y = 1,height do
			local cave = math.noise(x/16, y/16, z/16)

			if cave >= -0.2 then
				if y == height then
					grid[x][z][y] = 1
				elseif y >= height - 3 and y <= height - 1 then
					grid[x][z][y] = 2
				elseif y >= 2 and y <= height - 4 then
					grid[x][z][y] = 3
				end
			end

			if y == 1 then
				grid[x][z][y] = 4
			end
		end
	end
end

Yet this is practical for my game with chunks with the size of about 16 32 16, which is about 16.25KB when encoded in JSON, anything higher will cause freeze-ups due to the 50KB bandwidth limitation Roblox currently has. Currently, I’ve made a way to compress data that makes it go from 16.25KB usage to just under 2 KB without caves.

How does it work?
Every loop, it checks if the block ID is different than the previous block, if so, it will save the lowest Y coordinate of the block ID’s, overall compressing data down. If a Y cord is over one block above the previous, it will put a block ID of 0 (Air block) in the lowest spot possible, allowing caves, trees, and other things. It will also add an Air block to the highest point of the slice in the chunk, fixing a bug that would cause a table overflow error.

Code

local compressedgrid = {}

for x, grid2 in pairs(grid) do
	compressedgrid[x] = {}
	for z, grid2 in pairs(grid2) do
		compressedgrid[x][z] = {}
		local LowestSimilarBlockColor = nil
		
		for y, color in pairs(grid2) do
			
			-- Finds if the next y cord is not a similar color
			-- If it is not a similar color, it will change to the next color
			if LowestSimilarBlockColor ~= color then
				LowestSimilarBlockColor = color
				compressedgrid[x][z][y] = color
			end
			
			-- Finds air blocks and adds a air block to the code to make decompression not have an table overflow error
			if grid[x][z][y + 1] == nil then
				compressedgrid[x][z][y + 1] = 0
			end
		end
	end
end

This, however, makes the data unusable to render. So after the data is sent to the client, the client decompresses the data by looping up until it finds another block. If it finds another block with a block ID of 0, it will not add it to the decompressed data table.

Code

local decompressedgrid = {}

for x, grid in pairs(compressedgrid) do
	decompressedgrid[x] = {}
	for z, grid in pairs(grid) do
		decompressedgrid[x][z] = {}

		for y, color in pairs(grid) do
			-- Checks if the y cord block put is not an air block
			if color > 0 then
				local Currenty = y
				local Endit = false

				decompressedgrid[x][z][Currenty] = color
				
				repeat
					Currenty += 1
					
					-- Finds if next given block is not nil to end loop
					if compressedgrid[x][z][Currenty] ~= nil then
						Endit = true
					end
					
					-- Adds a block to the data
					if not Endit then
						decompressedgrid[x][z][Currenty] = color
					end
				until Endit
			end

		end
	end
end

Bugs
While this sounds great, there are a few bugs. Sometimes, there will be a void in the uncompressed Voxel data, and others, not add the block.

Complete source of the code

local grid = {}

-- This creates the chunk data table
for x = 1,16 do
	grid[x] = {}
	for z = 1,16 do
		local height = 32 + math.floor((math.noise(x/16, z/16) * 4) + 0.5)
		grid[x][z] = {}

		for y = 1,height do
			local cave = math.noise(x/16, y/16, z/16)

			if cave >= -0.2 then
				if y == height then
					grid[x][z][y] = 1
				elseif y >= height - 3 and y <= height - 1 then
					grid[x][z][y] = 2
				elseif y >= 2 and y <= height - 4 then
					grid[x][z][y] = 3
				end
			end

			if y == 1 then
				grid[x][z][y] = 4
			end
		end
	end
end

local compressedgrid = {}

for x, grid2 in pairs(grid) do
	compressedgrid[x] = {}
	for z, grid2 in pairs(grid2) do
		compressedgrid[x][z] = {}
		local LowestSimilarBlockColor = nil

		for y, color in pairs(grid2) do

			-- Finds if the next y cord is not a similar color
			-- If it is not a similar color, it will change to the next color
			if LowestSimilarBlockColor ~= color then
				LowestSimilarBlockColor = color
				compressedgrid[x][z][y] = color
			end

			-- Finds air blocks and adds a air block to the code to make decompression not have table overflow error
			if grid[x][z][y + 1] == nil then
				compressedgrid[x][z][y + 1] = 0
			end
		end
	end
end

local decompressedgrid = {}

for x, grid in pairs(compressedgrid) do
	decompressedgrid[x] = {}
	for z, grid in pairs(grid) do
		decompressedgrid[x][z] = {}

		for y, color in pairs(grid) do
			-- Checks if the y cord block put is not an air block
			if color > 0 then
				local Currenty = y
				local Endit = false

				decompressedgrid[x][z][Currenty] = color

				repeat
					Currenty += 1

					-- Finds if next given block is not nil to end loop
					if compressedgrid[x][z][Currenty] ~= nil then
						Endit = true
					end

					-- Adds a block to the data
					if not Endit then
						decompressedgrid[x][z][Currenty] = color
					end
				until Endit
			end

		end
	end
end

-- This generates a chunk with no sort of compression algorithm
for x, grid in pairs(grid) do
	for z, grid in pairs(grid) do
		for y, color in pairs(grid) do
			local p = Instance.new("Part", workspace)
			p.Size = Vector3.new(3,3,3)
			p.Position = Vector3.new(x * 3, y * 3, z * 3)
			p.Anchored = true

			if color == 1 then
				p.Color = Color3.fromRGB(0,200,0)
			elseif color == 2 then
				p.Color = Color3.fromRGB(120, 60, 0)
			elseif color == 3 then
				p.Color = Color3.fromRGB(150,150,150)
			elseif color == 4 then
				p.Color = Color3.fromRGB(100,100,100)
			end
		end
	end
end

-- This uses the Decompressed data table to generate the chunk
for x, grid in pairs(decompressedgrid) do
	for z, grid in pairs(grid) do
		for y, color in pairs(grid) do
			local p = Instance.new("Part", workspace)
			p.Size = Vector3.new(3,3,3)
			p.Position = Vector3.new((x - 32) * 3, y * 3, z * 3)
			p.Anchored = true

			if color == 1 then
				p.Color = Color3.fromRGB(0,200,0)
			elseif color == 2 then
				p.Color = Color3.fromRGB(120, 60, 0)
			elseif color == 3 then
				p.Color = Color3.fromRGB(150,150,150)
			elseif color == 4 then
				p.Color = Color3.fromRGB(100,100,100)
			end
		end
	end
end

Does anyone know why that’s the case, and if so, is there a fix? If not, does anyone have any other ways to compress data? Thank you for your time to read my page and for your assistance!

[Prototrode (Vernumerator)]

That’s a pretty unconventional way of data compression for voxels, which only makes it harder to understand and troubleshoot. Have you looked into greedymeshing? It’s a trivial form of optimization for any voxel-based game.

I coincidentally also have some experience with voxel games, and I have a post explaining my approach to data compression:

Procedurally generated voxel world

So it’s been a month now, and I thought it would be cool for me to showcase some of the changes since then. I’ve been working on it every now and then whenever I felt like it. Some significant changes include a compression system for world replication. Each chunk looks something like this which is sent via remotes to all clients: C1 and C2 are the actual block data. CP and CVP are just pointers telling the algorithm how to decompress it. As of now, only replication is compressed. …

Note that there’s also an open-source demo for the greedymesher in that thread, albeit it assumes that all regular voxels are of the same type

[redpepperdoc2006 (PETPWER)]

Sorry about the lack of clarity but the code above is a demo of my attempt to further compress Voxel data. I have tried to make a form of Greedy meshing for my game, but I had a hard time trying making it with player building and other things that can periodically modify a chunk. I may come back to this to have another attempt at solving this issue. The system I currently use checks if a voxel is covered on all sides, if so, it will not be made. This so far has made the game extremely fast and responsive and is even faster with the code at the start of the post. Many other optimizations have been put in place. As of now, I am experiencing no issues in terms of performance, even in lower-end devices. The only time I have issues with performance is when chunks contain data that surpasses the 50 KB Bandwidth limit.

With the compression algorithm you sent, I have tried to make a system to support Base 93, but with my lack of knowledge with bit32, I was unable to do so. While on my search for how to make a Base 93 algorithm, I came across this post and tried putting them together, but I was unable to get them working together. Is there any post or anything to help me understand?

Thank you for trying to help out, it is greatly appreciated!

[Prototrode (Vernumerator)]

This is the exact base93 module that I used. I didn’t make it, it’s pulled from some other module that I’ve lost the source to (it looks similar to the resource you shared ), originally given by a friend.

local dictionary = {}
do
	local length = 0
	for i = 32, 255 do
		if i ~= 34 and i ~= 92 then
			local c = string.char(i)
			dictionary[c], dictionary[length] = length, c
			length += 1
		end
	end
end

local escapemap = {}
local t = {34, 92, 127}
for i = 1, 34 do
	i = t[i - 31] or i
	local c, e = string.char(i), string.char(i + 31)
	escapemap[c], escapemap[e] = e, c
end

local b93Cache = {}
local function tobase93(n: number): number
	local value = b93Cache[n]
	if value then
		return value
	end

	value = ""
	repeat
		local remainder = n % 93
		value = dictionary[remainder] .. value
		n = (n - remainder) / 93
	until n == 0

	b93Cache[n] = value
	return value
end

local b10Cache = {}
local function tobase10(value: string): number
	local n = b10Cache[value]
	if n then
		return n
	end

	n = 0
	for i = 1, #value do
		n = n + 93 ^ (i - 1) * dictionary[string.sub(value, -i, -i)]
	end

	b10Cache[value] = n
	return n
end

local module = {
	tobase10 = tobase10,
	tobase93 = tobase93,
}

return module

The only function you should focus on is tobase93, which is used for indexing the LZW lookup table as I stated in that post. If it wasn’t clear yet on how to use it, you give it a regular base10 number and it returns a number in base93. For example, the number 69 becomes g.

[redpepperdoc2006 (PETPWER)]

When trying the code, the one you sent worked, for some reason, the other one would give an attempt to compare nil with number error. But with testing, the code at the start of the post was more performant than the one stated. I tried messing with it by base93ing the numbers in the code, JSON Encoding it, and more. But I was only able to go all the way down to about 2.9x more usage. Is there anything I’m doing wrong?

Here is the code

local dictionary = {}
do
	local length = 0
	for i = 32, 255 do
		if i ~= 34 and i ~= 92 then
			local c = string.char(i)
			dictionary[c], dictionary[length] = length, c
			length += 1
		end
	end
end

local b93Cache = {}
local function tobase93(n: number): number
	local value = b93Cache[n]
	if value then
		return value
	end

	value = ""
	repeat
		local remainder = n % 93
		value = dictionary[remainder] .. value
		n = (n - remainder) / 93
	until n == 0

	b93Cache[n] = value
	return value
end

local b10Cache = {}
local function tobase10(value: string): number
	local n = b10Cache[value]
	if n then
		return n
	end
	
	n = 0
	for i = 1, #value do
		n = n + 93 ^ (i - 1) * dictionary[string.sub(value, -i, -i)]
	end

	b10Cache[value] = n
	return n
end

local chunkQuadrantSize = 8



local encode: {[Vector3]: string} = {}
local decode: {[string]: Vector3} = {}
local lzwID: number = 0 --counter actually starts at 1

for x = 1,16 do
	for y = 1,64 do
		for z = 1,16 do
			lzwID += 1
			local hex: string = tobase93(lzwID)
			if lzwID < 93 then
				hex = [[\]]..hex --makes sure that each voxel takes up *exactly* 2 characters
			end
			local voxel: Vector3 = Vector3.new(x, y, z)
			encode[voxel] = hex
			decode[hex] = voxel
		end
	end
end

local uncompressedgrid = {}
local compressedgrid = {}

for x = 1,16 do
	local xe = [[\]]..tobase93(x)
	compressedgrid[xe] = {}
	uncompressedgrid[x] = {}
	
	for z = 1,16 do
		local ze = [[\]]..tobase93(z)
		compressedgrid[xe][ze] = {}
		uncompressedgrid[x][z] = {}
		
		for y = 1,64 do
			local ye = [[\]]..tobase93(y)
			local ide = [[\]]..tobase93(1)
			compressedgrid[xe][ze][ye] = ide
			uncompressedgrid[x][z][y] = 1
		end
	end
end

-- Gave it delays so than I can get accurate data for usage
wait(15)

-- My attempt to compress the data using base32
game.ReplicatedStorage.RemoteEvent:FireAllClients(compressedgrid)

wait(10)

-- My original code
game.ReplicatedStorage.RemoteEvent:FireAllClients(game:GetService("HttpService"):JSONEncode(uncompressedgrid))

wait(10)

-- The original code
game.ReplicatedStorage.RemoteEvent:FireAllClients(encode)

[Prototrode (Vernumerator)]

I used base93 in conjunction with LZW compression, tbh I don’t know what you’re doing here. It seems that you’re trying to use the base93 characters as the index for the world matrix, also not sure why you’re appending backslash to everything. I used base93 solely for LZW, only append the backslash as a filler character to make the string length consistent, and the world matrix is still stored/indexed with good ol’ base10.

[redpepperdoc2006 (PETPWER)]

I was able to mess with it a bit more and was able to shave off about 5-7% compared to my original with the conjunction of base 93, LZW, and handling of data. Thank you for helping me compress it more!