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
Back to 2-Dimensional Pattern Rotation

Matching Multiple Patterns on a 2-D Cellular Automata Board

The applet below generates random patterns with random widths and heights of between 2 and 4. It displays these patterns at the bottom of the applet, each in a different colour. It then searches for each of these patterns in a 2-dimensional cellular automata board, highlighting matches using the same colour that is used to display the pattern at the bottom of the applet.

Generating the Patterns

Unlike the previous applet in which all patterns were the same width and height, this applet uses a private class to store the random pattern's bitboard and the width and height of that bitboard, as well as providing a constructor which encapsulates the generation of a random pattern.
private class RandomPattern
    Long bitBoard[];
    int width, height;

    RandomPattern(int maxWidth, int maxHeight)
        width    = (int)(Math.random() * (maxWidth - 1)) + 2;
        height   = (int)(Math.random() * (maxHeight - 1)) + 2;
        bitBoard = new Long[height];

        for(int i = 0; i < height; i++)
            bitBoard[i] = new Long((long)(Math.random() * (1L << width)));

Storing Pattern Matches

A private class is used to store the co-ordinate at which each match is found, the size of its bounding box and the colour to be used to display it.
private class Match
    Point topLeftCoord;
    int width, height;
    Color color;

    public Match(Point topLeftCoord, int width, int height, Color color)
        this.topLeftCoord = topLeftCoord;
        this.width        = width;
        this.height       = height;
        this.color        = color;

Matching Patterns

The applet searches for the top line of every pattern using the same method used by the 1-dimensional pattern matching applet. The only modification made to this algorithm is that instead of always performing a bitwise-AND with the number 15, it performs the bitwise-AND with (2 ^ w) - 1 (which "w" is the width of the pattern's bounding box). If a match for the top line is found then the applet checks to see if the second line of the pattern exists immediately beneath it, and so on.


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

CellularAutomata2DMultiplePatternMatchingApplet.java - Full source for the applet above.