Strategies for detecting contiguous values in an 8x8 matrix

Question

I'm building a puzzle game, similar to Othello, and I'd like to build in a tutorial mode that helps the player learn the game. To do that, I need to detect horizontal, vertical, and diagonal lines of contiguous values (in this case, white or black) to show the player possible next moves they can make...

I'm building this in C++, but I'm really just interested in general strategies I can use to detect the lines using a 2D matrix (or 1D array if it simplifies things).

My current strategy is pretty straightforward, which makes me suspicious that it's the slowest way to do this...

for y = 0 to 7
  for x = 0 to 7
    cell = find the first unoccupied cell (no color)
    inspect the 8 surrounding cells to see if they contain a color
      if so, trace the cells in that direction to see if it forms a line of at least 3 contiguous colors
        if so, store the coords of those cells in a list of detected lines

Other ideas?

Thanks in advance for your wisdom!

Answer 1

Clustering and in particular hierarchical clustering can be helpful.