Goats and Tigers now available on iPhone ## Matching Rotated Patterns on a 2-D Cellular Automata Board

The applet below generates a random NxN pattern and rotates it through 90, 180 and 270 degrees. It uses bitboards to perform the rotations faster than by calculating the rotated position of each cell individually.

### Generating the Pattern

A NxN pattern is stored as N long integers. Three rotations of this pattern are then generated, giving four patterns. Each rotation is also reflected, giving a total of eight patterns.
```int width = N;

long[] pattern0 = new long[width];
long[] pattern1 = new long[width];
long[] pattern2 = new long[width];
long[] pattern3 = new long[width];
long[] pattern4 = new long[width];
long[] pattern5 = new long[width];
long[] pattern6 = new long[width];
long[] pattern7 = new long[width];
```
The starting NxN pattern is then generated in the same as way the 3x3 is generated in the previous applet.
```for(int i = 0; i < width; i++)
pattern0[i] = (int)(Math.random() * (1 << width));
```

### Rotating the pattern 90 degrees

A 3x3 pattern could be rotated as follows:

```pattern1  = (pattern0 & 4) >> 2;
pattern1 |= (pattern0 & 4) >> 1;
pattern1 |= (pattern0 & 4);

pattern1  = (pattern0 & 2) >> 1;
pattern1 |= (pattern0 & 2);
pattern1 |= (pattern0 & 2) << 1;

pattern1  = (pattern0 & 1);
pattern1 |= (pattern0 & 1) << 1;
pattern1 |= (pattern0 & 1) << 2;
```
This can be rewritten using a for-loop to allow the same algorithm to be used for patterns of size NxN (where N is a positive integer).
```int width         = N;
int bitCompliment = 1 << width;
int maxShift      = (width / 2) * 2;
for(int i = 0; i < width; i++)
{
pattern1[i]     = 0;
bitCompliment >>= 1;
for(int j = 0; j < width; j++)
{
int shift = maxShift - i - j;

if(shift > 0)
pattern1[i] |= (pattern0[j] & bitCompliment) >> shift;
else
pattern1[i] |= (pattern0[j] & bitCompliment) << -shift;
}
}
```

Note that since bitwise shift operators do not support shifting by a negative number of bits it is necessary to check whether the shift is positive or negative1. Similar logic can be used to rotate the pattern 270 degrees. Code to do this can be found in the applet below.

### Reflecting a pattern

Each pattern is reflected by copying its nth row into the (N - n)th row of the reflection.

```for(int i = 0; i < this.width; i++)
{
pattern4[i] = pattern0[this.width - i - 1];
pattern5[i] = pattern1[this.width - i - 1];
pattern6[i] = pattern2[this.width - i - 1];
pattern7[i] = pattern3[this.width - i - 1];
}
```

### Rotating a pattern 180 degrees

This is done by first reflecting the pattern as described above then setting each bit of this reflection to the bit whose distance from the end of the board equals the first bit's distance from the start of the board.

```int maxShift = width - 1;
for(int i = 0; i < this.width; i++)
{
int shift = maxShift;
for(int j = 0; j < this.width; j++)
{
int oppositeIndex = this.width - i - 1;

if(shift > 0)
pattern2[i] |= (pattern0[oppositeIndex] & (1L << j)) << shift;
else
pattern2[i] |= (pattern0[oppositeIndex] & (1L << j)) >> -shift;

shift -= 2;
}
}
```

### 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 4 - Searching for multiple patterns

### Footnotes

1. Some processors handle shifting by negative amounts by applying the modulo operator to the number of bits to shift by. For example, shifting a 32-bit unsinged integer by -2 bits to the left would be treated as shifting it 30 bits to the left. An alternative to checking whether the shift is a negative number of bits and using the right shift operator if it is would be to always add 32 to the number of bits to shift by and modulo this by 32. This is explained in more detail in this article.