The jam’s Snakyval is done, but I am working on better version. Interesting times are ahead. New mechanics, new levels, more fun. But how to cram it into 32 kB together with code, graphics, sounds, music?

Current state of affairs

When I made Snakyval for the jam, I put most levels in 20 minutes few hours before deadline. I had used PICO-8’s fantastic map editor to lay 15 levels into map memory. The map memory of PICO-8 is quite limited. See the specs:

• Upper half of the map space is 128 tiles wide, 32 tiles high, making it 4096 tiles, or 4 kB of memory.
• Below it is lower half, that weighs another 128×32 tiles, but, you have to give up half of sprite sheet as this part of memory is shared.
• You have 64 kB for code, but it gets compressed and then it must fit 15360 B for the cart PNG.

Let’s suppose you have 16×14 levels (only 14 rows, because upper and lower rows are used for level name, score, hints). You can cram it into the space:

• As is. That is 8 levels in a row, 2 rows of levels (and 128×4 tiles below them remain for tutorials schematics etc.). 16 levels total. This is our baseline from the jam.
• Using lower half as well, limiting the spritesheet. That would yield another 16 levels, amounting to 32 levels total.
• Each level has a walled border. If I stored only exit positions (four low numbers) somewhere else, I could tile world with 14×12 tiles rectangles, amounting to 9×2 (18) levels in case of using upper half only and 9×5 (45) levels in case of using both halves. I could also store exits in the world too, as there are 2 free columns and 4 free rows.

These are options that are still somehow sensible with editor. But I want 60 levels (at least) and I want to use upper half of the world only, as I want more sprites to have varied environments. I must be somewhat smarter. Let’s enter the word of bit manipulation and compression.

Bit manipulation

I can omit the walls around level, as there will always be walls with 4 exits whose locations I can just store somewhere. There remains 14×12 tiles, that is 168 tiles total. Each tile takes a byte, but I am not going to put 256 different sprites into the level. Instead, I can shrink it to few distinct tiles, and let the game fill in tile variants, themes etc. When enumerating planned mechanics and needed tiles, I have ended up with 8 distinct tiles. This means that I can do with 3 bits per tile, leading to 504 bits total. That is 63 bytes.

The encoding is simple - I take a group of 8 tiles, make it 24 bits and store it in 3 bytes; rinse and repeat for entire level. Then I have to put these bytes in the cart’s map somehow. This means I now have to make proper level editor for the game. But overall, encoding is not a problem, it is quite simple algorithm with some bit manipulation. Some goes with decoding - I take 3 bytes, extract their 24 bits into 8 tiles and place these somewhere else in the memory - when the PICO-8 cart is running, I can designate some other part of memory for map data. Ok, this approach is viable, it just requires some tool to make and encode levels, but that is easy to make.

The question is - Can I cram in more data? The answer is - Yes, I can.

Compression

Let me introduce you to variable length encoding. Compare frequencies of tiles in levels. Empty space is very frequent, followed by walls. Masks are extremely rare. So, instead of using 3 bits for each tile type, use less bits for more frequent tiles and more bits for rarer tiles. Imagine this:

• 0 = empty
• 10 = wall
• 1100 = …
• 1101 = …
• 11100 = …
• 11101 = …
• 11110 = …
• 11111 = …

When compressing the level, I feed the bits into a queue; when there are enough bits in the queue, I write a byte. Similar thing happens when reading the level. In PICO-8 the algorithm is simple, but one must take care of bit operations, especially the right bit shifting as it is not trimming bits below ones place because PICO-8 uses fixed point arithmetic, hence 1 >>> 1 is 0.5 and not a zero.

I counted that with this encoding empty level takes 24 bytes, with a few walls and a mask I may get 40 bytes in average. Which means I could cram 100 levels into the map space.

I could take even more aggressive approach with run length encoding, but I have decided that 100 levels is enough (and probably not an expected amount in a final game).

The place

The problem is that I need map space for rendering the extracted level. I could write a custom renderer, but I don’t want to waste precious Lua tokens on this. Luckily for us, PICO-8 offers more memory space that can be designated for map rendering. While the upper map rests in cartridge from 0x2000 address up, there is 0x8000 that is available in runtime and map rendering can be redirected there with a few pokes into PICO-8 configuration variables. I can even set map’s width to 16 tiles.

The tool

Another thing is that I have to put the compressed levels in the game’s cartridge somehow. And here lies the true genius of PICO-8 designers - the cartridges can read and write each other. While they can’t access other cartridge’s code (it is protected), they can access spritesheets, maps, sounds and music tracks. Which means I can make a cartridge that reads and writes the map part of another cartridge.

This way, a level editor for Snakyval has been born.

First version just used simple controls to set tiles in levels, but during few more hours I have developed it into a quite capable application that can even use a mouse and it can shuffle levels and show number of bytes taken when compressed (simply counting tiles by type is enough to achieve this). I also tried to mimic the PICO-8’s editor itself.

This way, I have a tool that I can use to make levels for my game. It is quite a game changer (pun intended), it is even more comfortable to use than the generic PICO-8’s editor was during the jam. I have quickly recreated the original set of 15 levels. It weighs 423 bytes in my encoding, so my guesstimate was a bit pessimistic (but because base levels cover base mechanics, it is better to have pessimistic estimates). Compare it with 15×14×16 = 3360 bytes of original storage.

Every game should have its editor as a base to determine good storage formats and to prepare content to work with. This might not be much of a case for games that don’t need to do a lot of specific magic with data and given universal tools are enough for it. But whenever something more complex has to be done, having a good specialized editor is a must. From this point, I can experiment with puzzle designs easily and move on to make a good level theming.

What’s next?

I am going to have quite a hectic week, so there will be no write-up next weekend. But on Sunday February 9th there is going to be a technical article on use of PICO-8 palettes and various environments I am putting levels in.

As for the release date, I am not ready to announce anything cast in concrete yet, but stay tuned.

Thankssss!