ChipKIT: Conway's Game of Life on VGA

Life: Classic version of Conway's Game of Life using a chipKIT UNO32.

After the success of the ChipKIT pong demo I started to think about the ways to improve the graphics output and came up with the idea of a coarse pixel display. This is a more traditional pixel based display where a rigid grid is displayed on the screen rather than the more vector based display that I had used previously. This demands more of the CPU time because it has to copy the pixels to the display manually as there is no DMA on the UNO32, rather than only having to display the colour for a tiny fraction of each display line like the pong game did.

If you haven't looked at my VGA Primer and VGA pong articles you might want to take a look as this project builds on what was done previously.

Background

Conway's Game of Life is a zero player game or cellular automata where the state of the "game board" is determined by applying the rules to the previous game board state. Essentially this produces some pretty patterns on an array of cells. LED based implementations are popular and some have been designed that can communicate with neighbours allowing tiled displays, but the cheapest way to make a really big one is on a computer screen.

I've been interested in them for years as an interesting programming challenge and remember my first very naive implementation on a PC being beaten by the demo on the Horizons tape that came with Sinclair ZX Spectrums. It struck me when I was looking at the pong game that the display could be made into a coarse pixel display which would be ideal for displaying a game of life implementation, and the rules of the game are easily simple enough for such a powerful processor to handle easily.

Setup

As with the pong game, the setup needs to enable a PWM peripheral for the H_SYNC signal and tie this to an interrupt. There's also the usual setup of the I/O pins for other functions. The screen driver needs a couple of flags setting (displaying screen and ready screen which take care of which buffer is on display (read-only) and which is being updated) and a row-counter initialised etc.

Initialising the game board uses the Arduino random function and initialises this with a read from the unconnected analogue pin AN0. I noticed this isn't really very random on the ChipKIT however, it reads almost exactly 0 when un-driven. This became less important after the new game button was added as you very soon got far enough into the pseudo-random sequence that you didn't remember this particular game grid, but as this is a common trick it's worth noting if you want something to be properly random.

Finally the system counter interrupt is disabled. This is the interrupt that allows for delay() calls in the Arduino stack so these can't be used after this. It is disabled to improve the stability of the display. In the pong game I found it actually caused the screen to loose sync occasionally when the system counter interrupt went off at just the wrong time.

Game Implementation

For the rules check out the Wikipedia article. The game logic is done in a very fast routine that I later had to slow down to keep the steps visible. It uses a set of for loops to deal firstly with all but the edge pixels which are very straight forward and simply applies the rules of the game to each pixel using the previous frame buffer as the input information. Next a pair of for loops deal with all the edge pixels on the vertical and horizontal edges and wraps the game board around the screen. Finally the four corners are dealt with in turn.

Coding each of these different pixel types (middle, edge and corner) as a separate loop case takes much more code space but ensures that the loops are very fast because they don't need to check for boundary conditions every time. Because each new board is dependent on the previous state of each pixel and its neighbours, the old board must be kept in memory unaltered to ensure all neighbours are from the same generation, until the entire new board is calculated. This fit very well with the double buffered display driver (see below) as the last generation (which is being displayed) is only needed for read access and so won't cause screen artefacts when accessed.

This code is pure C and I implemented and tested it on my linux box and ran it on the command line to debug before I just copy and pasted it into the Arduino sketch.

The dead/alive state of the cell is determined by its least significant bit. This allows it to be masked with a simple AND operation and then added up to find the number of living neighbours, note that this only works because the colour for alive pixels uses this last bit and the colour for dead pixels doesn't. As long as there is one bit different in the two colours and this is correctly masked this method can be used. Note that for bits other than the least significant one the sum of neighbours will be a multiple of the number alive.

Display Driver

The display on this version of the ChipKIT VGA driver is pixel based raster graphics. It uses a simplified version of the interrupt driven code from the [pong game][], so the H_SYNC is driven by a PWM output which causes an interrupt each time it is generated. In this interrupt the CPU checks which line is being generated, if it's a displayed line it pushes out the pixels from the active display buffer using the 8 bit parallel port the same as pong did. The timing for the pixels is controlled with assembly coded nop instructions and was tweaked with my 'scope until it worked. Each of the blocks on the screen represents an 8x8 block of the 640x480 pixels the screen is expecting. This means it is held eight times as long on the line, and the same data is displayed on eight lines. I don't think this is really a time constraint for the CPU (there are a lot of nop instruction in each pixel which could be drawing more detail) but it is a memory constraint, there simply isn't enough memory to make the display any bigger than 80x60 pixels at 1 byte per pixel.

There's still the logic for generating a V_SYNC signal in the last two lines of the vertical screen, and there's some additional code to pad the beginning of the line to centre the image.

The image on the screen is "double buffered" this means that while one frame is being written by the main loop, there is a second chunk of memory which is only being read and is displayed to the screen. When the frame has been all displayed, the last thing the interrupt code does is set the "display frame" value to match the "ready frame" value. When the display driver is drawing pixels it always takes them from the buffer indicated by "display frame" the main loop works on the buffer that isn't indicated by "display frame" until it is done then sets "ready frame" to indicate the frame it has just drawn. Next time the display gets to the end of the screen it will switch to drawing the new frame and once "display frame" and "ready frame" are equal again the main loop can start drawing the next frame. This arrangement ensures that there is no flicker on the screen no matter how far through drawing the frame the main loop is when the display completes a frame.

Restart Button

To make the game a bit more exciting and interactive I added a large red button that resets the game to a new initial board layout. The code handles this in software rather than tying the button into the reset line of the controller. This means that the display driver is never interrupted so the monitor won't go blank. I found that this improved the experience greatly because the monitors I tried all took several seconds to re-initialise after the display driver is stopped and started again, so after resetting the controller you would have to wait an uncomfortably long time before you could see it in action again.

Section:

Projects

Tags:

PIC,

ChipKit,

arduino,

VGA,

Open Hardware

Comments

Posting comments is not currently possible. If you want to discuss this article you can reach me on twitter or via email.