The Star Wars cellular automaton

You’ve probably heard of Conway’s Game of Life, a cellular automaton which produces intriguingly chaotic patterns from simple rules. (Stephen Wolfram would call it a “class 4 CA” as if that meant something.) This blog post is on another intriguingly chaotic cellular automaton known as “Star Wars,” which was discovered by Mirek Wójtowicz circa 1999.

It makes a pretty nice screensaver to stare at.

Many CAs in the general vicinity of Conway’s Life can be described via a compact notation pioneered by Mirek Wójtowicz. Life itself is “B3/S23”: a new cell is Born when a dead cell is surrounded by 3 live cells, and a living cell Survives when it is surrounded by 2 or 3 other living cells. (This assumes an eight-cell Moore neighborhood.)

One way to extend the rules of Life-like automata is to give cells a “refractory period.” When a cell in such a CA dies, it cannot immediately become alive again; instead, the dead cell enters a “countdown” of a certain number of timesteps, after which it becomes eligible for life again. That is, in these CAs, there are Life-like rules for transitioning from state 0 to state 1, and from state 1 to state 2, but then any cell in state 2 unconditionally enters state 3, any cell in state 3 unconditionally enters state 4, and so on, until finally any cell in state N enters state 0 and is once again subject to a Life-like rule. The compact notation for this kind of automaton is its Life-like rules for states 0 and 1, followed by the total number of states in the automaton (that is, the number of refractory states plus two).

Brian’s Brain is the most famous refractory Life-like CA; its rule happens to be B2/S/3. (The lone “S” indicates that live cells in Brian’s Brain never survive for multiple turns; the “3” indicates that it has three states: dead, alive, and refractory.)

Star Wars is a refractory Life-like automaton with the rule “B2/S345/4” (that is, it has two refractory states).

For more specimens of refractory Life-like rules, see the old MCell home page.

Refractory states tend to lead to tiny light-speed spaceships. In the same way that the “head” and “tail” states in Brian Silverman’s Wireworld create “electrons” that move in the direction of their head, Brian’s Brain and Star Wars are full of asymmetric constructs that birth living cells ahead of them as their “tail” enters the refractory state. In Star Wars a single pair of cells, with refractory cells behind them, makes a glider. If you curl up the ends of the glider into parentheses, you don’t even need the refractory cells.

One of the most common naturally occurring spaceships is a “fireball” that travels at light speed. (I see that Catagolue knows about this entity, but I don’t really have any idea what that means.) Here’s the fireball, plus another slightly larger and rarer naturally occurring spaceship below it:

Here’s an extensible ship that paddles along like a centipede, and a ship that gallops along like a centaur:

Star Wars also has aesthetically pleasing still lifes and blinkers, in the form of “planets.” A cross of five live cells makes a stable still life. But if a ship comes too close to the planet, the planet may gain a satellite — destroying the ship in a cloud of flaming debris!

Planets may have up to three satellites at once; and a two-planet system may be stabilized by four satellites.

For the big “random exploration/screensaver” grid at the top of this post, I decided to add some interest to the visual display by color-coding each living cell as part of a “faction.” Recall that in Star Wars, the only way to birth a new cell is for the cell to have exactly two living neighbors. So, I’ve assigned each new cell to the “fire” faction, the “water” faction, or the neutral “magenta” faction, according to whether its two parent cells are themselves majority-fire, majority-water, or neutral/tied. This produces a vivid display of strife between the factions, even though the rules of the underlying CA have not changed at all. (See ConwayLife’s wiki page on Colourised Life, which is the same kind of thing.)

Also, the north and south edges of the grid (about 10 cells off-screen in either direction) are constantly seeded with random noise, producing a steady influx of “immigrants” to the galaxy.

LifeWiki quotes John M. G. Elliott as observing that Star Wars is “active to a degree almost reminiscent of [Brian’s] Brain, with the distinction that it likes to build fixed Lego-like skeletal structures.” If you leave it running long enough, the galaxy will ossify — the Lego-like structures will accumulate like plaque and stifle anything interesting that the spaceships might try to do. But it does take quite a while to get to that point!

Participants on the ConwayLife forum have invented some pretty cool Wireworld-esque circuits and other gadgets in Star Wars; see here. The “electron-to-glider” gadget depicted here is due to ConwayLife poster “calcyman” and the general design of the wires is due to poster “ebcube”.

ConwayLife poster “knightlife” found a very cool “bug” that crawls around the inside of a slanted rectangular enclosure; see here.

What sorts of things might you discover in Star Wars?

Posted 2020-06-29