About "because unless until" - Appendices
This post contains supplemental information about because unless until. For the original article, check here.
Appendix A: Algorithm
To begin, the algorithm selects the "animation set" (referenced in features as Animation) and colors (features: Palette Mode and Palette 1-4) that will be used in the output. Animations are chosen for the animation set (non-default ones -- those that don't aren't the core animation in the set -- are captured in the SubAnimation feature).
Neighborhoods (features: First and Second Neighbors) are chosen, and each cell is given a list of neighboring cells to be used when updating state. Lists of random automata appropriate for the animation set and neighborhood selection -- four for foreground regions, and four for background regions -- are chosen.
A variety of variables related to the current day are instantiated to drive time-based features. One of 31 possible detail levels is chosen based on the day of the month, and a corresponding grid of cells with a randomized starting state is constructed, to be used for the CA that determine the textures and colors drawn to the canvas. A coloring mode is chosen (from a pool of 18 possible modes) for the eight regions of the animation based on the day of the week.
On the basis of the current month, the random seed is then perturbed to change how the rest of setup will progress. The animation set constructs its animations, whose properties depend on the [now perturbed] random seed. The core program loop is then ready to begin.
At the start of the draw loop, the animation set prompts each animation to update its internal state -- the variables that determine how it behaves. This may take the form of a fractal slightly shifting, or the movement of a spiral to its next position. Then, worker threads for each animation begin the work of assigning a value to each cell, which varies by animation. For spirals, this might be a measure of distance from the central point. For fractals, it might be a count of iterations before bailout, or a binary value representing whether a bailout was needed. CA animations report the state of their internal cells. This value assignment is what I consider the external state of each animation.
The animation set checks the last reported external states of its animations, and uses its own algorithm to combine them into an aggregated state where each cell is assigned to one of four regions, and a binary value indicating whether it's background or foreground. Depending on the timing of the worker threads, the external states from each animation may change at different times or rates, which gives their combination a non-deterministic quality by default. The threads can be synchronized to make them deterministic (at the cost of performance) by enabling Synchronous Mode (press V).
Now, it's time for the cellular automata to iterate their state. For each cell, a CA rule is applied -- depending on the region and background/foreground determination of the animation set -- to calculate the next state for the cell. Metrics are gathered on how many neighbors each cell has, to be used in deciding its color. The overall number of dead/living cells are measured, so that an intervention can be made to the CA selection if the canvas is becoming too full or empty.
A palette from the output is selected for the cell based on its region. The ratios of first/second/total neighbors (more on neighbors below) for the cell are combined, based on the rules of the coloring mode selected for its assigned region, to yield a ratio between 0 and 1. The ratio is used to select a color from the palette (e.g. a ratio of 0.65 would select the color closest to 65% of the way through the list of colors in the palette).
Here, the animation set occasionally makes changes to the automata in use to change the balance of textures. With each change, it evaluates the current balance of automata (are there both moving and still textures? Is there negative and positive space?) to ensure the animation maintains visual interest.
Armed with the color values needed for each cell, it's time to render. Each cell is drawn into the memory of a buffer canvas as the RGB value of an individual pixel. Some percentage of the previous value (an internal feature known as keep ratio) for that pixel is kept by taking an average with the new value, creating a blur effect that varies by output.
The buffer canvas is then redrawn on top of itself with the "screen" globalCompositeOperation enabled to lighten the colors. The buffer canvas is then stretched across the main canvas, and rendered to the screen. This approach means that many fewer pixels need to be calculated than are ultimately drawn on the screen, which significantly boosts performance. (Note: unlike my earlier works that drew squares to represent pixels, the squares displayed in this work are actually literal pixels from the buffer canvas, which for some reason I find really satisfying). The next iteration of the animation loop can now begin.
Appendix B: Neighborhoods
The neighborhood of a [current] cell is the group of cells used as inputs when calculating the next state for the current cell. Most commonly (as in Game of Life), the 8 surrounding cells are used -- a Moore neighborhood with a Chebyshev distance of 1 (analogous to the spaces a king could move to on a chessboard in 1 turn). This was the neighborhood used in my earlier works Implications and mono no aware, often referred to as "nearest neighbors."
One of my goals for this project was to use "next nearest neighbors" as well -- a Moore neighborhood with cells at a Chebyshev distance of 2 from the current cell -- increasing the number of inputs for an automaton from 8 to 24. This would mean that the number of possible input combinations rises from 2^8 to 2^24, giving 2^16 times as many possible combinations and radically increasing the diversity of possible behaviors.
Handling these additional inputs quickly enough to maintain fluid animation was a challenge, and required a total overhaul of my CA algorithm. Somewhere during this process, I discovered I'd made a mistake, and was including the current cell as its own "next nearest neighbor" in my calculations. When I fixed the bug, I noticed that the behavior of the ~50 CA I'd built subtly changed -- some for the worse. Should I fix the bug, or just leave it? Was it really a bug, or just an unexpected feature?
This idea led me to ask "what if I chose different cells for the neighborhoods?" I tried it, and was pleased with the variety of new behaviors that appeared. Each automaton was changed in unpredictable ways -- some for the better, some for the worse, and some... just different. I constructed a list of new neighborhoods, and loosened the concept of "nearest" and "next-nearest", instead referring to the two types of neighborhoods as "first" and "second," since the cells selected weren't necessarily the nearest by any metric.
While diverse, many of the CA's behaviors were poor for use in the animation. To solve this, I constructed a list for each combination of first and second neighborhoods, including any CA rules that had an interesting appearance when I tested them. This required manually testing 51 x 7 x 9 = 3213 combinations by hand, which was a really time-consuming and subjective process. But the overall quality of resulting textures and behaviors was worth the effort. In the end, 2072 rules were thrown away, and 1141 were kept.
Below is a description of the different neighborhoods, with illustrations to show what they look like. The colors mean:
Black - a cell in the neighborhood
Grey - a cell NOT in the neighborhood
Red - the current cell
Yellow - the current cell, which is also included in the neighborhood
Orange - the current cell, which has a 50% chance to be included in the neighborhood (a hat tip to the mistake that led me here)
First neighborhoods include cells that are somewhat close to the current cell, and which are weighed more heavily in determining the next state. The CA were developed to maintain a balance between growth and death using the Moore neighborhood with 8 neighbors. Including fewer cells in the neighborhood could result in "die out" (all empty cells) for CA that have just enough cells to persist; including more cells could result in "die out" for CA that are on the verge of overcrowding. So, there were some limitations on how many cells could be included in the neighborhood -- and appropriate CA choices are different from the standard Moore neighborhood.
Top Left: A Moore neighborhood, with the current cell at the center. All rules used for automata in because unless until were originally developed and tested using this neighborhood.
Top Center / Center: Rise A and B, respectively. These two together form the Rise neighborhood. Each has an asymmetry that causes most textures to have a slight bias for upwards or downwards growth. The upwards neighborhood is used for 5/8 of cells, and the downwards neighborhood is used for 3/8 of cells, giving the animation as a whole a slight bias for upwards growth (which gives this neighborhood its name).
The alternation of upwards and downwards growth, combined with the asymmetry in the neighborhood as it's used for coloring, cause a slight 'striping' effect across the canvas. A few of the automaton rules move in the opposite direction (falling), giving this neighborhood a complex set of behaviors.
Top Right / Center Right: Fall A and B, respectively. Together, they form the Fall neighborhood. Extremely similar to Rise, but with a slight bias for downwards growth and a different behavior -- so textures have a different appearance.
Center Left: The Self neighborhood -- it's also a Moore neighborhood, but the current cell includes itself as a neighbor. This changes the textures and colors that result from each automaton in complex ways that depend on its ruleset.
Bottom Left: The Plus neighborhood -- a von Neumann neighborhood where the current cell also includes itself as a neighbor.
Bottom Center: The Plus Plus neighborhood. One of two "first neighborhoods" to include what I'd consider a "second neighbor" (at a distance of two from the current cell). Because the automata rules included in the algorithm tend to more heavily weigh the state of cells in the "first neighborhood," the current cell is heavily impacted by cells at a distance.
Neighborhoods like this one where a current cell may receive more influence from distant cells than near ones behave differently than we're used to seeing in the ruleset of our universe (where events at a location in spacetime "ripple outwards" in a light cone, affecting nearby regions of spacetime before distant ones). Textures grow up/down and left/right faster than they grow diagonally. The topology of a space connected by this neighborhood seems like a network of connected grids -- which is sometimes visible in the behavior of automata.
Bottom Right: The Spiral neighborhood -- rotationally symmetrical neighborhood including some further neighbors.
Second neighborhoods include cells that are "at a greater distance" from the current cell, and tend to be weighed less heavily by the CA rules, giving their selections a more subtle (but still important) impact on CA behavior. There are 16 of them in the default Moore neighborhood, but the others have as few as 9 or as many as 24. The larger number of available cells to choose from at a distance means a wide variety of combinations are possible. Some of them include cells at a Chebychev distance of 3 or 4, giving them complex behaviors.
Top Left: The Moore2 neighborhood, which is typically the default way to calculate "next nearest neighbors" in a CA. All automata were originally developed using this neighborhood.
Top Center, Center: Invaders A and Invaders B, which together form the Invaders neighborhood. Each is used for 1/2 of the cells to remove overall growth bias. The first of the neighborhoods to use neighbors at a distance of 3 and 4, which means patterns can propagate quickly across the canvas. Has a highly irregular shape that causes some unusual patterns to appear.
Top Right, Center Right: These two are combined in different ways to create the Half Fall and Half Rise neighborhoods. They each have a bias for upwards and downwards growth, with one being used for 3/8 of cells, and the other for 5/8 of cells. Depending on which is chosen for each slot, gives the animation an overall upwards or downwards growth bias. This is the least dense of the second neighborhoods, with just 9 cells
Center Left: The Moore3 neighborhood -- includes all cells at a distance of 3. Similar in appearance to Moore2, but changes propagate more quickly, and textures have a slightly different character. One of the densest neighborhoods, with 24 cells.
Bottom Left: The Hashbox neighborhood. Similar Moore3, but with some gaps. Includes 16 cells like Moore2, so textures have a similar density.
Bottom Center: The Target neighborhood, which includes 20 symmetrical cells at a distance of 2 and 3.
Bottom Right: The Circle neighborhood, with 24 cells at distances of 3 and 4. Its large number of cells and distance have a large impact on the textures generated. It tends to kill "dust" -- small regions of isolated cells -- because it skips over cells close to the current cell.
Far Bottom Left: The Whirl neighborhood. Radially symmetrical, with two axes of symmetry -- which sometimes causes diagonal growth patterns with interesting structures. With 16 cells, it has similar survival characteristics to Moore2.