Goats and Tigers now available on iPhone  

Back to Life for iPhone Main Page

1-D Pattern Matching on a Cellular Automata Board

The applet on this page represents the first stage in creating a cellular automata application that can quickly match patterns (such as technologies like gliders and blinkers) in frames. It demonstrates matching a 1-dimensional bit pattern in one direction using bitwise arithmetic. It is part of a project to write an iPhone version of Conway's Game of Life which can highlight occurrences of technologies as they appear on the board in real time. Below is an explanation of how the applet functions. This explanation assumes the reader has some familiarity with bitboards. For a detailed example of bitboards this tutorial is highly recommended.

Using Bitboards for Data Storage

The applet represents a 32x32 cellular automata board using an array of 32 unsigned 32-bit integers1.

private long[] bitboard = new long[32];
The board is populated at random2.
for(int i = 0; i < 32; i++)
{
    this.bitboard[i] = (int)(Math.random() * Integer.MAX_VALUE);
}
A random pattern of four bits is then generated:
this.pattern = (int)(Math.random() * 16);

Pattern Matching

The app then iterates over every bit in every bitboard searching for the random pattern. It does this by creating an integer from the four bits starting from the x-co-ordinate of the bit currently being examined. This integer will equal the integer value of the random pattern if and only if the four bits at this offset of the bitboard match the pattern. This method is much faster than comparing each bit of the pattern to the corresponding bit on the bitboard one at a time. The four bits of the bitboard storing cells in which matches have been discovered are all set in a single line of code by doing a bitwise-OR with the number 15 (1111 in binary); this is obviously faster than setting each cell in the matches bitboard one at a time.

for(int i = 0; i < 32; i++)
{
    for(int j = 0; j < 32; j++)
    {
        int fourBits = (int)((this.bitboard[i] >> j) & 15);

        if(pattern == fourBits)
        {
            this.matches[i] |= 15 << j;
        }
    }
}

Applet

Your browser understands the <APPLET> tag but isn't running the applet, for some reason. Your browser is ignoring the <APPLET> tag!

Java Source Code

CellularAutomataApplet.java - Full source for the applet above.

Next

Part 2 - 2-Dimensional Pattern Matching

Footnotes

1. Better performance could be achieved using unsigned 64-bit (long) integers. Java does not support such a data type so the Applet actually uses signed long integers and treats them as unsigned 32-bit integers. The XCode implementation of Life for iPhone is intended to use unsigned longs.

2. The code snippet will never populate the left-most bit of the bitboard. The applet currently compensates for this by adding the following code inside the for-loop:
if(Math.random() >= 0.5)
    this.bitboard[i] |= 1 << 31;