Solving Minesweeper – Part 11: I’m Done

In the last post, we solved the issue about sizing, however I mentioned that, I needed to adapt a few things. Except the usual little code optimization and cleanups, there were two main things: the color approximation, and the way we process the frames.

The main idea about the buckets was good. The issue came in at the extremes, the smallest and largest cells. If you remember there was a threshold set to 5, being the acceptable difference in buckets in order to count that color. Well for the smallest images it was too small and excluded the actual cell value. If I adjusted it to bigger then there were some misreadings (although in hindsight these might have been caused by the frame processing). But let’s look at what I did.

void GameImageAnalyzer::ExtractColor(Mat* src, int* col, Rect roi)
{
	int stx = roi.x;
	int sty = roi.y;
	int enx = roi.x + roi.width;
	int eny = roi.y + roi.height;
	int count = 0;
	int totals[3]{ 0 };
	for (int i = stx; i < enx; i++)
	{
		for (int j = sty; j < eny; j++)
		{
			auto c = src->at<Vec3b>(j, i);
			auto diff01 = abs(c.val[0] - c.val[1]);
			auto diff02 = abs(c.val[0] - c.val[2]);
			auto diff12 = abs(c.val[1] - c.val[2]);
			// detect grayish color
			if (max(diff01, max(diff02, diff12)) < 30)
				continue;

			totals[0] += c.val[0];
			totals[1] += c.val[1];
			totals[2] += c.val[2];
			count++;
		}
	}

	if (count > 0)
	{
		col[0] = totals[0] / count;
		col[1] = totals[1] / count;
		col[2] = totals[2] / count;
		col[3] = (100 * count) / (roi.width * roi.height);
	}
}
Continue reading

Solving Minesweeper – Part 10: Size doesn’t matter (anymore)

Last time we parted ways I explained, that in order to tackle grids of various sized, I needed to adapt my matching logic. At the end of that post, the algorithm did the grid detect just by getting the cell size, than scaling the matching template, and dropping down the matching threshold to 60. Obviously that wasn’t an elegant solution, plus it didn’t work in all cases. It is time to change that!

Let’s consider these input images. For the sake of simplicity i kept the windows the same size (also it looks better this way). In real life we can even get smaller grids and in the 30X24 case, that can really be problematic. But let’s jump into it, shall we?

Continue reading

Solving Minesweeper – Part 9: Color approximation

“So what happened?”, you might ask. Remember Columbo? Remember how he used to ask that final question, just before leaving the suspect alone and walking out the door, later having a big significance in solving the case? This is a classic case of planning to do something and ending up doing a totally different thing.

Before I was closing down this series, for my final trick I was going to solve the issue of size. Our solution till now is great don’t get me wrong, but if you try to solve a 9X9 or a 30X24 grid, it will fail. The issue is that the templates I use now, were extracted from the 30X16 sized grid. I though I will get away very quickly just by doing the following.

  1. Detect the Cell Size
  2. Scale the templates according to the cell size
  3. Use the scaled templates in analysis
  4. Open the champagne

Well it didn’t go as planned. The issue was that I already apply a threshold in order to find the perfect match. Scaling the templates meant that the quality of the match will be even worse. I tried adjusting the threshold, but I got more incorrect detection and misbehavior. Shit!

The solution lies in the content of the cells. The game scales the whole grid to have a good visual representation, so size always changes. What doesn’t change is the contents (the numbers). Since i’m too lazy to apply OCR on it, I needed to resort to the other thing that is constant. The color of the characters. Each cell has a different dominant color if we don’t count gray. But how do we do that?

Continue reading

Solving Minesweeper – Part 8: Ludicrous Speed

If light speed isn’t fast enough, you can still go into ludicrous speed but keep in mind, you risk going into plaid. If you don’t know what I’m talking about, don’t worry and watch this funny sequence from the cult classic, Spaceballs. In other words, i managed to improve the speed, yes i know, i’m obsessed with performance.

To be honest, i didn’t make the algorithm run faster. Last time we introduced a 200ms delay so we wait for the animations to end. Setting a timeout is always a tricky system, especially if it would be hardware dependent. Luckily in our case it’s not, however we all still running faster than the game to catch-up. In our case sometimes having the timeout makes sense, other times it doesn’t.

To get rid of that 200ms delay, we need to detect when there are animations running. If animations are running, in my case, there will be cells which cannot be analysed. So what i did was to go into a loop, until i was able to successfully analyze all the cells that were still not discovered.

int tries = 0;
while (tries < 10)
{
	tries++;
	Sleep(25);
	gm.GetImageInto(imageAnalyzer.img.data);
	if (imageAnalyzer.Analyze())
		break;
}
if (tries == 10) // timeout
	break;
set<int> b, s;
decisionMaker.GetDecisions(b, s);
Continue reading

Solving Minesweeper – Part 7: Super Smart

Last time we managed to greatly optimize the image analysis part of our little solver. That is great, however we only managed to run into bomb a lot faster. In Part 5 i was very, very … VERY frustrated about the amount of guesses needed to solve a table. I was wrong!

A couple of very good friends told me that there are situations where analyzing only one cell doesn’t result in any additional moves, but switching our attention to a specific area can help us uncover more detail. Let’s look at the following image.

Continue reading