This is pretty basic image processing stuff, but it’s still fun to dig in a bit to see how this works.
The Smashgather algorithm is a combination of template matching and image similarity.
First, the screenshot is converted to grayscale (for simplicity and performance) and then matched to a template (cropped image) of the “WINS” text that accompanies every Super Smash Bros victory.
This matching is done by “convolving” the template across the entire screenshot — without getting too into the weeds, that basically means we compare the template to the screenshot at every possible x/y location to find the point at which the template and the screenshot have the strongest overlap.
For our screenshots, that’s roughly 2 million different locations, but OpenCV is pretty good at doing that quickly — so we don’t have to worry about implementing all the math.
The “WINS” template is matched to every location in the screenshot, producing the strange image on the right.
The bright point in that image indicates the strongest match; the coordinates at that location is where it seems the “WINS” template might fit.
Now that we have the coordinate where the template overlaps the most, we can set about trying to determine if the “WINS” text is actually there.
This is an easier problem to understand — we crop the screenshot and template to the same size, and then compute the SSIM (structural similarity) score between the two images to determine how similar they are.
Remember, the two images won’t be identical — the background will vary, the alignment might not be exact, etc.
The SSIM algorithm is designed to be relatively good at handling those kinds of errors, and it certainly works well enough for our purposes.
If the cropped screenshot and the “WINS” template are similar enough, we can safely say that we are, in fact, looking at a Super Smash Bros win screen!Next up, we have to figure out who the winning character is.
For this step, we run the exact same “match & compare” algorithm against templates for each of the character names.
As soon as we find a matching character template, we’ve got everything we need (if you’re curious, you can see the source for this simple algorithm here: WinDetector.
cpp).
This whole process (capture screenshot, “WINS” template matching & comparison, character name template matching & comparison) is performed every second in order to track the current state of the game.
We wrap up the process with a simple state machine, to avoid double counting wins, and we’ve got ourselves a program that can automatically keep track of Super Smash Bros games!Keeping ScoreThe rest of Smashgather is less interesting — whenever a win is detected, we record that on a server and then make those records accessible via a basic web app.
To make this part of the project more fun, I used a bunch of technologies that don’t really make sense for this problem: PostgreSQL for data storage, a GraphQL Node backend to serve up the results, and a React + Relay app to render the data.
Sure, a simple Ruby on Rails site would have taken a fraction of the time and would require a lot less Javascript (the un-minified, un-compressed bundle is a hilarious 2.
1 MB), but where’s the fun in that?.Besides, even with all that unnecessary work, we still had time Friday afternoon to put together a cringe-inducing 90s-style interface.
You can, of course, check our leaderboards anytime by visiting smashgather.
com.
…Why?To be honest, we’re busier than ever at Pathgather.
Between launching new customers, coding new features, and hiring new employees, we don’t exactly have a ton of free time — not exactly the ideal moment to spend a day or two hacking together an automated video game leaderboard, is it?I’d argue that there will always be an excuse to compromise on your company values and culture, but you shouldn’t compromise.
We had a lot of fun building Smashgather on our “learning Friday”; we learned new things about some interesting technologies, and I got to play around with my old love, C++.
Also, let’s be honest — keeping track of our wins is absolutely critical.
Work can wait until Monday.
Keep learning!Originally published at pathgather.
com on April 7, 2016.
.. More details