01 / The idea
Light whole cells in a straight line.
A pixel-art editor’s line tool takes two cells, A where you pressed and B where you let go, and fills the cells between them. There is no gray to hide a wobble, so the choice of cells is the whole job. On a 32 × 20 sprite, a line from (2, 3) to (29, 12) needs 28 cells, one in every column.
The first idea is school algebra: for each x, work out y = mx + b and round it. That needs a division for the slope, and it lights one cell per column, so a steep line gets gaps. From (4, 0) to (7, 9) it lights 4 cells over 10 rows.
Bresenham’s line algorithm walks from A to B one cell at a time, carrying a whole-number error term that says when to step across, up or down, or both. No division, no fractions, and every cell stays within half a cell of the true line.
Watch it on three lines: the steep one rounded, a shallow one with its error term, and a steep one going up and to the left.
Whole cells, one step at a time.
Rounded: 0 cells
lit by the loop rounded y true line
rounding
For each x from 4 to 7, work out y on the true line and round it.
Reduced motion: choose a scene to see its completed state.
Read this scene
For each x from 4 to 7, work out y on the true line and round it.
Round each x. For each x from 4 to 7, work out y on the true line and round it.
Watch and Step through replay three lines. Try it runs the same TypeScript on a 32 × 20 grid with ends you drag, next to your browser’s own canvas stroke.
In each column of a shallow line, the loop lights the cell nearest the true line; in a steep line, the nearest in each row. The caption shows err at each cell and the test that chose the next step.
02 / Name the rule
Carry the error, not the slope.
The loop needs three things, all worked out from the two ends:
The run
The columns to cross, and minus the rows to cover. sx and sy, each 1 or −1, say which way to go.
The error term
Starts at dx + dy. It scores the diagonal neighbor against the true line, scaled up so it stays a whole number.
Two tests
At least dy: step x and add dy. At most dx: step y and add dx. Both: a diagonal step.
Every update is an addition: 2·err is err + err, and each step adds dy or dx. Nothing is divided, so nothing is rounded and nothing drifts.
One fact holds at every cell. After u steps across and v steps up or down, err = dx × (v + 1) − |dy| × (u + 1). The two tests are the half-cell rule written with that number: step across only if the cell stays within half a cell of the true line, and the same for up or down. A shallow line passes the x test at every cell, so it lights one cell per column. A steep line passes the y test every time, one per row. That is why a line always has max(|dx|, |dy|) + 1 cells, both ends included.
Written for shallow lines only, you would need another copy with x and y swapped for steep lines, and mirrored copies for lines going left or up. This form doesn’t. sx and sy carry the direction, and for a steep line the y test passes every time while the x test passes now and then. All eight directions are one loop.
Halfway goes toward BWhy A to B and B to A can differ
Sometimes the true line passes exactly halfway between two cells. Both are equally close, and one has to win. Here a test that comes out equal still takes the step, so a halfway cell leans toward B.
From (0, 0) to (4, 1), the line is at y = 0.5 when x = 2, and the loop lights (2, 1).
Drawn from (4, 1) back to (0, 0), it lights (2, 0). A line with no exact halfway point
lights the same cells in both directions. Both test suites check both directions of every
generated line. When both directions must agree, put the ends in a fixed order first; strokeLine uses reading order.
Flat, upright, diagonal, one cellThe lines that look like edge cases
A horizontal line has dy = 0, so err starts at dx: 2·err is at least 0 and above dx, so every step is x only. A vertical line is the mirror, with dx = 0 and every step y only. An exact diagonal starts at err = 0, passes both tests at every cell, and err never changes. When A and B are the same cell, the loop lights it once and stops: 1 cell.
03 / Read the shape
One loop, two tests, whole numbers.
Basic form is the whole algorithm: the checks, roundEachColumn (the first idea, kept for comparison), and lineCells with its error term. In the wild is strokeLine, a pixel-art editor’s stroke that
puts its ends in reading order first. At the call site measures the lab’s shallow
and steep lines, prints the halfway line both ways, erases a stroke by dragging back over it,
and prints one refused line. Both languages print the same seven lines.
The whole algorithm: the checks, roundEachColumn (the first idea, kept for comparison), and lineCells with its error term.
export type Cell = { x: number; y: number };
export type Grid = { width: number; height: number };
export type LineErrorCode = 'bad-grid' | 'bad-ink' | 'not-integer' | 'off-grid';
export const MAX_SIDE = 4096;
export class LineError extends Error {
readonly code: LineErrorCode;
constructor(code: LineErrorCode, message: string) {
super(message);
this.name = 'LineError';
this.code = code;
}
}
function check(grid: Grid, from: Cell, to: Cell) {
for (const side of [grid.width, grid.height]) {
if (!Number.isInteger(side) || side < 1 || side > MAX_SIDE)
throw new LineError('bad-grid', `grid sides must be whole numbers from 1 to ${MAX_SIDE}`);
}
for (const cell of [from, to]) {
if (!Number.isInteger(cell.x) || !Number.isInteger(cell.y))
throw new LineError('not-integer', `(${cell.x}, ${cell.y}) is not a whole cell`);
if (cell.x < 0 || cell.y < 0 || cell.x >= grid.width || cell.y >= grid.height)
throw new LineError(
'off-grid',
`(${cell.x}, ${cell.y}) is outside the ${grid.width}×${grid.height} grid`
);
}
}
// The first idea: round y = mx + b for each x. It divides, and a steep line leaves gaps.
export function roundEachColumn(grid: Grid, from: Cell, to: Cell): Cell[] {
check(grid, from, to);
const sx = from.x < to.x ? 1 : -1;
const cells: Cell[] = [];
for (let x = from.x; ; x += sx) {
let y = from.y;
if (to.x !== from.x) y += ((to.y - from.y) * (x - from.x)) / (to.x - from.x);
cells.push({ x, y: Math.floor(y + 0.5) });
if (x === to.x) return cells;
}
}
// Every cell from `from` to `to`, both ends included, in drawing order. Whole numbers only.
export function lineCells(grid: Grid, from: Cell, to: Cell): Cell[] {
check(grid, from, to);
const dx = Math.abs(to.x - from.x);
const dy = Math.min(to.y - from.y, from.y - to.y); // minus the rows to cover
const sx = from.x < to.x ? 1 : -1;
const sy = from.y < to.y ? 1 : -1;
let { x, y } = from;
// How far the diagonal neighbor is from the true line, scaled up to a whole number.
let err = dx + dy;
const cells: Cell[] = [];
for (;;) {
cells.push({ x, y });
if (x === to.x && y === to.y) return cells;
const twice = err + err;
if (twice >= dy) {
err += dy; // a step across stays within half a cell of the line
x += sx;
}
if (twice <= dx) {
err += dx; // so does a step up or down
y += sy;
}
}
}const MaxSide = 4096
type Cell struct{ X, Y int }
type Grid struct{ Width, Height int }
type LineError struct{ Code, Message string }
func (e *LineError) Error() string { return e.Message }
func check(grid Grid, from, to Cell) error {
for _, side := range []int{grid.Width, grid.Height} {
if side < 1 || side > MaxSide {
return &LineError{"bad-grid", fmt.Sprintf("grid sides must be whole numbers from 1 to %d", MaxSide)}
}
}
for _, c := range []Cell{from, to} {
if c.X < 0 || c.Y < 0 || c.X >= grid.Width || c.Y >= grid.Height {
return &LineError{"off-grid", fmt.Sprintf("(%d, %d) is outside the %d×%d grid", c.X, c.Y, grid.Width, grid.Height)}
}
}
return nil
}
func abs(n int) int {
if n < 0 {
return -n
}
return n
}
func toward(from, to int) int {
if from < to {
return 1
}
return -1
}
// RoundEachColumn is the first idea: round y = mx + b for each x. It divides, and a steep
// line leaves gaps.
func RoundEachColumn(grid Grid, from, to Cell) ([]Cell, error) {
if err := check(grid, from, to); err != nil {
return nil, err
}
sx := toward(from.X, to.X)
cells := []Cell{}
for x := from.X; ; x += sx {
y := float64(from.Y)
if to.X != from.X {
y += float64((to.Y-from.Y)*(x-from.X)) / float64(to.X-from.X)
}
cells = append(cells, Cell{x, int(math.Floor(y + 0.5))})
if x == to.X {
return cells, nil
}
}
}
// LineCells returns every cell from `from` to `to`, both ends included, in drawing order.
func LineCells(grid Grid, from, to Cell) ([]Cell, error) {
if err := check(grid, from, to); err != nil {
return nil, err
}
dx, sx := abs(to.X-from.X), toward(from.X, to.X)
dy, sy := -abs(to.Y-from.Y), toward(from.Y, to.Y) // dy is minus the rows to cover
x, y := from.X, from.Y
// How far the diagonal neighbor is from the true line, scaled up to a whole number.
miss := dx + dy
cells := []Cell{}
for {
cells = append(cells, Cell{x, y})
if x == to.X && y == to.Y {
return cells, nil
}
twice := miss + miss
if twice >= dy {
miss += dy // a step across stays within half a cell of the line
x += sx
}
if twice <= dx {
miss += dx // so does a step up or down
y += sy
}
}
}Reading the TypeScriptNumbers that must be whole
Coordinates are plain numbers, so check refuses an end that Number.isInteger rejects with not-integer. dy is Math.min(to.y - from.y, from.y - to.y) rather than a negated Math.abs, so a flat line’s dy is 0, not −0, and the traced numbers match
Go’s.
traceLine runs the same loop and records err and the chosen step at every
cell; the animation and the lab draw from it. Errors are a LineError whose code matches the Go version.
Reading the Goint, miss, and image/draw
Go’s int can’t hold half a cell, so Go has no not-integer error; those cases run in TypeScript only. The error term is called miss, because err is what Go code calls an error.
The standard library won’t draw the line for you. The package comment of image/draw says “Package draw provides image composition functions,” and
its Image is “an image.Image with a Set method to change a single pixel.”
Painting LineCells into an image is one Set call per cell.
What is refusedGrids, ends, pictures, and ink
A grid is 1 to 4,096 cells on each side (bad-grid). Each end must be whole
(not-integer, TypeScript only) and inside the grid (off-grid),
checked for A and then for B. strokeLine’s picture is 1 to 4,096 rows of
the same width in printable ASCII (bad-grid), and its ink is one printable
character (bad-ink), both checked before the ends.
Both languages run the same cases from cases.json and 500 generated lines each.
They check the count, both ends, one king’s move between cells, the half-cell rule with halfway
cells leaning toward B, the err formula, and that drawing backwards changes cells exactly
when the line has a halfway point.
04 / Try a decision
Why did one pixel stay?
An eraser that runs the same loop over the same two cells should remove the line. Here it didn’t.
05 / Follow the cost
One step per cell, nothing to remember.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Check the ends | O(1) | O(1) | Two grid sides and two cells, before anything is drawn. |
| Light a line | O(n) | O(1) extra | n = max(|dx|, |dy|) + 1 cells. Two comparisons and at most two additions per cell; the list of n cells is the output. |
| Trace a line | O(n) | O(n) | The same loop, keeping err and the chosen step for every cell. |
| Round each column | O(|dx| + 1) | O(|dx| + 1) | One division per column, and too few cells when the line is steep. |
| Stroke a picture | O(w × h) | O(w × h) | strokeLine checks and copies the whole picture, which costs more than the line itself. |
| Paint into ImageData | O(n) | O(n) | The canvas snippet writes 4 bytes per cell in place; its only extra memory is the list of cells. |
The loop runs once per cell it lights and keeps a few whole numbers however long the line is: x, y, err, dx, dy, sx, and sy. On the lab’s 32 × 20 grid, no line is longer than 32 cells.
What costs more is what you draw into. strokeLine copies a picture of rows to
keep its input unchanged, so the copy dominates. The canvas snippet’s paintLine writes the cells straight into ImageData; its previewLine copies the
saved pixels back first, so each preview costs one copy of the picture.
What it doesn’t doSmooth edges, thickness, and collisions
It doesn’t anti-alias. Every cell is on or off, which is the point in pixel art and a staircase anywhere else. Shading edge pixels by how much the line covers them is a different job, anti-aliasing; Xiaolin Wu’s 1991 paper “An efficient antialiasing technique” is one published approach.
It has one thickness: one cell. A thicker brush needs more than this loop, such as stamping a shape at every cell.
It isn’t a collision test. From (0, 0) to (1, 1) it lights just those two cells, so a line of sight slips between walls at (1, 0) and (0, 1) that touch at a corner. A character that moves in four directions, like the one in the A* lesson, can’t get through there. If your game forbids that, also check the two side cells of every diagonal step.
06 / Give it a real job
A line tool that previews as you drag.
A pixel-art editor’s line tool shows the line while you drag. Every pointer move redraws it from A to the cell under the pointer, on top of the picture as it was when you pressed, and letting go keeps it. Each redraw copies the saved picture back, then lights at most 32 cells on our sprite.
An eraser is the same tool painting the background. In the wild’s strokeLine sorts the ends first, so an eraser dragged back over a line removes
all of it. In the lab, choose Halfway tie, press All cells, then Swap A and B: the lit cells stay, the two
that change shift, and the status line counts them.
Build UIs?The canvas draws smooth lines for you. Whole pixels are yours to set.
Where it already is in your components
Not as whole pixels. A canvas stroke covers an area, and the browser shades the pixels
it only partly covers. MDN’s canvas tutorial explains the gray outline from the top of this page, makes a vertical line crisp by moving
its path to pixel centers, and adds: “This phenomenon of partially filled pixels also extends
to shapes that don’t align to the pixel grid.” A slanted line is one of those shapes. The
lab draws your line with lineTo beside the cells, so you can see what your browser
does with it.
Two canvas settings sound like fixes. MDN describes imageSmoothingEnabled as the switch that “determines whether scaled images are smoothed,” which is about images. image-rendering: pixelated scales an element “with the "nearest neighbor" or similar algorithm,” so a small canvas stays
blocky when CSS enlarges it. Neither chooses which pixels a line lights. Use them for the
picture and set the line’s pixels yourself.
When you have to own it
Keep the picture in ImageData at its real size and let CSS enlarge the
canvas. On pointerdown, save the pixels and note A with pixelAt. On each
pointermove, previewLine starts from the saved pixels, paints the line to the
pixel under the pointer, and puts the result on the canvas. On pointerup, read the canvas
back as the new saved pixels.
Give the canvas touch-action: none, which will “Disable browser handling of all panning and zooming gestures,” so a
finger drawing a line doesn’t scroll the page instead.
import { lineCells, type Cell } from '../lines'; // this lesson's own function
export type RGBA = readonly [number, number, number, number];
// The canvas pixel under the pointer, whatever size CSS shows the canvas at. The box includes any CSS
// border or padding, so keep those off the canvas. Call setPointerCapture on pointerdown so a drag
// that leaves the canvas keeps previewing.
export function pixelAt(
event: { clientX: number; clientY: number },
canvas: HTMLCanvasElement
): Cell | null {
const box = canvas.getBoundingClientRect();
const x = Math.floor(((event.clientX - box.left) / box.width) * canvas.width);
const y = Math.floor(((event.clientY - box.top) / box.height) * canvas.height);
return x >= 0 && y >= 0 && x < canvas.width && y < canvas.height ? { x, y } : null;
}
// Set whole pixels from one end to the other. No stroke, so no partly covered pixels.
export function paintLine(image: ImageData, from: Cell, to: Cell, color: RGBA): number {
// Reading order first, as strokeLine does, so an eraser dragged back removes exactly this line.
const [a, b] = to.y < from.y || (to.y === from.y && to.x < from.x) ? [to, from] : [from, to];
const cells = lineCells({ width: image.width, height: image.height }, a, b);
for (const { x, y } of cells) image.data.set(color, (y * image.width + x) * 4);
return cells.length;
}
// On each pointermove: start again from the pixels saved at pointerdown, add the line, show it.
export function previewLine(
context: CanvasRenderingContext2D,
saved: ImageData,
from: Cell,
to: Cell,
color: RGBA
) {
const image = context.createImageData(saved.width, saved.height);
image.data.set(saved.data);
paintLine(image, from, to, color);
context.putImageData(image, 0, 0);
}
Nothing here belongs to React or Svelte. Attach the handlers with onpointerdown and friends in Svelte, or onPointerDown in React,
with a ref to the canvas. Its test drives a fake context and checks that exactly the line’s
pixels change, in either direction, and that the saved pixels stay untouched.
07 / Make the call
Whole cells: this loop. Smooth lines: a stroke.
Use this loop whenever the output is a grid of whole cells: a pixel-art tool, an LED matrix, a character-cell display, or a tile map where the cells between two points matter. Put the ends in a fixed order whenever two directions must agree.
Use the canvas’s own lineTo and stroke when smooth is what you want:
charts, diagrams, handwriting. And when a line must not slip between two cells that touch at a
corner, add the side-cell check or use a different test.
The algorithm is named for J. E. Bresenham, whose 1965 paper in the IBM Systems Journal is titled “Algorithm for computer control of a digital plotter.”
SourcesDocumentation, source, and bibliographic records, checked 14 September 2026
- MDN, Drawing shapes with canvas, “Seeing blurry edges?”: the 1-wide
strokeRectthat is “not only 2 pixels wide instead of 1, but also appears gray rather than the default black,” paths through pixel centers, and “This phenomenon of partially filled pixels also extends to shapes that don’t align to the pixel grid.” - MDN:
imageSmoothingEnabled,image-rendering, andtouch-action. - Go 1.24.0,
image/draw/draw.go: the package comment and theImageinterface. Its exported functions areDrawandDrawMask. - J. E. Bresenham, “Algorithm for computer control of a digital plotter”, IBM Systems Journal 4(1), 1965, 25–30 (Crossref record).
- Xiaolin Wu, “An efficient antialiasing technique”, ACM SIGGRAPH Computer Graphics 25(4), 1991, 143–152 (Crossref record).
08 / Take the idea with you
Explain the line without saying “Bresenham.”
“Walk from one end to the other, one square at a time. Keep a running score of how far off the true line the next square would be. Step sideways, down, or both, whichever stays closest. You never divide and never round; you only add.”
Before moving on, open the lab, choose Halfway tie, press All cells, and predict which two cells change before you press Swap A and B.
Connections to follow nextRelated lessons
- Floyd–Steinberg dithering also carries an error forward pixel by pixel, deciding black or white instead of which row.
- Ramer–Douglas–Peucker keeps a few points of a long stroke; the straight segments between them are the lines a tool like this one draws.
- A* pathfinding moves in four directions, which is why a diagonal line of sight isn’t a route there.