::

Hull Breach

HullBreach was developed in the Globalgamejam2020 by me and Alberto, one friend of mine that always do game jams with me.

The theme of the jam was "Repair" and we choose to use Pico8 as our game engine for the jam.

The core gameplay is pretty simple, but the adventure in making it is pretty interesting and quite a challenge.

The Sketch

After the jam theme announcement (which was Repair) we started to sketch out ideas on what kind of game to make. Those were plenty: a coop tetris-puzzle-builder, a cyborg brawler multiplayer, a motherboard repair simulator, and other. All those ideas were decent but not fully satisfying to us. Then we stumbled on an idea about managing the repair of a spaceship where each one of its pixel was simulated. That sounded instantly the right idea and we started right away.

So, the main design consisted in a spaceship going somewhere in space escaping from some sort of bad guy that is shooting lasers at you while you go through an area full of asteroids. The ship can self-repair from the damage by creating healing drones from its core, but you have to tell the drones which materials (colors of the pixel) they have to repair.

The Jam started Friday around 18:00 and in the early hours of Saturday morning (around 6am) we already had the final design of the spaceship, a damage system where you could click to create a hole in the shell, and an early version of the repairing bots to fix the damaged pixels.

The code was pretty brutal and rough but working, and that was fine for a jam… Fine until we hit the Pico8 memory and CPU limitation so hard that we couldn't add more cool feature because of that. It was time for some optimization.

I spent almost the entire Saturday trying to find a way to compress and rearrange all the main data structure into a smaller and more performing one.

NB: This is not a guide on "The perfect way to handle data" or anything like that. I just wanted to document my thought process during a game jam. There are way less complicated way to design data structures better than this, but I found this journey very interesting and a cool learning experience.

First Iteration

The first iteration was a 128x128 array containing data for each pixel on the screen. The pixel needed to hold its position, color, status, and a flag for the bot spawn point. This alone was:

• 128 width x 128 height = 16'384 cells
• 16384 cells x 5 numbers = 81'920 numbers
• 81920 numbers x 4 byte = 327'680 bytes

(I could have used true/false instead of 0 and 1 for flags, but that wouldn't have changed much because in this stage of design those wasn't really only 2 states flags)

320 Kb for the raw data inside a single structure is way too much for pico to handle.

Another big problem was that in order to draw each pixel the cpu was cycling every cell and calling PSET to draw a pixel on screen, and that was really taxing on the CPU time.

Second Iteration

The first improvement of that was to move the 2d array into a single array with only the point needed to draw the ship, so the number of cells dropped from 16'384 to somewhere around 5'000. That was really good for the drawing performance, but had a big drawback: single point checking for specific X and Y.

In fact, with the 2D array it was really easy to get the information of a single point knowing its coordinates because the time to get that information was really small and constant, no cycling needed.

On the other hand, having a 1D array of non-sorted points was exponentially slower since you needed to cycle all the point until you find some point with its coordinates equals to the one you needed.

The single point access was pretty much crucial to us since we wanted to add A-star pathfinding algorithm for the repair bots and for other things inside the game.

Third Iteration

We had to somehow get back at a 2D data structure design, but we had to forget the standard way of doing it.

After some research on the Pico8 memory layout I found out that it manage its memory in two way: the variables allocated in the code while the game is running uses a special Lua memory which is limited to around 2MB; but there is also the cart RAM which is used by all the cart assets (sprite, map layout, sfx, music, etc). This last one can be used to store extra arbitrary data.

So I started to layout some of the memory I needed to move it there while trying to compressing it into the smallest space I could.

Pico8 default integer size is 32 bit long: 16bit for the integer part and 16 for the floating one.

That's pretty huge in memory if you only need small integer numbers. The numbers I needed theoretically were:

• 1 bit integers for true/false flags
• 4 bit integers to store the color value of a pixel (numbers from 0 to 15)

So, knowing that the single memory registers in Pico8 are 1 byte long (8 bit), I could "easily" compress 1 color value (4 bit) and 4 boolean flags into a single 1 byte register.

I put quotes on easily, because it really wasn't so easy since it was the first time I was trying to do something like that. The ideal layout was indeed pretty straightforward, but I had to make some custom getters and setters to use from Pico8 to be able to store/read that compressed number to/from memory. That required some bit-wise logic and operations.

After some fiddling with that, around 5pm, it was ready. The memory usage dropped significantly to "only":

• 128 width x 128 width = 16'384 cells
• 16'384 cells = 16'384 bytes

From 327'680 to 16'384 bytes is not a bad improvement, but we could do better than that. In fact, even if it was an huge improvement, it moved from the Lua memory to the Pico8 cartridge memory, and that gave some issues.

The cartridge memory layout is this:

• 0x0000 to 0x0fff — Sprite sheet (0-127)
• 0x1000 to 0x1fff — Sprite sheet (128-255) / Map (rows 32-63) (shared)
• 0x2000 to 0x2fff — Map (rows 0-31)
• 0x3000 to 0x30ff — Sprite flags
• 0x3100 to 0x31ff — Music
• 0x3200 to 0x42ff — Sound effects
• 0x4300 to 0x5dff — General use (or work RAM)
• 0x5e00 to 0x5eff — Persistent cart data (64 numbers = 256 bytes)
• 0x5f00 to 0x5f3f — Draw state
• 0x5f40 to 0x5f7f — Hardware state
• 0x5f80 to 0x5fff — GPIO pins (128 bytes)
• 0x6000 to 0x7fff — Screen data (8k)

As you can see the whole pico8 memory is 32kb and it's shared between important cartridge data like sprite information, music, sounds, etc. We currently have 16k to fill in somewhere and the "General use memory" is only 6kb, so I needed to override some sprite sheet memory and map data to make it fit in. One minor problem was that even overriding sprite data I had to "jump" music and SFX memory to make it fit.

So I decided to use all the 11kb from 0 to 0x2fff and from 0x4300 to 0x5dff. It was very ugly but it worked.

Fourth Iteration

Then, suddently after the saturday dinner break, I realized one thing: I was trying to manage all the colors for each pixel on the spaceship sprite by myself, but Pico8 already does that for its spritesheet in the 0x0000 - 0x1fff memory space!

I felt particularly dumb. Pico stores that information by using 1 byte for 2 pixels since the color information is only 4 bits and the memory registers are 8 bit long. That was better than what I was trying to do, so I start thinking if I could cut down that information and only store my extra data (3 boolean flags).

I realized that we could cut down one flag by changing the code slightly, so with only 2 boolean per pixel I could store 4 pixel into a single byte by using each bit as an individual flag.

Leftmost 4 bits are for flag A and rightmost 4 bits are for flag B Example:

• 0000 0000 => all flags are false
• 1000 1000 => first pixel has flag A and B true, other 3 pixels has both flags on false
• 0100 1100 => flag A is set for second pixel, flag B is set for first and second pixels

This way I could squeeze all my information like:

• 128 width x 128 width = 16'384 cells
• 16'384 cells / 4 cells for bytes = 4'096 bytes

With only 4kb I could fit that into the General use memory space with no need of overriding important data!

In conclusion, after doing all this madness (the real pain was coding the getters and setters for those bit flags, but I'll not go into those details here since this post is already quite long) we were able to have both single point direct access to data AND we can create an array of memory pointers to focus down only important data.

Conclusion

With all this in place we finished the rest of the game on Sunday. The final game was "ok". We had fun making it, it's cool to watch, but the gameplay could be better.

Overall, it was a great event and is always nice to be part of it. Everyone interested in games should try that to push their limits and learn bunch of new things in an unique experience!