Most likely you already heard about Conway's Game of Life and you know that it's, in fact, Turing-Complete, meaning that you can make a full size computer with it.
Let's take a deeper look on how to make a simple circuit.
Getting Started
First of all we will need a way to run game of life. I am a JS dev so I've made a website with game of life simulation using one of my old projects, you can check it in this snapshot.
One thing to notice is that we make a parse function to load RLE which is JSON for game of life state. The very first RLE example you can see is 24bo$22bobo$12b2o6b2o12b2o$11bo3bo4b2o12b2o$2o8bo5bo3b2o$2o8bo3bob2o4bobo$10bo5bo7bo$11bo3bo$12b2o! which is Gosper Glider Gun. We'll use this RLE to test application and parsing function, which should look like following:
const isDigit = (s: string) =>
'0123456789'.indexOf(s) > -1;
const splitIntoTokens = (rle: string) => {
let buffer = 1;
return rle.split('').reduce((acc, token) => {
if (isDigit(token) && acc.length > 0 && isDigit(acc[acc.length - 1])) {
acc[acc.length-1] += token;
return acc;
} else {
return acc.concat([token]);
}
}, []).reduce((acc, token) => {
if (token === '$') {
return acc.concat([{ type: '$' }]);
} else if (token === '!') {
return acc.concat([{ type: '!' }]);
} else if (token === 'b') {
const count = buffer;
buffer = 1;
return acc.concat([{ count, type: 'b' }]);
} else if (token === 'o') {
const count = buffer;
buffer = 1;
return acc.concat([{ count, type: 'o' }]);
} else {
buffer = parseInt(token, 10) || 1;
return acc;
}
}, []);
};
export const parse = (rle: string) => {
let y = 0;
let x = 0;
return splitIntoTokens(rle).reduce((acc, token) => {
if (token.type === '$') {
y++;
x=0;
}
if (token.type === 'b') {
x += token.count;
}
if (token.type === 'o') {
for (let i = 0; i < token.count; ++i) {
acc.push({ x: x + i, y });
}
x += token.count;
}
return acc;
}, []);
};
After little bugfixing we should see the game itself in the browser. I am not adding game simulation code here as it's pretty straightforward and easily googlable.
The Circuitry
Before we design something meaningful, we have to understand what our building bricks are. The whole Game of Life's circuitry is built around few simple components.
Glider Gun
There are few different types of glider guns, they vary by period, glider direction and perks like ability to be destroyed or modified to change glider output. We'll stick to Gosper Glider Gun as the smallest (box wise).
Gosper Glider Gun produces a glider in a specific direction every 30 generations, building a so-called "stream" of gliders.
Glider
Glider is a basic but very usable Game of Life pattern. In circuitry it is used to transfer bit signal. Gliders cannot cary any information within them, but their presence inside the "stream" at a specific point of time (generation) can be interpreted as 1 or 0, somewhat like baud rate.
One important thing to know about Gliders is that, if they collide in just the right way, they annihilate each other.
Glider Reflector
Reflector is Game of Life pattern that will allow us to "redirect" the glider stream in a different direction. Again, there are few different types of reflector that work with different "baud", different angle or have interesting abilities to mutate, in this article we'll use this one.
Glider Eater
Glider Eater is a pattern that, being shot with a glider in just the right way, will destroy a glider. This is usable to end the "glider stream" if don't want it to mess with the rest of the circuit.
Drawing Patterns
Now we have all the knowledge to play around and try to make our own gates, but we don't have a way to do it. Let's modify the application we've made to support simple drawing around and pausing. This way we'll be able to create our own patterns and see them in action.
const handlePoint = (x: number, y: number) => {
if (this.gameOfLife.has(x, y)) {
this.gameOfLife.remove(x, y);
} else {
this.gameOfLife.put(x, y);
}
};
let mousepressed = false;
this.events.onMouseDown.subscribe(({ x, y }) => {
mousepressed = true;
const cellX = Math.floor(x / CELL_SIZE);
const cellY = Math.floor(y / CELL_SIZE);
handlePoint(cellX, cellY);
});
this.events.onMouseUp.subscribe(() => {
mousepressed = false;
});
this.events.onMouseMove.subscribe(({ x, y }) => {
if (mousepressed) {
const cellX = Math.floor(x / CELL_SIZE);
const cellY = Math.floor(y / CELL_SIZE);
handlePoint(cellX, cellY);
}
});
You can see how drawing works in this snapshot. After playing around I was able to draw components on my own and made the Glider Reflector pattern, but it took me too much time.
A lot of circuitry for Game Of Life is happening around adjusting distance to make the stream just the right length for gliders to hit reflectors or each other at the right time. In order to achieve this we'll have to move guns and reflectors by a couple of cells here and there. Redrawing Gosper Gun 2 cells left - that's gonna hurt. Let's upgrade our application to support selection and moving.
let selection = null as null | { from: Point, to: Point };
this.events.onMouseDown.subscribe((p) => {
if (this.modes.get() === 'select') {
const cell = this.getCellByPoint(p);
selection = { from: cell, to: cell };
}
});
this.events.onMouseMove.subscribe((p) => {
if (this.modes.get() === 'select') {
const cell = this.getCellByPoint(p);
selection.to = cell;
}
});
this.navigator.onRender.subscribe((context) => {
if (selection) {
const { from, to } = selection;
context.beginPath();
context.rect(
from.x * CELL_SIZE,
from.y * CELL_SIZE,
(to.x - from.x) * CELL_SIZE,
(to.y - from.y) * CELL_SIZE
);
context.setLineDash([15, 5]);
context.lineWidth = 5;
context.stroke();
context.setLineDash([]);
}
});
After that we should be able to select regions of the field. With that selection we can do many different operations like mirroring, rotating and even inverting.
Here is the listing for moving the selection with its content by arrows on the keyboard.
this.events.onKeyDown.subscribe((key) => {
if (this.modes.get() !== 'select') {
return;
}
// Move with arrows
if (key === 37) { // left
this.moveSelection(-1, 0);
}
if (key === 39) { // right
this.moveSelection(1, 0);
}
if (key === 40) { // down
this.moveSelection(0, 1);
}
if (key === 38) { // up
this.moveSelection(0, -1);
}
}
const moveSelection = (dx: number, dy: number) => {
this.gameOfLife.state.forEach((cell) => {
if (this.cellInSelection(cell)) {
cell.x += dx;
cell.y += dy;
}
});
this.selection.from.x += dx;
this.selection.from.y += dy;
this.selection.to.x += dx;
this.selection.to.y += dy;
};
Glider Stream
Before we design the gates themselves we should understand the concept of Glider Streams. The Glider Stream is a path that Gliders travel. Usually it starts in a glider gun, goes through several mutations like reflectors and annihilators and ends with a glider eater.
Let's add the highlight for the streams and observe the simplest glider stream. It starts with Gosper Glider Gun and ends with Glider Eater. Every 30 generations new Glider is created and it takes 60 generations for it to reach the glider eater.
If we assume that 30 generations is somewhat a "global period" we can check the presence of glider in the stream every "global period" generations in blue square and, if glider is present, take it as 1, if glider is absent, take it as 0. Thus said, the stream below is a constant stream of 1's.
On the screenshot below you can check 2 glider streams, one of them has a period of 30 and another one has a period of 60, but, if we measure them in one spot with a period of 30, we will see that the bottom stream is a constant stream of 1's, while the top stream's content is 1, 0, 1, 0...
Designing Gates
First of all we will make NOT gate. This gate will take the input stream of gliders (the one coming from the right top) and inverse it.
It'll do so by using a specific trait of gliders - if they collide in just the right time, they annihilate each other. If we collide the input stream with a constant stream, for every glider in an input stream there will be a corresponding emptiness inside the constant stream output (since input stream glider and constant stream glider annihilate each other). But for every empty spot inside the input stream, there will be a glider coming from constant stream as there will be nothing to annihilate it with.
If we add one more stream and make it point towards the constant stream the way it can annihilate gliders, we'll get AND gate. If glider is present in input A stream, it will annihilate the glider in constant stream and let input B go through unaffected.
If glider is not present in input A stream, it will not block the constant stream and input B, whatever it is, will not go through it.
The function we've described (if a is 1 then b else 0) is equivalent to a && b or AND gate.
One thing to notice is that input A and B actually should have an offset to each other. The glider in input B that corresponds to glider in input A comes 60 generations later.
If we add one more stream we'll get a complicated picture. I pointed out all the streams and all the collision places, so you can have a better understanding.
One of the "side effects" of AND gate is a constant stream, after all the collisions it implements not (A or B) expression, which, if being modified with NOT gate, results in not (not (A or B)) or A or B, which is OR gate.
If we get back to just one collision between 2 streams, we'll get a boolean inhibition function.
Now you should be good to make any logic circuit using these gates, feel free to play around inside the repo I've made and comment.
Top comments (0)