✮ Divalogical ✮

pico8 map compression: how to squeeze in just one more level...

why would i want to store my map data as a string?

with only 64 rows and 128 columns the PICO8 fantasy console does not have space for the multilevel minigame of your dreams by default :( luckily with some clever tricks we can get just a little more bang for our buck by fighting the character limit, rather than the token limit or the default map editor size ( yay! :D )

turning the map into a string

there are many ways to serialize (turn to a string) data. some are easier to read than others. for example, you could store each tile as:

"x_location = [X_POS], y_location = [Y_POS], sprite = [SNUM]"

but this takes up a lot of room. instead we could do "x[X_POS],y[Y_POS],sp[SNUM]", but this still takes up a lot of characters. what we want ideally is the shortest possible string that encodes the data we need. our data consists of 3 numbers, X_POS, Y_POS, and SNUM which are integers in the ranges [0,127], [0,63], and [0,t-1] where t is the number of distinct map tiles you have. how many characters can we squeeze this into?

firstly we need to answer the question of: how many characters do we have? in the case of decimal numbers we have 10 characters. represent these as hex and we have 16. for "safe" lua strings, we have 95 characters available. the first 32 characters are dedicated to things like newline and eof characters, which we want to avoid since they easily become problematic. it may be possible to use some of these but I haven't tried that. so we will say at least 95 characters for now, unless you would want to exclude '[' and ']' to make the string properly safe rather than "safe". but "safe" is good enough and it gives us more chars to encode with.

secondly, we can figure out how many we need. if we have k characters we can store any value at most 95^(k-1). so with X_POS being in [0,127] we need to know the smallest k such that 127 isn't larger than 95^(k-1). this is ceil(log_95(127)+1)=2. since Y_POS has only 64 values and 64 is smaller than 95 we can represent its y position with just one character. depending on how many distinct map tiles you want to represent SNUM might need a varying number of chars, but you can probably keep it to under 95.

so now we write a function to convert a number to a sequence of k characters:

function enc95(n,k)
	r=''
	for i=1,k do
		r=chr(32+(n%95))..r
		n=flr(n/95)
	end
	return r
end

this is a fixed length encoding. if k is too small it will not work correctly. how it works is at every iteration of the for loop, we take the remainder of n / 95 and convert that to a "safe" character (hence the +32). then we actually divide n by 95, before repeating the process. if we imagined the same thing in decimal format we would divide by 10 in order to move the digits over, and take the remainder to see what that digit was. we are doing the exact same thing but with 95 instead of 10.

this gets us to every map tile (of which there are 128x64=8192) being stored with 4 characters coming to a total of 4 x 8192 = 32,768 characters. you can save space by ommitting empty tiles, and then instead of storing 8192 tiles it will be however many non-empty tiles your map actually uses. for my case, a platformer with a lot of freedom of movement, the map was serializable (turn-to-a-string-able) in less than 10k characters

so we need to write our entire map down using this encoding function. we can do that as follows:

function serialize_map()
	s=''
	for x=0,127 do
		for y=0,63 do
			if mget(x,y) ~= 0 then
				s=s..enc95(x,2)..enc95(y,1)..enc95(mget(x,y),1)
			end
		end
	end
	prtinh('_map=[=['..s..']=]','map',1)
end
			

since we already know each tile is 4 characters we dont need a delimiter to seperate them. the printh() function allows us to save the string to a file _map.p8l that we can import later. in the future you'll want to have this flattened into your cartridge so it will just be a nasty string in your code. regardlessly, we need a way to read this string back into our map. this means we need a way to get a number back from its string encoding:

function dec95(s)
	n=0
	for i=1,#s do
		c=sub(s,-i,-i)
		b=ord(c)-32
		n+=b*(95^(i-1))
	end
	return n
end