2
\$\begingroup\$

I'm stumped trying to create a matching algorithm for my game.

I have a 2D grid like this for example:

0, 0, 0, 0, 0, 0

0, 1, 2, 2, 1, 0

0, 1, 1, 0, 0, 0

0, 0, 2, 0, 1, 0

0, 0, 0, 2, 1, 0

0, 0, 0, 0, 0, 0

Along with a list of patterns:

1, 2, 1

1, 1, 1

Where I am trying to find instances of the patterns in the grid, and the higher listed pattern has the higher priority if multiple patterns are found. That would normally not be a problem if I were searching for them appearing purely horizontally or vertically. But I want to implement the search for them appearing in more than just straight lines like this (an "L shaped" example for the first pattern):

1, 2

0, 1

Some implementations I've tried included picking a grid element and trying to crawl from it to neighboring elements, but this has been problematic since each element has 4 neighbors and when you go to a neighboring element it has 4 more possible neighbors, and sometimes the crawling path curls in on itself resulting in duplicates. I feel like there is an easier and more efficient way to implement this that I am missing.

Is there any already well known algorithm that would fit this criteria? I have not been able to find something that fits these criteria on google. Any help would be appreciated.

\$\endgroup\$
  • 1
    \$\begingroup\$ Pattern matching is certainly not specific to game development (I would say it's actually a rather uncommon problem for games). This would probably be a better question for StackOverflow. \$\endgroup\$ – bcrist Apr 12 '15 at 2:41
  • \$\begingroup\$ @bcrist I could think of several game genres where pattern matching like this would be necessary. \$\endgroup\$ – Philipp Apr 12 '15 at 2:47
  • 1
    \$\begingroup\$ @Philipp The general rule for posting to Game Development is "Would a game developer give me a different/better answer than a non-game developer?" In this case I think the answer to that is "probably not." \$\endgroup\$ – bcrist Apr 12 '15 at 3:34
  • \$\begingroup\$ I agree with bcrist, it's more of a search & compare. Lots of people can help there. \$\endgroup\$ – Ace Caserya Apr 12 '15 at 4:20
2
\$\begingroup\$

A naive algorithm to find one pattern in a grid would be this:

for (int grid_x = 0; grid_x < grid_width; grid_x++) {
    for (int grid_y = 0; grid_y < grid_height; grid_y++) {
         bool fail = false;
         for (pattern_x = 0; pattern_x < pattern_width && fail == false; pattern_x++) {
             for (pattern_y = 0; pattern_y < pattern_height && fail == false; pattern_y++) {
                  if (grid[grid_x + pattern_x][grid_y + pattern_y] != pattern[pattern_x][pattern_y]) {
                      fail = true;
                  }
             }
         }
         if (fail == false) {
              // found pattern
         }
    }
}

There is certainly some optimization potential in this algorithm which someone will surely point out in the comments, but it should be fast enough to get you started.

When you execute this algorithm for multiple patterns in a row and do not want to get a positive when cells are already part of a pattern which was checked before, perform the algorithm with a copy of the grid and when you find a pattern, overwrite those cells which are part of the pattern with a value which does not occur in any pattern.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.