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 bits^{1} starting from the x-co-ordinate of the bit currently being
examined^{2} 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

### 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.