Sunday, April 6, 2014

JavaScript Chaos with Canvas

I learned about chaos theory quite by accident. On a family vacation we stopped by a campground along the Blue Ridge Parkway in the Appalachian Mountains. I was not an outdoor enthusiast at the time so while my parents were hiking I preferred to head over to the arcade to play Donkey Kong and Tempest. One rainy day even the video games were boring so I sauntered over to the main cabin and started leafing through their modest library of books. In between westerns and romance novels I glimpsed a book with the intriguing title Chaos: Making a New Scienceand ended up reading it from cover to cover.

To put things in perspective, this was not the 2008 edition with a fancy new cover. This was the original 1987 edition and the copy I grabbed was only a year old. What I loved about the book was the fact it didn’t just cover various aspects of chaos theory but also shared the actual equations and algorithms used to generate the various fractals and graphics. At the time I had a graphing calculator and was able to program most of the examples.

The beauty of chaos is that most functions are iterative and the fact that “period 3 implies chaos” means some very simple equations can provide impressive results. Take, for example, the bifurcation diagram. The equation it is based on is simple:

f(x1) = R * x0 * (1 – x0)

That is, to get the next value for x, subtract the previous value from 1, multiply by itself and a factor called “R.” R is a sort of arbitrary constant that relates to environment. Presumably lower R means lower resources and higher R means higher resources. If you plot across values of R, what you find is that in many cases the population does what you might expect and stabilizes at a certain value. For higher R, things get interesting. The population can explode, causing over-crowding and therefore starvation resulting in a drop that then grows, etc. and fluctuates between two levels. As R approaches 4, things get even more interesting and it ends up with a seemingly random spread of values. However, within the increasing values you can find little bands or breaks in the pattern where the population stabilizes to a single value again. If you were to blow up those regions you’d find they look very similar to the overall graph, a feature referred to as self-similarity.

The addition of the canvas tag also makes it easy to play with these equations in the browser. Working with a canvas is straightforward. Define it in your HTML and reference it in your JavaScript. Grab a context – in this case I’m using a 2-dimensional context – and use the context to draw. Here’s some definitions for the iterator function.

var c = document.getElementById("c"),
        ctx = c.getContext("2d"),
        w = c.width,
        h = c.height,
        st = 2 / w,
        fx = function (x1, r) {
            return r * x1 * (1 - x1);
        },
        it = function (r) {
            var idx = 0,
                x = 0.5,
                xc = w * ((r - 2) / 2);
            while (idx++ < 2000) {
                x = fx(x, r);
                ctx.fillRect(xc, h - (x * h), 1, 1);
            }
        };

Note I’m figuring out how many pixels I can use to step over R values but otherwise I’m just running through the iterator function and plotting 1 x 1 rectangles. Next, I set the fill style then iterate over R and use the timeout function to queue up the rendering without blocking too much of the UI thread:

ctx.fillStyle = "rgba(32,64,128,0.05)";
    for (r = 2; r < 4; r += st) {
        (function (r1) {
            setTimeout(function () {
                it(r1);
            }, 0);
        })(r);
    }

This short amount of code produces an amazingly intricate graph, as you can see here:

Another example I love for its simplicity is called “the chaos game” and generates what is referred to as Sierpinski’s gasket. The game is simple. I pick three starting points that help bound/define my shape. Then I pick a random point we’ll call the “game point.” In each “turn” of the game, I roll a 3-sided die and determine which one of the starting points I’m going to use. I calculate a point halfway between the game point and the base point I picked, and that becomes the new game point. That’s it – each turn is picking one of three base points, traveling halfway to that point from an arbitrary spot, then plotting it. Here I define a the initial points (you can see they form a sort of triangle), generate my game point, provide some helper functions for getting a random number and plotting a point, and create my iterator function that will run 10,000 times.

var c = document.getElementById("c"),
        ctx = c.getContext("2d"),
        w = c.width,
        h = c.height,
        rfn = function(b) { return Math.random() * b; },
        px = [0, w/2, w],
        py = [0, h, h/2],
        gx = rfn(w),
        gy = rfn(h),
        pl = function(x, y) { ctx.fillRect(x, y, 1, 1); },
        iter = 0;
        i = function() {
            pl(gx, gy);
            pt = Math.floor(rfn(3));
            gx = (gx + px[pt])/2;
            gy = (gy + py[pt])/2;
            if (++iter < 10000) {
                setTimeout(i, 0);
            }
        };

To kick things off I set the fill style then call the iterator function. The result is amazing.

These are just a few of the simple yet elegant ways JavaScript can chart the mysterious terrains of chaos theory. I also consider this a metaphor for just how far the web has come. I still remember writing these routines in C++ on my old IBM PC and waiting for 20 minutes while the bifurcation diagram rendered on an 800 x 600 display. It is amazing how fast JavaScript is able to crunch these numbers and the browser is able to render the graphics in mere seconds. Computing power and the web have certainly come a long way. 25 years later, I still get excited about chaos theory and am reminded of why I fell in love with programming in the first place: it only takes minutes to take an abstract idea like a mathematical formula and use code to turn it into a tangible, discernable image on your display. That, in my book, is magic.

If you want to learn more magic, check out Jeff Prosise’s lesson on the HTML5 Canvas API. Use promo code LIKNESS-13 to watch it for free!

1 comment:

  1. Turns out quite a few people come to plotting different chaotic equations in browser.) I did a bit of it too, for example http://www.alex-turok.com/fern-map These things are really amazing and just experimenting with parameters to see what else the simple chaotic systems can give you is a lot of fun! Thanks for the post Jeremy!

    ReplyDelete