Jump to content
  • Advertisement
Sign in to follow this  
Mats1

Isolating groups on a board

This topic is 996 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Given an n by n board of squares, on which a square can be any of x colours, are there efficient algorithms for isolating groups, where a group consists of 1 or more squares of the same colour?

/*
A 7 x 7, nine 'colour' grid.

1 1 2 5 3 4 5 
1 4 1 3 5 5 5 
1 4 6 8 7 2 2 
2 1 2 2 3 4 5
6 7 8 9 5 6 6
1 1 3 5 3 8 9
1 3 5 8 7 3 2
*/

For instance, in the above grid, there is a group of 6 1s in the top left corner.

I wasn't sure exactly in which forum this belonged, but it feels like it should reduce to a known (hopefully solved) math problem?

Edited by Mats1

Share this post


Link to post
Share on other sites
Advertisement

You will probably want to

1) find unassigned cell (linear search will work if this isnt a bottleneck - maybe do each search from where previous left off to not search same stuff every time)

2) flood fill from that cell until you find all cells in the connected group of cells (while forming the group which could be by assigning the group ID to each cell, or adding each cell to some group objects list of cells)

3) repeat

Share this post


Link to post
Share on other sites
Here's some code, adapted from my go board:

#include <iostream>

// Size of the board and the extended board (with padding)
int const N = 7;
int const XN = N + 2;
int const XN2 = XN * XN;

auto const neighboring_directions = {-XN-1, -XN, -XN+1, -1, +1, +XN-1, +XN, +XN+1};

struct Board {
  int array[XN2];
  int chain_id[XN2];
  int chain_size[XN2];
  int next_in_chain[XN2];
  
  Board();
  
  void coalesce_chains(int p1, int p2);
  
  void place_color(int point, int color);
};

Board::Board() {
  for (int i = 0; i < XN2; ++i) {
    array[i] = -1;
    chain_id[i] = 0;
    chain_size[i] = 0;
    next_in_chain[i] = 0;
  }
}

void Board::coalesce_chains(int p1, int p2) {
  if (chain_size[p1] < chain_size[p2])
    std::swap(p1, p2);
  int chain_id1 = chain_id[p1];
  int chain_id2 = chain_id[p2];
  
  int p = p2;
  do {
    chain_id[p] = chain_id1;
    p = next_in_chain[p];
  } while (p != p2);
  
  int n1 = next_in_chain[p1];
  int n2 = next_in_chain[p2];
  next_in_chain[p1] = n2;
  next_in_chain[p2] = n1;
  
  chain_size[chain_id1] += chain_size[chain_id2];
}

void Board::place_color(int point, int color) {
  // Set up this point as its own chain
  array[point] = color;
  chain_id[point] = point;
  chain_size[point] = 1;
  next_in_chain[point] = point;
  
  // Coalesce neighboring chains
  for (int offset : neighboring_directions) {
    if (array[point + offset] == color && chain_id[point + offset] != chain_id[point])
      coalesce_chains(point + offset, point);
  }
}

int main() {
  int map[XN2] = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 1, 1, 2, 5, 3, 4, 5, 0, 
    0, 1, 4, 1, 3, 5, 5, 5, 0, 
    0, 1, 4, 6, 8, 7, 2, 2, 0, 
    0, 2, 1, 2, 2, 3, 4, 5, 0, 
    0, 6, 7, 8, 9, 5, 6, 6, 0, 
    0, 1, 1, 3, 5, 3, 8, 9, 0, 
    0, 1, 3, 5, 8, 7, 3, 2, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0
  };
  
  Board board;
  
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= N; ++j) {
      int point = i * XN + j;
      board.place_color(point, map[point]);
    }
  }

  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= N; ++j) {
      int point = i * XN + j;
      std::cout << board.chain_id[point] << ' ';
    }
    std::cout << "    ";
    for (int j = 1; j <= N; ++j) {
      int point = i * XN + j;
      std::cout << (board.chain_size[board.chain_id[point]]) << ' ';
    }
    std::cout << '\n';
  }
}
I call your islands "chains".

Once you have told the Board class what all the colors are, you can get the chain id for each point (chain_id) and you can also loop over the elements in a chain using next_in_chain.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!