2017-12-11 30 views
5

Tôi hiện đang làm việc trên một dự án sở thích để tự động giải quyết một câu đố từ trò chơi di động phổ biến I Love Hue. Trò chơi có sẵn here.Cách sắp xếp màu theo hai chiều?

Về cơ bản, toàn bộ tiền đề của trò chơi là bạn được cung cấp một loạt các khối hình chữ nhật màu được sắp xếp trong lưới. Bạn có thể hoán đổi hầu hết các khối ngoại trừ một vài khối cố định, được đánh dấu bằng các chấm đen. Đối tượng của trò chơi là trao đổi các khối xung quanh để bạn có được một phổ màu hai chiều. Các màu được sắp xếp sao cho màu của mỗi khối xấp xỉ trung bình của các màu xung quanh nó. (Xin lỗi, tôi không biết bất kỳ lý thuyết màu sắc nhưng có lẽ là một lời cho những gì tôi đang tìm kiếm.) Đây là những gì một câu đố đặc trưng trông giống như:

img

Tôi đã thể chụp ảnh màn hình thông qua adb, trích xuất ma trận RGB từ các khối và đánh dấu các khối nào là "cố định". Tôi đang gặp rắc rối với phần thuật toán thực tế của vấn đề này.

Dưới đây là những gì tôi đã làm như vậy cho đến nay:

  1. Chuyển đổi RGB để HSV và phân loại các màu sắc bởi màu sắc trong một danh sách một chiều. Điều này mang lại cho tôi một quang phổ, nhưng tôi không biết cách chuyển đổi kết quả này thành hai chiều.
  2. Rời khỏi các màu trong RGB và cố gắng làm việc với một màu ít. Có lẽ một số tính toán đa biến tôi có thể làm ở đây, nhưng khó khăn nằm trong thực tế là một số màu sắc chia sẻ một hoặc nhiều giá trị RGB của chúng. Nó sẽ là cần thiết để xem xét tất cả ba màu sắc.
  3. Sử dụng khoảng cách Euclide để tìm khoảng cách giữa mỗi cặp màu. Tôi hiểu rằng mục đích cuối cùng là để khoảng cách này là nhỏ nhất trong số các màu liền kề, nhưng lưới hai chiều đang làm cho việc này trở nên khó khăn hơn.
  4. Sử dụng khoảng cách Euclide, tôi đã phát triển một chỉ số về cách lý tưởng một lưới nhất định bằng cách nhìn vào khoảng cách Euclide của các khối liền kề. Tuy nhiên, tôi không thể tìm thấy một thuật toán hiệu quả có thể tìm ra các hoán đổi cần thiết để có được một trạng thái lý tưởng.
+0

ok Tôi đã chơi trò chơi nhưng từ bìa trước của trò chơi có vẻ như có 4 hướng có thể có màu sắc sẽ cho kết quả mịn ... chỉ cần tự hỏi nếu trò chơi chấp nhận tất cả 4 kết hợp. Hay luôn có một số khối cố định để đảm bảo chỉ có một giải pháp tồn tại? –

+0

@TheoWalton luôn có một số khối cố định để đảm bảo chỉ tồn tại một giải pháp. –

+1

Hình ảnh bạn đã tham chiếu trông giống như sự pha trộn giữa màu sắc và độ bão hòa khác nhau. Độ bão hòa màu tăng từ trung tâm hình ảnh xuyên qua biên giới hình ảnh. Màu sắc thay đổi theo góc xung quanh trung tâm hình ảnh. Bằng cách này bạn có 2 chiều trong các tọa độ cực. Các bản vá lỗi màu đen chấm hiện nay khai báo các điểm điều khiển cho một phép nội suy trên một lưới bất thường. Tuy nhiên, không nhìn thấy bất kỳ hình ảnh mẫu nào khác từ trò chơi đó, nó vẫn mở, cho dù các gradient màu luôn luôn theo các tọa độ cực tôi đã đề cập ở trên. –

Trả lời

4

Nếu bạn có nhiều solved hình ảnh mà bạn có thể tạo ra RGB đồ thị âm mưu

để vẽ đồ thị 3D nơi x,y là vị trí pixel và z được kiểm tra kênh màu (R, G hoặc B). Từ đó bạn có thể xác định một số thuộc tính của gradient. Nếu cốt truyện là một mặt phẳng hơn tất cả những gì bạn cần chỉ là bình thường (lấy từ 3 ô đã biết). Nếu nó là bề mặt cong tùy thuộc vào bao nhiêu điểm inflex nó có bạn có thể xác định như thế nào đa thức lớn đã được sử dụng cho nó. Từ tất cả những điều này bạn có thể bắt đầu giải quyết điều này.

tôi sẽ bắt đầu với một cái gì đó đơn giản (giả sử không khoảng cách quá lớn hoặc đa thức ưa thích):

Xử lý mỗi kênh màu riêng biệt. Tôi sẽ chỉ sử dụng các ô tĩnh và nội suy các màu lưới chỉ từ chúng.Một cái gì đó tương tự như:

Nếu không nhìn thấy các R, G, B đồ thị tôi không thể ước tính mà loại suy mà bạn cần. Nếu đồ thị là tuyến tính sử dụng nội suy tuyến tính hoặc tuyến tính. Nếu không sử dụng đa thức độ cao hơn.

Vì vậy, hãy điền vào bất kỳ ô lưới nào mà bạn có thể (có hàng xóm có màu đã biết). Sau đó, tìm ô có thể di chuyển gần nhất tới màu được tính toán (nếu ô có tất cả 3 kênh được nội suy) và đặt chúng (và đặt là tĩnh).

Bây giờ, chỉ cần lặp lại quy trình cho đến khi tất cả các ô được tính toán.

[Edit1 ngày 14 tháng 12 năm 2017] một số ghi chú thêm và các công cụ

Đã tò mò và có một số thời gian hiện nay vì vậy tôi đã cho nó một shot. Trước tiên, tôi tạo trò chơi trong C++/VCL để lấy hình ảnh của bạn làm đầu vào (được cắt và thay đổi kích cỡ). Sau đó, tôi được sắp xếp gạch bằng tay và vẽ đồ thị:

RGB plots

Các chấm trắng có nghĩa là gạch được đặt đúng (phù hợp với màu nội suy). Các vòng tròn màu xung quanh các chấm là các màu được nội suy (để so sánh trực quan, bạn cần thu phóng để xem chúng).

Như bạn có thể thấy các ô R, G, B 3D có nội suy tuyến tính do đó (bi) nên đủ.

Nếu tôi chỉ cố gắng nội suy tuyến tính cho các hàng, chỉ người giải quyết giải quyết câu đố ngay lập tức. Tuy nhiên Khi tôi mã hóa tương tự cho các cột (nhiều ô không xác định hơn giữa các cột đã biết), người giải quyết bắt đầu thực hiện vài lần đặt không chính xác (làm mất hiệu lực toàn bộ nội dung do đó các chấm trắng sai).

column solver

tôi cũng cố gắng HSL nhưng sau một thời gian tôi vứt nó đi do chạm vào tường vì Huế có thể vượt qua mức độ 0360 tại bất kỳ điểm nào mà không phải là phân biệt với trường hợp đã làm không vượt qua. Cho rằng nó sẽ cần một số heuristics hoặc tương quan chéo từ các khu vực lân cận giải quyết và đó sẽ là quá nhiều mã cho hương vị của tôi. Không có kết quả ở đó thậm chí còn tệ hơn khi sử dụng RGB.

Vì vậy, bây giờ tôi đang suy nghĩ về cách sử dụng Bilinear suy hoặc giải quyết interpolations khoảng cách ngắn nhất và chỉ sau đó giải quyết phần còn lại ...

[Edit2 14 Tháng 12 2017] Bilinear suy

Hình như bilinear RGB nội suy giải quyết tất cả các vấn đề. Vì vậy, nếu hội đồng quản trị của bạn được đính kèm với các tế bào cố định nó sẽ làm việc. Nếu không, bạn cần phải giải quyết các hội đồng lặp đi lặp lại và sau đó sử dụng các ô mới được giải quyết như là ràng buộc mới cho các khu vực chưa được giải quyết. Ngoài ra tôi nhận ra tôi đã RGB đảo ngược vì vậy tôi cũng sửa chữa đó :).

Đây C++/VCL nguồn cho các trò chơi (Nó không phải là tối ưu hóa ở tất cả):

//$$---- 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 
    } 
//--------------------------------------------------------------------------- 

Nó là một mẫu App duy nhất trong BDS2006 với single 40ms hẹn giờ trên đó. Vì vậy, chỉ cần thêm các sự kiện ... Bạn có thể bỏ qua các công cụ hiển thị và cửa sổ VCL. Điều quan trọng là lớp và hàm solve() trong đó. Nó được sử dụng cho cả hai kiểm tra đặt chính xác và để giải quyết (tùy thuộc vào bool _solve). Đây là hình ảnh đầu vào map.bmp

map.bmp

Tôi không mã hóa thích hợp lưu/chức năng nhà nước tải thay vào đó tôi đã chọn để sử dụng bitmap bản thân trực tiếp (lãng phí không gian nhưng hầu như không có nỗ lực code).

Bản đồ chính nó là 2D 32bit DWORD mảng với hình thức SSBBGGRR hex nơi SS là lá cờ của tế bào (cố định/giải quyết/chưa được giải quyết).

đây biên soạn bản demo với mã nguồn

Đọc readme.txt để biết thêm. Dưới đây là kết quả sau khi giải quyết (nhấn [S]):

solved state

Như bạn có thể (không) thấy các vòng tròn tan biến như màu bilinearly suy phù hợp chặt chẽ hơn đầu vào của bạn.

Chương trình đang mong đợi lưới có kích thước 7x9 độ phân giải của hình ảnh không quan trọng. Màu sắc được lấy mẫu từ điểm giữa của tế bào (chấm đen) và hơi bên phải (màu gạch)

Để thực hiện hiệu quả này, bạn có thể làm 2 điều:

  1. add/danh sách sử dụng có chứa ô chưa được giải quyết

    thay vì di chuột qua toàn bộ bản đồ chỉ lặp qua danh sách ô chưa được giải quyết.

  2. convert T(N^2) tìm kiếm để T((N^2)/2) bằng cách tìm kiếm tam giác

    này vẫn là tuy nhiên O(N^2) nhưng hằng số thời gian là nhỏ hơn.

  3. sử dụng 3D RGB LUT bảng

    dùng cho lưới lớn bạn có thể tạo 32K mục 3D LUT bảng để tìm ra tế bào phù hợp với tìm kiếm trong O(1).Chỉ cần chuyển đổi màu RGB thành 15 bit và sử dụng

    DWORD LUT[32][32][32]; 
    

    Nơi mà bạn sẽ biết vị trí của từng màu. Tất cả các màu chưa sử dụng được đặt thành 0xFFFFFFFF. Dưới đây là một ví dụ của việc sử dụng kỹ thuật này cho mục đích tương tự:

    Hãy tìm recolor[32][32][32] trong mã ... Trong màu 15bit thô có thể không đủ cho mục đích này rất có thể bạn sẽ cần nhiều bit hơn như 18bit dẫn đến 256K mục vẫn có thể quản lý được.

    Tạo điều này LUT sẽ mất O(N) thời gian nhưng chỉ sử dụng và duy trì thời gian là O(1).

0

Tôi không biết liệu điều này có hiệu quả hay không. Tôi vừa viết nó cho vui và không thể áp dụng một thử nghiệm thực sự trên đó. Nó sẽ được đánh giá cao nếu bạn vui lòng cho nó một thử và bình luận về nó.

 struct pixel 
     { 
      public int R; 
      public int G; 
      public int B; 
      public bool Fixed; 
      public pixel(int r, int g, int b, bool _fixed) 
      { 
       this.R = r; this.G = g; this.B = b; this.Fixed = _fixed; 
      } 
      public int DistanceSQ(pixel px) 
      { 
       int r = this.R - px.R; 
       int g = this.G - px.G; 
       int b = this.B - px.B; 
       return r * r + g * g + b * b; 
      } 
      public override string ToString() 
      { 
       return string.Format("{0} {1} {2} {3}", this.R, this.G, this.B, this.Fixed); 
      } 
      public override int GetHashCode() 
      { 
       return this.R.GetHashCode()^this.G.GetHashCode()^this.B.GetHashCode(); 
      } 
      public override bool Equals(object obj) 
      { 
       pixel px = (pixel)obj; 
       return this.R == px.R && this.G == px.G && this.B == px.B; 
      } 
     } 
     static void sort(pixel[,] img) 
     {    
      List<pixel> lst = new List<pixel>(); 
      foreach (pixel px in img) 
       if (!px.Fixed) 
        lst.Add(px); 

      int rows = img.GetLength(0); 
      int cols = img.GetLength(1); 
      while (lst.Count > 0) 
       for (int row = 0; row < rows; row++) 
        for (int col = 0; col < cols; col++) 
         if (!img[row, col].Fixed) 
         { 
          pixel[] neighbors = getFixedNeighbors(img, row, col, rows, cols).ToArray(); 
          int min = int.MaxValue; 
          pixel nearest = new pixel(); 
          foreach (pixel n in lst) 
          { 
           int dist = neighbors.Select((a) => a.DistanceSQ(n)).Sum(); 
           if (dist < min) 
           { 
            min = dist; 
            nearest = n; 
           } 
          } 
          nearest.Fixed = true; 
          img[row, col] = nearest; 
          lst.Remove(nearest); 
          if (lst.Count == 0) 
           return; 
         } 
     } 
     private static IEnumerable<pixel> getFixedNeighbors(pixel[,] img, int row, int col, int rows, int cols) 
     { 
      for (int r = Math.Max(0, row - 1); r < Math.Min(row + 2, rows); r++) 
       for (int c = Math.Max(0, col - 1); c < Math.Min(col + 2, cols); c++) 
        if (img[r, c].Fixed) 
         yield return img[r, c]; 

     } 



     //test 
     { 
      bool b0 = false; bool b1 = true;//for easy editing 
      { 
       pixel[,] img = new pixel[3, 4]; 
       img[0, 0] = new pixel(0, 0, 0, b1); img[1, 0] = new pixel(0, 1, 0, b0); img[2, 0] = new pixel(0, 2, 0, b1); 
       img[0, 1] = new pixel(1, 0, 0, b0); img[1, 1] = new pixel(1, 1, 0, b0); img[2, 1] = new pixel(1, 2, 0, b0); 
       img[0, 2] = new pixel(2, 0, 0, b0); img[1, 2] = new pixel(2, 1, 0, b0); img[2, 2] = new pixel(2, 2, 0, b0); 
       img[0, 3] = new pixel(3, 0, 0, b1); img[1, 3] = new pixel(3, 1, 0, b0); img[2, 3] = new pixel(3, 2, 0, b1); 
       sort(img); 
      } 
      { 
       pixel[,] img = new pixel[3, 4]; 
       img[0, 0] = new pixel(0, 0, 0, b1); img[1, 0] = new pixel(0, 1, 0, b0); img[2, 0] = new pixel(0, 2, 0, b1); 
       img[0, 1] = new pixel(2, 0, 0, b0); img[1, 2] = new pixel(2, 1, 0, b0); img[2, 2] = new pixel(2, 2, 0, b0); 
       img[0, 2] = new pixel(1, 0, 0, b0); img[1, 1] = new pixel(1, 1, 0, b0); img[2, 1] = new pixel(1, 2, 0, b0); 
       img[0, 3] = new pixel(3, 0, 0, b1); img[1, 3] = new pixel(3, 1, 0, b0); img[2, 3] = new pixel(3, 2, 0, b1); 
       sort(img); 
      } 
     } 

Mã đơn giản. Nó giữ những cái chưa được xếp hạng trong một danh sách và loại bỏ mỗi khi vị trí được tìm thấy cho nó. Để quyết định nên chọn màu nào cho một vị trí, màu sắc có tổng khoảng cách vuông tối thiểu được chọn. Sqrt là không cần thiết vì chúng tôi chỉ cần nó để so sánh.

"sắp xếp" là chức năng chính thay đổi vị trí của các pixel không cố định. Dữ liệu đầu vào cho hàm này là một mảng các hàng pixel. "sắp xếp" chức năng thực hiện thay đổi trên mảng này.

+0

thêm một số từ về cách hoạt động của nó. Mã không được nhận xét thuần túy khó nắm bắt đối với bất kỳ ai khác thì tác giả của nó ngay cả khi nó trông đơn giản .... – Spektre

+0

@Spektre Tôi đã thêm một số giải thích về nó. Tôi hy vọng nó đủ. Mã giải thích chính nó tốt hơn. Tôi không nghĩ rằng chúng ta cần phải đối phó với nội suy cho vấn đề này; nhưng tôi không chắc chắn về nó. Cảm ơn. – Koray

+1

đó là tốt hơn một chút nhưng tôi cảm thấy để làm cho điều này có thể sử dụng cho người khác Bạn nên ít nhất thêm những gì các biến chính và phương tiện và làm thế nào đầu vào và đầu ra của câu đố được lưu trữ (định dạng). – Spektre

Các vấn đề liên quan