FLOOD FILL the paint bucket, and its missing father
Click a region; it fills. Flood fill spreads a colour outward through every same-coloured neighbour until it hits a different colour — the paint-bucket tool, and the same traversal as BFS/DFS on a grid. Its recursion runs in I-13; its real frontier is a stack of coordinate pairs, which presses the array-of-pairs the box has begun to name.
THE TECHNIQUE spread while the colour matches
Read the seed’s colour. Recolour it, then move to each neighbour (N,E,S,W — 4-connected) and do the same wherever the colour still matches. A stack gives a depth-first tendril, a queue a breadth-first ring — same region either way. Click any cell to flood its region. live demo
click a region to flood it
HISTORY & CREDIT a tool with no clear author
Widely credited to Alvy Ray Smith — who wrote something the same adjacent (tint fill), not the plain paint bucket, which has no confirmed first author. cited
~1973–76 · Dick Shoup’s SuperPaint at Xerox PARC (the first frame-buffer paint system) has an auto-fill — the leading guess for the earliest fill routine, never cleanly credited as “first.” 1978 · Henry Lieberman (MIT) publishes an area fill (“How to Color in a Coloring Book,” SIGGRAPH) — before Smith’s paper. 1979 · Alvy Ray Smith (NYIT) publishes “Tint Fill” — an anti-aliased soft fill that keeps a pixel’s value while retinting, an ancestor of alpha compositing. A refinement, not the invention. 1990 · Paul Heckbert’s span-stack scanline seed fill (Graphics Gems) is the version most “scanline flood fill” code silently copies.
The famous online “history of flood fill” blurb is actually Andrew Glassner’s 2001 column — not Smith’s paper. no single father
RECOMMEND FOR I-13 recursion runs; the frontier wants pairs
The recursive fill is recursion + an indexed array — both of which I-13 has. A 1-D flood runs on the real compiler (fill the contiguous run from a seed, stop at the boundary):
$ i13 run flood.i13 # recurse while the cell equals the old colour
out[0] = 9 out[2] = 9 out[3] = 0 # the run of 1s filled to 9, stopped at the 0
Recommend: the recursion + array is a no-wall. The real 2-D flood, though, keeps an explicit stack (or queue) of coordinate PAIRS — and the efficient scanline form pushes span records (4-tuples). That is the array-of-pairs the suggestion box began naming with FFT and Pascal (a relative of PS-014): a bounded array whose elements are small tuples, not scalars. The naive recursive form also overflows a real call stack on big regions — where I-13’s 4096-frame ceiling (E0503) would fire, exactly the honest boundary the language declares. Note: flood fill is BFS/DFS on a grid and is single-component connected-component labelling — three names, one traversal.