| Goats and Tigers now available on iPhone | 
|
Back to Life for iPhone Main Page
Back to 1-Dimensional Pattern Matching
Back to 2-Dimensional Pattern Matching
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[0] = (pattern0[0] & 4) >> 2; pattern1[0] |= (pattern0[1] & 4) >> 1; pattern1[0] |= (pattern0[2] & 4); pattern1[1] = (pattern0[0] & 2) >> 1; pattern1[1] |= (pattern0[1] & 2); pattern1[1] |= (pattern0[2] & 2) << 1; pattern1[2] = (pattern0[0] & 1); pattern1[2] |= (pattern0[1] & 1) << 1; pattern1[2] |= (pattern0[2] & 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;
}
}