Skip to main content
gamedev.net
🔒 Locked

Help with Algorithm?

Started by Space_Panda Jan 10, 2003 at 7:00 PM 3 replies 200+ views
Original Post
Space_Panda
Space_Panda
I''m making a game called collapse. I''m almost done. This algorithm checks the blocks at x and y positions on my playing surface and sees if its neighbours are its colour and then if the next neighbours are the same colour and so forth. It also keeps track how many neighbours it has of its colour in a line. I''m sure someone of you must have played this game before. Anyways I know recurrsion is bad but it is the best algorithm I can come up with. Does anyone know anything better than this? 
  
int Surface::Scan_Block_Neighbours(int x, int y, int colour)
{
	if(Surface::line[y].Get_Block_Colour(x) == colour && !Surface::line[y].blocks[x].is_Selected())
	{
		Surface::line[y].blocks[x].Select();
		if(x == 0 && y == 0)
		{
			return (1 + Surface::Scan_Block_Neighbours(x + 1, y, colour) + Surface::Scan_Block_Neighbours(x, y + 1, colour));
		}
		else if(x == 0 && y == 11)
		{
			return (1 + Surface::Scan_Block_Neighbours(x + 1, y, colour) + Surface::Scan_Block_Neighbours(x, y - 1, colour));
		}
		else if(x == 9 && y == 0)
		{
			return(1 + Surface::Scan_Block_Neighbours(x - 1, y, colour) + Surface::Scan_Block_Neighbours(x, y + 1, colour));
		}
		else if(x == 9 && y == 11)
		{
			return(1 + Surface::Scan_Block_Neighbours(x - 1, y, colour) + Surface::Scan_Block_Neighbours(x, y - 1, colour));
		}
		else if(x == 0)
		{
			return(1 + Surface::Scan_Block_Neighbours(x + 1, y, colour) + Surface::Scan_Block_Neighbours(x, y + 1, colour) + Surface::Scan_Block_Neighbours(x, y - 1, colour));
		}
		else if(x == 9)
		{
			return(1 + Surface::Scan_Block_Neighbours(x - 1, y, colour) + Surface::Scan_Block_Neighbours(x, y + 1, colour) + Surface::Scan_Block_Neighbours(x, y - 1, colour));
		}
		else if(y == 0)
		{
			return(1 + Surface::Scan_Block_Neighbours(x + 1, y, colour) + Surface::Scan_Block_Neighbours(x - 1, y, colour) + Surface::Scan_Block_Neighbours(x, y + 1, colour));
		}
		else if(y == 11)
		{
			return(1 + Surface::Scan_Block_Neighbours(x + 1, y, colour) + Surface::Scan_Block_Neighbours(x - 1, y, colour) + Surface::Scan_Block_Neighbours(x, y - 1, colour));
		}
		else
		{
			return(1 + Surface::Scan_Block_Neighbours(x + 1, y, colour) + Surface::Scan_Block_Neighbours(x - 1, y, colour) + Surface::Scan_Block_Neighbours(x, y + 1, colour) + Surface::Scan_Block_Neighbours(x, y-1, colour));
		}
	}
	else
		return (0);
}
Zipster
Zipster
Recursion isn't bad, just easy to misuse. Unfortunatly, it appears that you may be misusing recursion just a bit, especially since your game world is a simple grid. You can work on the assumption that you are checking lines of blocks of similar colors. Recursion would be a better solution for arbitrary, non-regular worlds.

What you do is find the "bounds" of your colored lines. For example, if the block as (x1,y1) is red, then you simply check for the first block in each direction that isn't red. So find the first block above that isn't red, the first block below that isn't red, etc., and it logically follows that everything before that block is red. Since you already found your bounds, it's easy to count the blocks of similar color in each direction

Here's some pseudo-code showing what I mean. I'll try to use some of the functions you already have:


int Get_Num_Blocks(int x, int y, int colour)
{
   // Set "bounds" to coordinates
   int left=x, right=x, top=y, bottom=y;
   
   if( BlockAt(x,y) == colour && !IsBlockSelected(x,y) )
   {
      // Check right direction
      for(int s = x + 1; s < GRID_WIDTH; ++s)
      {
         if( BlockAt(s, y) != colour )
         {
            right = s - 1;
            break;
         }
      }

      // Check left direction
      for(s = x - 1; s >= 0; --s)
      {
         if( BlockAt(s, y) != colour )
         {
            left = s + 1;
            break;
         }
      }

      // Check up direction
      for(int t = y - 1; t >= 0; --t)
      {
         if( BlockAt(x, t) != colour )
         {
            top = t + 1;
            break;
         }
      }

      // Check down direction
      for(t = y + 1; t < GRID_HEIGHTl; ++t)
      {
         if( BlockAt(x, t) != colour )
         {
            bottom = t - 1;
            break;
         }
      }

      // Calculate number of blocks
      // Left + right + top + bottom + this block (1)
      return   (x - left) +
               (right - x) +
               (y - top) +
               (bottom - y) +
               1;
   }

   return 0;
}


That code screams "modulize me!". In other words, those inline loops could be extracted to a seperate function so you don't have to repeat such similar code.

EDIT: Just to point out, inside each inner loop the bounds is set to something off by one, for example right = s - 1. This is because the logic checks for blocks that are of a different color and stores their offset. That block shouldn't be included, so we have to "short change" the calculations by moving the offset 1 towards the original block.

[edited by - Zipster on January 10, 2003 9:32:34 PM]
Space_Panda
Space_Panda
That''s an excellent algorithm for lines just straight up and down but across. But when I get to a new block I also have to check all its neighbours as well. Up, down, left and right. But thanks for the help I''m trying to modify the one you gave me right now.
Premandrake
Premandrake
Well, you are basically doing a floodfill here. You can do this without recursion by using a queue (with stl, this becomes very easy). Here is how I would write a quick non-recursive floodfill.

  
struct pt {
	int x,y;
	pt(int x_,int y_) : x(x_), y(y_) {}
};

int GetChunkSize(int x,int y,int color) {
	vector<vector<bool> > searched;
	for (int i=0; i<height; i++) {
		searched.push_back(vector<bool>(width));
		for (int j=0; j<width; j++)
		{
			searched[i][j] = false;
		}
	}

	if (getColor(x,y) != color) return 0;

	int chunkSize = 1;
	queue<pt> pts;
	pts.push(pt(x,y));
	searched[y][x] = true;

	int xi[4] = {1,0,-1,0};
	int yi[4] = {0,1,0,-1};

	while (!pts.empty())
	{
		pt top = pts.front();
		pts.pop();
		for (int i=0; i<4; i++)
		{
			int nx = top.x + xi[i];
			int ny = top.y + yi[i];

			if (nx >= 0 && nx < width &&
			    ny >= 0 && ny < height &&
			    searched[ny][nx] != true &&
			    getColor(nx,ny) == color)
			{
				chunkSize++;
				searched[ny][nx] = true;
				pts.push(pt(nx,ny));
			}
		}
	}

	return chunkSize;
}

But truly, for floodfill type algorithms, recursion is a natural fit and works well unless you are working on a huge map and blowing your stack space.

[edited by - premandrake on January 11, 2003 2:40:16 PM]
Zipster
Zipster
quote:
Original post by Space_Panda
That''s an excellent algorithm for lines just straight up and down but across. But when I get to a new block I also have to check all its neighbours as well. Up, down, left and right. But thanks for the help I''m trying to modify the one you gave me right now.


The algorithm does work left, right, up and down. That''s why I suggested you break those loops into functions. A possible prototype could take both an X an Y delta. In this way you could also make it check diagonals.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.