JavaScript Run-Length Encoding for Arcade Sprites

This is the first post in my series about Run-Length Encoding (RLE) compression:

1. JavaScript Run-Length Encoding for Arcade Sprites
2. JavaScript RLE algorithm v2 - Sprite Tiles
3. JavaScript RLE algorithm v3 - Bit-Level RLE

A few days ago, I had an idea related to retro Arcade sprites, but to try it, first I needed to implement the Run-length encoding algorithm. It is as simple as grabbing how many times in sequence each color repeats, and storing the color and the number of repetitions (instead of each color occurrence).

Let me directly show a JavaScript implementation:

export function rleEncode(input) {
  let result = [];
  let count = 1;

  for (let i = 0; i < input.length; i++) {
    if (input[i] === input[i + 1]) {
      count++;
    } else {
      result.push(count);
      result.push(input[i]);
      count = 1;
    }
  }

  return result;
}

And the decoding is the opposite: read each color, and how many times it repeats, and "expand" to that number:

export function rleDecode(input) {
  let result = [];

  for (let i = 0; i < input.length; i += 2) {
    let count = input[i];
    result = result.concat(new Array(count).fill(input[i + 1]));
  }

  return result;
}

Lossless, not very useful for images with plenty of colors or dithering patterns, but for retro games very handy, as at minimum you'd save the transparent color bytes of game sprites.

I first read a game sprite from a .png image, and convert it into a raw pair of a colors palette plus the image converted to a mere list of palette color indexes. The palette keeps the RGBA components, and always puts (0,0,0,0) (transparent) as the first value (common practice back in the day).

Once we have the palette + raw image, I output the size (not counting the palette), RLE-encode it, and print the compressed value. In my tests I'm getting around a 32% decrease in size, with a single pose of a full sprite (cropped to the minimum size, not aligned to any tile size).

Now, to ensure that I did it well, I output in ASCII [1] the raw image (before encoding):

But, it would be way better if we also generate back a PNG, decoding the encoding, right?

I RLE-decode the encoded image, and write back a PNG with a different name. I have a simple index.html file that just shows both images side by side (disabling blurring and smoothing, to compare the pixels), and via manual visual inspection we can confirm that they are the same.

I've uploaded all the code and sample input images to my JavaScript assorted GitHub repository, inside the rle/v1 folder.

In the next post, I'll write about the real experiment: exploring if chunking the sprite into tiles and reordering them can yield better compression results.

[1] It works good with palettes of up to 16 colors, which is precisely the number of colors that many Capcom CPS games used to draw a given sprite. Both my examples have exactly 16 colors.