Melhorando o desempenho da detecção de cliques em uma grade isométrica de coluna escalonada

Estou trabalhando em um motor de jogo isométrico e já criei um algoritmo para detecção de cliques perfeitos em pixels. Visite o projeto e observe que a detecção de cliques é capaz de detectar qual borda do bloco foi clicada. Ele também verifica o índice y para clicar no bloco mais inicial.

Uma explicação do meu algoritmo atual:

A grade isométrica é composta de imagens de blocos de 100 x 65 pixels. TileW=100, TileL=50, tileH=15

Dimensionamento de telha

O mapa é representado por um map[z][y][x] matriz tridimensional map[z][y][x] .

Os pontos centrais da telha (x,y) são calculados da seguinte forma:

 //x, y, z are the position of the tile if(y%2===0) { x-=-0.5; } //To accommodate the offset found in even rows this.centerX = (x*tileW) + (tileW/2); this.centerY = (y*tileL) - y*((tileL)/2) + ((tileL)/2) + (tileH/2) - (z*tileH); 

Grade isométrica

Funções de protótipo que determinam se o mouse está dentro de uma determinada área no bloco:

 Tile.prototype.allContainsMouse = function() { var dx = Math.abs(mouse.mapX-this.centerX), dy = Math.abs(mouse.mapY-this.centerY); if(dx>(tileW/2)) {return false;} //Refer to image return (dx/(tileW*0.5) + (dy/(tileL*0.5)) < (1+tileHLRatio)); } 

Tile.prototype.allContainsMouse() retorna true se mouse estiver dentro de verde. A área vermelha é cortada, verificando se dx> metade da largura do ladrilho

figura 1


 Tile.prototype.topContainsMouse = function() { var topFaceCenterY = this.centerY - (tileH/2); var dx = Math.abs(mouse.mapX-this.centerX), dy = Math.abs(mouse.mapY-topFaceCenterY); return ((dx/(tileW*0.5) + dy/(tileL*0.5) <= 1)); }; 

Retorna verdadeiro se o mouse estiver na face superior


 Tile.prototype.leftContainsMouse = function() { var dx = mouse.mapX-this.centerX; if(dx<0) { return true; } else { return false; } }; 

(Se o mouse for deixado do ponto central)


 Tile.prototype.rightContainsMouse = function() { var dx = mouse.mapX-this.centerX; if(dx>0) { return true; } else { return false; } }; 

(Se o mouse estiver à direita do ponto central)

Reunindo todos os methods para funcionar como um:

  • Loop Através de todo o mapa 3d [z] [y] [x] array
  • Se allContainsMouse() retornar true, map [z] [y] [x] é o bloco em que nosso mouse está.
  • Adicione este bloco à matriz tilesUnderneathMouse matriz.
  • Faça um loop pelo array tilesUnderneathMouse e escolha o bloco com o maior y . É o azulejo mais inicial.

     if(allContainsMouse && !topContainsMouse) 

Jogo inferior

  •  if(allContainsMouse && !topContainsMouse && leftContainsMouse) 

partida esquerda

(Conceito semelhante aplica-se para a direita)

Finalmente, minhas perguntas:

# 1 Como você conseguiria isso, de modo que seja mais eficiente (não em loop através de todas as peças) (o código pesudo é aceito)?

# 2 Se você não conseguir responder # 1, que sugestões você tem para melhorar a eficiência da minha detecção de cliques (o carregamento do bloco já foi considerado)?

O que eu pensei:

Eu originalmente tentei resolver esse problema não usando pontos centrais de blocos, e sim convertendo a posição do mouse (x, y) diretamente para o bloco x, y. Na minha opinião, isso é o mais difícil de codificar, mas a solução mais eficiente. Em uma grade quadrada, é muito fácil converter uma posição (x, y) em um quadrado na grade. No entanto, em uma grade de coluna escalonada, você lida com compensações. Tentei calcular deslocamentos usando a function a que leva um valor x ou y e retorna o deslocamento resultante y ou x. O gráfico Zig-zag de arccos (cosx) resolveu isso.

Verificar se o mouse estava dentro do bloco, usar esse método foi difícil e não consegui descobrir. Eu estava verificando se o mouse (x, y) estava abaixo de uma linha y=mx+b que dependia da aproximação tileY, tileY (uma grade quadrada aprox).

Se você chegou até aqui, obrigado!

Esta resposta é baseada em:

  • Valores de imagem em grade 2D para matriz 2D

Então aqui vai:

  1. conversão entre grade e canvas

    Como mencionei no comentário, você deve criar funções que convertam entre posições de grade de canvas e célula. algo como (em C ++ ):

     //--------------------------------------------------------------------------- // tile sizes const int cxs=100; const int cys= 50; const int czs= 15; const int cxs2=cxs>>1; const int cys2=cys>>1; // view pan (no zoom) int pan_x=0,pan_y=0; //--------------------------------------------------------------------------- void isometric::cell2scr(int &sx,int &sy,int cx,int cy,int cz) // grid -> screen { sx=pan_x+(cxs*cx)+((cy&1)*cxs2); sy=pan_y+(cys*cy/2)-(czs*cz); } //--------------------------------------------------------------------------- void isometric::scr2cell(int &cx,int &cy,int &cz,int sx,int sy) // screen -> grid { // rough cell ground estimation (no z value yet) cy=(2*(sy-pan_y))/cys; cx= (sx-pan_x-((cy&1)*cxs2))/cxs; cz=0; // isometric tile shape crossing correction int xx,yy; cell2scr(xx,yy,cx,cy,cz); xx=sx-xx; mx0=cx; yy=sy-yy; my0=cy; if (xx< =cxs2) { if (yy> xx *cys/cxs) { cy++; if (int(cy&1)!=0) cx--; } } else { if (yy>(cxs-xx)*cys/cxs) { cy++; if (int(cy&1)==0) cx++; } } } //--------------------------------------------------------------------------- 

    Eu usei o seu layout (demorei mi para converter o meu para ele, espero que eu não tenha feito algum erro bobo em algum lugar):

    layout

    • cruz vermelha representa coordenadas retornadas por cell2scr(x,y,0,0,0)
    • cruz verde representa coordenadas do mouse
    • aqua highlight representa a posição da célula retornada

    Cuidado se você estiver usando aritmética de números inteiros que você precisa ter em mente se você dividir / multiplicar por metade dos tamanhos, você pode perder a precisão. Use o tamanho total e divida o resultado por 2 para tais casos (gaste muito tempo imaginando aquele no passado).

    O cell2scr é bastante simples. A posição da canvas é deslocamento horizontal + posição da célula multiplicada pelo seu tamanho (etapa). O eixo x precisa de uma correção para as linhas pares / ímpares (é para isso que ((cy&1)*cxs2) ) e o eixo y é deslocado pelo eixo z ( ((cy&1)*cxs2) ). O meu ecrã tem um ponto (0,0) no canto superior esquerdo, o eixo +x está a apontar para a direita e o +y está a apontar para baixo.

    O scr2cell é feito pela posição da canvas resolvida algebricamente a partir das equações de cell2scr , assumindo-se z=0 portanto, seleciona apenas o grid ground. Além disso, apenas a correção par / ímpar é adicionada se a posição do mouse estiver fora da área da célula encontrada.

  2. digitalizar vizinhos

    o scr2cell(x,y,z,mouse_x,mouse_y) retorna apenas a célula onde seu mouse está no chão. por isso, se você quiser adicionar sua funcionalidade de seleção atual, você precisará verificar a célula superior nessa posição e algumas células vizinhas e selecionar aquela com a menor distância.

    Não há necessidade de escanear toda a grade / mapa apenas algumas células em torno da posição retornada. Isso deve acelerar consideravelmente a coisa.

    Eu faço assim:

    padrão de varredura

    O número de linhas depende do tamanho do eixo z da célula ( czs ), do número máximo de camadas z ( gzs ) e do tamanho da célula ( cys ). O código C ++ meu com scan se parece com isso:

     // grid size const int gxs=15; const int gys=30; const int gzs=8; // my map (all the cells) int map[gzs][gys][gxs]; void isometric::scr2cell(int &cx,int &cy,int &cz,int sx,int sy) { // rough cell ground estimation (no z value yet) cy=(2*(sy-pan_y))/cys; cx= (sx-pan_x-((cy&1)*cxs2))/cxs; cz=0; // isometric tile shape crossing correction int xx,yy; cell2scr(xx,yy,cx,cy,cz); xx=sx-xx; yy=sy-yy; if (xx< =cxs2) { if (yy> xx *cys/cxs) { cy++; if (int(cy&1)!=0) cx--; } } else { if (yy>(cxs-xx)*cys/cxs) { cy++; if (int(cy&1)==0) cx++; } } // scan closest neighbors int x0=-1,y0=-1,z0=-1,a,b,i; #define _scann \ if ((cx>=0)&&(cx=0)&&(cy=0)&&(a< =cxs)&&(b>=0)&&(b< =cxs)) \ if (cz>=z0) { x0=cx; y0=cy; z0=cz; } \ } _scann; // scan actual cell for (i=gzs*czs;i>=0;i-=cys) // scan as many lines bellow actual cell as needed { cy++; if (int(cy&1)!=0) cx--; _scann; cx++; _scann; cy++; if (int(cy&1)!=0) cx--; _scann; } cx=x0; cy=y0; cz=z0; // return remembered cell coordinate #undef _scann } 

    Isso seleciona sempre a célula superior (a mais alta de todas as possíveis) ao jogar com o mouse, é sentida corretamente (pelo menos para mim):

    Resultado do scaneamento

Aqui completa a fonte VCL / C ++ para o meu motor isométrico que eu ataquei hoje:

  //--------------------------------------------------------------------------- //--- Isometric ver: 1.01 --------------------------------------------------- //--------------------------------------------------------------------------- #ifndef _isometric_h #define _isometric_h //--------------------------------------------------------------------------- //--------------------------------------------------------------------------- // colors 0x00BBGGRR DWORD col_back =0x00000000; DWORD col_grid =0x00202020; DWORD col_xside=0x00606060; DWORD col_yside=0x00808080; DWORD col_zside=0x00A0A0A0; DWORD col_sel =0x00FFFF00; //--------------------------------------------------------------------------- //--- configuration defines ------------------------------------------------- //--------------------------------------------------------------------------- // #define isometric_layout_1 // x axis: righ+down, y axis: left+down // #define isometric_layout_2 // x axis: righ , y axis: left+down //--------------------------------------------------------------------------- #define isometric_layout_2 //--------------------------------------------------------------------------- //--------------------------------------------------------------------------- /* // grid size const int gxs=4; const int gys=16; const int gzs=8; // cell size const int cxs=100; const int cys= 50; const int czs= 15; */ // grid size const int gxs=15; const int gys=30; const int gzs=8; // cell size const int cxs=40; const int cys=20; const int czs=10; const int cxs2=cxs>>1; const int cys2=cys>>1; // cell types enum _cell_type_enum { _cell_type_empty=0, _cell_type_ground, _cell_type_full, _cell_types }; //--------------------------------------------------------------------------- class isometric { public: // screen buffer Graphics::TBitmap *bmp; DWORD **pyx; int xs,ys; // isometric map int map[gzs][gys][gxs]; // mouse int mx,my,mx0,my0; // [pixel] TShiftState sh,sh0; int sel_x,sel_y,sel_z; // [grid] // view int pan_x,pan_y; // constructors for compiler safety isometric(); isometric(isometric& a) { *this=a; } ~isometric(); isometric* operator = (const isometric *a) { *this=*a; return this; } isometric* operator = (const isometric &a); // Window API void resize(int _xs,int _ys); // [pixels] void mouse(int x,int y,TShiftState sh); // [mouse] void draw(); // auxiliary API void cell2scr(int &sx,int &sy,int cx,int cy,int cz); void scr2cell(int &cx,int &cy,int &cz,int sx,int sy); void cell_draw(int x,int y,int tp,bool _sel=false); // [screen] void map_random(); }; //--------------------------------------------------------------------------- //--------------------------------------------------------------------------- isometric::isometric() { // init screen buffers bmp=new Graphics::TBitmap; bmp->HandleType=bmDIB; bmp->PixelFormat=pf32bit; pyx=NULL; xs=0; ys=0; resize(1,1); // init map int x,y,z,t; t=_cell_type_empty; // t=_cell_type_ground; // t=_cell_type_full; for (z=0;zCanvas->Draw(0,0,a.bmp); int x,y,z; for (z=0;zSetSize(_xs,_ys); xs=bmp->Width; ys=bmp->Height; if (pyx) delete pyx; pyx=new DWORD*[ys]; for (int y=0;yScanLine[y]; // center view cell2scr(pan_x,pan_y,gxs>>1,gys>>1,0); pan_x=(xs>>1)-pan_x; pan_y=(ys>>1)-pan_y; } //--------------------------------------------------------------------------- void isometric::mouse(int x,int y,TShiftState shift) { mx0=mx; mx=x; my0=my; my=y; sh0=sh; sh=shift; scr2cell(sel_x,sel_y,sel_z,mx,my); if ((sel_x<0)||(sel_y<0)||(sel_z<0)||(sel_x>=gxs)||(sel_y>=gys)||(sel_z>=gzs)) { sel_x=-1; sel_y=-1; sel_z=-1; } } //--------------------------------------------------------------------------- void isometric::draw() { int x,y,z,xx,yy; // clear space bmp->Canvas->Brush->Color=col_back; bmp->Canvas->FillRect(TRect(0,0,xs,ys)); // grid DWORD c0=col_zside; col_zside=col_back; for (y=0;yCanvas->Pen->Color=clBlue; bmp->Canvas->MoveTo(mx0-10,my0); bmp->Canvas->LineTo(mx0+10,my0); bmp->Canvas->MoveTo(mx0,my0-10); bmp->Canvas->LineTo(mx0,my0+10); // mouse cross bmp->Canvas->Pen->Color=clGreen; bmp->Canvas->MoveTo(mx-10,my); bmp->Canvas->LineTo(mx+10,my); bmp->Canvas->MoveTo(mx,my-10); bmp->Canvas->LineTo(mx,my+10); // grid origin cross bmp->Canvas->Pen->Color=clRed; bmp->Canvas->MoveTo(pan_x-10,pan_y); bmp->Canvas->LineTo(pan_x+10,pan_y); bmp->Canvas->MoveTo(pan_x,pan_y-10); bmp->Canvas->LineTo(pan_x,pan_y+10); bmp->Canvas->Font->Charset=OEM_CHARSET; bmp->Canvas->Font->Name="System"; bmp->Canvas->Font->Pitch=fpFixed; bmp->Canvas->Font->Color=clAqua; bmp->Canvas->Brush->Style=bsClear; bmp->Canvas->TextOutA(5, 5,AnsiString().sprintf("Mouse: %ix %i",mx,my)); bmp->Canvas->TextOutA(5,20,AnsiString().sprintf("Select: %ix %ix %i",sel_x,sel_y,sel_z)); bmp->Canvas->Brush->Style=bsSolid; } //--------------------------------------------------------------------------- void isometric::cell2scr(int &sx,int &sy,int cx,int cy,int cz) { #ifdef isometric_layout_1 sx=pan_x+((cxs*(cx-cy))/2); sy=pan_y+((cys*(cx+cy))/2)-(czs*cz); #endif #ifdef isometric_layout_2 sx=pan_x+(cxs*cx)+((cy&1)*cxs2); sy=pan_y+(cys*cy/2)-(czs*cz); #endif } //--------------------------------------------------------------------------- void isometric::scr2cell(int &cx,int &cy,int &cz,int sx,int sy) { int x0=-1,y0=-1,z0=-1,a,b,i,xx,yy; #ifdef isometric_layout_1 // rough cell ground estimation (no z value yet) // translate to (0,0,0) top left corner of the grid xx=sx-pan_x-cxs2; yy=sy-pan_y+cys2; // change aspect to square cells cxs x cxs yy=(yy*cxs)/cys; // use the dot product with axis vectors to compute grid cell coordinates cx=(+xx+yy)/cxs; cy=(-xx+yy)/cxs; cz=0; // scan closest neighbors #define _scann \ if ((cx>=0)&&(cx=0)&&(cy=0)&&(a< =cxs)&&(b>=0)&&(b< =cxs)) \ if (cz>=z0) { x0=cx; y0=cy; z0=cz; } \ } _scann; // scan actual cell for (i=gzs*czs;i>=0;i-=cys) // scan as many lines bellow actual cell as needed { cy++; _scann; cx++; cy--; _scann; cy++; _scann; } cx=x0; cy=y0; cz=z0; // return remembered cell coordinate #undef _scann #endif #ifdef isometric_layout_2 // rough cell ground estimation (no z value yet) cy=(2*(sy-pan_y))/cys; cx= (sx-pan_x-((cy&1)*cxs2))/cxs; cz=0; // isometric tile shape crossing correction cell2scr(xx,yy,cx,cy,cz); xx=sx-xx; yy=sy-yy; if (xx< =cxs2) { if (yy> xx *cys/cxs) { cy++; if (int(cy&1)!=0) cx--; } } else { if (yy>(cxs-xx)*cys/cxs) { cy++; if (int(cy&1)==0) cx++; } } // scan closest neighbors #define _scann \ if ((cx>=0)&&(cx=0)&&(cy=0)&&(a< =cxs)&&(b>=0)&&(b< =cxs)) \ if (cz>=z0) { x0=cx; y0=cy; z0=cz; } \ } _scann; // scan actual cell for (i=gzs*czs;i>=0;i-=cys) // scan as many lines bellow actual cell as needed { cy++; if (int(cy&1)!=0) cx--; _scann; cx++; _scann; cy++; if (int(cy&1)!=0) cx--; _scann; } cx=x0; cy=y0; cz=z0; // return remembered cell coordinate #undef _scann #endif } //--------------------------------------------------------------------------- void isometric::cell_draw(int x,int y,int tp,bool _sel) { TPoint pnt[5]; bmp->Canvas->Pen->Color=col_grid; if (tp==_cell_type_empty) { if (!_sel) return; bmp->Canvas->Pen->Color=col_sel; pnt[0].x=x; pnt[0].y=y ; pnt[1].x=x+cxs2; pnt[1].y=y+cys2; pnt[2].x=x+cxs; pnt[2].y=y ; pnt[3].x=x+cxs2; pnt[3].y=y-cys2; pnt[4].x=x; pnt[4].y=y ; bmp->Canvas->Polyline(pnt,4); } else if (tp==_cell_type_ground) { if (_sel) bmp->Canvas->Brush->Color=col_sel; else bmp->Canvas->Brush->Color=col_zside; pnt[0].x=x; pnt[0].y=y ; pnt[1].x=x+cxs2; pnt[1].y=y+cys2; pnt[2].x=x+cxs; pnt[2].y=y ; pnt[3].x=x+cxs2; pnt[3].y=y-cys2; bmp->Canvas->Polygon(pnt,3); } else if (tp==_cell_type_full) { if (_sel) bmp->Canvas->Brush->Color=col_sel; else bmp->Canvas->Brush->Color=col_xside; pnt[0].x=x+cxs2; pnt[0].y=y+cys2; pnt[1].x=x+cxs; pnt[1].y=y; pnt[2].x=x+cxs; pnt[2].y=y -czs; pnt[3].x=x+cxs2; pnt[3].y=y+cys2-czs; bmp->Canvas->Polygon(pnt,3); if (_sel) bmp->Canvas->Brush->Color=col_sel; else bmp->Canvas->Brush->Color=col_yside; pnt[0].x=x; pnt[0].y=y; pnt[1].x=x+cxs2; pnt[1].y=y+cys2; pnt[2].x=x+cxs2; pnt[2].y=y+cys2-czs; pnt[3].x=x; pnt[3].y=y -czs; bmp->Canvas->Polygon(pnt,3); if (_sel) bmp->Canvas->Brush->Color=col_sel; else bmp->Canvas->Brush->Color=col_zside; pnt[0].x=x; pnt[0].y=y -czs; pnt[1].x=x+cxs2; pnt[1].y=y+cys2-czs; pnt[2].x=x+cxs; pnt[2].y=y -czs; pnt[3].x=x+cxs2; pnt[3].y=y-cys2-czs; bmp->Canvas->Polygon(pnt,3); } } //--------------------------------------------------------------------------- void isometric::map_random() { int i,x,y,z,x0,y0,r,h; // clear for (z=0;z>3)+1; h=Random(gzs); for (z=0;(z=0)&&(y=0)&&(x 

O layout define apenas o sistema de coordenadas axises direções (para o seu uso #define isometric_layout_2 ). Isso usa o Borlands VCL Graphics::TBitmap portanto, se você não usar o Borland, altere-o para qualquer bitmap GDI ou sobrescreva a parte gfx para a sua API gfx (isso é relevante apenas para draw() e resize() ). Também o TShiftState faz parte do VCL , é apenas o estado dos botões do mouse e teclas especiais como shift,alt,ctrl então você pode usar o bool ou qualquer outra coisa (atualmente não usado, pois ainda não tenho nenhuma funcionalidade).

Aqui meu código de janela da Borland (aplicativo de formulário único com um timer) para ver como usar isto:

 //$$---- Form CPP ---- //--------------------------------------------------------------------------- #include  #pragma hdrstop #include "win_main.h" #include "isometric.h" //--------------------------------------------------------------------------- #pragma package(smart_init) #pragma resource "*.dfm" TMain *Main; isometric iso; //--------------------------------------------------------------------------- void TMain::draw() { iso.draw(); Canvas->Draw(0,0,iso.bmp); } //--------------------------------------------------------------------------- __fastcall TMain::TMain(TComponent* Owner) : TForm(Owner) { Cursor=crNone; iso.map_random(); } //--------------------------------------------------------------------------- void __fastcall TMain::FormResize(TObject *Sender) { iso.resize(ClientWidth,ClientHeight); draw(); } //--------------------------------------------------------------------------- void __fastcall TMain::FormPaint(TObject *Sender) { draw(); } //--------------------------------------------------------------------------- void __fastcall TMain::tim_redrawTimer(TObject *Sender) { draw(); } //--------------------------------------------------------------------------- void __fastcall TMain::FormMouseMove(TObject *Sender, TShiftState Shift, int X,int Y) { iso.mouse(X,Y,Shift); draw(); } void __fastcall TMain::FormMouseDown(TObject *Sender, TMouseButton Button,TShiftState Shift, int X, int Y) { iso.mouse(X,Y,Shift); draw(); } void __fastcall TMain::FormMouseUp(TObject *Sender, TMouseButton Button,TShiftState Shift, int X, int Y) { iso.mouse(X,Y,Shift); draw(); } //--------------------------------------------------------------------------- void __fastcall TMain::FormDblClick(TObject *Sender) { iso.map_random(); } //--------------------------------------------------------------------------- 

[Edit1] abordagem gráfica

Dê uma olhada no Conselho de Interação do Usuário do Simple OpenGL GUI Framework? .

A idéia principal é criar um buffer de canvas de sombra onde o id da célula renderizada é armazenado. Isso fornece uma seleção de sprite / célula perfeita em pixels em O(1) apenas com poucas linhas de código.

  1. criar buffer de canvas de sombra idx[ys][xs]

    Ele deve ter a mesma resolução que a sua visualização de mapa E deve ser capaz de armazenar o valor (x,y,z) da célula de renderização dentro de um único pixel (em unidades de célula de grade de mapa). Eu uso o formato de pixel de 32 bits, então eu escolho 12 bits para x,y e 8 bits para z

     DWORD color = (x) | (y< <12) | (z<<24) 
  2. antes da renderização do mapa, limpe esse buffer

    Eu uso 0xFFFFFFFF como cor vazia, por isso não está colidindo com a célula (0,0,0) .

  3. na renderização de sprite de célula de mapa

    sempre que você renderizar pixel para buffer de canvas pyx[y][x]=color você também renderizar pixel a buffer de canvas de sombra idx[y][x]=c onde c é a posição da célula codificada nas unidades de grade do mapa (ver # 1 ).

  4. No clique do mouse (ou qualquer outro)

    Você tem a posição da canvas do mouse mx,my então se estiver na faixa, basta ler o buffer de sombra e obter a posição da célula selecionada.

     c=idx[my][mx] if (c!=0xFFFFFFFF) { x= c &0x00000FFF; y=(c>>12)&0x00000FFF; z=(c>>24)&0x000000FF; } else { // here use the grid floor cell position formula from above approach if needed // or have empty cell rendered for z=0 with some special sprite to avoid this case. } 

    Com a codificação acima deste mapa (canvas):

    tela

    é renderizado também para a canvas de sombra como esta:

    sombra

    Seleção é pixel perfeito, não importa se você clicar em cima, lado ...

    As telhas usadas são:

     Title: Isometric 64x64 Outside Tileset Author: Yar URL: http://opengameart.org/content/isometric-64x64-outside-tileset License(s): * CC-BY 3.0 http://creativecommons.org/licenses/by/3.0/legalcode 

    E aqui Win32 Demo:

    • demonstração