Goats and Tigers now available on iPhone  

Back to Life for iPhone Main Page
Back to 1-Dimensional Pattern Matching

2-D Pattern Matching on a Cellular Automata Board

The applet on this page builds on the previous applet which matched 1-dimensional patterns. It matches 2-dimensional patterns on a 2-dimensional cellular automata board by dividing the pattern into a series of 1-dimensional patterns (one for each row of the pattern) and using the 1-d matching algorithm developed in the previous applet to search for each row in turn.

Pattern Matching

A integer containing the three bits1 starting from the x-co-ordinate of the bit currently being examined2 is created, as described in the previous page. This is then compared to the first line of the pattern. If and only if this matches the first line of the pattern then the bits at the same offset in the two bitboards below are examined.

for(int i = 0; i < 29; i++)
{
    for(int j = 0; j < 29; j++)
    {
        int k;
        for(k = 0; k < 3; k++)
        {
            int threeBits = (int)((this.bitboard[i + k] >> j) & 7);
            if(pattern[k] != threeBits)
            {
                break;
            }
        }
        if(k == 3)
        {
            for(int a = 0; a < 3; a++)
            {
                matches[i + a] |= 7 << 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 3 - Rotating 2-D Dimensional patterns on a bitboard

Footnotes

1. The previous applet matched patterns four bits in length. This applet matches 3x3 patterns because the probability of a 4x4 pattern occurring on a 32x32 board are too low for this demonstration.

2. Only the first 30 of the 32 rows are examined. This is because the applet does not support wrapping around (i.e. patterns which begin on the bottom rows of the board and continue on the top rows) so a pattern three rows high cannot begin below the 30th row of the board.