Pixel-art-style Conway's game-of-life using a tile shader in WebGL

Implementation of Conway's game of life cellular automata with a retro-style shader. Added as example on webgpgpu Github.

[view in browser]

[smaller version for mobile]

Sketch of WebGL implementation:

• Underlying cellular automata runs Conway's game of life
• States as game tiles: new cells: small blue; live cells: blue; died: skulls
• Life diffuses out coloring nearby areas
• A single RGBA texture stores the game state. We render to/from this texture as a framebuffer.
• Each color channel in [0,1] can be mapped to a [0,255] byte value
• The green channel stores the game of life state
• The blue channel stores the diffusing field
• The red channel outputs a tile ID value that is passed to a tile shader to render the game

Retro-styled forest-fire cellular automata in WebGL

Added as example on webgpgpu Github.

This is a cellular automata analogue of the model that we used for developmental retinal waves in this paper. 

[view in browser]

Key rules

• Vegetation "grows" occasionally (flip a coin to increment amount of trees)
• Fires have a small chance of starting spontaneously
• Intensity of ignited fires decay down to zero, at which point they leave ash
• Fires spread to adjacent cells with a probability that depends on their intensity
• Probability of a cell igniting given a fire is related to how much vegetation there is

Sketch of WebGL implementation:

• A single RGBA texture stores the game state
• Each color channel in [0,1] can be mapped to a [0,255] byte value
• A "noise" texture creates pseudorandom numbers
• The green channel stores the level of vegetation (BURNT,NONE,GRASS,SCRUB,TREE)
• The blue channel stores the intensity of the fire
• The red channel outputs a tile ID value that is passed to a tile shader to render the game

Algorithms for rendering quasicrystal tilings

Quasicrystals are aperiodic spatial tilings, and 2D quasicrystals have been used for centuries in Islamic art. I find these patterns beautiful, and I think more people should know how to render them.

You can render 2D quasicrystals as a sum of plane waves. They can also be constructed using aperiodic tilings (e.g. 4-fold Ammann-Beenker tiles and 5-fold Penrose Tiles), and there are fractal constructions that recursively subdivide a set of tiles using a smaller set of the same tiles (e.g. 5- and 7-fold tilings). Many more constructions can be found on the Tilings Encyclopedia

This post focuses on the "cut and project" construction, which is easy to implement in code. The routines shown here can be found in this iPython notebook on Github.

The cut-and-project construction

The simplest way to render crisp, geometric quasicrystals is the "cut and project" construction. This views the quasicrystal as a two-dimensional projection of a planar slice through a N-dimensional hyper-lattice. Let's implement this algorithm. 

A (hyper) lattice

First, we need to define the idea of a hyperlattice. This is a N-dimensional generalization of a cubic crystal lattice. It tiles ND space using ND hypercubes. We can represent the center of each hypercube (hypercell? hyperpixel?) as a N-D vector of integers
$$
\mathbf q_0 = [ x_1, ... x_N ],\,\,x_i\in\mathbb Z
$$
The associated N-cube, then, includes all points on a unit hypercube $\left[-\tfrac 1 2, \tfrac 1 2\right]^N$ offset to location $\mathbf q_0$:
$$
\mathbf q = \left[-\tfrac 1 2, \tfrac 1 2\right]^N + \mathbf q_0
$$

An irrational projection onto a 2D plane

To construct the quasicrystal, we cut through this ND lattice with a 2D plane. To get a aperiodic slice, this plane must not align with any periodic direction in the hyperlattice. 

A good choice is to project each direction of the hyperlattice onto an evenly-spaced set of basis directions, centered at the origin. We define a 2D $(s,t)$ plane $\mathcal P$ in terms of two N-D basis vectors, $\mathbf u, \mathbf v \in \mathbb R^N$.

$$
\begin{aligned}
\mathbf p &= \mathbf u \cdot s + \mathbf v \cdot t,\,\,s,t\in\mathbb R
\\
\mathbf u &= [ \cos(\theta_0), \dots , \cos(\theta_{N-1}) ]
\\
\mathbf v &= [ \sin(\theta_0), \dots , \sin(\theta_{N-1}) ]
\\
\theta_i &= \frac {\pi\cdot i}{N}
\end{aligned}
$$

To render the quasicrystal, cut the N-D lattice along this plane, and project the exposed surface of this cut isometrically onto the 2D (s,t) plane $\mathcal P$. I've searched for an elegant algorithm for this to no avail. It seems like there should be some generalization of e.g. Bresenham's line algorithm to finding the hypercubes (hyperpixels?) associated with the cut. But, inelegant solutions work: it suffices to find the set of N-cubes in the ND lattice that intersect this plane.

$$
\mathcal Q = \left\{ \mathbf q_0 \bigm| \mathcal P \cap \mathbf q\ne \varnothing \right\}
$$

 

 

Algorithm 1: brute-force (wrong, but easy)

An easy to code (but terrible) way to find points in $\mathcal Q$ is by a brute-force search: Check lots of points in the s,t plane, and quantize them to the nearest vertex $\mathbf q_0$ of the hyper-lattice:
$$
\mathcal Q = \left\{ \mathbf q_0 \bigm| \exists (s,t)\in\mathbb R^2 \text{ s.t. } \left \lfloor \mathbf u s + \mathbf v t \right \rceil =  \mathbf q_0 \right\},
$$
where $\lfloor\cdot\rceil$ denotes rounding to the nearest integer vector. This is massively inefficient: many $(s,t)$ points map to the same lattice point $\mathbf q$, and it will miss points if the grid resolution is too coarse. But, for small renderings and run-once code, it does the job. Here it is Python3 code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

from scipy.spatial.distance import squareform, pdist from pylab import * from numpy import * N = 4 # Dimension of crystal θ = linspace(0,pi,N+1)[1:] # Arrange basis vectors evenly on [0,π) A = array([cos(θ),sin(θ)]) # Convert from complex notation L = 501 # Number of grid points to search over dx = 5 # Size of square portion of plane to check # Generate the search grid x = linspace(-dx,dx,L) xy = array(meshgrid(x,x)).reshape(2,L*L) # Collapse all grid points to the nearest hyper-cell p = unique(np.round(A.T@xy),axis=1) def plotpoints(p): u = pinv(A).T@p D = squareform(pdist(p.T)) e = {tuple(sorted(e)) for e in zip(*where(abs(D-1)<1e-6))} xy = concatenate([[u[:,a],u[:,b],[NaN,NaN]] for a,b in e]) plot(*xy.T,lw=0.5,color='k') axis("equal") axis("off") plotpoints(p)

Figure 1: rendered output of a rhobic tiling for the N=4 quasicrystal, computed by brute-force search of the cut-and-project approach.

Inverting the "Simple Sabotage Field Manual"

In 1944, the US Office of Strategic Services published an internal document: the "Simple Sabotage Field Manual". 

In addition to specific techniques for breaking machines, it included suggestions for how to cripple an organization. 

All of the suggestions are things that already happen spontaneously, because organizing large numbers of people reliably and safely is hard.

Rather than re-state the "sabotage" tips, I thought I'd invert each one to create guidelines for positive change in an organization:

• Always share your competencies and knowledge freely and liberally.
• Expedite when it is safe to do so, and whenever failing to do so would lead to something worse.
• Rules that don't serve a purpose can be changed, or broken in emergencies (but this must be done with extreme thought, caution, and community support, see Chesterton's fence).
• No speeches. Be brief and clear, and say nothing without purpose.
• No committees, but if you must, never more than four persons.
• Stay on mission. Do not re-open closed (or no longer relevant) matters.
• With regards to language: be liberal in what you accept and conservative in what you give out; if the words communicated understanding, spend no time revising them.
• Leadership requires action; Take thoughtful and calculated risks (hedging if appropriate). Beware inertia and cowardice in the name of caution.
• Prioritize important jobs first, and assign them to the most competent and efficient.
• Avoid perfectionism, be pragmatic.
• Allocate promotions and responsibilities according to ability (but be kind and take care of all).
• Conferences are a waste of time, if you already know what you need to do.
• Minimize admin bottlenecks, but If a process really needs N persons to sign off, build in redundancy: ensure that at least 2N persons are trained and authorized to do so.
• Be diligent and serious in your work.
• Avoid distractions, minimize interruptions from co-wokers and avoid breaking up the workday.
• Learn how to build and maintain good tools, and how to do good work with bad tools.

Wildcard selectors in uBlock Origin

The extension uBlock Origin for Chrome and Firefox allows users to block offensive elements on websites.

It works by matching the name of elements on a page against a block list, but some websites randomize element IDs, making this tricky. One can block elements with parts of their ID randomized in uBlock, but it is not automatic. First:

• Have uBlock Origin installed
• Identify element to block
• Right click and select "block element"
• uBblock will highlight the element, and a white box should appear in the lower right corner of the browser.

If the website is randomly-generating IDs, you won't be able to block the element with a fixed rule. You might see something like this:

##[randomly generated string]_[some predictable unique tag]

or

##[some predictable unique tag]_[randomly generated string]

Now, you might think that these could be blocked by "##*_[some predictable unique tag]" or "##[some predictable unique tag]_*", but uBlock does not use regular wildcard syntax. Instead, it uses CSS selector syntax, which is idiosyncratic. For example, this Reddit post suggests transforming the desired wildcard selector

###leaderboard_ad-*.block_article_ad.leaderboard_ad.etc

Into a rule expressed in terms of a CSS selector

##.block_article_ad.leaderboard_ad.etc[id^="leaderboard_ad-"]

This (1) Specifies the parts of the rule that are fixed, downstream of the wildcard, and (2) adds a string-matching query that finds elements whose ID starts with "leaderboard_ad-" (that's what "^=" means).

This post corroborates this approach, suggesting a generic format if the offending element has an ID starting with a predictable string:

www.annoyingwebsite.com##div[id^="start_of_div_name_before__randomnumber"]

This works, provided you can uniquely match the element based on a prefix. What if the unique identifier is a suffix? Referring back to CSS selector synatx, we find that ^= means "begins with" and $= means "ends with". So the wildcard rule for an element that randomizes the end of a div's ID would be:

www.annoyingwebsite.com##div[id$="_end_of_div_name_after_random_number"]

Box Drawing Characters + Marching Squares = Marching Boxes?

I couldn't figure out the name of this to search for it online, and it wasn't mentioned on Wikipedia's marching squares page, so… here's to reinventing wheels ( :

Sebastian Blomfield's "Lord of the Manor" game inspired me to explore retro-game engine coding. So far, I've got a basic tile-shader that renders tiled 2D game environments (e.g. game of life, forest fire simulation). Next up: what if I want to draw maps where the adjacent tiles of e.g. walls are continuous?

Box-drawing characters are a nice way to generate rectilinear paths in a tile-based game environment. By checking whether the tiles above/below/left/right are also walls, we can select one of 16 box drawing symbols to create continuous walls:

Note that this extends the usual unicode box-drawing characters with five additional tiles: one for an isolated (disconnected) wall, and four for "dead ends". These suffice for rendering square hallways, e.g:

With some tweaks to the tiles, we can coax box-drawing tiles to generate more curved and diagonal paths:

See here for an example page that renders dendriform growth using the above tile sets (refresh to get a new randomly-selected tile set).

Marching squares is another nice algorithm for rounding off corners on a map (e.g.). This doesn't quite work out-of-the-box for our tile shader, however, since marching squares accepts the values for the corners of each tile, and I want it to operate on the tile values directly. It also uses 16 tiles:

So! box-drawing is good for lines, and marching squares is good for borders/contours. Can we combine these and get a best-of-both-worlds approach? One that renders tiles based on their current value and the values of their neighbors?

Yes. I'm not sure what its name is, so I'm calling it "marching boxes" for now. Marching-boxes extends the box-drawing tiles with 31 tiles (below). These provide versions of the corner, T-junction, and cross-junction tiles that account for the possibility of nearby filled-in regions. The resulting tiles can render contours around filled-in regions as well as sharp lines.

Including background and foreground tiles, marching boxes uses 48 tiles.

This could be nice for any pattern that has a mixture of lines and enclosed regions, like a dungeon connected by hallways, or a water system that includes both lakes and rivers.

Click here to view a WebGL demo of marching-boxes tile rendering

More LED layouts for hand crafting

LED multiplexing layouts for hand-crafting outlined LED grid layouts using a diagonal section of a Charlieplexed grid of LEDs. This post presents some additional layouts designed for e-textiles (e.g. embroidery, bead-weaving).

The main idea of these layouts is that they should consist of a regular, repeating lattice of N driving lines, such that each pair of lines cross exactly twice. One LED is placed at each crossing (one forward and one backwards, in terms of polarity, for each pair).

Grid arrangements

The diagonal nature of the diagonal-multiplexing grid does not lend itself easily to conventional row/column display designs. Previously, we distorted the diagonal grid to create a square layout. This is tricky to solder correctly. One can achieve the same effect by skipping every-other position in the diagonal grid. Then, repeat the whole diagonal-multiplex pattern again, this time with the polarity of the LEDs reversed.

Here is an example where 9 control lines drive a 4×18 LED matrix. Below, the red/blue halves of the LEDs denote polarity (not color, these would be single-color LEDs). The polarity of the rightmost half of LEDs should be flipped. This approach works if the number of control lines is odd.



The two repeated patterns can also be sewn together in parallel. In this case, building a 9×8 grid.

Linear arrangements

In two special cases, its possible to lay out a straight line of LEDs. One pattern drives 6 LEDs on 3 lines, and another drives 20 LEDs on five lines. These designs intended for LED embroidery projects.

3 lines control 6 LEDs. (The polarity of the rightmost half of LEDs should be flipped.)

5 lines control 20 LEDs. (The polarity of the rightmost half of LEDs should be flipped.)



These could also be wrapped to form a circle.
 

RGB tiles

These RGB tiles were designed to work with 6-pin RGB LED modules, which expose both the anodes and cathode of each individual color channel. It is possible to design a single "tile" sewable PCB that will work with both layouts below. The idea is that this could enable a tile or "scale" pattern on e-textiles.

9 lines control 72 LEDs, creating 24 RGB tiles arranged in a 4×6 grid. Every three rows of the diagonal-Charlieplexing grid are grouped to produce one set of RGB tiles.

This pattern can be generalized to any number of control lines that is both odd and divisible by 3. E.g. 9, 15, and 21 control lines produce 4×6, 7×10, and 10×14 grids, respectively. (I think.. double check these.)

13 lines control 156 LEDs, creating 52 RGB tiles arranged in a 4×13 grid. Each row is grouped in alternating patterns of 2 and 1 LEDs, which are then groups by row into groups of 2+1=3.




This pattern can be generalized to any number of control lines $N$ such that $N$ is odd and $N-1$ is divisible by 3. E.g. 7, 13, and 19 control lines produce 2×7, 4×13, and 6×19 grids, respectively. (I think.. double check these.)

RGB Matrices

Other ways of grouping the LEDs into (R,G,B) triplets support ordinary rectangular RGB LED matrix layouts. N*3+1 control lines can be grouped to support a N×N*3+1 matrix of common-anode or common-cathode RGB LEDs:

For example, 13 control lines can support four groups of three (R,G,B) triples in 13 rows

Or 16 control lines can support a 5x16 matrix:

Notes

All of these designs assume tri-state drivers (positive, negative, and high-impedance (off)) that can source fairly large currents (e.g. ~40 mA). This is typical of the AtMega and AtTiny AVR chips powering most flavors of Arduino.

For large e-textile designs, the resistance of the conductive thread might be an issue. It may be necessary to use multiple threads in parallel, or to selecting a high conductance thread. Adjusting the layout so that no LEDs are too distant from the driver might also help. Crude software balancing of brightness via PWM may also be possible, but difficult on larger displays. Take care not to let driving lines short at points where they cross.

When driving displays that mix LEDs of different forward voltages: If more than one LED is lit at a time, then the red/green/blue LEDs must be scanned separately. Unless individual current-limiting resistors are provided for each LED, the forward voltage of the red LEDs must not be less than half the forward voltage of the blue LEDs.

There's a good argument that manually creating LED meshes is not a good use of time, and that one should use e.g. NeoPixels instead. These patterns, however, have the obsessive repetition and tedious assembly of knitting, and may appeal to some people. 

I have not had the opportunity to mass-produce the sewable LED boards that would be needed to complete these projects.