Creating animated GIFs from OpenSCAD

animated

I do almost all my physical designs in OpenSCAD, and sometimes I want to post an image of my models. Since these are 3D models we’re talking about, a static image is kinda insufficient, but an animated GIF can do the job nicely.

OpenSCAD has an animation feature which allows you to create models that can mutate relative to time. While it’s primitive, it lets you slap a time-based rotate around your top-level object to get a nice 360 spin view. Then, when you select Animate from the View menu, the display will animate.

To go from the animated view in OpenSCAD to an animated GIF, check the “Dump Images” checkbox in the animation controls. This will cause each frame to be written out to a PNG file in the same directory as the .scad file. I like to check the box and then wait for the animation to repeat a little more than once to be sure that all the images have been dumped.

Once all the images are on disk, converting them into an animated GIF is surprisingly simple if you have ImageMagick’s convert utility. Here’s the command I use to convert a bunch of frames into an animated GIF:

The only real gotcha here is the “-set delay” option, which has a cryptic syntax: NxM means “N units of 1 second divided by M”. Thus, “1×24″ means 1/24 of a second. I’ve had the most success setting the frame delay this way, but there are probably other ways to do it.

Designing a capacitive touch wheel in OpenSCAD and EAGLE

I’m a big fan of DIY capacitive touch sensors. Without any custom parts or special fabrication techniques (beyond regular PCB creation), you can create really impressive interfaces. I first used this on the Question Block Lamp (Getting ready to ship! Order yours now!), and ever since I’ve been looking for great places to apply the technique.

Recently, I decided that one of my projects would really benefit from the addition of a capacitive touch wheel. I didn’t want to re-invent the wheel, so to speak, so I started Googling for designs.

The design

The page for the Arduino CapSense library sent me looking for the Quantum Scrollwheel sensor datasheet, which contains a handy schematic for a scroll wheel. wheel_schematic So how’s this thing supposed to work? The wheel is composed of three separate, identical electrodes that are tessellated together to form a ring. Each electrode is interleaved with its neighbors such that as you move away from the center of one electrode, the current electrode exposes less and less surface area while the next one exposes more and more. This means that if you measure the capacitance values of all three electrodes in succession, you should see approximately complimentary values on two of them, and an “untouched” value on the third. This should be sufficient information to figure out the orientation of the touch.

Ok, so how do we draw this?

The schematic for this wheel design is straight-forward enough, but this is far from an easy shape to draw. As I highlighted in a previous post, EAGLE really isn’t going to help you draw something like this, so you need to turn to another program to do it and then import the results. My tool of choice is OpenSCAD, so I got to work on a script to generate this shape.

Since all the electrodes are identical, we really only have to draw one and then rotate some copies around to complete the tessellation. Only, this shape is a bit unique – the curved triangular sections don’t lend themselves to being described with simple OpenSCAD primitives.

The first approach I considered was to think of each curved triangle is as a regular 2D triangle, only rendered incrementally along an arc. Polar coordinates would make this especially easy to describe. While this feels like it would be an elegant way to express these sections, OpenSCAD isn’t friendly to this approach. You can define arbitrary polygons, but you can’t add points to a polygon with any sort of native loop. In the past, when I had no other choice, I’ve written a Ruby script to generate the point list manually and then pasted them into my OpenSCAD script. This is clunky and involved, so I try to avoid it if at all possible.

However, I came up with another way to express this shape that is more amenable to being generated directly in OpenSCAD. It’s a technique I found on the OpenSCAD mailing list that the creator referred to as “chain hull”. A chain hull of a list of primitives is the union of the convex hulls of neighboring pairs of said primitives. Did you follow that? This page has a good visual example of the operation in action. I think chain hulling is a brilliant use of the primitive functions available in OpenSCAD and allows for complex shapes to be described very concisely.

To build our curved triangle sections with a chain hull, I laid out an arc of very thin squares ranging from the minimum width to the maximum width in a linear fashion. The chain hull magic takes each pair of squares, hulls them, and then unions all the results. Here’s the code that generates the shape:

And here’s a view of the intermediate shapes and the resulting chain hull:

hull_illustration

The base shapes, and the chain hull that gets drawn around them.

With a module built to create these curved triangles, the rest of the script is glue code to put the triangles in the right places. I wrote one module to generate the concentric/alternating triangles for an entire electrode, and then another module to generate the whole scroll wheel by rotating three electrodes into their proper positions. The final result comes out looking pretty good:

scroll_wheel

One gotcha I figured out in the course of this project is that EAGLE really doesn’t like to have zero-width lines, even if they’re just describing the outline of a polygon. To account for this, I drew the wheel sections a tiny bit smaller to account for the line width I’d use in EAGLE. This is not unlike accounting for the kerf on a laser cutter, so if you’ve done that before you’ll be familiar.

Getting it into EAGLE

The next step is getting it out of OpenSCAD and into EAGLE. I wrote about using OpenSCAD shapes as board outlines in another post, but this case is a little different. Board outlines can just be simple wires, but polygons need to be closed shapes. The DXFs that come out of OpenSCAD are just collections of segments. I needed a way to convert these segment lists into ordered lists of points that they could be entered with the POLYGON command. So, of course, I wrote a Ruby script to do it.

The operation for converting a set of segments into a ordered list of points is pretty easy. The trick is to think of the list of segments as edges in a graph, and then the objective becomes traversing the graph and outputting a list of connected components. To do this, first I read all the segments into memory, then put them into a map indexed by their start point. Then I pick an arbitrary segment, write its two points to a list, and then use the second point to do a map lookup for the next segment that matches it. This process then repeats with the second point of each segment until we’re back to the start point. This process nets a list of lists of points, each list being a closed polygon. Once all the segments appear in a polygon, we’re done, and from there it’s easy to generate a set of EAGLE commands and write them into a .scr file.

Before I run this generated script from the EAGLE command prompt, I do one hand editing pass to name the polygons so that they are connected to the proper signals in the schematic. With that done, I set the my desired line width to match what I used in the OpenSCAD script, and then load the polygons into EAGLE by running the command “script poly” where poly is the name of the .scr file created in the last step.

When EAGLE renders the polygons, they’ll start out empty with dotted borders. To get them filled in, you need to route connections to them and then run the RATSNEST command. If you’re planning to use the autorouter, a good practice at this point is to use the restrict and keepout layers to defend these polygons. If you cover the electrodes with a polygon in tRestrict or bRestrict layer (depending on whether your electrode is on the top or bottom), then the autorouter will leave it alone when routing other traces. Just make sure to hand-route a connection point through the protective layer, and then the autorouter will be able to take it from there. (tRestrict/bRestrict are just hints to the autorouter and will not trigger design rule warnings. Pretty handy!)

touch_wheel_on_board

The whole bottom of the board, featuring the the scroll wheel!

Next steps

I just ordered a batch of boards using the scroll wheel described in this post, so when they arrive, I will populate one and get to work on creating a library for easily reading out a position. Stay tuned for a future post!

Simple constant current LED driver

Here’s a simple circuit for driving LEDs at constant current. I like this one because it can be built with a variety of different components based on what you have on hand. I built my version with two 2N2222A transistors and a sense resistor from my resistor kit.

constant_current_driver

How does it work?

A small current on the CONTROL line causes the DRIVE transistor to switch on and sink through the SENSE resistor. The FEEDBACK transistor only operates when the voltage at the SENSE resistor is greater than its VBE, or turn-on voltage. When it turns on, it draws some current away from the base of the DRIVE transistor, reducing its gain and causing it to drop more voltage. This negative feedback will cause the whole system to equilibrate such that the SENSE resistor is seeing exactly the FEEDBACK transistor’s VBE. 

Why is this better than a ballast resistor?

You can drive a variety of LEDs with different forward voltages without worrying about changing any of the components (provided that you are comfortable using the same current). The DRIVE transistor will just drop more or less volts as necessary.

Also, if you’re trying to drive some high-current LEDs, you’re more likely to have common transistors that can handle the power dissipation than you are to have high wattage resistors. This makes prototyping and experimentation easier.

Finally, depending on your LEDs and your power supply, you could end up using fewer components by driving multiple LEDs in a string, rather than driving each LED separately.

Sizing components and calculating current and power

LEDs: You can use as many LEDs as you’d like provided that their combined forward voltage is less than the supply voltage minus VBE.

Power supply: Your input voltage needs to be at least the sum of the forward voltages of your LED string plus the minimum drop across the DRIVE transistor plus the VBE of your FEEDBACK transistor. Otherwise there won’t be enough voltage to turn on the LEDs.

Transistors: Anything NPN (or N-channel, if you’re using MOSFETs) you have handy has the potential to work. The most important thing to think about is how much voltage you’re expecting it to drop for you and what that means for power dissipation. This transistor will be acting in its linear region, so any voltage it doesn’t pass on from collector to emitter will turn into heat! For instance, let’s use an example of a 12V power supply and two white LEDs with a 3.2V forward voltage. The drive transistor will have to drop 12 V – (2 * 3.2 V + 0.6 V) = 5 V. If your target current is, say, 200 mA, then the transistor will be dissipating 5 V * 0.2 A = 1 watt of power. For some transistors this is no problem, but for others that’s a death sentence. Read your datasheet!

Sense resistor: This resistor sets the amount of current you want to pass through the LEDs. You can compute its value by taking the VBE of your FEEDBACK transistor and dividing by desired current. For instance, if you’re using a 2n2222A transistor with a VBE of 0.6 V, and you want to sink 200 mA of current, you would need a 3 ohm resistor. Power dissipation is straight forward, since you know the voltage and the current. Using our existing example, a 3 ohm sense resistor would see 0.6 V * 0.2 A = 0.12 watts. That’s small enough that you can use 1/4 watt resistors from a part kit with little worry.

Over-driving LEDs for brightness

Most of the time when I’m driving an LED, I do it with a simple ballast resistor, and that’s all there is to it. Lately, however, I’ve been working on a few LED matrix projects, and while it’s certainly possible to use the same simple resistor approach, this leads to a very dim display. (Since any given LED’s duty cycle is 1/N max, they appear much dimmer than they normally would.) 

The good news is that there’s a straightforward solution to this problem. LEDs have a rated forward current, but they also have a rated peak current, specified at a given pulse width and duty cycle. For instance, these red LEDs are rated for 30mA forward current and 185mA peak in 0.1 ms pulses at 10% duty cycle. Why is this stat useful? As long as you stick to the pulse width and duty cycle parameters, you can intermittently drive an LED at an excess current and get a brighter light without burning it out. 

There is a risk in using this setup, though. If for some reason your PWM signal were to lock up in the “high” state, then the pulse width limitations would be exceeded and you’ll probably fry the LED in an instant. This means you need to be especially cautious during development – crashing your microcontroller at the wrong time can be costly!

While the theory of this is straight-forward, I wanted to test how it actually looks in practice before I integrated it into my design. If it was only moderately brighter, I didn’t want to spend the energy (and money) on adding an array of transistors to my board.

breadboard_setup

My test setup.

I decided to throw together a test setup that would allow me to compare brightness of an LED at its full-on steady current, one PWM’d with a ballast resistor to keep it at its steady current, and one at peak current and PWM’d. This sets up a comparison between the maximum brightness, the brightness of the same LED in a naively driven matrix, and finally the same LED over-driven.

The LEDs I’m using here are surface mount in a 1206 package. Saying that they are very small is an understatement. They are by no means breadboard compatible, so the first step was creating a simple breakout board.

I used a piece of pre-drilled perfboard with a solid copper pour on one side to make the breakout. I marked off a few columns of 6 holes each so that it would span the IC gutter on a breadboard, then cut the piece out with a pair of aircraft snips. Next, I used a utility knife and a straightedge to score the copper and separate the columns from each other, and then did one horizontal stroke to make a grid of 1×3 hole pads.

breakout_board_detail

Detail of the LED breakout board

Next, I soldered two rows of 0.1″ header to the top and bottom of the board for mating with the breadboard. Then, I hand-soldered 6 LEDs, 3 red and 3 green, onto the board. (Judicious use of continuity tester and solder sucker not optional.) Finally, I used a file to chop one corner as an orientation indicator and then cleaned up the rough edges.

To prove that everything was working, I started out by connecting the steady current resistor and probed all the LEDs. Everything lit up fine. With the baseline established, the next step was to set up the PWM signal. According to this page, the Arduino’s built-in analogWrite() PWM runs at about 500Hz, which is too slow for the target pulse width. Since I didn’t need crazy precision or performance here, I decided to quickly write up an Arduino sketch that toggled the output pin manually and used delayMicros() to set the interval. The sketch turned out to be pretty simple:

To verify that this was giving the output I expected, I hooked up the output pin to my handy DSO Nano. On the first try I ended up with a 996 Hz frequency and good pulse width. The error in the frequency is probably due to the fact that there’s overhead to toggling pins and calling delayMicros(). I suspect I could dial it into precisely 1000 Hz by guess and test on the delay durations, but it’s not that important at this point. In the real production scenario, I’ll be using a hardware timer and it’ll be worth getting it exactly right.

Connecting the PWM output to the second LED was straight forward, though I did add a NPN transistor in between the output pin and the LED so that it could drive all the PWM inputs without any worries about current draw.

The over-driven LED was the most complicated to set up. I plugged the peak current number into an LED resistor calculator, and it told me I needed a 12 ohm, 2 watt resistor. Yikes! I certainly don’t have anything like that on hand. Rather than putting a whole ton of resistors in parallel, I wired up a simple constant current LED driver circuit using some common transistors and resistors. I’ll leave the discussion of that driver circuit for another time, but the cool thing about it is that it allows the transistors to do all the heavy wattage dissipation while the resistors see a tiny load. 

With everything wired up, I powered it on to assess the results:

Closeup of the final brightness test. Hooray for DSLR cameras!

Closeup of the final brightness test. Hooray for DSLR cameras!

I would say that the PWM-only LED is substantially dimmer, and the overdriven LED is almost but not quite as bright as the steady-on LED. This turned out to be exactly the sort of obvious difference I was looking for. It seems well worth adding the additional circuitry to get a much brighter display.

Cellular Chronometer Part 2: The PCB

I’m designing an LED matrix clock that plays Conway’s Game of Life to evolve a representation of the current time. See the whole series of blog posts about the project here.

At the heart of this project is the PCB. I set out to push my limits a bit, and I certainly succeeded at that. This is by far the most complex board I’ve ever worked on, owing mostly the sheer number of components (132 LEDs, 14 resistors, 4 capacitors, a crystal, a microcontroller, and a linear regulator) crammed in such a small space (25 x 100 mm).

The basic layout is that the front of the board is the LED matrix, while the back hosts all the support circuitry. Let’s look at each of those in turn.

The matrix

top

Laying out a grid of LEDs should be easy, right? Well, not that easy. Immediately after I got done drawing the schematic for the matrix, I discovered that the LEDs I selected simply weren’t going to fit in the available space. Faced with the prospect of 132 separate REPLACE commands, I quickly developed the beginnings of what I’m now considering my EAGLE secret weapon: what I’m calling external scripting. I wrote a simple Ruby script that generated all the names of the LEDs, and then piped that through some bash magic to compose the commands I needed. Once I pasted the results into the EAGLE command bar, boom, all LEDs replaced in one fell swoop.

Not an easy schematic to draw. Yes, I did it by hand.

Not an easy schematic to draw. Yes, I did it by hand.

This technique worked so well that I knew I’d take advantage of it again. I didn’t have to wait long. As soon as I switched from the schematic to the board, I found myself needing to actually position the LEDs. I tried making the grid match my desired spacing, but that was proving too tricky, especially when combined with having to position all the LEDs in a precise order. Scripting to the rescue!

A word on the LED layout scheme

A quick aside: at this point in the project, I had to decide on a layout scheme for the LEDs that both made it easy to route the board as well as write code to map the LEDs into a 2D grid. Charlieplex LEDs are addressed by (high pin, low pin) pairs, but I’ll need to interact with them from a more (x, y) perspective. This would not be something easy to change later, as its encoded in the hardware itself.

I elected to go with a strategy that put high/low pairs and their inverse next to each other, thinking that this would limit the number of far-flung connections needed. These pairs are laid out in a sort of round-robin fashion so that they’re all exercised. The result ends up looking like this:

charlie_scheme_illustration

Anyways. Using the earlier technique, I wrote another Ruby script that generated EAGLE commands to position all the LEDs according to this scheme. The scripting here was really crucial, because I had to try out multiple tweaks before I got everything just right, and without a script, I would have been committing to several hundred clicks per experiment!

Supporting electronics

board_bottom

The ATMEGA is the centerpiece of the back of the board. Nearby is the 16MHz crystal, and to either side are the momentary switches that allow the setting of the time. The top edge of the board is the bank of current-limiting resistors needed to drive the LEDs. Finally, on the edges of the board, there’s a 6-pin ICSP programming header and your standard LM317 linear regulator circuit set up to output 5V.

A note on the power supply. I don’t think this thing is going to be a power hog, and I’d ultimately like it to be pretty compact and beautiful, so I’m planning to just stick a 9V battery in there and call it a day. This is sorta phoning it in, but since the ICSP header breaks out the 5V bus, I figure I can always solder in a USB cable and power it from a wall wart if I have to.

Putting it together

I sent the Gerber files off to Seeed Studio’s FusionPCB service for production. About a month later, the boards turned up, and I couldn’t wait to assemble them.

2013-09-11 18.55.49

When reading about other folks’ LED matrix projects online, a common complaint was that it was difficult to get all the SMD LEDs aligned properly without some sort of jig. I didn’t want to mess around with creating a special fab tool, so instead I made the conscious choice to go with solder paste and hot air reflow. The idea was that I’d get the automatic alignment effect that solder paste + hot air exhibits.

Here, I made a miscalculation. Instead of making a solder paste stencil and applying it with a putty knife (which I’ve done before!), I decided to just dispense the paste directly from the syringe. This was a disaster. The paste I have has gotten kind of old, making it less apt to flow out the tiny syringe tips I have. Plus, I somehow lost the plunger that came with the paste, and was stuck using a Sharpie marker as a makeshift plunger. Not what I would call ergonomic. Still, this might have been OK for a few tens of pads… but I was applying paste to both sides of 125 LEDs! It took well over an hour, and by the end, I was in a lot of pain and didn’t have the patience to do it correctly. Consequently, a lot of the later LEDs got a huge glop of paste that sometimes bridged their pads and was just generally poorly done.

Populating the board was painstaking, but nowhere near as difficult as the pasting. When it was done, I fired up my trusty heat gun to reflow the board. About 85% of the LEDs did exactly what I was hoping for and sucked themselves right into place, but the rest pulled away from their pads, tombstoned, or clearly bridged under. I ended up spending another hour or so just going through and doing rework on the bad LEDs.

matrix_populated

With the matrix side behind me, I turned my attention to the back of the board. At this point I was pretty done with solder paste, so I switched over to the iron. First up was the microcontroller. I used the “flow and wick” technique, which worked like a charm - after I refreshed my memory from this excellent SparkFun tutorial. (Heres a better video that illustrates the technique more closely.) The rest of the components were no problem – I just tinned the pads, positioned the components with tweezers, and then reflowed the pads until the pieces stuck. The one exception here was the crystal, which doesn’t have any exposed leads. For this guy, I just tinned the pads, then positioned the crystal and hit it with the hot air gun. I was relieved when I saw the crystal shift and adjust itself into place. Phew.

back_populated

Turning it on

With the board fully populated, it was time to turn it on. It’s always scary to do the first power on test of a new project, particularly one where it’s impossible to do incremental tests. I flashed a spare Arduino with with ArduinoISP sketch, hooked it up to the programming header, and proceeded to burn a bootloader. Astoundingly, it worked the first time!

Next, it was time to test the matrix itself. I had already developed a Charlieplex matrix driver during my minimal prototyping stage, but the new board was really different and needed a new driver. But before I dove into porting the complex logic onto the new board, I wrote a trivial sketch that just exercised all the LEDs in sequence by manually toggling the pin pairs according to the scheme described above.

Guess what? It didn’t work. At least, not all of it. There were numerous spots in the matrix where LEDs were skipped, and a few spots where instead of a single LED lighting, multiple LEDs would glow dimly. It turns out there were a few problems here. The first was that my test sketch accidentally referenced the same pin twice, making it do a weird rewind-stutter thing during the test sweep. That one took an embarrassingly long time to find. With that software error out of the way, I proceeded from one LED to the next, debugging each misbehaving one. A few of the LEDs were in backwards – a population error. Some just seemed to be busted, and worked after replacing with a spare. Whether they came off the reel that way or were damaged during reflow, who knows.

By the end of the night, I was done debugging and all the LEDs worked as expected. Hooray! No disastrous issues! Now, I could finally start on the actual production sketch.

Using an OpenSCAD shape as the board outline in EAGLE

I’ve been working on a Charlieplexed LED analog clock. The finished product will be an artfully routed PCB in a clear acrylic enclosure. Since the PCB will be the centerpiece, I want it to be pretty cool looking, including an interesting outline. The design I’m going for pictured below. It’s the union of four different rotations of the convex hull of a central circle and a smaller outer circle. Simple, right?

scad_version

While EAGLE is a pretty capable CAD package, it stops short of making it easy to lay out complex shapes like this one. On the other hand, OpenSCAD is designed with exactly this use case in mind. (Check out how easy it was to make the shape above.) So we just have to find a way to get from OpenSCAD into EAGLE. Should be simple!

OpenSCAD supports exporting 2D shapes to the DXF format. Some initial Googling made it seem like EAGLE could import DXFs, but after some clicking I found myself on a plugin page that was in German and had a link to a .EXE file. (I’m on a Mac.) Not exactly what I’m looking for.

Lacking an out of the box solution, I did what any self-respecting hacker would do, and wrote a script. DXF files are text, which is helpful, though they are in an impressively goofy format. A little searching got me to the format specification, which explained how to read the sets of points that formed line segments. With the points in hand, I had my script output a set of EAGLE WIRE commands. After switching into the “dimension” layer, I pasted the WIRE commands into the command bar. Voila, I’ve got my outline!

eagle

While it works, this script is pretty hacky. It makes a bunch of assumptions about the structure of the file that might not hold in DXFs generated by programs other than OpenSCAD. But given the amount of time invested, I’m pretty comfortable with the results!

 

Cellular Chronometer Part 1: Reversing the Game of Life

I’m designing an LED matrix clock that plays Conway’s Game of Life to evolve a representation of the current time. See the whole series of blog posts about the project here.

The very first step of making the Cellular Chronometer is figuring out how I’m going to make the clock display the time. As a quick refresher, Conway’s Game of Life is what’s called a “cellular automaton“, which is a set of simple rules that’s played over a grid of cells, each of which are alive or dead. You process the grid with the rules and get a new grid with a different set of cells. Cellular automata are interesting because simple starting configurations can lead to really wild phenomena like self-replicating patterns and apparent movement.

But what I want to do is be able to get the game to display specific states. I want to populate the grid with a state that I know will evolve into a digital display of the current minute. The only reasonable way I could think to do this is to craft my desired state in advance and then do a search backwards – that is, in the reverse direction of the regular Game of Life – to find prior states. This happens to be a nontrivial problem. Played forwards, the Game of Life has very simple deterministic rules, but played backwards, there are an immense number of possible configurations to examine. In computer science terms, this problem is bounded by 2^n, where n is the number of cells in the grid. 2^n gets really big really fast. Not good.

Luckily, like so many other aspects of the Game of Life, work has been done trying to efficiently search for prior game states. I figured this out after two weeks of fruitless genetic algorithms experiments when a desperate Google search led me here. While the code didn’t prove useful to me, I managed to suss out that there are several existing algorithms that do what I need. The one that I best understood is called Duparc’s Method. The key win is that instead of being 2^n in the size of the pattern, Duparc’s method is only 2^n in the height of the grid! Since my grid is only five cells tall, this makes the search into a tractable problem, even if it does turn my MacBook into a proper lap-roaster.

duparc_illustrationIt’s hard to be 100% sure if I took the same approach as Duparc, since his original research paper is written in French. The way my algorithm works is to divide the grid in half vertically again and again until I’m working with single columns, at which point I essentially rotate the column into a row apply the same subdivision algorithm again until I reach a single cell. Single cells – both alive and dead – have a nice, cacheable method for determining all their prior states. Once I have the partial answers for a single cell, I intersect them with the answers from the neighboring cell by checking the overlap between the two. If the cells shared by the two possible solutions match, then the combined solution is also viable. Partial solutions that don’t match neighbors are discarded. This same process of merging based on overlapping cells continues back up the search tree until we reach the root, at which point we have a set of possible prior generations.

Something that took me a long time to grasp fully is that the algorithm naturally has to search in a grid bigger than the one you’re starting with. The reason for this is that while true “gardens of eden” are extremely rare, if you constrain the grid to a finite number of cells, it’s not at all hard to come up with a pattern that isn’t produceable. I ultimately came up with this sort-of logical proof to convince myself on this one:

  • In a grid of N cells, there are 2^N unique configurations
  • Some of these 2^N configurations will lead to non-unique next generations (ie, all cells dead is pretty common)
  • Therefore, it cannot be possible to generate each of the 2^N initial configurations from one of the other initial configurations.

In practice, this just means that you have to allow a “gutter” of arbitrary-valued cells around your desired image. If it’s really important to trim the excess, you just select ultimate solutions that have the extra cells as dead, since that’s the same as the border on a finite grid. The risk is that you’ll filter all the possible solutions by doing so.

As I developed this algorithm, I found that the line between “ever finishes” and “never finishes” was very fine. Most of the problems stemmed from running out of memory on my 16GB MacBook. A given target grid can have millions of intermediate states, and they need to be cached to make the algorithm run in a reasonable amount of time. The tweak that I credit with getting me all the way over the line was to discard many of the intermediate answers that, while actually unique, had the same border regions as other answers. Since the merging algorithm examines only the region of overlap between two sets of sub-solutions, any non-overlapping sections don’t actually increase your chance of finding some solution, and as such they can be discarded. This does mean that not all prior states are found, but for my purposes, I only need one.

Screen Shot 2013-09-01 at 8.57.39 PM

Along with improving the algorithm, I found that I had to tweak my font. Early on I guessed that different fonts and digit spacings would have an effect on whether a given configuration was reversible. I was surprised by how many of the configurations I wanted to generate were impossible with the grid dimensions I was enforcing. I had the algorithm report a bunch of statistics while searching so that I could see (at an aggregate level) when all possible solutions were being eliminated. I learned that particular characters were difficult to reverse, like 4s, 5s, and 0s. But the one that most surprised me was the colon I added between the hours and minutes. That guy turned out to be stubborn in some of the worst cases. In the end, I had to compromise and hand-edit certain minutes so that they would reach a prior generation.

The end result of all this hard work is 720 unique start states that will each evolve into one of the minutes of the 12-hour day. I’ll embed these states directly into the firmware for the clock so that my tiny microcontroller won’t have to do any “real” work, just run the Game of Life from each start state and advance the pointer every minute.

You can find the Ruby code for this crazy search in my GitHub repo.