Ilan Bernstein

How did this problem arise?

My team at a hackathon came up with the idea of creating a snapchat clone, but instead of sending pictures back and forth, you would send one pixel of a 10x10 grid. We called this app Canvas. There were a lot of moving parts to this app, most of which were shoddily implemented for the hackathon. After the hackathon let out (we got 2nd!), we decided to continue working on this project (which we soon abandoned). During this time, we reimplemented the entire app from the ground up, and an interesting problem arose: how should we store the Canvas?

Some notes before we begin

In the real app, each pixel could be one of twenty colors and the grid was 10x10 pixels. For this article, I’ve decided to keep the 20 colors, but cut down the grid to 5x5 pixels (just for simplicity’s sake).

The example grid we will try to store

The Original Idea

The first idea we had was to store each pixel as a string representing its color, and then store each of those strings within a 2d array.

const canvas = [
  [ "white", "white", "white", "white", "white" ],
  [ "white", "green", "white", "green", "white" ],
  [ "white", "white", "white", "white", "white" ],
  [ "white", "blue", "blue", "blue", "white" ],
  [ "white", "white", "white", "white", "white" ]
];

This seemed intuitive, yet it led to a very unexpected and strenuous debugging session. This was our code (slightly edited for readability) we made to create the initial Canvas.

const canvas = new Array(5);

canvas.fill(Array(5).fill("white"));

Now, lets try to set a pixel to the correct color:

canvas[1][1] = "green";

And finally, let’s see a render of our canvas!

What??? How did that happen??? Shocking isn’t it (unless you already know what’s going on here). Let’s break down the code a little more.

const canvas = new Array(5);
const row = new Array(5);
row.fill("white");
canvas.fill(row)

Do you see it yet? If not, I’m going to spoil it for you. When you run canvas.fill(row) the entire canvas is filled with pointers to just one row object. Now you might be asking, why doesn’t the same apply for the "white" string? That’s because "white" is a primitive while row is an object! Aren’t computers fun?

Anyways, let’s see the solution:

const canvas = new Array(5);
for (let i = 0; i < 5; i++) {
  canvas[i] = new Array(5).fill("white");
}

Here, we create a new row object each time instead of reusing the same object for each space in our array.

The next idea

Now I’ll preface this idea by saying I’m not very proud of it. This idea was the starting point of the solution we chose though, so I’ll include it as a chapter in this story anyways.

We decided to store our pixels as objects in an array: numbers for x and y and a string for color.

const canvas = [
  {
    x: 0,
    y: 0,
    color: "white"
  },
  {
    x: 1,
    y: 3,
    color: "blue"
  },
  // ...
];

This solution worked, but it was not space efficient by any means. On top of that, if we wanted to edit a pixel we had to do this:

canvas.find(pixel => pixel.x === 1 && pixel.y === 1).color = "green";

This was a pain to work with, so we reverted to storing our pixels just as colors, but dropped the 2d array.

const canvas = [
  "white", "white", "white", "white", "white",
  "white", "green", "white", "green", "white",
  "white", "white", "white", "white", "white",
  "white", "blue", "blue", "blue", "white",
  "white", "white", "white", "white", "white"
];

I included line-breaks here to improve readability, but all of these colors are in the same array.

And to edit our canvas all we had to do was:

const x = 1;
const y = 1;
canvas[x + (y * 5)] = "green";

Pushing it

How far could we push this though? Our next idea was to use Node.js’s Buffer instead of a normal Array. At first, we thought of storing colors by their hex value, but later decided to store them using a palette instead. For example, white could be 0x00, green could be 0x01, and blue could be 0x02.

function createBlankCanvasBuffer() {
  // you can also use allocUnsafe here!
  let buffer = Buffer.alloc(5 * 5);
  buffer.fill(0x00);
  return buffer;
}

function writePixelToCanvasBuffer(buffer, x, y, color) {
  // mutates the Buffer directly
  buffer.writeUint8(color, x + (y * 5));
}

Now to try out our code:

const canvas = createBlankCanvasBuffer();
writePixelToCanvasBuffer(canvas, 1, 1, 0x01);

Perfect! Now we can store an entire 5x5 grid using just 25 bytes!

Ending thoughts

I have no code for this section, but I do have just one more idea. We decided not to implement this since it would’ve taken more space than the code above, but its still an intriguing way to approach this problem. Our next idea was to record “actions” instead of the entire grid.

A series of “actions”

Anyhoo, I hope that was a fun exploration, and I hope you learned something too!

Have a good one,
Ilan Bernstein