The simulated flame code isn't very sophisticated or even technically accurate, yet does a good enough job of fooling our eyes. How can it do that? Fractals!
Fractals are mathematical objects exhibiting self-similarity at the macro and micro scales…any small part resembles the whole…
Fractals are great for simulating natural phenomena!
Notice how each floret of this (real) romanesco broccoli resembles the full head…and each floret, in turn, has smaller florettes.
This notion of repetition across scales is used in computer simulations…for example, each peak and valley in this fractal terrain has several smaller sub-peaks, with progressively smaller mounds and nooks all the way down…but the same mathematical formula defines them at every level, only the scale changes.
(Image credits: Wikimedia Commons public domain.)
Fire is another natural phenomenon where this math could help. The flame code works a little like the fractal terrain, but much simpler. Instead of three dimensions, it only has to work in two (time and brightness), and one of those…time…always moves linearly forward. So really the code just has to create those “hills” and “valleys” along the brightness axis.
In the sketch, brightness is represented with a uint8_t variable — an 8-bit value in the range 0 to 255 (darkest to lightest). Consider two values randomly offset from the middle (128) up or down by 64 (or less). Those will be the starting and ending brightness for some time interval. Now consider a straight line between them…
Divide the line at its midpoint into two equal segments, then move that midpoint up or down randomly by up to half the previous range; somewhere between -32 and +32.
Do the same on each of the two resulting segments: split in two, randomly move the midpoint of each up or down by 16. Repeat with the four resulting segments, ±8, then eight segments ±4 and so forth…
And that’s all there is to a simple fractal! Assign those numbers over time to the brightness of an LED (or all the NeoPixels around the Circuit Playground board) and you have a not-too-shabby candle flicker effect.
To achieve that line segment split, and the split-split, and split-split-split-split and so forth, the code uses a techniqe called recursion.
Normally when programming you’ll call some function (e.g. Serial.println()), it performs some operation and then returns, and the code resumes at the next statement.
Recursion is what happens when a function calls itself…
void foo() {
foo();
}
Normally this would create a sort of infinite loop, but even worse.
Any time any C function is called, a tiny bit of RAM is used: a pointer back to the next statement upon return (called the stack pointer), plus space for any local variables used in that function. This RAM is freed when the function returns. If just keeps “nesting” calls and never returns though…the example above, despite being just a couple of bytes per function call...with only 2K RAM on most Arduino-type boards, it’ll run out of space in no time and the program will soon crash.
To avoid this, some limit can be placed on the maximum depth of recursion…the number of times a function can call itself from within itself from within itself. This can be passed along as an argument…
void foo(int depth) {
if(depth < 10) {
foo(depth + 1);
}
}
foo() now requires four bytes per invocation (two for the stack pointer, two for the “depth” argument…a local variable). The first call to foo() would pass a value of 0. By checking the value of depth and limiting it to 10, this won’t use more than 40 bytes worst case.
In the candle flame sketch, the split() function calls itself recursively, twice: one call handles the left or first half of the line segment, other handles the right or second half. Each of those, in turn, may call split() again, and so on…but only up to a point…
void split(uint8_t y1, uint8_t y2, uint8_t offset) {
if(offset) { // Split further into sub-segments w/midpoint at ±offset
uint8_t mid = (y1 + y2 + 1) / 2 + random(-offset, offset);
split(y1 , mid, offset / 2); // First segment (offset is halved)
split(mid, y2 , offset / 2); // Second segment (ditto)
} else ...
...
}
“offset” is the maximum amount to move the center point up or down. Each time we call split() recursively, we divide that value by 2…because that’s the nature of fractals…big broccoli head = big offset, little broccoli florets = little offset. When offset reaches zero (which will happen due to integer rounding: 1÷2 = 0), no further subdivision/recursion takes place…a RAM disaster is averted and the LEDs are set to a brightness level corresponding to the “y1” argument before returning.
The code recurses and returns down and up and down and up like this until the final brightness level is reached, at which point this becomes the next starting value and a new random end value is chosen and the whole process is repeated.
The MakeCode version works a little differently, because this sort of recursion is not supported in “BLOCKS” mode. Instead the brightness level bounces back and forth semi-randomly…not quite the same, but still pretty effective.
Page last edited October 12, 2016
Text editor powered by tinymce.
