提高交错列等距网格上点击检测的性能

本文介绍了提高交错列等距网格上点击检测的性能的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我正在开发一个等距的游戏引擎，并已经创建了像素完美的点击检测算法。访问 地图由三维数组 map [z] [y] [x] 平铺中心点（x，y）的计算方式如下： // x，y，z是图块的位置 if（y％2 === 0）{ x = 0.5; } //适应在偶数行中找到的偏移 this.centerX =（x * tileW）+（tileW / 2）; this.centerY =（y * tileL）-y *（（ti​​leL）/ 2）+（（tileL）/ 2）+（tileH / 2） - （z * tileH） 确定鼠标是否在图块上的给定区域内的原型函数： 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;} //参考图像 return（dx /（tileW * 0.5）+（dy / ）} Tile.prototype.allContainsMouse c $ c>如果鼠标在绿色范围内则返回true。通过检查dx>图元宽度的一半来裁剪红色区域 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）}; Tile.prototype.leftContainsMouse = function（）{ var dx = mouse.mapX -this.centerX; if（dx< 0）{return true; } else {return false; } }; （如果鼠标离开中心点） Tile.prototype.rightContainsMouse = function（）{ var dx = mouse.mapX-this.centerX; if（dx> 0）{return true; } else {return false; } }; （如果鼠标在中心点右侧） 将所有方法集中在一起工作： 循环遍历整个3d地图[如果 allContainsMouse（）返回true，map [z] [y] [x] 将此图块添加到数组 tilesUnderneathMouse 数组。 li> 循环通过 tilesUnderneathMouse 数组，并选择具有最高 y 的图块。这是最前面的图块。 if（allContainsMouse&&！topContainsMouse） if（allContainsMouse&&！topContainsMouse&& leftAnsencesMouse） （类似的概念适用于权利） 最后，我的问题： 1 ＃2如果你不能回答＃1，那么它会更有效率（不循环遍历所有图块） ，你有什么建议，以提高我的点击检测的效率（块装载已被考虑） 我想到的： 我最初试图通过不使用瓦片中心点来解决这个问题，而是直接将鼠标（x，y）位置转换为瓦片x，y。在我看来，这是最难的代码，但最高效的解决方案。在正方形网格上，很容易将（x，y）位置转换为网格上的正方形。然而，在交错列网格中，您处理偏移。我试图使用一个函数计算偏移量，该函数接受x或y值，并返回结果偏移y或x。 红十字 cell2scr（x，y，0,0,0） 绿色交叉 li> aqua highlight 表示返回的单元格位置 整数算术，你需要记住，如果你划分/乘以一半大小，你可以失去精度。对于这种情况，请使用完整大小并将结果除以 2 （花费很多时间计算过去的结果）。 cell2scr 非常简单。屏幕位置为平移偏移+像元位置乘以其大小（步长）。 x 轴需要校正偶数/奇数行（即（（cy& 1）* cxs2） is for），并且 z 轴（（（cy& 1） ）* cxs2））。矿井屏幕的左上角有（0,0）， + x 轴指向右边， + y 向下。 scr2cell 在假设 z = 0 时，从 cell2scr 的等式求解屏幕位置，因此仅选择网格地面。 扫描邻居 scr2cell（x，y，z，mouse_x，mouse_y）只返回鼠标在地上的单元格。因此，如果您要添加当前的选择功能，您需要扫描该位置上的顶层单元格和几个邻近单元格，并选择最小距离的单元格。 不需要扫描整个网格/地图只有几个单元格周围返回的位置。 我这样做： 行数取决于单元格 z 轴大小（ czs ），最大数量 z 图层（ gzs ）和单元格大小c $ c> cys ）。扫描的 C ++ 代码如下所示： //网格大小 const int gxs = 15; const int gys = 30; const int gzs = 8; //我的地图（所有单元格） int map [gzs] [gys] [gxs]; void isometric :: scr2cell（int& cx，int& cy，int& cz，int sx，int sy） { //粗略单元格地面估计（没有z值） cy =（2 *（sy-pan_y））/ cys; cx =（sx-pan_x - （（cy& 1）* cxs2））/ cxs; cz = 0; //等距的瓷砖形状交叉校正 int xx，yy; cell2scr（xx，yy，cx，cy，cz）; xx = sx-xx; yy = sy-yy; if（xx else {if（yy>（cxs-xx）* cys / cxs）{cy ++; if（int（cy& 1）== 0）cx ++; }} //扫描最近邻居 int x0 = -1，y0 = -1，z0 = -1，a，b，i; #define _scann \ if（（cx> = 0）&&（cx< gxs））\ if ;&（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 if（cz> = z0）{x0 = cx; y0 = cy; z0 = cz; } \ } _scann; //扫描实际单元格 for（i = gzs * czs; i> = 0; i- = cys）//根据需要扫描实际单元格的多少行 { 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 } 这里完成了 VCL / C ++ 今天： // --------------------- -------------------------------------------------- ---- // ---等长版本：1.01 --------------------------------- ------------------ // -------------------------- ------------------------------------------------- #ifndef _isometric_h #define _isometric_h // ------------------------------- -------------------------------------------- // -------------------------------------------------- ------------------------- //颜色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; // -------------------------------------------- ------------------------------- // ---配置定义-------- ----------------------------------------- // --- -------------------------------------------------- ---------------------- // #define isometric_layout_1 // x轴：righ +下，y轴：左+下 // #define isometric_layout_2 // x axis：righ，y axis：left + down // -------------------------- ------------------------------------------------- #define isometric_layout_2 // -------------------------------------- ------------------------------------- // ------- -------------------------------------------------- ------------------ / * //网格大小 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; * / //网格大小 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; //电池类型 enum _cell_type_enum { _cell_type_empty = 0， _cell_type_ground， _cell_type_full， _cell_types } // -------------------------------------------- ------------------------------- class isometric { public： //屏幕缓冲区 Graphics :: TBitmap * bmp; DWORD ** pyx; int xs，ys; //等长图 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; //用于编译器安全的构造函数 isometric（）; 等距（等距& a）{* this = a; } 〜isometric（）; isometric * operator =（const isometric * a）{* this = * a;返回这个; } 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（） { //初始屏幕缓冲区 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; （y = 0; y （对于（x = 0; x for（z = 0; z map [z] [y] [x] = t; //初始化鼠标 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;对于（x = 0; 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 if（_ys 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 // 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 for（x = 0; x { cell2scr（xx，yy，x，y ，0）; cell_draw（xx，yy，_cell_type_ground，false）; } b $ b col_zside = c0; // cells for（z = 0; z for（y = 0; y for（x = 0; ; 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）; //鼠标交叉 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 = b，i，xx，yy; #ifdef isometric_layout_1 //粗糙的单元格地面估计（没有z值） //翻译为（0,0,0）网格的左上角 xx = sx-pan_x-cxs2; yy = sy-pan_y + cys2; //将方面改为方形单元格cxs x cxs yy =（yy * cxs）/ cys; //使用带有轴向量的点积来计算网格单元坐标 cx =（+ xx + yy）/ cxs; cy =（ - xx + yy）/ cxs; cz = 0; //扫描最近邻居 #define _scann \ if（（cx> = 0）&&（cx< gxs））\ 对于（cz = 0;（map [cz + 1] [cy] [cx]），if（（cy> = 0）&&（cy {\ ！= _ 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 if（cz> = z0）{x0 = cx; y0 = cy; z0 = cz; } \ } _scann; //扫描实际单元格 for（i = gzs * czs; i> = 0; i- = cys）//根据需要扫描实际单元格的多少行 { cy ++; _scann; cx ++ cy--; _scann; cy ++; _scann; } cx = x0; cy = y0; cz = z0; // return remembered cell coordinate #undef _scann #endif #ifdef isometric_layout_2 //粗略单元格地面估计（没有z值） cy =（2 *（sy-pan_y））/ cys; cx =（sx-pan_x - （（cy& 1）* cxs2））/ cxs; cz = 0; //等距的瓷砖形状交叉校正 cell2scr（xx，yy，cx，cy，cz）; xx = sx-xx; yy = sy-yy; if（xx else {if（yy>（cxs-xx）* cys / cxs）{cy ++; if（int（cy& 1）== 0）cx ++; }} //扫描最近邻居 #define _scann \ if（（cx> = 0）&&（cx< gxs））\ if （cz = 0;（map [cz + 1] [cy] [cx]！= 0）的（cyz = 0）&（cy< gys））\ _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 if（cz> = z0）{x0 = cx; y0 = cy; z0 = cz; } \ } _scann; //扫描实际单元格 for（i = gzs * czs; i> = 0; i- = cys）//根据需要扫描实际单元格的多少行 { 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->多边形（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->多边形（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->多边形（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->多边形（pnt，3）; } } // ---------------------------------- ----------------------------------------- void isometric :: map_random （） { int i，x，y，z，x0，y0，r，h; //清除（z = 0; z for（y = 0; y for（x = 0; x map [z] [y] [x] = _ cell_type_empty; //添加伪随机凸起 Randomize（）; for（i = 0; i { x0 = Random（gxs）; y0 = Random（gys）; r = Random（（gxs + gys）> 3）+1; h = Random（gzs）;对于（y = y0-r; y （z = 0;（z （x> x0-r; x if（（x& = 0）&&（x< gxs）） map [z] [y] [x] = _ cell_type_full; } } // ---------------------------------- ----------------------------------------- #endif // ------------------------------------------- ---------------------------- 布局仅定义坐标系轴方向（对于您使用 #define isometric_layout_2 ）。这使用 Borlands VCL Graphics :: TBitmap ，因此如果您不使用 Borland 将其更改为任何 GDI 位图或将gfx部分覆盖到您的gfx API （仅与 draw（）和 resize（））。此外 TShiftState 是 VCL 的一部分，它只是鼠标按钮和特殊键的状态，例如 shift，alt，ctrl ，因此您可以使用 bool 或其他任何东西（目前没有使用，因为我还没有任何点击功能）。 这里是我的 Borland 窗口代码（单表单应用程序，其中有一个计时器），以便您了解如何使用此功能：//$$---- 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);画（）; } void __fastcall TMain::FormMouseDown(TObject *Sender, TMouseButton Button,TShiftState Shift, int X, int Y) { iso.mouse(X,Y,Shift);画（）; } void __fastcall TMain::FormMouseUp(TObject *Sender, TMouseButton Button,TShiftState Shift, int X, int Y) { iso.mouse(X,Y,Shift);画（）; } //--------------------------------------------------------------------------- void __fastcall TMain::FormDblClick(TObject *Sender) { iso.map_random(); } //--------------------------------------------------------------------------- [Edit1] graphics approach Have a look at 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 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=15The 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 tileif(y%2===0) { x-=-0.5; } //To accommodate the offset found in even rowsthis.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 widthTile.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] arrayif 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! 解决方案 This answer is based on:2D grid image values to 2D arraySo here it goes:conversion between grid and screenAs I mentioned in comment you should make functions that convert between screen and cell grid positions. something like (in C++)://---------------------------------------------------------------------------// tile sizesconst 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 coordinatesaqua highlight represents returned cell positionBeware 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 neighborsthe 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 sizeconst 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 approachHave 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 zDWORD color = (x) | (y<<12) | (z<<24)before rendering of map clear this bufferI use 0xFFFFFFFF as empty color so it is not colliding with cell (0,0,0).on map cell sprite renderingwhenever 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 TilesetAuthor: YarURL: http://opengameart.org/content/isometric-64x64-outside-tilesetLicense(s): * CC-BY 3.0 http://creativecommons.org/licenses/by/3.0/legalcodeAnd here Win32 Demo:demo 这篇关于提高交错列等距网格上点击检测的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！