Best way to find the eleminated blocks?

no-reply@allegro.cc (Recorder) — Thu, 25 May 2006 22:07:57 +0000

I'm making a game where a rows of blocks rises from the bottom of the screen and you have to click on an area of 3 or more blocks of the same color and they disappear. You loose if a block reaches the top row. I'm sure you've all played a game like this.

What I'm having touble with is finding the blocks in the array to be removed.
The board is represented by an array of blocks (struct).

Lets say x are blocks of the same color, if I click on one they all should disappear, but I'm not sure of a good way to do this.

_ _ _ _ _
|_|_|_|_|_|
|_|_|x|_|_|
|_|x|x|x|_|
|_|x|_|_|_|
|_|_|_|_|_|

My only idea is:
add the block I click on to a vector
check the four blocks surrounding it for the same color
if same color, add to vector
loop until no more can be added
finaly remove blocks in the vector from the board

I'm not necessarily looking for code. Just wondering if ther is an easier way. Seems like this my be more than I need to do.

no-reply@allegro.cc (Richard Phipps) — Thu, 25 May 2006 22:12:20 +0000

Well, if all blocks move up at the same speed and are alligned in a grid then:

1. Draw those blocks to a temporary bitmap.
2. Floodfill which block has been clicked on with a special colour.
3. Count the pixels with this colour, if less than 3 than ABORT.
4. Using the bitmap, change the block array to reflect the missing pieces.

no-reply@allegro.cc (Recorder) — Thu, 25 May 2006 22:32:50 +0000

Thanks Richard, but that's not exactly what I'm having a problem with.
I know how to make the blocks disappear.

I'm not sure how to find which blocks need to be removed based only on the position of the one block I clicked on.

I can check if the blocks to the top, bottom, left, and right of the one I clicked on have the same color. But then I have to check the one surrounding those and so on.

no-reply@allegro.cc (Richard Phipps) — Thu, 25 May 2006 22:34:43 +0000

That's why you can use floodfill, it will mark all touching blocks of the same colour.

no-reply@allegro.cc (Shawn Hargreaves) — Thu, 25 May 2006 22:54:04 +0000

Or you can just do your own floodfill algorithm to avoid messing around with a temporary copy of the data.

Very simple to do this recursively:

1void ClickedOnPoint(int x, int y)
2{
3    std::list<std::pair<int, int>> results;
4 
5    int color = grid.get(x, y);
6 
7    floodfill(x, y, color, results);
8 
9    // do something interesting with the result list
10}
11 
12void floodfill(int x, int y, int color, std::list<std::pair<int, int>> &results)
13{
14    if ((x < 0) || (y < 0) || (x >= gridWidth) || (y >= gridWidth))
15        return;
16 
17    if (grid.get(x, y) != color)
18        return;
19 
20    results.add(std::make_pair(x, y));
21 
22    floodfill(x-1, y,   color, results);
23    floodfill(x+1, y,   color, results);
24    floodfill(x,   y-1, color, results);
25    floodfill(x,   y+1, color, results);
26}

That will be terribly inefficient and use lots of stack space if the grid is very large, but I guess yours is only going to be 10x10 or at most maybe 30x30 or so? In which case this naiive implementation is no problem at all.

To make it more efficient you can use your own stack structure rather than relying on recursion, and also change it to work in horizontal line spans rather than just single pixels (do a rapid scan left and right from each point, then only bother to floodfill into the line spans above and below that resulting span). I think Foley & Van Damme gives the standard algorithm for this, or you could look at how the Allegro implementation works.

no-reply@allegro.cc (Carrus85) — Thu, 25 May 2006 22:55:27 +0000

Recorder - This is easily solved using a recursive algorithm.

Example:

1int table_of_blocks[10][10] = ...; // Zero this out
2 
3int number_of_blocks_touching( int row, int column )
4{
5  int count = 0;
6  bool processed_marker[10][10];
7  // zero processed_marker, I'll leave this up to you.
8  number_of_blocks_touching_recurisve( table_of_blocks[row][column], row, column, count, processed_marker );
9  return count;
10}
11 
12void number_of_blocks_touching_recursive( int orig, int row, int column, int& count, bool* processed_marker[10] )
13{
14  if ( row < 0 || row >= 10 ) return;
15  if ( column < 0 || column >= 10 ) return;
16  if ( processed_marker[row][column] ) return;
17 
18  processed_marker[row][column] = true;
19 
20  if ( table_of_blocks[row][column] != orig ) return;
21 
22  ++count;
23  number_of_blocks_touching_recurisve( orig, row-1, column, count, processed_marker );
24  number_of_blocks_touching_recurisve( orig, row+1, column, count, processed_marker );
25  number_of_blocks_touching_recurisve( orig, row, column-1, count, processed_marker );
26  number_of_blocks_touching_recurisve( orig, row, column+1, count, processed_marker );
27}

Of course, this algorithm is basically the exact same thing as floodfill. (Beware, there are probabily syntax errors and such in that code, but I'm too lazy to fix them right now )

Edit:

DOH! Beaten.

no-reply@allegro.cc (Recorder) — Thu, 25 May 2006 23:13:11 +0000

Ooooh, I didn't realize floodfill would take care of the adjacent block too. Can you see the light bulb above my head.

Thanks alot.

I'm glad I asked.

1	void ClickedOnPoint(int x, int y)
2	{
3	std::list<std::pair<int, int>> results;
4
5	int color = grid.get(x, y);
6
7	floodfill(x, y, color, results);
8
9	// do something interesting with the result list
10	}
11
12	void floodfill(int x, int y, int color, std::list<std::pair<int, int>> &results)
13	{
14	if ((x < 0) \|\| (y < 0) \|\| (x >= gridWidth) \|\| (y >= gridWidth))
15	return;
16
17	if (grid.get(x, y) != color)
18	return;
19
20	results.add(std::make_pair(x, y));
21
22	floodfill(x-1, y, color, results);
23	floodfill(x+1, y, color, results);
24	floodfill(x, y-1, color, results);
25	floodfill(x, y+1, color, results);
26	}

1	int table_of_blocks[10][10] = ...; // Zero this out
2
3	int number_of_blocks_touching( int row, int column )
4	{
5	int count = 0;
6	bool processed_marker[10][10];
7	// zero processed_marker, I'll leave this up to you.
8	number_of_blocks_touching_recurisve( table_of_blocks[row][column], row, column, count, processed_marker );
9	return count;
10	}
11
12	void number_of_blocks_touching_recursive( int orig, int row, int column, int& count, bool* processed_marker[10] )
13	{
14	if ( row < 0 \|\| row >= 10 ) return;
15	if ( column < 0 \|\| column >= 10 ) return;
16	if ( processed_marker[row][column] ) return;
17
18	processed_marker[row][column] = true;
19
20	if ( table_of_blocks[row][column] != orig ) return;
21
22	++count;
23	number_of_blocks_touching_recurisve( orig, row-1, column, count, processed_marker );
24	number_of_blocks_touching_recurisve( orig, row+1, column, count, processed_marker );
25	number_of_blocks_touching_recurisve( orig, row, column-1, count, processed_marker );
26	number_of_blocks_touching_recurisve( orig, row, column+1, count, processed_marker );
27	}