Will Thimbleby

Stepping through code in the browser is very cool, but it can already be done with a bit of work by enabling developer mode on your browser and writing your own .html and .js files.

What you can’t do is go back in time.

Which leads me to Tailspin. It is a fully reversible, standards-compliant¹, meta-circular Javascript interpreter. As well as running in the browser and allowing algorithms to be visualised, it can run code both forwards and backwards.

A reversible interpreter provides some really interesting opportunities for exploration and education. So far I have focused on algorithm visualisation where reversibility makes it possible to scrub through the execution of algorithms. This is not just fun, it transforms the experience of understanding the algorithm. You can see this used to great effect in the Algorithm Wiki and in the depth-first traversal example below. The code that is highlighted on the left-hand side is the actual code that is running.

All the visualisations on the Algorithm Wiki have been updated and support reversible execution. You can now scrub through algorithms such as Factorial, Insertion Sort or Fisher-Yates Shuffle.

I have also updated the in-browser IDE to support reversibility, so you can step backward through your own code. Even after your code has hit an exception or ended, you can step backwards into the code to see what happened.

I just rescued this from the handy Wayback Machine. It spells out some of my thinking at that point about UI design and it calls me an “Interface Master” which doesn’t hurt.

Apple PR

After spending a while looking for a decent scanline flood fill algorithm and not finding one, I built my own. The above interactive example shows how both scanline and simple flood filling work. You can draw and test any of the four different flood fills to see how they compare. Once you have filled an area, clicking and holding the “Show pixels tested” button shows a “heat” map of the number of times each pixel has been tested (from green:1 to red:8).

The scanline flood fill algorithm works by scanning a line, and adding ranges on the next/previous lines to a stack. For a shape with no loops or thin walls which are filled on both sides the scanline algorithm will only test each pixel once. It achieves this by skipping testing the range of pixels that the current line was filled from.

A rough outline of the algorithm is:

1. Add the starting range [x, y] to a stack.
2. While there is a range to fill:
   1. Extend the current range left and right.
   2. Add new ranges on the previous and next lines that overlap the current range to the stack. Skip testing the range of pixels that the current range was created from.

This implementation is nice, clean, fast and supports 8-way (diagonal) filling. All the values needed are passed in as parameters to floodFillScanline. The test(x, y) function returns true for pixels that need filling, the paint(x, y) function paints the pixel. This function will fill all connected pixels starting from (x, y) as long as test and paint are defined over x:[0, width) and y:[0, height) and a painted pixel does not test true.

function floodFillScanline(x, y, width, height, diagonal, test, paint) {
    // xMin, xMax, y, down[true] / up[false], extendLeft, extendRight
    var ranges = [[x, x, y, null, true, true]];
    paint(x, y);

    while(ranges.length) {
        var r = ranges.pop();
        var down = r[3] === true;
        var up =   r[3] === false;

        // extendLeft
        var minX = r[0];
        var y = r[2];
        if(r[4]) {
            while(minX>0 && test(minX-1, y)) {
                minX–;
                paint(minX, y);
            }
        }
        var maxX = r[1];
        // extendRight
        if(r[5]) {
            while(maxX0) minX–;
            if(maxXr[1])) && test(x, newY);
                if(!inRange && empty) {
                    rMinX = x;
                    inRange = true;
                }
                else if(inRange && !empty) {
                    ranges.push([rMinX, x-1, newY, downwards, rMinX==minX, false]);
                    inRange = false;
                }
                if(inRange) {
                    paint(x, newY);
                }
                // skip
                if(!isNext && x==r[0]) {
                    x = r[1];
                }
            }
            if(inRange) {
                ranges.push([rMinX, x-1, newY, downwards, rMinX==minX, true]);
            }
        }

        if(y0)
            addNextLine(y-1, !down, false);
    }
}