Frenchfaso

Algorithms I fell in love with

An interactive journey through my algorithmic memories

First love never dies

Once upon a time…

As a teenager in the late ’80s and early ’90s, I was deeply fascinated by computers. My buddies Toni and Dano were lucky enough to own the iconic C64. You hooked it up to a television and suddenly you were in control. You could paint and animate anything on the screen instead of passively watching the TV stream.

It was magical.

Unfortunately, I couldn’t convince my parents to get me a C64 because, as they put it, “Video games are a waste of time!” To be fair, they eventually got me a marvelous 486DX-33 with 4 MB of RAM and a powerful Cirrus Logic graphics card. This happened after I took a computer class at school. At the end of the course, we showed our parents a project: a robotic toy car that could (mostly…) follow a white line on the floor. It was connected to a PC through a parallel cable and programmed in QBASIC. My buddies did most of the work, having developed their coding superpowers on the C64. Nevertheless, that did the trick, and my parents were finally convinced that computers had more to offer than video games and wasted time. Back then, when home computers first made their way into our households, they were predominantly used for gaming. It took a while for them to be recognized as valuable work tools.

While I was eagerly waiting for my PC, Toni lent me his C64 (thank you, Toni!), so I practiced writing BASIC by working through the comprehensive manual that came with it. Dano had also moved on from his C64 and got his 486DX-33 earlier than I did (dammit!), so I spent some afternoons at his place, amazed by what this powerhouse could do. Then he showed me an image that made me feel as if I had been struck by lightning. It was the first computer-generated 3D image I had ever seen: a shiny sphere and a checkerboard plane reflecting each other in glorious 256 colors! He explained that he had used POV-Ray, a program that could render photorealistic images from a text file written in a special scene description language. The algorithm behind it was called ray tracing.

The first algorithm I fell in love with.

Ray tracing works backwards from the way we see the world. For each pixel, it casts a ray from the camera into the scene and finds the closest object it hits. The renderer then uses the object’s material and the scene’s lights to calculate the pixel’s color. Additional rays can test whether the point is in shadow or follow reflections, which is how the sphere and the checkerboard could mirror each other. The idea is elegant, but tracing all those rays was computationally expensive on a 486.

3D rendered image of a red shiny, reflective ball, floating over a green and blue checkerboard plane — The image that Dano showed me was very similar to this one (although this one was rendered with 3D Studio for DOS).

I was flabbergasted and wanted to use my computer to generate images like that. A couple of months later, with my 486 finally up and running, Dano brought me a copy of 3D Studio for DOS. It was a more sophisticated program for creating 3D images, with a powerful user interface and no need to learn a weird scene description language. Its renderer followed a scanline-based pipeline rather than POV-Ray’s ray-tracing approach.

I ran to the bookstore and bought a big 3D Studio book. My long journey through the amazing world of computers and algorithms had begun.

Plasma

But plasma is, by far, the most fun!

The plasma effect was one of the first demos I remember running on my 486 ‘DOS box’. Its speed and fluidity were astonishing on such limited hardware.

A common DOS implementation stored each pixel as an 8-bit index into a palette of 256 colors. Changing the VGA palette registers could animate the colors without rewriting the entire image. Fast lookup tables and integer arithmetic were often used to calculate the plasma field itself, so palette cycling was an important optimization, but not the whole story.

The implementation below uses modern JavaScript and the Canvas 2D API. For each logical pixel, it adds three sine waves: one horizontal, one vertical, and one based on the distance from the center. Their sum is normalized to an intensity and mapped through a fixed color palette. The waves change phase over time, creating motion without cycling the palette.

Every logical pixel is written to an RGBA ImageData buffer on each frame. To keep the work small and preserve the pixel-art look, the canvas is rendered at one quarter of the display width and height, then scaled up by the browser. For a logical canvas of W × H pixels, each frame takes O(W × H) time and the pixel buffer uses O(W × H) memory.

const canvas = document.querySelector("#effect-canvas");
const context = canvas.getContext("2d", { alpha: false });

const pixelScale = 4;
const paletteSize = 256;
const prefersReducedMotion = window.matchMedia(
  "(prefers-reduced-motion: reduce)",
).matches;

const hsvToRgb = (hue, saturation = 1, value = 1) => {
  const sector = (hue / 60) % 6;
  const chroma = value * saturation;
  const secondary = chroma * (1 - Math.abs((sector % 2) - 1));
  const offset = value - chroma;

  const [red, green, blue] = [
    [chroma, secondary, 0],
    [secondary, chroma, 0],
    [0, chroma, secondary],
    [0, secondary, chroma],
    [secondary, 0, chroma],
    [chroma, 0, secondary],
  ][Math.floor(sector)];

  return [red, green, blue].map((channel) =>
    Math.round((channel + offset) * 255),
  );
};

const palette = new Uint8ClampedArray(paletteSize * 3);

for (let index = 0; index < paletteSize; index += 1) {
  const [red, green, blue] = hsvToRgb((index / paletteSize) * 360);
  const offset = index * 3;

  palette[offset] = red;
  palette[offset + 1] = green;
  palette[offset + 2] = blue;
}

let width = 0;
let height = 0;
let frame;

const resize = () => {
  width = Math.max(1, Math.floor(window.innerWidth / pixelScale));
  height = Math.max(1, Math.floor(window.innerHeight / pixelScale));
  canvas.width = width;
  canvas.height = height;
  frame = context.createImageData(width, height);
};

const render = (timestamp = 0) => {
  const time = timestamp / 1000;
  const centerX = width / 2;
  const centerY = height / 2;
  const frequency = 0.075;
  const pixels = frame.data;

  for (let y = 0; y < height; y += 1) {
    for (let x = 0; x < width; x += 1) {
      const horizontal = Math.sin(x * frequency + time * 1.4);
      const vertical = Math.sin(y * frequency + time * 0.9);
      const radial = Math.sin(
        Math.hypot(x - centerX, y - centerY) * frequency - time * 1.2,
      );

      const intensity = Math.round(
        ((horizontal + vertical + radial + 3) / 6) * (paletteSize - 1),
      );
      const paletteOffset = intensity * 3;
      const pixelOffset = (x + y * width) * 4;

      pixels[pixelOffset] = palette[paletteOffset];
      pixels[pixelOffset + 1] = palette[paletteOffset + 1];
      pixels[pixelOffset + 2] = palette[paletteOffset + 2];
      pixels[pixelOffset + 3] = 255;
    }
  }

  context.putImageData(frame, 0, 0);

  if (!prefersReducedMotion) {
    window.requestAnimationFrame(render);
  }
};

window.addEventListener("resize", resize);
resize();
render();

Fire

Burn baby burn!

The fire effect was another DOS demo I remember vividly. In this case, too, the speed was extraordinary. How could my 33 MHz machine possibly run such a complex simulation?

It turns out that this is not a full fluid simulation. Each cell stores only an intensity, and the bottom row is continuously set to the hottest value. On every frame, each other cell is replaced by the average of its current intensity and that of the cell directly below it. A small amount is occasionally subtracted to cool the result. Repeating this local rule makes heat propagate upwards while random cooling breaks the smooth gradient into flickering vertical flames.

The deterministic averaging step is a two-point, convolution-like stencil. Because rows are processed from top to bottom, the cell below still contains its value from the previous frame when it is sampled. The complete update is not a linear convolution, however, because it also includes random cooling and a fixed heat source at the bottom. A 16-color palette converts the intensities from black through red and yellow to white.

As in the plasma demo, the effect is rendered on a low-resolution Canvas 2D buffer and scaled up. Updating a logical canvas of W × H cells takes O(W × H) time per frame and O(W × H) memory.

const canvas = document.querySelector("#effect-canvas");
const context = canvas.getContext("2d", { alpha: false });

const pixelScale = 4;
const paletteSize = 16;
const maximumIntensity = paletteSize - 1;
const coolingProbability = pixelScale / 20;
const prefersReducedMotion = window.matchMedia(
  "(prefers-reduced-motion: reduce)",
).matches;

const hsvToRgb = (hue, saturation, value) => {
  const normalizedSaturation = Math.max(0, Math.min(1, saturation));
  const normalizedValue = Math.max(0, Math.min(1, value));
  const sector = (hue / 60) % 6;
  const chroma = normalizedValue * normalizedSaturation;
  const secondary = chroma * (1 - Math.abs((sector % 2) - 1));
  const offset = normalizedValue - chroma;

  const [red, green, blue] = [
    [chroma, secondary, 0],
    [secondary, chroma, 0],
    [0, chroma, secondary],
    [0, secondary, chroma],
    [secondary, 0, chroma],
    [chroma, 0, secondary],
  ][Math.floor(sector)];

  return [red, green, blue].map((channel) =>
    Math.round((channel + offset) * 255),
  );
};

const palette = new Uint8ClampedArray(paletteSize * 3);

for (let index = 0; index < paletteSize; index += 1) {
  const hue = (index / paletteSize) * 65;
  const saturation = (300 - (index / paletteSize) * 300) / 100;
  const brightness = ((index / paletteSize) * 200) / 100;
  const [red, green, blue] = hsvToRgb(hue, saturation, brightness);
  const offset = index * 3;

  palette[offset] = red;
  palette[offset + 1] = green;
  palette[offset + 2] = blue;
}

let width = 0;
let height = 0;
let intensities;
let frame;

const resize = () => {
  width = Math.max(1, Math.floor(window.innerWidth / pixelScale));
  height = Math.max(1, Math.floor(window.innerHeight / pixelScale));
  canvas.width = width;
  canvas.height = height;
  intensities = new Float32Array(width * height);
  frame = context.createImageData(width, height);
};

const updateAndDraw = () => {
  const pixels = frame.data;

  for (let y = 0; y < height; y += 1) {
    for (let x = 0; x < width; x += 1) {
      const index = x + y * width;

      if (y === height - 1) {
        intensities[index] = maximumIntensity;
      } else {
        intensities[index] =
          (intensities[index] + intensities[index + width]) / 2;

        if (Math.random() < coolingProbability) {
          intensities[index] -= 1;
        }
      }

      const paletteIndex = Math.max(
        0,
        Math.min(maximumIntensity, Math.floor(intensities[index])),
      );
      const paletteOffset = paletteIndex * 3;
      const pixelOffset = index * 4;

      pixels[pixelOffset] = palette[paletteOffset];
      pixels[pixelOffset + 1] = palette[paletteOffset + 1];
      pixels[pixelOffset + 2] = palette[paletteOffset + 2];
      pixels[pixelOffset + 3] = 255;
    }
  }

  context.putImageData(frame, 0, 0);
};

const render = () => {
  updateAndDraw();

  if (!prefersReducedMotion) {
    window.requestAnimationFrame(render);
  }
};

window.addEventListener("resize", resize);
resize();
render();