Saturday, December 03, 2011
Running some test cases pointed out that the extrapolation from first order Lagrange basis functions to those higher than third order cubic Lagrange basis functions were in error. The extrapolated functions had high degrees of oscillations. The bug has been reported to the developers. They have put in a check so that the first release will throw an error instead of attempting an extrapolation.
So it's back to traditional interpolation methods. Keep this in mind when viewing the code from the last two posts.
Tuesday, November 29, 2011
I have wrapped the interpolation method using the Fenics Project into a template class. The class is template on the interpolation basis function so that the user may choose the order of interpolation. The class also contains an array of y values so that it may serve as a table of values. Part of this is a map to the variable name for convenience when calling for tabled values.
Since all the work goes into extrapolating to a higher basis function when the Constructor is called, lookups are cheap to retrieve. The cost should be about the level of evaluating a polynomial of the order of the interpolation level (since the weights are known).
An example of it being used:
boost::shared_ptr<Vector> xs (new Vector(n));
boost::shared_ptr<Vector> ys1 (new Vector(n));
boost::shared_ptr<Vector> ys2 (new Vector(n));
std::vector<boost::shared_ptr<Vector> > yss;
std::vector<string> names;
// Populate test data
for(int i=0; i<n; i++)
{
xs->setitem(i,i+i*0.1);
ys1->setitem(i,(*xs)[i]*(*xs)[i]);
ys2->setitem(i,(*xs)[i]*(*xs)[i]*(*xs)[i]);
}
yss.push_back(ys1);
names.push_back("squared");
yss.push_back(ys2);
names.push_back("cubed");
InterpolationTable<Interpolate3::FunctionSpace> interpTable (xs, yss, names);
std::cout << interpTable.eval(0,2.12) << "\t" << interpTable.eval("squared",2.12) << "\n";
std::cout << interpTable.eval(1,2.12) << "\t" << interpTable.eval("cubed",2.12) << "\n";
The code listing:
// InterpolationTable.h
// Class for interpolating tabled values using the Fenics Project.
// Charles R. Cook v1.0 29 Nov 2011
// Copyright (c) 2011 Charles R. Cook
// http://www.charlesrcook.com
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to
// deal in the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.
#ifndef _INTERPOLATIONTABLE_H
#define _INTERPOLATIONTABLE_H
#include <dolfin.h>
#include "Interpolate1.h"
#include "Interpolate2.h"
#include "Interpolate3.h"
#include "Interpolate4.h"
using namespace dolfin;
template <class TFunctionSpace>
class InterpolationTable
{
public:
InterpolationTable(boost::shared_ptr<Vector> xs_in,
std::vector<boost::shared_ptr<Vector> > ys_in);
InterpolationTable(boost::shared_ptr<Vector> xs_in,
std::vector<boost::shared_ptr<Vector> > ys_in,
std::vector<std::string> names_in);
double eval(int index, double x);
double eval(std::string name, double x);
// These vectors contain the raw data
boost::shared_ptr<Vector> xs;
boost::shared_ptr<std::vector<boost::shared_ptr<Vector> > > ys;
// The mesh (defined as nodes at x locations)
boost::shared_ptr<Mesh> mesh;
boost::shared_ptr<Interpolate1::FunctionSpace> V1;
boost::shared_ptr<TFunctionSpace> V2;
boost::shared_ptr<std::vector<Function> > fy1;
boost::shared_ptr<std::vector<Function> > fy2;
boost::shared_ptr<std::vector<std::string> > Names;
private:
void Setup(boost::shared_ptr<Vector> xs_in,
std::vector<boost::shared_ptr<Vector> > ys_in);
boost::shared_ptr<std::map<std::string,int> > mapping;
};
template <class TFunctionSpace>
double InterpolationTable<TFunctionSpace>::eval(
std::string name, double x)
{
if((*Names).size()==0)
throw ("names not defined");
// check key exists in map
if ((*mapping).find(name) == (*mapping).end() )
throw ("name was not found");
int index = (*mapping)[name];
return eval(index, x);
}
template <class TFunctionSpace>
double InterpolationTable<TFunctionSpace>::eval(
int index, double x)
{
if(index >= (*ys).size())
throw ("index out of range");
if(x < mesh->coordinates()[0] ||
x > mesh->coordinates()[(*mesh).num_cells()])
throw ("x location out of range");
return (*fy2)[index](x);
}
template <class TFunctionSpace>
void InterpolationTable<TFunctionSpace>::Setup(
boost::shared_ptr<Vector> xs_in,
std::vector<boost::shared_ptr<Vector> > ys_in)
{
// copy the x locations in
xs = xs_in;
// copy the data in
for (uint i=0; i<ys_in.size(); i++)
{
(*ys)[i] = ys_in[i];
}
// Setup the mesh to interpolate on
// Note the count is the number of elements, not nodes
// when the interval is constructed
for(uint i=0; i<xs->size(); i++)
mesh->coordinates()[i] = (*xs)[i];
// Setup the Function space(s)
for (uint i=0; i<ys->size(); i++)
{
Function fv1(V1,(*ys)[i]);
fy1->push_back(fv1);
Function fv2(V2);
fv2.extrapolate(fv1);
fy2->push_back(fv2);
}
}
template <class TFunctionSpace>
InterpolationTable<TFunctionSpace>::InterpolationTable(boost::shared_ptr<Vector> xs_in,
std::vector<boost::shared_ptr<Vector> > ys_in,
std::vector<std::string> names_in) :
xs(new Vector(xs_in->size())),
ys(new std::vector<boost::shared_ptr<Vector> > (ys_in.size())),
mesh(new Interval(xs_in->size()-1,0,1)),
V1(new Interpolate1::FunctionSpace(mesh)),
V2(new TFunctionSpace(mesh)),
fy1(new std::vector<Function>),
fy2(new std::vector<Function>),
Names(new std::vector<std::string>),
mapping(new std::map<std::string, int>)
{
Setup(xs_in, ys_in);
(*Names) = names_in;
for(uint i=0; i < (*Names).size(); i++)
(*mapping)[(*Names)[i]] = i;
}
template <class TFunctionSpace>
InterpolationTable<TFunctionSpace>::InterpolationTable(boost::shared_ptr<Vector> xs_in,
std::vector<boost::shared_ptr<Vector> > ys_in) :
xs(new Vector(xs_in->size())),
ys(new std::vector<boost::shared_ptr<Vector> > (ys_in.size())),
mesh(new Interval(xs_in->size()-1,0,1)),
V1(new Interpolate1::FunctionSpace(mesh)),
V2(new TFunctionSpace(mesh)),
fy1(new std::vector<Function>),
fy2(new std::vector<Function>),
Names(new std::vector<std::string>),
mapping(new std::map<std::string, int>)
{
Setup(xs_in, ys_in);
}
#endif /* _INTERPOLATIONTABLE_H */
Wednesday, November 23, 2011
My recent research has been with the Fenics Project, which is an amazing finite element project. In general it provides the tools needed to solve differential equations with the finite element method. For some examples check out their website and view the demos and applications (my interest is in CFD).
In my particular code I need to interpolate tabulated properties (steam tables) with some reasonable level of accuracy. The solution in MATLAB is straight forward, call interp1:
y_i = interp1(xs, ys, x_i, 'cubic');
Where xs and ys are vectors of known x and y values and y_i is the interpolated value at x_i.
The code I am working on is already using the Fenics Project to solve a set of PDEs, so I wanted to see if I could use it for the interpolation as well through the finite element's basis functions. As the title of this post indicates, it can be done and here is how through a code snippet.
In C++…
// Setup data vectors
Vector xs(n);
Vector ys(n);
// Populate test data (this would be the tabulated data)
for(int i=0; i<n; i++)
{
xs.setitem(i,i+i*0.1);
ys.setitem(i,xs[i]*xs[i]);
}
// Setup the mesh to interpolate on
// Note the count is the number of elements, not nodes.
// there are general n-1 elements than nodes.
Interval mesh (n-1,0,1);
for(int i=0; i<n; i++)
mesh.coordinates()[i] = xs[i];
// create the function space of order one.
// this is done so that dof maps directly to
// data points. This provides a linear interpolation.
Interpolate1::FunctionSpace V (mesh);
// copy the data into the function space
Function fy (V, ys);
// Create quadratic function space (quadratic interpolation)
Interpolate2::FunctionSpace V2 (mesh);
Function fy2 (V2);
// 'fit' to the quadratic basis functions through least squares
fy2.extrapolate(fy);
// The fitted function is now available in fy2 as a quadratic fit
std::cout << "O(1): " << fy(2)
<< "\tO(2): " << fy2(2)
<< "\n";
Note that two UFL files (form files) are needed for this snippet.
Interpolate1.ufl
# First order (linear) lagrange elements (polynomials)
element = FiniteElement("Lagrange", interval, 1)
Interpolate2.ufl
# Second order lagrange elements (polynomials)
element = FiniteElement("Lagrange", interval, 2)
To create higher order fitting you can change the element to be of the desired order (instead of 2).
The very nice feature of interpolation through this method is that it will work in two dimensions and three dimensions as well. To do so, the elements would be updated to 2-d or 3-d element types instead of 'interval' (say triangle or tetrahedral). Too cool!
Tuesday, November 22, 2011
The posts so far have been rather technical in nature, but this post is a bit different. It's a bit more personal as I am sharing my recent engagement to my amazing fiancée Kristy.
It's an exciting time and I can't wait to see what's down the road for us. We have started planning for the wedding which is roughly two years out. The process is being well documented on her blog, I Do Times Two.
image source
Monday, June 20, 2011
I have been lax in updating posts on the blog. Mostly this is because I have been transitioning from web development to my Ph.D. research work in Aerospace Engineering over the last two or so years. The topic of the blog thus far has been mostly web development related, with less significant posts on the topic recently.
I’ve decided to transition the blog into my current focus, research, as my personal focus has also shifted (it is a personal blog after all). As part of this I have updated the blog engine itself (subtext). Many thanks to those at subtext for maintaining a blog so well that after three years of update neglect an automated update script goes flawlessly!
Over the past couple of years I have worked with gravity currents for my Masters research in Aerospace Engineering. Some of the research effort was spent in Davos, Switzerland at WSL SFL (Summer 2010). I earned my MS this last May (2011), and am starting a new research project for my Ph.D. on Cryogenic Thermal and Fluid Physics. My focus is as one might imagine computational. I’m looking forward to delving deeply into the topic over the next few years.
More to come!
Tuesday, January 18, 2011
I was getting the following error after installing IIS and starting a new Web Site in Windows 7
---------------------------
Internet Information Services (IIS) Manager
---------------------------
The process cannot access the file because it is being used by another process. (Exception from HRESULT: 0x80070020)
---------------------------
OK
---------------------------
And in the System Event Log:
The World Wide Web Publishing Service (WWW Service) did not register the URL prefix http://something.local:80/ for site 1. The site has been disabled. The data field contains the error number.
It turns out Skype automatically listens to port 80 and 443. Change this is the advanced settings of Skype to fix the issue.
Wednesday, January 12, 2011
It's a new year, a new spring semester, and my school, the University of Florida, gave us a nice present. They have obtained a site license for Windows 7 Ultimate and Office 2010 Professional Plus for the students and faculty. We can obtain each for just $15. Combined with our MSDNAA account for engineering students, this makes just about everything made by Microsoft free for the Engineering students.
The spur of new software and a clean start motivated me to put some time into some early spring cleaning on my primary computer, a desktop replacement laptop.
One of my first steps was to install Office 2010, which was met with a nice installation 1402 setup error regarding the registry entries for the installer. The solution for me was to simply over right the permissions of those keys from the Components level down. More explicitly, run regedit as an administrator. Find the key hklm\software\Microsoft\Windows\CurrentVersion\Installer\UserData\S-1-5-18\Components and right click Components, select permissions, advanced, the owner tab, and change the owner to Administrators and check the checkbox for replace on all sub containers. Click okay and the problem should be solved if it was the same problem I had. Note that this is a nice little trick for resurrecting rights to a set of files on disk as well. Well, trick may be over glorifying it…
With Office installed I did an upgrade anytime upgrade to Windows 7 Ultimate. The process couldn't be any simpler, just click start and search for 'upgrade' and click any time upgrade. Enter your key and wait for fifteen minutes or so (and the reboot).
After the upgrade I had finished my changes to Windows, so I ran Windows update a few times after un-hiding hidden updates (I had a few hidden that failed previously due to Office 2007). Be sure to re-check for updates after installing updates, some updates don't show until their dependencies are installed.
Now for my 'superficial' security, I updated Microsoft Security Essentials and ran a Quick Scan. Neat, no viruses or spy-ware… As an aside, the best security for a computer is a smart user and conversely nothing more dangerous than a 'risky' user.
With Windows up-to-date and scanned I next chose to clean up the hard drive. One tool I find essential for this is TreeSize Free, which has a new version. First I updated the version, which was a nice improvement over the last, and started a full scan of my drive. Space for me is still at a premium because of the 130GB SSD; for me every GB matters.
- The scan reminded me of some games I had installed and no longer played. The games Left 4 Dead and Left 4 Dead 2 were huge on disk, so I removed them without issue through Steam.
- It also pointed out that my Outlook files were excessively large and needed to be compacted. To do so, right click a mail folder in Outlook 2010 (the main folder for an account) select Data File Properties, and go to Advanced. Then choose Compact now. I did this for each of my accounts. Note that it takes a few minutes for a large account.
- My Google application data was in excess of a Gig and needed to be cleared. I started Chrome, went to options, under the hood and clicked 'Clear browsing data…'
- The same was true for Internet Explorer. I went to Internet Options and deleted my browsing History.
- I manually emptied my 'Temp' folders. They can, by definition, be deleted at will (I killed the contents, not the folder).
- I deleted the contents of my 'Downloads' folder, good for many Gigabytes.
- Note that if you a running a Vista Service Pack you can save some space in WinSXS.
- I deleted C:\Dell, where Dell loves to extract software.
- Finally don't forget to empty the Recycling bin.
I then simply cleaned up my Desktop. There is something to be said of keeping things looking clean. It reminds me of a mechanic saying the best way to make a customer feel like their car is running better is to clean their windshield. My desktop is my windshield, and it is clean. I also cleaned the actual screen.
My next focus was on bringing software up to date. My favorite text editor, Notepad2, was a version behind and needed to be updated. Note that I replace Window's notepad with Notepad2 by replacing the file in the Window's directory. This is probably not the best practice, but it's worked great for me for years. Note to do so you have to take ownership of the original notepad file and add modify rights for yourself.
I also installed the newest versions of Pidgin, Adobe Reader (through help update), Sumatra PDF, Winamp, and Dropbox (yes, that's a referral link. It gives both you and me extra space).
I then checked Dell for new drivers for my laptop. I chose to let it check my service tag because it's simply easier than flipping the laptop. I also downloaded and installed new video drivers from NVIDIA. They added some 3D Vision links to my start menu… not too thrilled about that, but oh well.
Next I checked the Windows logs for any errors that have been occurring. This is perhaps the most important maintenance step imho. Right click computer in the start menu, select manage, and expand the Event Viewer under System Tools and then Windows Logs, Application. I looked through my events, filtering for Warnings, Critical and Errors. These results will vary heavily between computers so Google will be your friend. Try to search by unique things in the error, such as file names, error numbers and the like. Inspection of my logs pointed out that I had to do the following
After checking the logs I went back to removing bloat and uninstalled old Applications I no longer needed.
To increase login performance I ran msconfig and removed some applications from startup (Almost everything).
Along the same vein I then stopped unnecessary services by running services.msc. Note that the important thing is to change the startup type to manual on optional services. I made services by Apple 'Manual' for example (Bonjour being one of them). Starting iTunes will re-enable these services.
Note that I did not run Disk Defrag as I have a SSD, which in general should not be defragged.
Finally, I ran a Full Backup of my Machine.
A final reboot and the machine is running like new for the new year.
Thursday, December 09, 2010
Over the past two years I have been working heavily in the LINUX world. For software development I love it, package distribution to obtain dependencies and the free tools make development really nice. Moving back to the Windows has been a bit frustrating as many tools I have come to use are missing. A simple solution has been to install Cygwin, which is 'like' a package manager for Windows, and add the binary location to Cygwin to my PATH variable. Now I can use linux commands such as 'ls' and 'ssh' from CMD. Or better yet, use Cygwin to have BASH on my Windows machines.
Cygwin is available here: http://www.cygwin.com/
Don't let the circa 1998 web design fool you; the project is still very active.
Friday, October 01, 2010
Matlab's symbolic toolbox is great for abstracting algebraic operations. For example, generating Lagrange basis functions. However, when generalizing an operation of order n, n symbolic variables are needed. Creating n symbolic variables in Matlab isn't as obvious as creating a static set of symbols. For example:
syms x
y
vs.
syms x1
x2
x3
…
xn
Fortunately the function sym takes a string argument and returns the symbolic variable. This way we can build a string for each xi, and append the resulting variable into a container such as a vector. Generating n symbolic variables can be done like so
% generate xi symbolic values
xi = [];
for (i=1:n)
t = sym(['x' int2str(i)]);
xi = [xi; t];
end
We now have a symbolic vector with n variables
Sunday, September 05, 2010
One of the more addictive games out there is Bejeweled Blitz on Facebook. It's fun to play, but as a programmer one thing nags at you as you play. The thought 'I could program something that would do this much better.' I program mostly scientific codes and business applications. A bot application is quite different, and hence a great project. I'll cover the process of making a bot here; however, I will not give a direct download. If you want to run the bot you will have to compile your own application. Cheating isn't the goal here.
First, credit where it is due, Mike Vallotton posted on the same topic. Between this and his article assembling a bot should be straight forward. My additions are in locating the game window, using statistics to identify game pieces, and using a damper on game moves. He reports a score of 212K; I have reached 1.06M without much attention to the pattern recognition.
The approach is to create a bot that interfaces with the game in the same way a user would, through the mouse. Doing so involves three major steps, reading the game state from the screen, solving for a move, and finally making the move. Reading the game state from screenshots may be the trickiest of the three.
Locating the game window
Locating where the game window is on the screen was one of the more interesting problems to solve. While we could use some libraries to get the window location of a browser which contains the Bejeweled game, we would not know where within the window the game resides. Further, when needing to know where the game is to the pixel, the game location on the page is far too volatile with changing ads, content, etc.
To find the window I use a screenshot of the whole desktop and then find the game within this image. Doing a per-pixel match is absurdly expensive, so I use an idea I borrowed from multigrid solvers, yet much simpler. To find the window I first capture a screenshot and crop it down to the game I want to find, and save it to disk; In this case the title screen of the game. Then I take a screenshot of the desktop captured during the run and attempt to find the title screen within.
To find the title screen I first convert both images to grayscale by simply taking the red channel. With grayscale images we then have a two dimensional array to work with, speeding things up a bit. To speed things up further, both images are scaled down to 0.10 their original size (this is the idea of successive scales is borrowed from the multigrid solver). Then the title screen is subtracted from the array at various locations. After the subtraction the two dimensional array is summed to get a total sum value. The location where the sum has the least value is taken to be the location where the window is located.
For the first levels of locating we do not need to be exact; we are just looking for regions where the title screen is so that the next level will have a reduced area to search. For the first search I stepped across the screenshot by 2 pixels (20 pixels on the original image). This then locates the game title screen to +/- (2*10) pixels on the screen. Great, now we can resize to 0.25 and search a 10 by 10 region. This is repeated at 0.50 before searching the final full scale screenshot. I prefer to work in Matlab for such operations. This does require compiling the Matlab code and referencing it from the .NET application.
The C# code to get a screenshot and call the compiled Matlab function:
private void FindGameScreen()
{
Rectangle r = new Rectangle(0, 0,
Screen.PrimaryScreen.Bounds.Width,
Screen.PrimaryScreen.Bounds.Height);
Bitmap bmp = new Bitmap(r.Width, r.Height);
using (Graphics g = Graphics.FromImage(bmp))
{
g.CopyFromScreen(
new Point(0, 0),
new Point(0, 0),
r.Size);
}
int[,] bmpmat = new int[r.Height, r.Width];
for (int i = 0; i < r.Width; i++)
for (int j = 0; j < r.Height; j++)
{
Color pixelColor = bmp.GetPixel(i, j);
bmpmat[j, i] = pixelColor.R;
}
var bmpinp = (MWNumericArray)bmpmat;
var fileinp = (MWCharArray)@"gametitle.bmp";
MWArray test = (MWNumericArray)findWindow.findwindow(bmpinp, fileinp);
double[,] data = (double[,])test.ToArray();
double x = data[0, 0];
double y = data[0, 1];
gamex = Convert.ToInt32(x);
gamey = Convert.ToInt32(y);
}
The Matlab code which performs the described method:
%
% Uses rescaling to find successive approximate locations of the window,
% finally finding the location to the pixel.
function [data]= findwindow(fullscreen, game_filename)
gametitle = imread(game_filename);
fullscreen = uint8(fullscreen);
gametitle = gametitle(:,:,1);
fullscreen2 = imresize(fullscreen,.1);
gametitle2 = imresize(gametitle,.1);
[x,y] = findwindow2(fullscreen2,gametitle2,1,1,0,0,2);
x = x*10;
y = y*10;
fullscreen2 = imresize(fullscreen,.25);
gametitle2 = imresize(gametitle,.25);
x = x*.25-6*3;
y = y*.25-6*3;
xn = x+2*6*3;
yn = y+2*6*3;
if (x<1)
x=1;
end
if (y<1)
y=1;
end
[x,y] = findwindow2(fullscreen2,gametitle2,x,y,xn,yn,3);
x = x*4;
y = y*4;
if (x<1)
x=1;
end
if (y<1)
y=1;
end
%
fullscreen2 = imresize(fullscreen,.5);
gametitle2 = imresize(gametitle,.5);
%
x = x*.5-3*3
y = y*.5-3*3
xn = x+2*3*3;
yn = y+2*3*3;
%
[x,y] = findwindow2(fullscreen2,gametitle2,x,y,xn,yn,3);
x = x*2;
y=y*2;
if (x<1)
x=1;
end
if (y<1)
y=1;
end
%
x = x-2*3
y = y-2*3
xn = x+2*2*3;
yn = y+2*2*3;
%
[x,y] = findwindow2(fullscreen,gametitle,x,y,xn,yn,1);
data = [x,y]
end
function [x,y] = findwindow2(fullscreen,gametitle,x0,y0,xn,yn,stepsize)
xmin=0;
ymin=0;
testmin = inf;
[gheight, gwidth] = size(gametitle);
[fheight, fwidth] = size(fullscreen)
if (xn == 0)
xn=fwidth-gwidth-stepsize
end
if (yn == 0)
yn = fheight-gheight-stepsize
end
for(x=x0:stepsize:xn)
for(y=y0:stepsize:yn)
test = error_fun([x,y]);
if (test < testmin)
xmin = x;
ymin = y;
testmin = test;
end
end
end
x=xmin;
y=ymin;
function f = error_fun(x)
f= test_sub(x(1),x(2),fullscreen,gametitle);
end
end
function fit = test_sub(x, y, full, game)
x = round(x);
y = round(y);
[height, width] = size(game);
sub = full(y:y+height-1,x:x+width-1);
sub = sub-game;
fit = sum(sum(sub,1));
end
Recognizing pieces
To get the game state from the screenshots I chose to avoid OCR methods and just go with a statistical approach. The idea was that the histogram for a piece will be unique from the other colors. For example, the mean red value for red would be different than that of the other pieces. To get the reference statistics from the game I used AForge.NET. The Framework comes with a nice application to work with images and a library to reference from the bot.
The first step is to collect statistics for all the game pieces. To do this, get a screenshot of all of them, and then crop down to just the game pieces. Each piece has some shape surrounded by the background board. To improve the statistics I chose to grab a 20 by 20 pixel box centered on the piece location. That is to say, crop down the 40 by 40 location to just the inner 20 by 20 and what remains is the core of a game piece.
The statistics I collected using AForge .NET.
Piece | Red Mean | Green Mean | Blue Mean |
white | 218.79 | 218.79 | 218.79 |
purple | 176.7325 | 38.1 | 177.2425 |
blue | 16.975 | 109.5675 | 204.7625 |
green | 43.06 | 214.2775 | 75.365 |
yellow | 227.01 | 197.165 | 28 |
orange | 238.49 | 143.535 | 55.7425 |
red | 242.855 | 31.28 | 62.07 |
Great, we now have readily available statistics to match a game piece too. Further, the statistics are calculated by the same library so matching should be good.
Matching a piece to the statistics is straightforward using a Root Sum Square error approach. For a statistic at a location we calculate the error to each piece and take the one with the smallest error. The code would look something like:
double bestScore = 255;
double curScore = 0;
foreach (KeyValuePair<Color, List<double>> item in statReference)
{
curScore = Math.Pow(item.Value[0] / 255 - stats.Red.Mean / 255, 2)
+ Math.Pow(item.Value[1] / 255 - stats.Green.Mean / 255, 2)
+ Math.Pow(item.Value[2] / 255 - stats.Blue.Mean / 255, 2);
if (curScore < bestScore)
{
PieceColor = item.Key;
if (item.Key == Color.YellowGreen)
PieceColor = Color.Yellow;
if (item.Key == Color.MediumPurple)
PieceColor = Color.Purple;
bestScore = curScore;
}
}
In this implementation a score, or error, is calculated by differencing the mean color values from an 'ideal' value and them performing the RSS on that value. The score with the smallest error indicates the piece which has the closest match. With pieces 20 by 20 and a cheap RSS being used, this method parses the game state very fast and accurately. Note that it is important to crop down to the 'core' of the game piece as the background board tends to smooth out the statistics, especially between yellow and orange.
Finding the statistics for the pieces can be done like so, where game is the current screenshot cropped to the game and gGamePieces is an array of initialized Graphics objects.
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
{
gGamePieces[i, j].DrawImage(
game,
new Rectangle(
new Point(0, 0),
new Size(20, 20)),
new Rectangle(
new Point(gameStartX + (i * 40) + 10,
gameStartY + (j * 40) + 10),
new Size(20, 20)),
GraphicsUnit.Pixel);
ImageStatistics stats = new ImageStatistics
(bmpGamePieces[i, j]);
ImageStatisticsYCbCr stats2 = new ImageStatisticsYCbCr(
bmpGamePieces[i, j]);
pGame[i, j].Parse(stats, stats2);
}
I chose to store the piece reference statistics in a dictionary and initialize as follows:
private void BuildReference()
{
//RedMeanB GreenMeanB BlueMeanB
statReference = new Dictionary<Color, List<double>>();
statReference.Add(Color.White,
new List<double> { 218.79, 218.79, 218.79 });
statReference.Add(Color.Purple,
new List<double> { 176.7325, 38.1, 177.2425 });
statReference.Add(Color.Blue,
new List<double> { 16.975, 109.5675, 204.7625 });
statReference.Add(Color.Green,
new List<double> { 43.06, 214.2775, 75.365 });
statReference.Add(Color.Yellow,
new List<double> { 227.01, 197.165, 28 });
statReference.Add(Color.Orange,
new List<double> { 238.49, 143.535, 55.7425 });
statReference.Add(Color.Red,
new List<double> { 242.855, 31.28, 62.07 });
}
We now have a way to locate the game window and identify the game pieces on the board. We have our game state, great.
Determining a move
For this I did not do anything fancy. With our known game state I simply search the board for any locations where swapping two pieces resulted in a three piece chain. I didn't bother to add any checks for larger combos as I did not see this as accomplishing anything other than improving a score.
There was an additional component to determining the moves. After doing a simple implementation I noticed an interesting dynamic feedback on the game. The bot would move fast enough to try and create combos where they did not exist. For example, it would swap a piece and while it was moving notice that if it also moved another piece a combo would be created while the pieces moved. The game does not allow you to move two pieces to create a combo, so this just resulted in a bunch of spinning pieces that oscillated back and forth. I chose to damp the board to prevent this.
To do this, I used an eight by eight double array to keep track of a delay. Any time a move was performed I added 550 to that location and 275 to locations around it. The values are delay values in milliseconds. This way the bot will not move pieces away from an action in that area. Every tick of the engine would subtract the elapsed time from the entire array. Game moves are only made to locations where the delay value is zero (negative values are kept to zero). This allows us to simply call all possible moves without destroying previous moves. Note that for each tick I send moves for every possible match on the board. I don't perform a move and exit the loop; I send them all without a Sleep. The game does remarkably well at handling this.
Running the bot is similar to a game loop. I just created a timer which ticked at 50 milliseconds and stopped after 63 seconds (typically three seconds from the game pausing for specials).
Making the move
Making the move involves an Interop call to user32. Here I refer you to Mike Vallotton's post. One 'gotcha' here, if you are running on x64 you need to change the offsets in the class or nothing will happen. Also, I suggest putting in a Thread.Sleep while you test; the last thing you want is your mouse moving out of control with a bug, clicking around your Facebook page at 20 Hz.
[StructLayout(LayoutKind.Explicit)]
private struct INPUT
{
[FieldOffset(0)]
public int type;
[FieldOffset(8)]
public MOUSEINPUT mi;
[FieldOffset(8)]
public KEYBDINPUT ki;
[FieldOffset(8)]
public HARDWAREINPUT hi;
}
Of course you will need to figure out the pixel offsets for the game board within the game and how to calculate piece locations as well. Something like the following where the gameStart values are found by using an image editor (the game seems to change every once in a while as they update) and the game locations come from the title screen locating.
var x1 = i1 * 40 + gameStartX + gameX + 20;
var y1 = j1 * 40 + gameStartY + gameY + 20;
var x2 = i2 * 40 + gameStartX + gameX + 20;
var y2 = j2 * 40 + gameStartY + gameY + 20;
SendInputClass.Click(x1, y1);
SendInputClass.Click(x2, y2);
Good luck, and have fun.