Monday, March 31, 2014

StarCraft is Life

Fast pace of modern life got you down? By golly, I've got just the answer.

I was going through an old (that is, pre-spideroak) hard drive recently and found a pointlessly absurd Conway's Game of Life simulator I made a few years ago as a StarCraft: Brood War custom map:

Conway's Game of Life.scx

The simulation is meant to be viewed on the minimap, since it shows the whole map at once, and the dots representing buildings and units end up doing a fair approximation of a proper display. The user interface consists of a row of Medics you move up and down to set switches, which control starting and stopping the simulation, clearing the board, as well as choosing birth and survival rules, should you want to simulate something other than the classic B3/S23 ruleset. (You can also edit the board itself with a Mutalisk while the simulation isn't running.)

Gosper's glider gun, about to be run.

To those familiar with the limitations of StarCraft's map format, the map is somewhat surprising at first. Brood War allows you to define only 256 "locations" per map (the original StarCraft allowed only 64!), yet this Life simulator has nearly 1,000 cells (plus a user interface!)

Rather than take the naive approach of assigning one location per grid cell (like in Blizzard's own StarCraft native Tetris clone, Firing Line), this map uses just three locations for the entire grid. The first spans the whole grid and never moves. The second is only as big as a single cell (that is, a single Photon Cannon), and it jumps around via triggers as long as any unprocessed living (or potentially living) cells still exist in the grid. The third is exactly as big as a 3x3 square of cells, and it continually centers itself on the 1x1 location and defines the neighborhood of cells around each living cell that needs to be examined for potential life.

As well as being location efficient, this procedure has the side effect of only examining cells that are in the 3x3 neighborhood of a living cell, which makes small patterns run much more quickly than otherwise. But that also means the Birth 0 condition must be permanently disabled. Birth 0, unique among the birth and survival rules, changes the states of cells that aren't in the neighborhood of a living cell. (Golly uses some fancy rule translations to efficiently process B0 rulesets, but that seems a little beyond the scope of this relatively simple map.)

Unfortunately, even with that optimization, and liberal use of hyper-triggers, Conway's Game of Life.scx is agonizingly slow, and only gets slower as patterns grow. A medium-sized pattern like Gosper's glider gun takes 5-10 seconds per iteration. It turns out StarCraft's arcane triggering system isn't well suited for fast, generic computation. Who knew?

Luckily for you, I've assembled a few (massively accelerated) GIFs depicting an interesting pattern in each of three different rulesets:

Gosper's glider gun

Well-known replicator in HighLife

Typical explosive growth in Maze

No comments:

Post a Comment