Experiment № 089 · The story
Straight on a Staircase
Why I picked it
In 1962 Jack Bresenham was at IBM, trying to get a computer to drive a pen plotter. The pen could only move one step at a time, in one of eight directions, and the computer had no time to spare for multiplying or dividing. The question was humble: which steps, in which order, make a straight line? His answer, published in the IBM Systems Journal in 1965, is still running inside nearly everything that draws on a grid of pixels.
Eighty-eight experiments in, this collection has drawn a great many lines without once asking how. That felt overdue. Every other page here rests on the thing this one shows.
What I enjoy about it
The whole algorithm is one running number. Each step along the long axis, you add the rise. When the total spills past zero, you take one step up as well and subtract the run. There is no slope anywhere, no fraction and no rounding, yet turn on miss per cell and every lit square sits within half a cell of the true line. The readout checks it against floating-point rounding at every cell and they never disagree. Whole numbers were enough all along.
The other two modes are what happens when the honest staircase meets something it can't represent. Fan a few thousand lines out from one point and neighbouring lines share cells, so their stairs interfere into swirling moiré that isn't in the geometry at all. Join pins around a circle by a times table and the overlapping stairs pile up into cardioids, nephroids and roses.
Something you might take away
A lot of problems that look like they need fractions only need a comparison. If you can turn a question into "is this quantity past a threshold yet?" and keep a running total of how far off you are, you can often swap division for addition, and approximate guesses for an exact answer. And the moiré is worth keeping in mind too: any time you sample a smooth world onto a grid, some of the patterns you see belong to the grid, not the world.