Improving performance of click detection on a staggered column isometric grid

Asked 9/3, 2016 at 7:1 Answered 10/3, 2016 at 13:32

javascript algorithm click collision-detection isometric

I am working on an isometric game engine and have already created an algorithm for pixel perfect click detection. Visit the project and notice that click detection is able to detect which edge of the tile was clicked. It is also checks the y-index to click the most upfront tile.

An Explanation of my current algorithm:

The isometric grid is made of tile images that are 100*65px. TileW=100, TileL=50, tileH=15

The map is represented by a three-dimensional array map[z][y][x].

Tile center points (x,y) are calculated like so:

//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);

Prototype functions that determine if the mouse is within a given area on the tile:

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() returns true if mouse is within green. Red area is cropped out by checking if dx > half the tile's width

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));
};

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

(If mouse is left of the center point)

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

(If mouse is right of the center point)

Bringing all the methods together to work as one:

Loop Through the entire 3d map[z][y][x] array
if allContainsMouse() returns true, map[z][y][x] is the tile our mouse is on.
Add this tile to the array tilesUnderneathMouse array.
Loop through tilesUnderneathMouse array, and choose the tile with the highest y. It is the most upfront tile.
```
if(allContainsMouse && !topContainsMouse)
```

if(allContainsMouse && !topContainsMouse && leftContainsMouse)

(Similar concept applies for right)

Finally, my questions:

#1 How would you accomplish this, such that it is more efficient(not looping through all tiles)(pesudo code accepted)

#2 If you are unable to answer #1, what suggestions do you have to improve the efficiency of my click detection (chunk loading has already been considered)

What I've thought of:

I originally tried to solve this problem by not using tile center points, rather converting the mouse(x,y) position directly to the tile x,y. In my mind this is the hardest to code, yet most efficient solution. On a square grid it's very easy to convert an (x,y) position to a square on the grid. However in a staggered column grid, you deal with offsets. I tried to calculate offsets using the a function that takes an x or y value, and returns the resultant offset y, or x. The Zig-zag graph of arccos(cosx) solved that.

Checking if the mouse was within the tile, using this method was difficult and I couldn't figure it out. I was checking whether the mouse(x,y) was beneath a y=mx+b line that was dependent on the tileX, tileY approximation(a square grid approx).

If you got to here, Thanks!

Valenciavalenciennes answered 9/3, 2016 at 7:1 Comment(4)

see 2D grid image values to 2D array you can compute the floor grid coordinates directly from mouse coordinates and then just loop through the Y,Z axis of close neighbors only – Dammar 9/3, 2016 at 11:31

Can a tile be tall enough to completely hide the tiles above/above-to-the-left/above-to-the-right? – Scoot 9/3, 2016 at 13:20

@DavidEisenstat No, this is a game engine and must support every tile the programmer wishes to have. – Valenciavalenciennes 9/3, 2016 at 16:45

@MaxMastalerz was curios so I played a bit with my isometric engine and successfully implemented my approach. Have edited my answer and added also the scanning part ... – Dammar 10/3, 2016 at 18:28

This answer is based on:

2D grid image values to 2D array

So here it goes:

conversion between grid and screen

As I mentioned in comment you should make functions that convert between screen and cell grid positions. something like (in 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++; } }
     }
 //---------------------------------------------------------------------------
```
I used your layout (took mi while to convert mine to it hopefully I do not made some silly mistake somewhere):
- red cross represents coordinates returned by cell2scr(x,y,0,0,0)
- green cross represents mouse coordinates
- aqua highlight represents returned cell position
Beware if you are using integer arithmetics you need to take in mind if you dividing/multiplying by half sizes you can lose precision. Use full size and divide the result by 2 for such cases (spend a lot of time figuring that one out in the past).

The cell2scr is pretty straightforward. The screen position is pan offset + cell position multiplied by its size (step). The x axis need a correction for even/odd rows (that is what ((cy&1)*cxs2) is for) and y axis is shifted by the z axis (((cy&1)*cxs2)). Mine screen has point (0,0) in upper left corner, +x axis is pointing right and +y is pointing down.

The scr2cell is done by algebraically solved screen position from the equations of cell2scr while assuming z=0 so selects only the grid ground. On top of that is just the even/odd correction added if mouse position is outside found cell area.

scan neighbors

the scr2cell(x,y,z,mouse_x,mouse_y) returns just cell where your mouse is on the ground. so if you want to add your current selection functionality you need to scan the top cell on that position and few neighboring cells and select the one with least distance.

No need to scan the whole grid/map just few cells around returned position. That should speed up thing considerably.

I do it like this:

The number of lines depends on the cell z axis size (czs), max number of z layers (gzs) and the cell size (cys). The C++ code of mine with scan looks like this:

 // 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<gxs))                                                  \
      if ((cy>=0)&&(cy<gys))                                                 \
         {                                                                   \
         for (cz=0;(map[cz+1][cy][cx]!=_cell_type_empty)&&(cz<czs-1);cz++);  \
         cell2scr(xx,yy,cx,cy,cz);                                           \
         if (map[cz][cy][cx]==_cell_type_full) yy-=czs;                      \
         xx=(sx-xx); yy=((sy-yy)*cxs)/cys;                                   \
         a=(xx+yy);  b=(xx-yy);                                              \
         if ((a>=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
     }

This selects always the top cell (highest from all the possible) when playing with mouse it feels correctly (at least to me):

Here complete VCL/C++ source for mine isometric engine I busted for this today:

    //---------------------------------------------------------------------------
    //--- 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;z<gzs;z++,t=_cell_type_empty)
         for (y=0;y<gys;y++)
          for (x=0;x<gxs;x++)
           map[z][y][x]=t;
        // init mouse
        mx =0; my =0; sh =TShiftState();
        mx0=0; my0=0; sh0=TShiftState();
        sel_x=-1; sel_y=-1; sel_z=-1;
        // init view
        pan_x=0; pan_y=0;
        }
    //---------------------------------------------------------------------------
    isometric::~isometric()
        {
        if (pyx) delete[] pyx; pyx=NULL;
        if (bmp) delete   bmp; bmp=NULL;
        }
    //---------------------------------------------------------------------------
    isometric* isometric::operator = (const isometric &a)
        {
        resize(a.xs,a.ys);
        bmp->Canvas->Draw(0,0,a.bmp);
        int x,y,z;
        for (z=0;z<gzs;z++)
         for (y=0;y<gys;y++)
          for (x=0;x<gxs;x++)
           map[z][y][x]=a.map[z][y][x];
        mx=a.mx; mx0=a.mx0; sel_x=a.sel_x;
        my=a.my; my0=a.my0; sel_y=a.sel_y;
        sh=a.sh; sh0=a.sh0; sel_z=a.sel_z;
        pan_x=a.pan_x;
        pan_y=a.pan_y;
        return this;
        }
    //---------------------------------------------------------------------------
    void isometric::resize(int _xs,int _ys)
        {
        if (_xs<1) _xs=1;
        if (_ys<1) _ys=1;
        if ((xs==_xs)&&(ys==_ys)) return;
        bmp->SetSize(_xs,_ys);
        xs=bmp->Width;
        ys=bmp->Height;
        if (pyx) delete pyx;
        pyx=new DWORD*[ys];
        for (int y=0;y<ys;y++) pyx[y]=(DWORD*) bmp->ScanLine[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;y<gys;y++)
         for (x=0;x<gxs;x++)
            {
            cell2scr(xx,yy,x,y,0);
            cell_draw(xx,yy,_cell_type_ground,false);
            }
        col_zside=c0;
        // cells
        for (z=0;z<gzs;z++)
         for (y=0;y<gys;y++)
          for (x=0;x<gxs;x++)
            {
            cell2scr(xx,yy,x,y,z);
            cell_draw(xx,yy,map[z][y][x],(x==sel_x)&&(y==sel_y)&&(z==sel_z));
            }
        // mouse0 cross
        bmp->Canvas->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: %i x %i",mx,my));
        bmp->Canvas->TextOutA(5,20,AnsiString().sprintf("Select: %i x %i x %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<gxs))                                                  \
         if ((cy>=0)&&(cy<gys))                                                 \
            {                                                                   \
            for (cz=0;(map[cz+1][cy][cx]!=_cell_type_empty)&&(cz<czs-1);cz++);  \
            cell2scr(xx,yy,cx,cy,cz);                                           \
            if (map[cz][cy][cx]==_cell_type_full) yy-=czs;                      \
            xx=(sx-xx); yy=((sy-yy)*cxs)/cys;                                   \
            a=(xx+yy);  b=(xx-yy);                                              \
            if ((a>=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<gxs))                                                  \
         if ((cy>=0)&&(cy<gys))                                                 \
            {                                                                   \
            for (cz=0;(map[cz+1][cy][cx]!=_cell_type_empty)&&(cz<czs-1);cz++);  \
            cell2scr(xx,yy,cx,cy,cz);                                           \
            if (map[cz][cy][cx]==_cell_type_full) yy-=czs;                      \
            xx=(sx-xx); yy=((sy-yy)*cxs)/cys;                                   \
            a=(xx+yy);  b=(xx-yy);                                              \
            if ((a>=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<gzs;z++)
         for (y=0;y<gys;y++)
          for (x=0;x<gxs;x++)
           map[z][y][x]=_cell_type_empty;
        // add pseudo-random bumps
        Randomize();
        for (i=0;i<10;i++)
            {
            x0=Random(gxs);
            y0=Random(gys);
            r=Random((gxs+gys)>>3)+1;
            h=Random(gzs);
            for (z=0;(z<gzs)&&(r);z++,r--)
             for (y=y0-r;y<y0+r;y++)
              if ((y>=0)&&(y<gys))
               for (x=x0-r;x<x0+r;x++)
                if ((x>=0)&&(x<gxs))
                 map[z][y][x]=_cell_type_full;
            }
        }
    //---------------------------------------------------------------------------
    #endif
    //---------------------------------------------------------------------------

The layout defines just the coordinate system axises directions (for yours use #define isometric_layout_2). This uses Borlands VCL Graphics::TBitmap so if you do not use Borland change it to any GDI bitmap or overwrite the gfx part to your's gfx API (it is relevant just for draw() and resize()). Also TShiftState is part of VCL it is just state of mouse buttons and special keys like shift, alt, ctrl so you can use bool or whatever else instead (currently not used as I do not have any click functionality yet).

Here my Borland window code (single form app with one timer on it) so you see how to use this:

//$$---- Form CPP ----
//---------------------------------------------------------------------------
#include <vcl.h>
#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] graphics approach

Have a look at Simple OpenGL GUI Framework User Interaction Advice?.

The main idea is to create shadow screen buffer where the id of rendered cell is stored. This provides pixel perfect sprite/cell selection in O(1) just with few lines of code.

create shadow screen buffer idx[ys][xs]

It should have the same resolution as your map view And should be capable of storing the (x,y,z) value of render cell inside single pixel (in map grid cell units). I use 32 bit pixel format so I choose 12 bits for x,y and 8 bits for z
```
 DWORD color = (x) | (y<<12) | (z<<24)
```
before rendering of map clear this buffer

I use 0xFFFFFFFF as empty color so it is not colliding with cell (0,0,0).
on map cell sprite rendering

whenever you render pixel to screen buffer pyx[y][x]=color you also render pixel to shadow screen buffer idx[y][x]=c where c is encoded cell position in map grid units (see #1).

On mouse click (or whatever)

You got screen position of mouse mx,my so if it is in range just read the shadow buffer and obtain selected cell position.

 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.
  }

With above encoding this map (screen):

is rendered also to shadow screen like this:

Selection is pixel perfect does not matter if you click on top, side...

The tiles used are:

 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

And here Win32 Demo:

demo

Dammar answered 10/3, 2016 at 13:32 Comment(8)

A lot of this could be more cleanly explained with pseudocode, especially the neighbor scanning section. – Valenciavalenciennes 15/3, 2016 at 20:40

@MaxMastalerz I do not think it is necessary as the image is self explanatory and text contains the description. Also you claimed you have the scanning part working but scanning all the cells so you need just the selection of cells to scan from this. – Dammar 16/3, 2016 at 6:40

Does your code detect the mouse when it is on the edge of a tile? – Valenciavalenciennes 16/3, 2016 at 22:47

@no just the top side is detected (as that suit my needs) if you need also sides then use your own detection – Dammar 16/3, 2016 at 23:24

I don't see any simple way of extending this functionality to do full tile scans. Either ways, thanks for your effort. – Valenciavalenciennes 18/3, 2016 at 3:35

@MaxMastalerz why not? this just selects region where possible click can occur. The way you tell if the point belong to cell or not is irrelevant for the area. It affects only the way of selecting cells the area stays the same. So if you use your own predicates your functionality should not change only the speed (as you do not need to scann gxs*gys*gzs cells ... instead only ~3*gzs*czs/cys cells). – Dammar 18/3, 2016 at 6:26

@MaxMastalerz added [edit1] with graphics based pixel perfect O(1) approach. – Dammar 22/3, 2016 at 15:50

@MaxMastalerz Added link with my demo at the end of my answer (read the txts) so you can try the pixel perfect selecting I wrote about. – Dammar 7/4, 2016 at 14:1

Hot tags

Godot Unity Godot Help Programming Godot 4.X GUI GDScript 3D 2D Physics CSharp Godot 3.X VR XR Projects C++

An Explanation of my current algorithm:

Finally, my questions:

What I've thought of:

Recommended topics

Hot tags