ECE 5760: Wireworld and Conway's Game of Life

By Aidan McNay and Thomas Figura

Introduction Background Hardware Design Program Design Results/Conclusions Appendices

Background

Wireworld

Wireworld is a cellular automata with rules that cause it to mimic electron flow. To do this, it defines four states that a cell can have:

The four WireWorld states: Empty, Conductor, Head, and Tail

On each update, a cell will update its state based on the current state of the cell and its neighbors:

Empty updates to Empty, Head updates to Tail, Tail updates to Conductor, and Conductor updates to Head if one or two neighbors are head (otherwise staying Conductor)

(Here, "neighbors" refers to the eight cells surrounding a cell on a grid)

Through these rules, "electrons" (head-tail pairs) flow in the direction of the head along a conductor path. Additionally, all of the basic digital logic blocks (AND gates, NOT gates, OR gates, etc.) can be constructed using the rules of Wireworld, making the cellular automata Turing-complete.

Below is an example of a clock generator, which continuously generates and sends electron pulses off to the right. This is a basic building block in Wireworld, and is useful for intuitively understanding why electrons follow conductor paths.

An animation of a clock generator that sends electron pulses

While the group decided it would be fun and cool to implement Wireworld on the FGPA, being able to simulate some sort of large design became the end goal of the project. To this end, since Wireworld is a Turing complete system, the group found online a "Wireworld Computer" (Main Page, Processor Layout), where the creators designed and implemented a processor in Wireworld capable of executing instructions (in this case, running a program that tests odd numbers for primality). We determined that our project would be successful if we could simulate and display this large design running; since the design requires a grid of ~940 by ~610 cells, this would represent a significant amount of state updating simultaneously, allowing us to demonstrate the computational power of the FPGA.

Game of Life

The second Cellular Automota that was implemented during this project was Conway's Game of Life. This cellular automata is very similar to Wireworld; instead of four states, it defines two states:

The two Game of Life states: Dead and Alive

Note the similarity in colors; states are re-used between automata, bearing different semantics based on which automata rules we're using.

Similar to Wireworld, Conway's Game of Life also provides rules for how to update state based on the current state of a cell and its neighbors:

Dead becomes Alive if exactly 3 neighbors are Alive. Alive becomes Dead if fewer than 2 or greater than 3 neighbors are Alive

When initially implementing Wireworld, our design centered around a single RTL module that would compute the next state based on the current state of the cell and its neighbors. Due to the similarities between the automata, we were able to have the update rules switch dynamically between Wireworld and Conway's Game of Life, allowing for a significant amount of more functionality for relatively few changes (as the rest of the infrastructure to simulate and view the automata was already present).

Also, since Wireworld has two more states than Conway's Game of Life. When switching from Wireworld to Conway's Game of Life, Electron Head and Electron Tail will first switch to the Alive state before they become actors in Conway's Game of Life.