Checking patterns in a 2D Array

Questions & Answers
1

Hi,

I’m trying to check if a specific pattern is in an 2D Array. E.g.:

Check if this pattern:

1 1
1 1

Is inside this 2D array:

0 0 0
1 1 0
1 1 0

I’m on a quest to create the 1 billion Match-3 like, and I would like to left the box open to more matching patterns without going “if, if, if, if…”.

Thanks a lot to everyone!

2

Iterate through all possible windows. I’ll use X to denote the array is being sampled at that current iteration.

Iteration
0, 0     1, 0     0, 1     1, 1

Pattern sample (X)
X X 0    0 X X    0 0 0    0 0 0
X X 0    1 X X    X X 0    1 X X
1 1 0    1 1 0    X X 0    1 X X

Pattern match on 3rd iteration (at 0, 1)

If any of the tests succeed, then it contains the pattern.
So we don’t need to run the 4th test (at 1, 1).

using UnityEngine;

public class PatternExample : MonoBehaviour
{
    int[,] pattern = {
        { 1, 1 },
        { 1, 1 },
    };
    int[,] containsPattern = {
        { 0, 0, 0 },
        { 1, 1, 0 },
        { 1, 1, 0 },
    };
    int[,] lacksPattern = {
        { 1, 1, 0 },
        { 1, 2, 2 },
        { 5, 2, 2 },
    };

    void Start() {
        print(HasPattern(containsPattern, pattern)); // true
        print(HasPattern(lacksPattern, pattern)); // false
    }

    bool HasPattern(int[,] array, int[,] pattern) {
        int patternWidth = pattern.GetLength(0);
        int patternHeight = pattern.GetLength(1);

        // testsFit is how many tests fit in x and y
        // for example a 2x2 in a 3x3 can be tested 2x2
        // for example a 3x3 in a 3x3 can be tested 1x1
        int testsFitWidth = array.GetLength(0) - patternWidth + 1;
        int testsFitHeight = array.GetLength(1) - patternHeight + 1;

        // For every possible location the pattern can test
        for (int ty = 0; ty < testsFitHeight; ++ty)
        for (int tx = 0; tx < testsFitWidth; ++tx) {
            // For every item in pattern
            for (int py = 0; py < patternHeight; ++py)
            for (int px = 0; px < patternWidth; ++px) {
                // If there is any item in pattern that doesn't
                // match the array, stop, it's not a match.
                if (pattern[px, py] != array[tx + px, ty + py])
                    goto NextTest; // fugly nested loop break
            }
            return true;
            NextTest: continue;
        }
        return false;
    }
}