Jeśli więcej solved
obraz można utworzyć RGB Wykresy przedstawiają
tak wykreślić wykres 3D gdzie x,y
jest położenie piksela i z
jest kontrolowane kanał koloru (R, G i B). Z niego można określić niektóre właściwości gradientów. Jeśli wykres jest płaszczyzną, to wszystko, czego potrzebujesz, to normalne (wzięte z 3 znanych komórek). Jeśli jest to powierzchnia zakrzywiona w zależności od tego, ile punktów inflex dostała, możesz określić, w jaki sposób został użyty duży wielomian. Z tego wszystkiego możesz zacząć to rozwiązywać.
chciałbym zacząć od czegoś prostego (zakładając, że nie jest zbyt duży lub fantazyjne luki wielomiany):
Handle każdego kanału koloru oddzielnie. Używałbym tylko płytek statycznych i interpolowałem kolory siatki tylko od nich.Coś podobnego do:
nie widząc R, G, B wykresy nie mogę oszacować jaki rodzaj interpolacji trzeba. Jeśli wykresy są liniowe, użyj interpolacji liniowej lub liniowej. Jeśli nie, użyj wielomianów wyższego stopnia.
Wypełnij wszystkie komórki siatki, które możesz (ma sąsiadów o znanym kolorze). Następnie znajdź najbliższą ruchomą płytkę do obliczonego koloru (jeśli komórka ma wszystkie 3 kanały interpolowane) i umieść je (i ustaw jako statyczne).
Teraz wystarczy powtórzyć proces, aż wszystkie komórki zostaną obliczone.
[Edit1 14 grudnia 2017] Pewne dodatkowe informacje i rzeczy
był ciekawy i trochę czasu dzisiaj więc dałem mu strzał. Najpierw tworzę grę w C++/VCL, która zabrała twój obraz jako wejście (przycięte i zmienione). Następnie płytki klasyfikowane ręcznie i wykreślić wykres:
Białe kropki oznaczają płytka jest umieszczony prawidłowo (mecz interpolowaną koloru). Kolorowe kółka wokół kropek są interpolowanymi kolorami (dla porównania wizualnego musisz powiększyć, aby je zobaczyć).
Jak widać, wykresy R, G, B 3D wyglądają liniowo, więc (bi) liniowa interpolacja powinna wystarczyć.
Jeśli spróbowałem liniowej interpolacji tylko dla wierszy, solver natychmiast rozwiązuje zagadkę. Jednak gdy kodowałem to samo dla kolumn (bardziej nieznane komórki między znanymi), solver zaczął robić kilka niepoprawnych rozmieszczeń (unieważniając cały materiał, stąd błędne białe kropki).
Próbowałem też HSL ale po chwili wyrzucić z powodu trafienia ścianę bo Hue może przekroczyć 0
i 360
stopnia w dowolnym punkcie, który nie różni się od spraw, które czynił nie krzyżować się. W tym celu potrzebowałaby pewnej heurystyki lub korelacji krzyżowej z sąsiednimi rozwiązanymi obszarami, co byłoby zbyt dużym kodowaniem dla mojego gustu. Bez tego wyniki byłyby gorsze niż używanie RGB.
Więc teraz myślę o albo za pomocą interpolacji bilinear lub rozwiązać krótkie wstawki dystansowe najpierw, a dopiero potem rozwiązać resztę ...
[Edit2 14 grudnia 2017] interpolacja bilinear
Wygląda bilinear RGB interpolacja rozwiązuje wszystkie problemy. Więc jeśli twoja plansza jest zamknięta ze stałymi komórkami, powinna działać. Jeśli nie, musisz rozwiązać planszę iteracyjnie, a następnie użyć nowo rozwiązanych komórek jako nowych dla nierozwiązanych obszarów. Również zdałem sobie sprawę, że mam RGB odwróconą, więc też naprawiłem to :).
Tutaj C++/VCL źródło do gry (nie jest zoptymalizowany w ogóle):
//$$---- 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
}
//---------------------------------------------------------------------------
Jest to pojedyncza postać App w BDS2006 z pojedynczym 40ms czasowy na nim. Więc dodaj wydarzenia ... Możesz zignorować rendering VCL i zawartość okna. Ważną rzeczą jest klasa i funkcja solve()
. Jest używany zarówno do prawidłowego sprawdzania położenia, jak i do rozwiązywania (w zależności od bool'a _solve
). To jest obraz wejściowy map.bmp
nie kodować odpowiednie zapisać/funkcje państwowe obciążenia zamiast Zdecydowałem się użyć samego bezpośrednio (strata przestrzeni, ale prawie bez wysiłku code) bitmapy.
sama mapa jest 2D 32-bitowy DWORD
tablicę z postaci SSBBGGRR hex
gdzie SS
jest flaga komórki (stała/rozwiązany/rozwiązany).
Tutaj skompilowany demo z kodem źródłowym
Przeczytaj readme.txt
aby uzyskać więcej informacji. Oto wynik po rozwiązaniu (naciskając klawisz [S]):
Jak można (nie) zobaczyć kręgi znikają jak dopasowuje bilinearly interpolowane kolor dokładniej swój wkład.
Program oczekuje siatki o rozmiarze 7x9, rozdzielczość obrazu nie jest ważna. Kolor jest próbą od połowy punktu komórce (czarna kropka) i lekko w prawo (kolor dachówka)
Aby uczynić to wydajny można zrobić 2 rzeczy:
add/lista użycie zawierającego nierozwiązane komórki
zamiast itearting na całej mapie iterują tylko po liście nierozwiązanych komórek.
nawrócony T(N^2)
wyszukiwania do T((N^2)/2)
przez poszukiwaniu trójkąta
To jednak wciąż O(N^2)
ale stała czasowa jest mniejsza.
użycie RGB 3D LUT tabeli
dla dużych sieci można utworzyć 32k wpisów 3D LUT tabeli można odnaleźć szukane dopasowanie komórkę O(1)
.Wystarczy przekonwertować RGB do 15 bitowego koloru i używać
DWORD LUT[32][32][32];
gdzie LUT[r][g][b]=row+(column<<16);
Tis sposób będziesz wiedział, gdzie każdy kolor jest umieszczony. Wszystkie niewykorzystane kolory ustawione na 0xFFFFFFFF
. Oto przykład użycia tej techniki do podobnych celów:
Look dla recolor[32][32][32]
w kodzie ... Z grubej koloru 15bit może być nie tyle do tego celu może być tak, że trzeba więcej bitów, takich jak 18-bit, co daje 256-krotne wpisy, które wciąż można zarządzać.
Utworzenie tego LUT zajmie O(N)
czas, ale używanie i utrzymywanie jest tylko O(1)
czasu.
ok Nie grałem w tę grę, ale z przedniej okładki gry wygląda to tak, że są 4 możliwe orientacje kolorów, które skutkowałyby gładkim wykończeniem ... tylko zastanawiasz się, czy gra akceptuje wszystkie 4 kombinacje. Czy zawsze są jakieś stałe bloki, aby zapewnić tylko jedno rozwiązanie? –
@TheoWalton zawsze istnieją pewne stałe bloki, aby zapewnić tylko jedno rozwiązanie istnieje. –
Obraz, do którego się odwołujesz, wygląda jak mieszanka zmiennej barwy i nasycenia. Nasycenie kolorów zwiększa się od środka promieniowo do krawędzi obrazu. Odcień zależy od kąta wokół środka obrazu. W ten sposób masz 2 wymiary we współrzędnych biegunowych. Czarne plamki barw deklarują teraz punkty kontrolne dla interpolacji na nieregularnej siatce. Jednakże, nie widząc żadnych innych przykładowych obrazów z tej gry, wciąż jest otwarty, niezależnie od tego, czy gradienty kolorów zawsze podążają za współrzędnymi biegunowymi, o których wspomniałem powyżej. –