Title: JavaScript Run-Length Encoding for Arcade Sprites
Slug: js-rle-run-length-encoding-for-arcade-sprites
Date: 2024-06-26 20:50:00
Author: Kartones
Lang: en
Tags: Game Dev, Development, Videogames, Javascript
og_image: https://images.kartones.net/posts/screenshots/rle_cli_output.png
Description: A JavaScript implementation of the RLE algorithm, applied to retro arcade game 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](https://blog.kartones.net/post/js-rle-algorithm-v2-sprite-tiles/)
3. [JavaScript RLE algorithm v3 - Bit-Level RLE](https://blog.kartones.net/post/js-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](https://en.wikipedia.org/wiki/Run-length_encoding). 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:

```javascript
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:

```javascript
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):

![Screenshot of the CLI output and partial ASCII representation of the raw image](https://images.kartones.net/posts/screenshots/rle_cli_output.png)

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.

![Screenshot of the html comparison of input and generated images](https://images.kartones.net/posts/screenshots/rle_screenshot.png)

I've uploaded all the code and sample input images to [my JavaScript assorted GitHub repository](https://github.com/Kartones/JSAssorted), 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.