-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathqft.html
98 lines (98 loc) · 4.66 KB
/
qft.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
<!doctype html>
<html>
<head>
<title>Kenny Zhang - Projects - QFT</title>
<meta charset="utf-8" />
<link rel="stylesheet" href="/styles/global.css" />
<link rel="icon" href="/images/icon16.png" type="image/png" sizes="16x16" />
<link rel="icon" href="/images/icon32.png" type="image/png" sizes="32x32" />
<script src="/scripts/includes.js"></script>
</head>
<body>
<div class="include include_main_header"></div>
<div class="include include_navbar"></div>
<div class="hflex">
<div>
<p>
On the Code Golf and Coding Challenges Stack Exchange, there was a
long standing open problem to
<a href="https://codegolf.stackexchange.com/q/11880/52152">
Build a working game of Tetris in Conway's Game of Life
</a>
.
When I first saw this problem in high school, I completely disregarded
it as something I could solve or contribute to.
But it sat in the back of my head, nagging at me, and every now and
then I'd check back in, and one day I noticed that there was actually
a group of people working on a solution.
</p>
<p>
The plan was to abstract away from plain Conway's Game of Life using
an existing pattern called the OTCA Metapixel, which allows individual
metapixels to follow different simulation rules.
Then, using the rule variations — which we called VarLife
— simple wires and logic gates could be designed.
The logic gates would be designed on a standard 11×11 grid with
strict timings so that they are compatible when assembled together.
Using the logic gates, more complex hardware necessary for a simple
computer architecture could be built.
Finally, Tetris could be programmed in this computer's assembly
language.
</p>
<p>
That was the plan, anyways.
When I joined, while there was a system for how to make ROM, RAM, and
other circuitry components, but it all seemed pretty clunky to me.
No one had come up with a dedicated latching mechanism, and RAM was
going to be designed by keeping data in loops.
</p>
<p>
As I got to tinkering with VarLife, I found some more compact delay
circuitry and was able to shrink down a lot of the existing circuits.
I devised a latching mechanism that allowed the creating of a much
more compact synchronizer and RAM.
I also worked out the details of the read queue, one of the last
components that needed to be designed for the computer.
Admittedly, my read queue looked like a mess of spaghetti, but it did
work.
</p>
<p>
Then also came the conversion from the rule variation simulator to
actual Game of Life metapixels.
The original script we had was extraordinarily inefficient, taking
multiple hours to generate a file whose size is in the gigabyte range.
I wrote an improved script leveraging a different file format that is
better suited to handle the inherent repetitveness of our pattern, and
reduced the runtime down to a handful of seconds, and the output file
size down to the hundred kilobyte range.
</p>
<p>
Once this project was done and we had written everything up for our
Stack Exchange posts, I had become so more familiar with tinkering in
Varlife that I had the urge to redesign the computer.
I wanted to use 8×8 tiles instead of 11×11 because the
Game of Life simulator we were using runs more efficiently if the
pattern repeats on a power of 2.
I also believed I could compact and clean up some of my circuitry
further, especially the rat's nest I had made for the read queue.
I enjoyed experimenting with creating a computer in a very esoteric
environment, and learned a lot about computer hardware in the process.
</p>
</div>
<div class="hfill"></div>
<figure>
<a class="expand_image" href="#tetris8_full">
<img class="pixel" src="/images/Tetris8_thumb.png" width="472" height="472" />
</a>
<a id="tetris8_full" class="overlay" href="#">
<div class="overlay_content">
<img class="pixel" src="/images/Tetris8.png" width="944" height="3680" />
</div>
</a>
<figcaption>
A snapshot of the Varlife computer running a game of Tetris.
</figcaption>
</figure>
</div>
</body>
</html>