Browsed by
Author: PhiNotPi

Intro to Metapixels

Intro to Metapixels

The core of Conway’s Game of Life is the cell, which can either be live or dead.  Or rather, a grid of such cells with unbounded size.  The simulation is run in generations, similar to “ticks” in video games.  The state of the simulation during a particular generation is derived from the state of the previous generation, following simple rules.  If a dead cell is surrounded by exactly three live neighbors (out of 8 total), then it is born.  If a live cell is surrounded by either two or three live neighbors, it survives.  Otherwise, the cell dies.  Using some simple notation, this rule is known as B3/S23.  Despite these simple rules, very intricate patterns can be made.

Gosper’s Glider Gun (source: Wikipedia)

So far, I’ve never created anything interesting in the basic rules describe above.  There are many limitations to work around, since even though there’s lots of “parts” to build with, there’s no guarantee that the parts will fit together in any simple/convenient way.  When building a computer, which involves many complex parts, the keys are regularity, predictability, controllability.  It would be very convenient if there were a way to dictate exactly which cells are allowed to do what, and instead design the rules to fit your pattern instead of designing patterns based on the rule.  Except… there is.

Enter the Metapixel

The OTCA metapixel is a large (2048×2048) construction which allows for the emulation of any “life-like” rules.  That is, any rule of the form B[0-8]*/S[0-8]*.  The most common use is emulation of B3/S23, which is meta-life.

A pattern in meta-life. (Source: conwaylife.com)

The suggestion of using metapixels in the project originally came from the challenge author, although he did not specify anything more than that they may be useful.  Several months ago (I don’t know the time scale exactly), I had a realization: the grid of metapixels can be programmed independently.  This fact, which I verified using Golly, was big news.   By having a grid of mostly background (B/S) cells, other cell types can be arranged form wires, much like how wireworld has copper wires on a black background.

Unfortunately, there’s no simple way to create an “electron” (a pulse along a wire) with only two types of cells (background and wire) and two states (live or dead).  Wireworld uses a 3-state cell for its wire, which provides both a “head” and “tail” that gives the electron direction.  For our project, we could either construct a complex spaceship to serve as our electron, or use an additional type of cell.  I chose to use a third type of cell.

Below is an animation (my first, created in MS Paint), of an electron flowing in a wire and going around a corner.  The grey cells are B/S, the blue cells are B1/S, and the green cells are B2/S.  The live blue cell serves as the electron head, and the green live cells are the tails.  Each cell, of course, represents a single metapixel, which is actually 2048×2048 real GoL cells.  Each generation in this animation represents 35328 real GoL generations.

Electron flowing around a corner.

You can play with an electron in some wire with this Variations of Life simulation.   An important thing to note is the speed of travel: one cell per generation (also known as c, the “speed of light” in CAs).  Even though there appears to be a gap in the wire, the timing is correct: the number of generations matches the Manhattan distance (our preferred measure of distance, so that the time it takes for a signal to travel depends less on the exact path used).

More information on wires and other simple components will be in the next post.

The Quest for Tetris

The Quest for Tetris

Just under 3 years ago, a codegolf.SE user created this challenge:

Build a working game of Tetris in Conway’s Game of Life

As of writing, this challenge is the most upvoted unanswered question on the site, by a large margin.  Some users have predicted that the challenge will never be answered.  I say, this will not be due to a lack of trying.  I am currently involved in a large, serious, and very promising attempt to build a programmable computer in GoL.  This is… the Quest for Tetris.


The Team

As of writing, there are three core developers working on this project, although there have been several additional users participating in the dedicated chat room.

  • PhiNotPi (me) – I consider myself the “project leader.”  I’ve probably done the plurality of physical logic gate/circuit design and construction, although little actual programming.  I was the initiator of this solving attempt.
  • El’endia Starman – He created Variations of Life, the mixed-rule CA simulator that has been the “base of operations” for most of our work so far.  He has also discovered several logic gates.
  • Cᴏɴᴏʀ O’Bʀɪᴇɴ – He is currently programming the tile-based circuit simulator, on which we will develop most of the more complex logic circuits of the computer.

Prior Work

We stand on the shoulders of giants.  There are two main sources from which we are basing our computer design:

  • The OTCA metapixel was created by Brice Due in 2006.  It is a square-shaped GoL construction that is capable of emulating any life-like rule (that is, 2-state Moore-neighborhood outer totalistic rule).  The details of its inner workings are beyond the scope of this project, but the ability to program cells independently of their neighbors is the key to this project.
  • The wireworld computer was built by David Moore and Mark Owen in 1992.  It is (as far as I’m aware), the only CA-based computer of similar complexity and usability.  We intend on using several similar methods in the construction of our computer.  His website describes several parts of the computer, but unfortunately lacks the thoroughness I would prefer (and which I will attempt to provide in this series of blog posts).

Our Approach

We are building our computer on several layers of abstraction.

  1. The Game of Life is the lowest level, of course.
  2. Next is the OTCA metapixel, which is used to emulate a larger grid of cells.  These cells can contain a variety of rules.  We are using the rules B/S (for background), B1/S, B2/S, and B12/S1.
  3. By stringing certain types of metapixels together, we can create wires, down which signals can flow (in the form of “highly controlled spaceships”).  We can also create logic gates that take signals as input and give other signals as output.  All of the basic logic units will be of comparable size and delay, allowing further abstraction.
  4. Logic gates can be arranged to build logic circuits, like adders, multiplexers, memory cells, etc.
  5. These circuits can be combined to form a functional, although basic, computer.
  6. The computer can be programmed to have Tetris.

These steps will be broken down into more detail in additional blog posts.


Current Status

We have finished the majority of logic gate discovery, and are now working on building larger circuits.  Some of our work will still be done with hand-crafting compact circuits, but eventually our circuit design work will be tile-based, without needing to simulate the underlying circuitry.  Our current bottleneck is the programming of this tile-based circuit simulator.

Hello world!

Hello world!

Welcome to WordPress. This is your first post. Edit or delete it, then start writing!

Today I bought my own domain, phinotpi.com.   I chose the “.com” TLD simply because it’s typically considered the most popular, and I decided to take it while it was still available.  I’m hosting this blog with OpenShift, a PaaS by RedHat (currently for free).

I don’t really have any big plans for this blog, but most of it will probably deal with PPCG and related shenanigans.

www.000webhost.com