This is an example of constructing and storing maps in a way that is efficient in terms of both bytes and tiles.
The map in this demo takes only 98 bytes and 26 tiles (not counting the player sprite). That's about 2.4% of the dedicated map space or 1.2% of the total map space. As implemented here, the decoding and map functions - the main things you'd actually need in a game - take 666 tokens. It's meant more as an example than a library, but it's usable as it is, and you're welcome to do so. There's plenty of room for optimization, but I didn't want to make it too hard to read.
The first points of interest are the encode() and decode() functions, which allow you to write and read arbitrary numbers of bits. These makes it trivial to serialize data with a minimum of waste.
local get=decode(0x2000) -- start reading data from 0x2000 local width=(get(4)+1)*16 -- get(4) reads 4 bits, i.e. 0-15, local height=(get(4)+1)*16 -- so (get(4)+1)*16 is 16, 32, 48, ..., 256 |
The map is made of of "objects." Each object has a type, a shape, and a rectangular bounding box.
The map is rectangular and divided into 8x8 tile sections, referred to here as "fragments." Dividing up the map this way reduces the storage needed for each object. If the map is 256 tiles wide, storing each object's X position would take a full byte per object. By dividing it into fragments 8 tiles wide, an object's X position takes just 3 bits. The tradeoff is a small (2 bits, in this case) end-of-fragment marker per fragment and a little more code.
Map data format:
map width: (4 bits +1)*16
map height: (4 bits +1)*16
background color: 4 bits
(width*2)*(height*2) fragments
A map fragment consists of any number of objects followed by an end-of-fragment marker. Format:
shape/eof: 2 bits (if 0, there are no more objects in this fragment; 1-3 indicates a shape)
type: 4 bits +1
x: 3 bits
y: 3 bits
width: 3 bits +1
height: 3 bits +1
That makes the total size of a map 12 bits + 8 bits per screen + 18 bits per object. This format can be adjusted easily; see the load_map() and read_fragment() functions for reading and the create_level() and write_objects() functions for writing.
An object's type definition simply specifies its draw function and base tile. The number stored is an array index.
object_types={
{ tile=0, draw=function() end },
{ tile=1, draw=draw_merge },
{ tile=6, draw=draw_merge },
{ tile=11, draw=draw_rect },
-- etc.
}
|
Giving object 1 a blank draw function is a handy trick: it allows object 1 to be used as an eraser. That is, it can be placed on top of other objects to erase parts of them, allowing you to create complex shapes with fewer objects and without adding more shape functions. One caveat, however: this doesn't always work right when an object extends beyond the boundary of the fragment it's placed in. Objects in later fragments will always appear on top of those in earlier ones.
The shape of an object determines which tiles in its bounding box it actually occupies:
The number stored identifies a function that takes a position in the rectangle and returns true or false, indicating whether that position should be filled.
As for tiles, there are a few different drawing functions here. One simply calls spr(), drawing a single tile as usual. The others divide tiles into 4x4 sub-tiles and construct larger tiles from those. While this is a bit more limited than using full 8x8 tiles, it means every possible edge and corner piece can be drawn with just five tiles.
There's nothing in this map besides background objects, mind. In a real game, you'd probably want to place enemies, items, etc. These can be encoded in a similar way, with a few bits each for the type and coordinates. You might put them after the map objects for each fragment, but it might make more sense to store them separately.
This is a pretty basic implementation of these concepts, and there are a number of ways it could be made more efficient. However, this is highly dependent on the specific game and maps. What's more efficient for large maps with lots of similar objects may be less efficient for smaller maps with fewer but more varied objects. There's always a tradeoff; saving a few bits in one area will require either using more elsewhere or adding more code. If you want to cram as much stuff as you can into a game, it's worth working out how to save as much space as possible. A couple of bits here and there can add up to a lot with hundreds of objects.
One of the simplest things to change is fragment size. In general, smaller fragments are better for maps with more objects. Comparing 8x8 and 16x16 fragments, 8x8 requires 6 more bits per screen (3 additional end-of-fragment markers), while 16x16 requires 2 more bits per object (coordinates are 0-15 instead of 0-7). Fragments don't have to be square; 8x16 or 32x4 will work just fine. They can also be different sizes on different maps.
Increasing the number of bits used for an object's size may or may not be a good idea. Increasing width and height by one bit each increases the maximum size to 16x16, but it also means using 2 more bits for every single object. If you've got a lot of large objects, it's probably worth it. But if most things are 8x8 or smaller, it would make more sense to use fewer bits and build larger objects from multiple smaller ones when needed.
Some other possible modifications for efficiency or different behavior:
- Tilesets - Use fewer bits for the object type, but with a different set of objects depending on the map.
- Meta-objects - Instead of placing rectangles directly in the map, use them to build more complex objects or screen layouts and place those in the map. Metroid is a very noticeable example of this.
- Variable-length encoding - You can save more space by using fewer bits for more common values. You can also use different numbers of bits depending on object type. For instance, wall and floor objects might use 4 bits for width and height, while flat platforms use 3 for width and none for height.
- Background and foreground layers - Each tile can have two objects and two draw functions. It may be worth flagging foreground objects that completely hide the background to avoid unnecessary drawing.
- Different tile sizes - If 8x8 pixel tiles don't work for you, it's pretty easy to make them bigger or smaller; just use pixel coordinates on the tile sheet instead of tile numbers in the object type definitions. Using flags becomes trickier, however.
- Different sub-tile sizes - For a game with a top-down perspective, where the front of an object is taller and the back is shorter, it might make sense to use different tile quadrant sizes. It's a simple change to make the corners and edges 4x5 pixels on the bottom and 4x3 on top.
This looks pretty good ... any chance of converting a string to map and back again using your compressor ?
With a few changes, sure. Here are modified versions of the serialization functions. encode() will ultimately output a string if called with no argument, and decode() will check if its argument is a number or a string.
They're a bit hastily put together and could probably use a little more work, to be honest, but they work well enough.
data_str="abcdefghijklmnopqrstuvwxyz1234567890`~!@#$%^&*()-_=+[{]}|;:',./?"
function decode(input)
local bit=0
local byte, advance
if type(input)=="number" then
advance=function()
bit=128
byte=peek(input)
input+=1
end
else
local char_vals={}
for i=1, 64 do
char_vals[sub(data_str, i, i)]=i-1
end
advance=function()
bit=32
byte=char_vals[sub(input, 1, 1)]
input=sub(input, 2)
end
end
return function(bits)
local ret=0
for i=1, bits do
bit/=2
if bit<1 then
advance()
end
ret*=2
if band(byte, bit)>0 then
ret+=1
end
end
return ret
end
end
function encode(addr)
local byte=0
local written, advance, ctr_max
if addr then -- assume number
written=0
ctr_max=8
advance=function()
poke(addr, byte)
addr+=1
written+=1
end
else
local chars={}
for i=1, 64 do
chars[i-1]=sub(data_str, i, i)
end
written=""
ctr_max=6
advance=function()
written=written..chars[byte]
end
end
local ctr=ctr_max
return function(num, bits)
if not num then
num=0
bits=ctr!=ctr_max and
ctr or
0
end
local bit=shl(1, bits)
for i=1, bits do
byte*=2
bit/=2
if band(num, bit)!=0 then
byte+=1
end
ctr-=1
if ctr==0 then
advance()
ctr=ctr_max
byte=0
end
end
return written
end
end
|
Saffith, I'm not seeing raw map data in your main program (now that I got the tabs out of it) :)
Are you drawing the map based on a series of recalled commands and instances or is this a true map compressor that saves the final decompressed results so the programmer need only use map() directly ?
Failing this, can you please decompress your sample map to map() as the same or separate cart so I can backtrack the compression you are using ?
There's no map data saved. This isn't compression of regular map data; it's a completely different way of encoding it. The map in the demo can't be loaded as map data, because it doesn't use regular tiles. It wouldn't take big changes to the code to make that happen, but you'd lose the ability to draw quarter tiles.
The map is defined by a list of objects in create_level(). That's called from _init(), then it's read back by load_map().
Well the reason I'm asking Saffith is ... that's going to be a big decider for people using this lib.
That they can actually see their maps get compressed and decompressed thissaways. If not, the novice or lazy might feel it's more trouble to figure out than just to use the onboard default Pico-8 map editor and not worry about compression.
Simplicity is always priority when it comes to writing useful utilities and libs for others to use in coding. Versatility and flexibility second.
It's not meant to be a library. It's meant to be an example to illustrate and explain the concepts. It's not super hard, but it does take some effort. Even doing the same thing with regular map data would require at least a separate map editor cart, which is a pretty big change in workflow for anyone using the built-in editor.
I like the functional style you went for - it's an elegant way to encode resetting the read state (e.g. at the end of a data 'chunk').
I'm using a procedural version with global state for doing similar bit encoding things & it does tend to litter the code with unrelated 'state=reset' lines at the end of loading routines.
I'm at a point where I'm not willing to change that code now, but I'll remember this for future projects, thanks.
(The map format seems neat too)
[Please log in to post a comment]
.png){kind=link}