How to sort colors in two dimensions?
I am currently working on a hobby project to automatically solve a puzzle from the popular mobile game I Love Hue. The game is available here.
Basically, the whole premise of the game is that you're given a bunch of colored rectangular blocks organized in a grid. You can swap most of the blocks except for a few fixed blocks, which are marked by black dots. The object of the game is to swap the blocks around so you get a two-dimensional spectrum of color. The colors are sorted such that the color of each block is approximately the average of the colors around it. (Sorry, I don't know any color theory but there's probably a word for what I'm looking for.) Here's what a typical puzzle looks like:
I have already been able to take screenshots through adb, extract the RGB matrix from the blocks and mark which blocks are "fixed". I'm having trouble with the actual algorithmic part of this problem.
Here's what I've done so far:
- Converting the RGB to HSV and sorting the colors by hue in a one-dimensional list. This gives me a spectrum, but I do not know how to convert this result into two dimensions.
- Leaving the colors in RGB and attempting to work with a singular color. There's probably some multivariable calculus I could do here, but the difficulty lies in the fact that some colors share one or more of their RGB values. It would be necessary to consider all three colors.
- Using Euclidean distance to find the distance between each pair of colors. I understand that the final goal is to have this distance to be the smallest among adjacent colors, but the two-dimensional grid is making this more difficult.
- Using Euclidean distance, I have developed a metric for how ideal a certain grid is by looking at the Euclidean distance of the colors of adjacent blocks. However, I cannot find an efficient algorithm that can figure out the swaps necessary to get to an ideal state.
If you have more solved images you could create RGB graphs plot
so plot the 3D graph where x,y is pixel position and z is inspected color channel (R,G or B). From it you can determine some properties of the gradients. If the plot is a plane than all you need is just the normal (taken from 3 known cells). If it is curved surface depending on how many inflex points it got you can determine how big polynomial was used for it. From all this you can start solving this.
I would start with something simple (assuming not too big gaps or fancy polynomials):
Handle each color channel separately. I would use just the static tiles and interpolate the grid colors only from them. Something similar to:
Without seeing the R,G,B graphs I can not estimate which kind of interpolation you need. If the graphs are linear use bi-linear or linear interpolation. If not use higher degree polynomials.
So fill in any grid cells that you can (has neighbors with known color). After this find the closest movable tile to computed color (if cell has all 3 channels interpolated) and place them (and set as static).
Now just repeat the process until all the cells are computed.
[Edit1 Dec 14 2017] some additional notes and stuff
Was curious and got some time today so I gave it a shot. First I create the game in C++/VCL which took your image as input (cropped and resized). Then I sorted the tiles manually and plot the graphs:
The White dots means tile is placed correctly (match the interpolated color). The colored circles around the dots are the interpolated colors (for visual comparison you need to zoom to see them).
As you can see the R,G,B 3D plots looks linear so (bi)linear interpolation should be enough.
If I tried just linear interpolation for rows only the solver solves the puzzle immediately. However When I coded the same for columns (more unknown cells between known ones) the solver started to make few incorrect placings (invalidating the whole stuff hence the wrong white dots).
I Also tried HSL but after a while I throw it away due to hitting a wall because Hue can cross the 0 and 360 degree at any point which is not distinguishable from cases that did not cross. For that it would need some heuristics or cross correlation from neighboring solved areas and that would be too much coding for my taste. Without it the results where even worse then using RGB.
So now I am thinking about either using bilinear interpolation or solve the short distance interpolations first and only then solve the rest ...
[Edit2 Dec 14 2017] bilinear interpolation
Looks like bilinear RGB interpolation solves all the issues. So if your board is enclosed with fixed cells it should work. If not you need to solve the board iteratively and then use the newly solved cells as new bound for the unsolved areas. Also I realized I got RGB reversed so I also repaired that :).
Here the C++/VCL source for the game (It is not optimized at all):
//$$---- Form CPP ----
//---------------------------------------------------------------------------
#include <vcl.h>
#include <math.h>
#pragma hdrstop
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
//---------------------------------------------------------------------------
TForm1 *Form1;
bool _update=false;
//---------------------------------------------------------------------------
const _ILoveHue_state_fixed =255<<24;
const _ILoveHue_state_unsolved= 0<<24;
const _ILoveHue_state_solved = 1<<24;
const _ILoveHue_render_board=0;
const _ILoveHue_render_graph=1;
//---------------------------------------------------------------------------
int rgbdist(DWORD c0,DWORD c1) // AABBGGRR
{
int r0,g0,b0,r1,g1,b1;
r0=( c0 &255); r1=( c1 &255);
g0=((c0>> 8)&255); g1=((c1>> 8)&255);
b0=((c0>>16)&255); b1=((c1>>16)&255);
r0-=r1; g0-=g1; b0-=b1;
return (r0*r0)+(g0*g0)+(b0*b0);
}
//---------------------------------------------------------------------------
class ILoveHue
{
public:
// variables
bool _redraw; // redraw needed?
Graphics::TBitmap *bmp; // screen buffer
int sxs,sys,mxs,mys,gxs,gys;// screen,map,grid cell resolution
DWORD **map,**imap; // map[y][x] actual and interpolated
int mx,my,mx0,my0; // mouse position state actual and last
TShiftState sh,sh0; // mouse buttons and spec keys state actual and last
int render_mode;
// class constructors and destructors
ILoveHue() { bmp=new Graphics::TBitmap; bmp_resize(1,1); map=NULL; imap=NULL; mxs=0; mys=0; mx=-1; my=-1; mx0=-1; my0=-1; gxs=1; gys=1; render_mode=_ILoveHue_render_board; }
~ILoveHue() { map_free(); if (bmp) delete bmp; }
ILoveHue(ILoveHue& a) { *this=a; }
ILoveHue* operator = (const ILoveHue *a) { *this=*a; return this; }
//ILoveHue* operator = (const ILoveHue &a) { ...copy... return this; }
// game/Window API and stuff
void map_free() // relese map
{
if ( map) { if ( map[0]) delete[] map[0]; delete[] map; } map=NULL; mxs=0; mys=0;
if (imap) { if (imap[0]) delete[] imap[0]; delete[] imap; } imap=NULL;
}
void map_resize(int x,int y) // resize/allocate map
{
_redraw=true;
if ((x==mxs)&&(y==mys)) return; map_free();
map=new DWORD*[y]; if ( map==NULL) return; map[0]=new DWORD[x*y]; if ( map[0]==NULL) return;
imap=new DWORD*[y]; if (imap==NULL) return; imap[0]=new DWORD[x*y]; if (imap[0]==NULL) return;
mxs=x; mys=y; for (x=mxs,y=1;y<mys;y++,x+=mxs) { map[y]=map[0]+x; imap[y]=imap[0]+x; }
if (mxs) gxs=sxs/mxs; else gxs=1;
if (mys) gys=sys/mys; else gys=1;
}
void bmp_resize(int x=-1,int y=-1) // resize bmp
{
_redraw=true;
if ((x>=0)&&(y>=0)) bmp->SetSize(x,y);
bmp->HandleType=bmDIB;
bmp->PixelFormat=pf32bit;
sxs=bmp->Width;
sys=bmp->Height;
if (mxs) gxs=sxs/mxs; else gxs=1;
if (mys) gys=sys/mys; else gys=1;
}
void bmp_load(AnsiString file) // init game from image (map must be resized already)
{
_redraw=true;
// load file
bmp->LoadFromFile(file);
bmp_resize();
// convert to map
int x,y;
DWORD *p,c;
for (y=0;y<mys;y++)
for (p=(DWORD*)bmp->ScanLine[(y*gys)+(gys>>1)],x=0;x<mxs;x++)
{
c=p[(x*gxs)+(gxs>>1)+4]&0x00FFFFFF; // near mid point (0<<24 is unsolved state)
c=((c>>16)&0x000000FF) // RGB -> BGR (file has reverse RGB order than bmp)
|((c<<16)&0x00FF0000)
|( c &0x0000FF00);
map[y][x]=c;
c=p[(x*gxs)+(gxs>>1)]&0x00FFFFFF; // mid point
if ((((c)|(c>>8)|(c>>16))&255)<64) // ~max(R,G,B)<32
map[y][x]|=_ILoveHue_state_fixed;
}
}
void mouse(int x,int y,TShiftState s) // handle mouse
{
_redraw=true;
mx=x/gxs;
my=y/gys;
sh0=sh; sh=s;
bool q0=sh0.Contains(ssLeft);
bool q1=sh .Contains(ssLeft);
if ((!q0)&&( q1)){ mx0=mx; my0=my; } // mouse left button down
if (( q0)&&(!q1)) // mouse left button up (swap)
{
// swap if valid coordinates
if ((mx0>=0)&&(mx0<mxs)&&(my0>=0)&&(my0<mys)) if (DWORD(map[my0][mx0]&0xFF000000)!=_ILoveHue_state_fixed)
if ((mx >=0)&&(mx <mxs)&&(my >=0)&&(my <mys)) if (DWORD(map[my ][mx ]&0xFF000000)!=_ILoveHue_state_fixed)
{
DWORD c=map[my0][mx0]; map[my0][mx0]=map[my][mx]; map[my][mx]=c; // swap cells
map[my0][mx0]&=0x00FFFFFF; map[my0][mx0]|=_ILoveHue_state_unsolved; // set them as unsolved
map[my ][mx ]&=0x00FFFFFF; map[my ][mx ]|=_ILoveHue_state_unsolved;
map_solve(false); // check for solved state
}
// clear selection
mx0=-1; my0=-1;
}
}
void draw() // render game
{
_redraw=false;
int x,y,z,x0,x1,x2,y0,y1,y2,r;
DWORD c;
if (render_mode==_ILoveHue_render_board)
{
for (y0=0,y1=gys,y2=gys>>1,y=0;y<mys;y++,y0+=gys,y1+=gys,y2+=gys)
for (x0=0,x1=gxs,x2=gxs>>1,x=0;x<mxs;x++,x0+=gxs,x1+=gxs,x2+=gxs)
{
c=map[y][x];
bmp->Canvas->Pen->Color=TColor(c&0x00FFFFFF);
if ((x==mx )&&(y==my )) bmp->Canvas->Pen->Color=clYellow;
if ((x==mx0)&&(y==my0)) bmp->Canvas->Pen->Color=clGreen;
bmp->Canvas->Brush->Color=TColor(c&0x00FFFFFF);
bmp->Canvas->Rectangle(x0,y0,x1,y1);
if (DWORD(c&0xFF000000)!=_ILoveHue_state_fixed)
{
r=10;
bmp->Canvas->Pen->Color=imap[y][x]&0x00FFFFFF;
bmp->Canvas->Brush->Style=bsClear;
bmp->Canvas->Ellipse(x2-r,y2-r,x2+r,y2+r);
bmp->Canvas->Brush->Style=bsSolid;
}
if (DWORD(c&0xFF000000)!=_ILoveHue_state_unsolved)
{
if (DWORD(c&0xFF000000)==_ILoveHue_state_fixed ) c=clBlack;
if (DWORD(c&0xFF000000)==_ILoveHue_state_solved) c=clWhite;
r=4;
bmp->Canvas->Pen->Color=c;
bmp->Canvas->Brush->Color=c;
bmp->Canvas->Ellipse(x2-r,y2-r,x2+r,y2+r);
}
}
}
if (render_mode==_ILoveHue_render_graph)
{
bmp->Canvas->Pen->Color=clBlack;
bmp->Canvas->Brush->Color=clBlack;
bmp->Canvas->Rectangle(0,0,sxs,sys);
r=13; x0=15; y0=sys-15;
int c=r*double(256.0*cos(55.0*M_PI/180.0));
int s=r*double(256.0*sin(55.0*M_PI/180.0));
bmp->Canvas->Pen->Color=clRed;
for (y=0;y<mys;y++)
for (x=0;x<mxs;x++)
{
z=(map[y][x])&255;
x1=x0+(x*r)+((y*c)>>8);
y1=y0 -((y*s)>>8);
bmp->Canvas->MoveTo(x1,y1);
bmp->Canvas->LineTo(x1,y1-z);
} x0=x1+5;
bmp->Canvas->Pen->Color=clGreen;
for (y=0;y<mys;y++)
for (x=0;x<mxs;x++)
{
z=(map[y][x]>>8)&255;
x1=x0+(x*r)+((y*c)>>8);
y1=y0 -((y*s)>>8);
bmp->Canvas->MoveTo(x1,y1);
bmp->Canvas->LineTo(x1,y1-z);
} x0=x1+5;
bmp->Canvas->Pen->Color=clBlue;
for (y=0;y<mys;y++)
for (x=0;x<mxs;x++)
{
z=(map[y][x]>>16)&255;
x1=x0+(x*r)+((y*c)>>8);
y1=y0 -((y*s)>>8);
bmp->Canvas->MoveTo(x1,y1);
bmp->Canvas->LineTo(x1,y1-z);
}
}
}
// Solver
void map_solve(bool _solve) // check for solved state and try to solve if _solve is true
{
_redraw=true;
const int _thr=10; // color comparison threshold
int x,y,x0,x1,y0,y1,xx,yy;
int r0,g0,b0,r,g,b;
int r1,g1,b1;
int r2,g2,b2;
int r3,g3,b3;
DWORD c;
// compute interpolated colors to imap (wanted solution)
for (x=0;x<mxs;x++)
for (y=0;y<mys;y++)
if (DWORD(map[y][x]&0xFF000000)!=_ILoveHue_state_fixed)
{
for (x0=-1,xx=x;xx>= 0;xx--) if (DWORD(map[y][xx]&0xFF000000)==_ILoveHue_state_fixed){ x0=xx; break; }
for (x1=-1,xx=x;xx<mxs;xx++) if (DWORD(map[y][xx]&0xFF000000)==_ILoveHue_state_fixed){ x1=xx; break; }
for (y0=-1,yy=y;yy>= 0;yy--) if (DWORD(map[yy][x]&0xFF000000)==_ILoveHue_state_fixed){ y0=yy; break; }
for (y1=-1,yy=y;yy<mys;yy++) if (DWORD(map[yy][x]&0xFF000000)==_ILoveHue_state_fixed){ y1=yy; break; }
c=0;
if (int(x0|x1|y0|y1)>=0)
{
// bilinear interpolation
c=map[y0][x0]; r0=c&255; g0=(c>>8)&255; b0=(c>>16)&255;
c=map[y0][x1]; r1=c&255; g1=(c>>8)&255; b1=(c>>16)&255;
c=map[y1][x0]; r2=c&255; g2=(c>>8)&255; b2=(c>>16)&255;
c=map[y1][x1]; r3=c&255; g3=(c>>8)&255; b3=(c>>16)&255;
r0=r0+(r1-r0)*(x-x0)/(x1-x0);
g0=g0+(g1-g0)*(x-x0)/(x1-x0);
b0=b0+(b1-b0)*(x-x0)/(x1-x0);
r1=r2+(r3-r2)*(x-x0)/(x1-x0);
g1=g2+(g3-g2)*(x-x0)/(x1-x0);
b1=b2+(b3-b2)*(x-x0)/(x1-x0);
r =r0+(r1-r0)*(y-y0)/(y1-y0);
g =g0+(g1-g0)*(y-y0)/(y1-y0);
b =b0+(b1-b0)*(y-y0)/(y1-y0);
c=(r)+(g<<8)+(b<<16);
}
imap[y][x]=c;
}
// compute solved state
for (x=0;x<mxs;x++)
for (y=0;y<mys;y++)
if (DWORD(map[y][x]&0xFF000000)!=_ILoveHue_state_fixed)
{
map[y][x]&=0x00FFFFFF;
if (rgbdist(map[y][x],imap[y][x])<_thr) map[y][x]|=_ILoveHue_state_solved;
else map[y][x]|=_ILoveHue_state_unsolved;
}
// solver/checker
if (_solve)
{
// process all unsolved cells
for (x=0;x<mxs;x++)
for (y=0;y<mys;y++)
if (DWORD(map[y][x]&0xFF000000)==_ILoveHue_state_unsolved)
// find match in unsolved cells
for (xx=0;xx<mxs;xx++)
for (yy=0;yy<mys;yy++)
if (DWORD(map[yy][xx]&0xFF000000)==_ILoveHue_state_unsolved)
if (rgbdist(map[yy][xx],imap[y][x])<_thr)
{
// swap if found
c=map[yy][xx];
map[yy][xx]=map[y][x];
map[y][x]=(c&0x00FFFFFF)|_ILoveHue_state_solved;
}
}
}
} gam;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner)
{
gam.map_resize(7,9);
gam.bmp_load("map.bmp");
gam.map_solve(false);
_update=true;
ClientWidth=gam.sxs;
ClientHeight=gam.sys;
_update=false;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormDestroy(TObject *Sender)
{
gam.render_mode=_ILoveHue_render_board;
gam.draw();
gam.bmp->SaveToFile("map.bmp");
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender){ gam.draw(); Canvas->Draw(0,0,gam.bmp); }
void __fastcall TForm1::FormResize(TObject *Sender){ if (_update) return; gam.bmp_resize(ClientWidth,ClientHeight); }
void __fastcall TForm1::Timer1Timer(TObject *Sender){ if (gam._redraw) FormPaint(Sender); }
void __fastcall TForm1::FormMouseMove(TObject *Sender, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
void __fastcall TForm1::FormMouseUp(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
void __fastcall TForm1::FormMouseDown(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormKeyDown(TObject *Sender, WORD &Key, TShiftState Shift)
{
if (Key=='S') gam.map_solve(true); // try to solve
if (Key=='M') { gam.render_mode^=1; gam._redraw=true; } // swap render modes
if (Key==115) gam.bmp->SaveToFile("screenshot.bmp"); // [F4] screenshot
}
//---------------------------------------------------------------------------
It is a single Form App in BDS2006 with single 40ms Timer on it. So just add the events ... You can ignore the VCL rendering and window stuff. The important thing is the class and the solve() function in it. It is used for both correct placing check and for solving (depending on the _solve bool). This is the input image map.bmp
I did not code appropriate save/load state functions instead I chose to use the bitmap itself directly (waste of space but almost no code effort).
The map itself is 2D 32bit DWORD array with form of SSBBGGRR hex where SS is the flag of the cell (fixed/solved/unsolved).
Here compiled demo with the source code
Read the readme.txt for more info. Here result after solving (pressing [S]):
As you can (not) see the circles vanish as the bilinearly interpolated color matches more closely your input.
Program is expecting grid of size 7x9 the resolution of image is not important. The color is sampled from mid point of cell (black dot) and slightly to the right (the tile color)
To make this efficient you can make 2 things:
add/use list containing unsolved cells
instead of itearting over whole map iterate only through list of unsolved cells.
convert
T(N^2)searches toT((N^2)/2)by triangle searchThis is still
O(N^2)however but the constant time is smaller.use 3D RGB LUT table
for large grids you can create 32K entries 3D LUT table to find the searched matching cell in
O(1). Simply convert RGB to 15 bit color and useDWORD LUT[32][32][32];where
LUT[r][g][b]=row+(column<<16);Tis way you will know where each color is placed. All the unused colors set to0xFFFFFFFF. Here an example of using this technique for similar purpose:Look for
recolor[32][32][32]in the code... Of coarse 15bit color may be not enough for this purpose so may be you would need more bits like 18bit resulting in 256K entries which is still manageable.Creating this LUT will take
O(N)time but using and maintaining it is onlyO(1)time.