Sign in to follow this  
Endar

Repetitive 'if' statements with same action and different conditions

Recommended Posts

I have a 2d grid of objects (crystals), of different colours, and I have a function whose job it is, is to start with the 2d index of a crystal and recursively check the neghbours (adjacent crystals) that are the same colour as the start crystal, as defined by 'm_currentGroupColour'. Info:
  • 'm_checkedList' is a list of the indices of the crystals that have already been examined, so we don't go on a recursive stack kill.
  • 'm_groupList' is a list of the indices of the crystals that are in the current group (have the same colour and are adjacent to the start crystal, or to one of it's neighbours, or to one of it's neighbours, etc, etc)
  • This does work, albiet with only a couple of small tests, but it will be tested more intensively later (when I get back home after the weekend), but I can't see any major problems.
  • The checking function wraps left and right, so a crystal at (0,1) is adjacent to a crystal at ([width of array],1), but it does not wrap up and down.
/**
 * A function to start with a crystal and check all of it's neighbours. If the neighbours are the same 
 * colour as the start crystal, it checks the neighbours of those blocks and comes up with a group of the
 * same coloured blocks that are connected by edges (horizontally or vertically, not diagonally).
 *
 * NB. The checking will wrap around left and right, but not up and down.
 *
 * \param index The index of the crystal to start with
 */
void Cylinder::findMatchingCrystalGroup(const Index2d& index)
{
	// Check Crystal Above
	Index2d next_index(index.x, index.y+1);
	// If we're not at the top row of crystals
	if( next_index.y < m_levelSettings.rows && 
		// If the colour of the crystal above is the same colour as the current group of crystals
		getCrystal(next_index)->isColourMatch(m_currentGroupColour) &&
		// if the index we're looking at has not been looked at before
		std::find<IndexList::iterator, Index2d>(m_checkedList.begin(), m_checkedList.end(), 
		next_index) == m_checkedList.end() &&
		// if the block is not already in the current group
		std::find<IndexList::iterator, Index2d>(m_groupList.begin(), m_groupList.end(), next_index) == m_groupList.end() ){

		// add the index of the crystal to the group list
		m_groupList.insert(next_index);

		// add the new index to the 'looked at' list
		m_checkedList.insert(next_index);

		// check the neighbours of the next crystal
		findMatchingCrystalGroup( next_index );
	}

	// Check Crystal Below
	next_index = Index2d(index.x, index.y-1);
	// If we're not on the bottom row of crystals
	// NB. Needs to be 'index.y', because it is unsigned, if we try to test 'next_index.y' after the assignment,
	// it will wrap around from 0 to large positive values.
	if( index.y > 0 && 
		// If the crystal below is the same colour as the current group of crystals
		getCrystal(next_index)->isColourMatch(m_currentGroupColour) &&
		// if the index we're looking at has not been looked at before
		std::find<IndexList::iterator, Index2d>(m_checkedList.begin(), m_checkedList.end(),
		next_index) == m_checkedList.end() &&
		// if the block is not already in the current group
		std::find<IndexList::iterator, Index2d>(m_groupList.begin(), m_groupList.end(), next_index) == m_groupList.end() ){
		
		// add the index of the crystal to the group list
		m_groupList.insert(next_index);

		// add the new index to the 'looked at' list
		m_checkedList.insert(next_index);

		// check the neighbours of the next crystal
		findMatchingCrystalGroup( next_index );
	}

	// Check Crystal Right
	next_index = Index2d(index.x+1, index.y);
	// wrap around to the other side if necessary
	if( next_index.x >= m_levelSettings.columns )
		next_index.x = 0;

	// If the crystal to the right is the same colour as the current group of crystals
	if( getCrystal(next_index)->isColourMatch(m_currentGroupColour) &&
		// if the index we're looking at has not been looked at before
		std::find<IndexList::iterator, Index2d>(m_checkedList.begin(), m_checkedList.end(),
		next_index) == m_checkedList.end() &&
		// if the block is not already in the current group
		std::find<IndexList::iterator, Index2d>(m_groupList.begin(), m_groupList.end(), next_index) == m_groupList.end() ){

		// add the index of the crystal to the group list
		m_groupList.insert(next_index);

		// add the new index to the 'looked at' list
		m_checkedList.insert(next_index);

		// check the neighbours of the next crystal
		findMatchingCrystalGroup( next_index );
	}

	// Check Crystal Left
	next_index = Index2d(index.x-1, index.y);
	// wrap around to the other side if necessary
	// NB. Needs to be 'index.x', because it is unsigned, if we try to test 'next_index.x' after the assignment,
	// it will wrap around from 0 to large positive values.
	if( index.x <= 0 )
		next_index.x = m_levelSettings.columns-1;

	// If the crystal to the left is the same colour as the current group of crystals
	if( getCrystal(next_index)->isColourMatch(m_currentGroupColour) &&
		// if the index we're looking at has not been looked at before
		std::find<IndexList::iterator, Index2d>(m_checkedList.begin(), m_checkedList.end(),
		next_index) == m_checkedList.end() &&
		// if the block is not already in the current group
		std::find<IndexList::iterator, Index2d>(m_groupList.begin(), m_groupList.end(), next_index) == m_groupList.end() ){

		// add the index of the crystal to the group list
		m_groupList.insert(next_index);

		// add the new index to the 'looked at' list
		m_checkedList.insert(next_index);

		// check the neighbours of the next crystal
		findMatchingCrystalGroup( next_index );
	}

}

My problem is that I feel that the 4 major if statements are really unwieldy, because they all do the exact same thing, it's just that the if statements have 1-2 different conditions, and 2 conditions that are exactly the same. It just feels like bad coding. Ideas on how to get this down to something more readable?

Share this post


Link to post
Share on other sites
Factor out identical or nearly identical function into an auxiliary function, which is then called from the main code with different parameters. Judging from your code, this function would start with two or three distinct conditions, with an early return when they fail, and then execute the associated code.


int wrap(int x, int max)
{
if (x < 0) return max - 1;
if (x == max) return 0;
return x;
}

void Cylinder::findMatchingCrystalGroup(const Index2d& index)
{
// Check Crystal Above
if( next_index.y < m_levelSettings.rows)
ExploreCrystal(Index2d(index;x,index.y+1));
// Check Crystal Below
if (index.y > 0)
ExploreCrystal(Index2d(index.x,index.y-1));

// Check Crystal Right
ExploreCrystal(Index2d(
wrap(index.x + 1, m_levelSettings.columns),index.y));

// Check Crystal Left
ExploreCrystal(Index2d(
wrap(index.x - 1, m_levelSettings.columns),index.y));
}

void Cylinder::ExploreCrystal(const Index2d& next_index)
{
// Different color
if (!getCrystal(next_index)->isColourMatch(m_currentGroupColour))
{
return;
}

// if the index we're looking at has been looked at before
if (std::find(m_checkedList.begin(), m_checkedList.end(),next_index)
!= m_checkedList.end())
{
return;
}

// if the block is already in the current group
if (std::find(m_groupList.begin(), m_groupList.end(), next_index)
!= m_groupList.end())
{
return;
}

// add the index of the crystal to the group list
m_groupList.insert(next_index);

// add the new index to the 'looked at' list
m_checkedList.insert(next_index);

// check the neighbours of the next crystal
findMatchingCrystalGroup( next_index );
}

Share this post


Link to post
Share on other sites
	
Index2D test_and_adjust( Index2D &index, int dx, int dy )
{
Index2D next_index( index.x + dx, index.y + dy);
if (index.x <= 0) next_index.x = m_levelSettings.columns-1;
if (index.x > m_levelSettings.columns) next_index.x = 0;

if( getCrystal(next_index)->isColourMatch(m_currentGroupColour) &&
// if the index we're looking at has not been looked at before
std::find<IndexList::iterator, Index2d>(m_checkedList.begin(), m_checkedList.end(),
next_index) == m_checkedList.end() &&
// if the block is not already in the current group
std::find<IndexList::iterator, Index2d>(m_groupList.begin(), m_groupList.end(), next_index) == m_groupList.end() ){

// add the index of the crystal to the group list
m_groupList.insert(next_index);

// add the new index to the 'looked at' list
m_checkedList.insert(next_index);

// check the neighbours of the next crystal
findMatchingCrystalGroup( next_index );
}

}

void Cylinder::findMatchingCrystalGroup(const Index2d& index)
{
test_and_adjust( index, 1, 0 );
test_and_adjust( index, -1, 0 );
test_and_adjust( index, 0, -1 );
test_and_adjust( index, 0, 1 );
}



I don't guarantee the code is still correct, make sure to check the conditions are really the same, and that there aren't any other hidden conditions or similar.

But this is the most trivial refactoring. You perform 1 - 2 redundant tests for each test_and_adjust, that could be solved with templates, but I don't think it's necessary.

Share this post


Link to post
Share on other sites
Ah, good old flood fill.

1) Simplify the recursion. Instead of checking whether the neighbours are part of the group, check whether the *current* node is part of the group; and if it is, always recurse to the neighbours (because they might be).

2) (Actually, I'm doubting myself about this one. ToohrVyk also has a good idea with the wrap() function.) Take advantage of the wrapping of the unsigned values. Since this will produce a large positive value - certainly larger than the rows/columns of the grid - you can actually use the exact same checking condition.

3) Don't specify the template parameters for std::find. One of the nice things about C++ is that templated functions can infer their template types from the parameters.

4) The checked list and group list are actually completely redundant with each other (I assume you clear both in a helper function before starting the recursion, the same place that m_currentGroupColour gets set): each time you add to one, you add the same node to the other, so they'll always have the same contents. After all, the nodes that you know are in the group (group list) are the same as the ones that you already checked and know to be in the group (checked list), yeah?


void Cylinder::findMatchingCrystalGroupVertical(int x, int y) {
Index2d index(x, y);
if (index.y < m_levelSettings.rows) {
findMatchingCrystalGroup(index);
}
}

void Cylinder::findMatchingCrystalGroupHorizontal(int x, int y) {
Index2d index(x, y);
// If strictly greater, we must have wrapped around the left side...
if (index.x > m_levelSettings.cols) { index.x = m_levelSettings.cols - 1; }
else if (index.x == m_levelSettings.cols) { index.x = 0; }
findMatchingCrystalGroup(index);
}

void Cylinder::findMatchingCrystalGroup(const Index2d& index) {
// If the colour matches...
if (getCrystal(index)->isColourMatch(m_currentGroupColour) &&
// and we don't already know about this one,
std::find(m_groupList.begin(), m_groupList.end(), index) ==
m_groupList.end()) {
// add it,
m_groupList.insert(index);
// and consider its neighbours.
findMatchingCrystalGroupVertical(index.x, index.y + 1);
findMatchingCrystalGroupVertical(index.x, index.y - 1);
findMatchingCrystalGroupHorizontal(index.x + 1, index.y);
findMatchingCrystalGroupHorizontal(index.x - 1, index.y);
}
}



5) The packing with Index2d's seems a bit unwieldy. It might be easier to create them within the main recursive function, like this:


void Cylinder::findMatchingCrystalGroupVertical(int x, int y) {
if (y < m_levelSettings.rows) {
findMatchingCrystalGroup(x, y);
}
}

void Cylinder::findMatchingCrystalGroupHorizontal(int x, int y) {
// If strictly greater, we must have wrapped around the left side...
if (x > m_levelSettings.cols) { x = m_levelSettings.cols - 1; }
else if (x == m_levelSettings.cols) { x = 0; }
findMatchingCrystalGroup(x, y);
}

void Cylinder::findMatchingCrystalGroup(int x, int y) {
Index2d index(x, y);
// If the colour matches...
if (getCrystal(index)->isColourMatch(m_currentGroupColour) &&
// and we don't already know about this one,
std::find(m_groupList.begin(), m_groupList.end(), index) ==
m_groupList.end()) {
// add it,
m_groupList.insert(index);
// and consider its neighbours.
findMatchingCrystalGroupVertical(x, y + 1);
findMatchingCrystalGroupVertical(x, y - 1);
findMatchingCrystalGroupHorizontal(x + 1, y);
findMatchingCrystalGroupHorizontal(x - 1, y);
}
}


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