Sign in to follow this  
SomeoneX

Count with recursion? C++

Recommended Posts

This might seem simple to some people, but I've only used textbook examples of recursive functions. Brief description of what I'm trying to do. Same game that I asked about amorphous groups about, in fact same functions, but a different problem. The "flood fill" function that checks for the groups of objects seems perfectly fine (hasn't actually been tested however), but the next problem is counting how many objects are in each group. For now I think it really wouldn't cost much time (tens of milliseconds perhaps) with the current board size, but if it's ever increased, repeatedly going over the entire board with several functions could result in visible lag between the object falling and the popping animation. My question is, would it work to have a counter inside of a recursive function, before it calls itself, Or should I just make another function that simply goes over the board again, counting how many objects are in each group? Currently I have one function checkObjects() set a group number via recursive flood fill type function. Then I have a function countGroup() go over the entire board for each group just to count how many there are in each group. What also bothers me is that the countGroup() function is called within another function that loops until every group has been counted. In the end I have several hundred function calls just to set 2 values - the Group number and the boolean of whether it is to be popped when yet another function is called.

Share this post


Link to post
Share on other sites
Quote:
Original post by SomeoneX
My question is, would it work to have a counter inside of a recursive function, before it calls itself, Or should I just make another function that simply goes over the board again, counting how many objects are in each group?


I reckon you can go either way, counting inside the recursion would be a bit faster. From the top of my head,



int gameGrid[h][w]; // The block data, 0 - no block, 1 - red, 2 - green, ...
int visitedAreas[h][w]; // Initialized to 0 first to denote no positions checked yet.

/// Counts a single cell position and recurses to all others.
void CheckPattern(int x, int y, int color, int &count)
{
if (visitedAreas[y][x] != 0)
return;
if (gameGrid[y][x] == color)
{
++count;
visitedAreas[y][x] = color;
CheckPattern(x-1,y,color,count);
CheckPattern(x+1,y,color,count);
CheckPattern(x,y-1,color,count);
CheckPattern(x,y+1,color,count);
}
}

/// @return The number of blocks found of the same color starting from the given position.
int CheckPattern(int x, int y)
{
int count = 0;
if (gameGrid[y][x] != 0)
CheckPattern(x, y, gameGrid[y][x], count);
return count;
}

/// Does a O(w*h) scan over the whole grid and performs game actions.
void ScanGrid()
{
Erase visitedAreas to 0.
for(int y = 0; y < height; ++y)
for(int x = 0; x < width; ++x)
if (visitedAreas[y][x] == 0)
{
int count = CheckPattern(x,y);
if (count >= 4)
Add (x,y) to To-Be-Exploded list;
}

Process To-Be-Exploded;
}


Might have some bugs and/or syntax errors, just wrote it in the message reply box without testing. But the main idea - you can see how to carry that count variable as a reference inside the recursion. (You can do that without the reference, using a return value and passing a parameter as value, but I find this more readable)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this