Conway’s Game of Life in HD

We’re going to have to take [Mike’s] word for it that he built Conway’s Game of Life with high-definition video output. That’s because this screenshot is his only proof and it looks a bit fuzzy to us. But we are interested in the project which used an FPGA to generate a 1080p VGA output of the classic programming challenge.

One of the biggest benefits of using an FPGA for this application is the hardware’s parallel processing ability. For every frame of the game, the area around each living cell must be analyzed to produce the next evolutionary step. Most of the time this means processing all of the pixels in the playing area, which is the case here. [Mike] is using VHDL to program a Papilio Plus which has a Spartan 6 chip on it. He separated his code into the different components when writing about it. This makes it easy to find the chunks relating to the game if that’s what you’re interested in. If you just want to see how he implemented the VGA interface that’s well documented as well.

If you’re not familiar, Conway’s Game of Life has simple rules regarding when a cell will live, die, or be reborn. As [Mike] points out, every programmer should give it a shot at some point. We’ve seen many iterations from the very large to the very small.

8 thoughts on “Conway’s Game of Life in HD

  1. Ahh, brings back memories of coding it in assembler on a 10MHz PC AT using the 80×40 char video ram for a super fast memory array and the two nibbles for the current and new generation – got a smoking 15 iterations per second!

  2. I don’t think that’s a good candidate application for an FPGA. He uses a brute force method and only manages 60 iterations per second, whereas PC programs can use techniques such as memoization to compute billions of iterations per second.

    Maybe something such as quadratic fractals which don’t really have shortcuts may have been a better choice.

    1. If your design goal is to calculate the distant future this isn’t a good design – But if you want to display every frame at a stable 60Hz, regardless of complexity of the scene, this is a reasonable way to go.

      But the technology limit for brute-forcing on an FPGA is far higher than my little project.

      The current (unoptimized) design uses only 8% of my small FPGA. If I was to use a block RAM for the delay lines it would need only 5%. With a bit of extra design work the “Life Engine” component could be ‘chained’, as it just receives a stream of bytes and generates a new one. The outgoing stream could be feed into another instance, and this “n+2″ stream could then be feed into another instance… and so on

      This chaining could go on for something like 10 levels on my small FPGA, allowing it to achieve a consistent 600 generations per second (only displaying 1 in 10).

      On a high end FPGA, where you have more internal memory it would be possible to buffer the whole frame, and the extra logic cells would allow maybe 150 levels of chaining, giving 9000 generations per second – when using clocking @ approx 72MHz.

      But as the frame would be buffered, the calculation logic could run 2 or three times faster before reaching the low end SRAM’s 10ns cycle time. making 20,000 generations per second possible (300+ times faster than my project).

      The important note is that this is regardless of a frame’s complexity – a busy frame updates just as quick as a slow frame.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s