Last time we reached the point where we had an in memory representation of the game. Today we are going to make some decisions based on the game state. Basically we will decide about an empty field if it is a bomb or it is safe. Let’s consider the following input image (I’ve cut out the excess, the rest is just empty squares).

If you are an experienced player, you will instantly spot that there are a lot of information available here. This is how the magic happens.

int* game = new int[SIZE];
Point* coords = new Point[SIZE];
Extract(points, values, game, coords);
while (true)
{
	std::set<int> bombs, safes;
	ScanGame(game, bombs, safes);
	MarkActions(img, game, coords, bombs, true);
	MarkActions(img, game, coords, safes, false);
	if (bombs.size() == 0 && safes.size() == 0)
		break;
}
imshow("", img);
waitKey();

The Extract method is pretty much the same as last time. What i’ve changed is to memorize the coordinates of that cell into the coords point array. We go into an “infinite” loop to scan the game state and come up with cells that currently are unknown but can be considered safe or bombs. Why the loop you ask? Very much like the SuDoKu solving algorithm that we wrote, once you uncover a hidden info, that info now can be used to decide on previously undecidable cells. We do this until our scanning doesn’t find any additional information. MarkActions is currently a temporary function that draws in the image red circles for bombs and green circles for safe cells. It will be removed or changed since the plan is to actually imitate mouse movement. So lets get into the ScanGame function.

void ScanGame(int* game, std::set<int>& bombs, std::set<int>& safes)
{
	for (int i = 0; i < SIZE; i++)
	{
		auto z = game[i];
		if (z > 0 && z < BOMB)
		{
			std::vector<int> unk;
			int b = 0;
			ScanCell(game, i, &b, unk);
			int u = unk.size();
			int outcome = 0;
			if (z == b && u > 0)// not bomb
			{
				safes.insert(unk.begin(), unk.end());
			}
			else if (z != b && z == u + b) // bomb
			{
				bombs.insert(unk.begin(), unk.end());
			}
		}
	}
}

I’ve kept the game state as a one dimensional array because i find it easier when i need to go through every element either way. We go through each cell and if it has a value (bomb around it) then we go and scan the surrounding of that cell. I will get to that in a minute. The output of the ScanCell method is the number of bombs around the cell and the list of the unknown cells. Here we need the actual cell in order to make changes to it. We use sets to collect the values in order to remove the duplicates (multiple cells can mark a neighbor as bomb or safe but we only need to make one action for them). We could have removed the loop and the need of the sets if we would have reset the iterator to 0 each time we decide on a cells value, but for some reason this seems a bit more straightforward for me. The first if translates to the following: “if we detected the correct number of bombs around the cell but there still are neighboring cells that are blue we can consider them safe”. The second if translates to “if we didn’t found the correct number of bombs but together with the neighboring blue cells we would then we can consider those as bombs”. Ok so the ScanCells function.

void ScanCell(int* game, int c, int* bmb, std::vector<int>& unk)
{
	int xc = c % WIDTH, yc = c / WIDTH;
	for (int i = -1; i <= 1; i++)
	{
		for (int j = -1; j <= 1; j++)
		{
			if (i == 0 && j == 0) continue;
			int ic = xc + i;
			if (ic < 0 || ic >= WIDTH) continue;
			int jc = yc + j;
			if (jc < 0 || jc >= HEIGHT) continue;

			auto cord = jc * WIDTH + ic;
			int z = game[cord];
			if (z == BOMB) (*bmb)++;
			else if (z == UNDISCOVERED) unk.push_back(cord);
		}
	}
}

There is really no magic here. I switch to the table like calculations because it’s simpler. I scan through all the eight neighbors, I’m checking that i’m still in bounds of the game. If the neighbor is already marked as a bomb, i count it, if i’ts still unknown i remember it. This simple methods achieve the following output.

As you can see we detected quite a lot of information. Next time we meet we will proceed in automating the actions back to the game. Since i would like to see if i can improve the whole application a bit, I also plan to do an Optimizations part at the very end of it. Till then, take care.