38

Struggeling translating the position of the mouse to the location of the tiles in my grid. When it's all flat, the math looks like this:

this.position.x = Math.floor(((pos.y - 240) / 24) + ((pos.x - 320) / 48));
this.position.y = Math.floor(((pos.y - 240) / 24) - ((pos.x - 320) / 48));

where pos.x and pos.y are the position of the mouse, 240 and 320 are the offset, 24 and 48 the size of the tile. Position then contains the grid coordinate of the tile I'm hovering over. This works reasonably well on a flat surface.

https://i.sstatic.net/gp7qU.png

Now I'm adding height, which the math does not take into account.

https://i.sstatic.net/jWGMf.png

This grid is a 2D grid containing noise, that's being translated to height and tile type. Height is really just an adjustment to the 'Y' position of the tile, so it's possible for two tiles to be drawn in the same spot.

I don't know how to determine which tile I'm hovering over.

edit:

Made some headway... Before, I was depending on the mouseover event to calculate grid position. I just changed this to do the calculation in the draw loop itself, and check if the coordinates are within the limits of the tile currently being drawn. creates some overhead tho, not sure if I'm super happy with it but I'll confirm if it works.

edit 2018:

I have no answer, but since this ha[sd] an open bounty, help yourself to some code and a demo

The grid itself is, simplified;

let grid = [[10,15],[12,23]];

which leads to a drawing like:

for (var i = 0; i < grid.length; i++) {
    for (var j = 0; j < grid[0].length; j++) {
        let x = (j - i) * resourceWidth;
        let y = ((i + j) * resourceHeight) + (grid[i][j] * -resourceHeight); 
        // the "+" bit is the adjustment for height according to perlin noise values
    }
}

edit post-bounty:

See GIF. The accepted answer works. The delay is my fault, the screen doesn't update on mousemove (yet) and the frame rate is low-ish. It's clearly bringing back the right tile.

enter image description here

Source

9
  • 1
    I am curious as to how you ultimately solved this. My own idea was to start at the highest layer (a map could store the highest layer used) and then check if a tile exists at the location clicked on and work it's way down through the layers until you arrive at an existing tile for the location clicked.
    – Neil Roy
    Commented Dec 8, 2017 at 8:15
  • Hi @NeilRoy, I haven't actually :/ question is still open. I don't really have layers as such, it's just a grid containing height values IE; [ [ 0.01, 0.0015, 0.02...] [ ... ] ]. I have the source on github if you're interested.
    – Jorg
    Commented Dec 11, 2017 at 5:22
  • It would still work. You would calculate the normal tile position at the maximum height and see if a tile exists at that height, if not, than you lower the height, recalculate based on the offset for that height and check for a tile again. Repeat until you have a tile at that location and height. Another method I thought of would be to "walk" your way up the map, checking the base tile at a position south of where you clicked and seeing if its height matches your mouse position (tile south of your mouse, could be located at your mouse given the height), then move north a tile, check again
    – Neil Roy
    Commented Dec 13, 2017 at 8:07
  • Lowering the height in this case is more or less infinite. Any value between 0 and 1 is a valid one. I tried getting all touching tiles and checking which one was more “front”. I did that in the update loop and it was slow as hell. I’ll ponder the map walking comment.
    – Jorg
    Commented Dec 13, 2017 at 8:11
  • Another idea I seen someone else use was they used a heightmap. This takes up more memory as you need a separate map the same size as your level. They used a greyscale bitmap as a heightmap,the darker the shade, the higher that section was. So you clicked the map, then they checked the heightmap and mapped each shade of grey on it to a height. I'm not crazy about this solution as it seems like a horrible waste of memory. But these days, most people have plenty of memory, so I guess it depends on your target audience.
    – Neil Roy
    Commented Dec 17, 2017 at 5:28

7 Answers 7

21
+500

Intresting task.

Lets try to simplify it - lets resolve this concrete case

Solution

Working version is here: https://github.com/amuzalevskiy/perlin-landscape (changes https://github.com/jorgt/perlin-landscape/pull/1 )

Explanation

First what came into mind is:

Step by step

Just two steps:

  • find an vertical column, which matches some set of tiles
  • iterate tiles in set from bottom to top, checking if cursor is placed lower than top line

Step 1

We need two functions here:

Detects column:

function getColumn(mouseX, firstTileXShiftAtScreen, columnWidth) {
  return (mouseX - firstTileXShiftAtScreen) / columnWidth;
}

Function which extracts an array of tiles which correspond to this column.

Rotate image 45 deg in mind. The red numbers are columnNo. 3 column is highlighted. X axis is horizontal

enter image description here

function tileExists(x, y, width, height) {
  return x >= 0 & y >= 0 & x < width & y < height; 
}

function getTilesInColumn(columnNo, width, height) {
  let startTileX = 0, startTileY = 0;
  let xShift = true;
  for (let i = 0; i < columnNo; i++) {
    if (tileExists(startTileX + 1, startTileY, width, height)) {
      startTileX++;
    } else {
      if (xShift) {
        xShift = false;
      } else {
        startTileY++;
      }
    }
  }
  let tilesInColumn = [];
  while(tileExists(startTileX, startTileY, width, height)) {
    tilesInColumn.push({x: startTileX, y: startTileY, isLeft: xShift});
    if (xShift) {
      startTileX--;
    } else {
      startTileY++;
    }
    xShift = !xShift;
  }
  return tilesInColumn;
}

Step 2

A list of tiles to check is ready. Now for each tile we need to find a top line. Also we have two types of tiles: left and right. We already stored this info during building matching tiles set.

enter image description here

function getTileYIncrementByTileZ(tileZ) {
    // implement here
    return 0;
}

function findExactTile(mouseX, mouseY, tilesInColumn, tiles2d,
                       firstTileXShiftAtScreen, firstTileYShiftAtScreenAt0Height,
                       tileWidth, tileHeight) {
    // we built a set of tiles where bottom ones come first
    // iterate tiles from bottom to top
    for(var i = 0; i < tilesInColumn; i++) {
        let tileInfo = tilesInColumn[i];
        let lineAB = findABForTopLineOfTile(tileInfo.x, tileInfo.y, tiles2d[tileInfo.x][tileInfo.y], 
                                            tileInfo.isLeft, tileWidth, tileHeight);
        if ((mouseY - firstTileYShiftAtScreenAt0Height) >
            (mouseX - firstTileXShiftAtScreen)*lineAB.a + lineAB.b) {
            // WOHOO !!!
            return tileInfo;
        }
    }
}

function findABForTopLineOfTile(tileX, tileY, tileZ, isLeftTopLine, tileWidth, tileHeight) {
    // find a top line ~~~ a,b
    // y = a * x + b;
    let a = tileWidth / tileHeight; 
    if (isLeftTopLine) {
      a = -a;
    }
    let b = isLeftTopLine ? 
       tileY * 2 * tileHeight :
       - (tileX + 1) * 2 * tileHeight;
    b -= getTileYIncrementByTileZ(tileZ);
    return {a: a, b: b};
}
8
  • Loving var topCornerPositionX = 4 /*wtf*/ + .... I don't know where that comes from either :') Yeah all works out I love it.
    – Jorg
    Commented Mar 13, 2018 at 5:32
  • Added bonus of this approach is that - at least at first glance - the impact on performance is very minimal.
    – Jorg
    Commented Mar 13, 2018 at 5:33
  • @Jorg Spent almost a half of the time debugging the code because of "scaling"... So commited code is not 100% the same... Commented Mar 13, 2018 at 12:39
  • 1
    @Jorg Complexity is min(n,m) where n and m are dimensions of the grid. Also complexity may be reduced if there is height limit Commented Mar 13, 2018 at 12:41
  • 1
    @NeilRoy, it is working as you described, starts search from the closest tile. Thanks! Commented Nov 8, 2019 at 15:00
8

Please don't judge me as I am not posting any code. I am just suggesting an algorithm that can solve it without high memory usage.

The Algorithm:

Actually to determine which tile is on mouse hover we don't need to check all the tiles. At first we think the surface is 2D and find which tile the mouse pointer goes over with the formula OP posted. This is the farthest probable tile mouse cursor can point at this cursor position.

Farthest Perline Tile

This tile can receive mouse pointer if it's at 0 height, by checking it's current height we can verify if this is really at the height to receive pointer, we mark it and move forward.

Then we find the next probable tile which is closer to the screen by incrementing or decrementing x,y grid values depending on the cursor position.

Next to Farthest Perline Tile

Then we keep on moving forward in a zigzag fashion until we reach a tile which cannot receive pointer even if it is at it's maximum height.

Zigzag Perline Tile Search

When we reach this point the last tile found that were at a height to receive pointer is the tile that we are looking for.

In this case we only checked 8 tiles to determine which tile is currently receiving pointer. This is very memory efficient in comparison to checking all the tiles present in the grid and yields faster result.

4
  • 1
    Doesn't this assume that the heights of the tiles won't have much variance? What if one of the tiles was 20x taller than any of the others?
    – Dan Prince
    Commented Mar 6, 2018 at 22:16
  • Perdon me if I am wrong, but does the tile next to each other can have much variance? It looks like there will be little varience. The algorithm actually does not assume little or much variance, it will work on both if formula is right, i will update my answer with working code later. Commented Mar 7, 2018 at 3:49
  • (Please help me on this) -> thats exactly what my code is doing :) Commented Mar 7, 2018 at 6:18
  • This could work, except you walk your way UP the map rather than down it. This would be like ray tracing into the map as you move up the tiles, you test which tile top matches your position, this way no matter what the tile heights are, or how much they vary, you're going to hit the visible tile first (front to back sort of thing).
    – Neil Roy
    Commented Nov 7, 2019 at 5:01
5

One way to solve this would be to follow the ray that goes from the clicked pixel on the screen into the map. For that, just determine the camera position in relation to the map and the direction it is looking at:

 const camPos = {x: -5, y: -5, z: -5}
 const camDirection = { x: 1, y:1, z:1}

The next step is to get the touch Position in the 3D world. In this certain perspective that is quite simple:

 const touchPos = {
   x: camPos.x + touch.x / Math.sqrt(2),
   y: camPos.y - touch.x / Math.sqrt(2),
   z: camPos.z - touch.y / Math.sqrt(2)
 };

Now you just need to follow the ray into the layer (scale the directions so that they are smaller than one of your tiles dimensions):

 for(let delta = 0; delta < 100; delta++){
   const x = touchPos.x + camDirection.x * delta;
   const y = touchPos.y + camDirection.y * delta;
   const z = touchPos.z + camDirection.z * delta;

Now just take the tile at xz and check if y is smaller than its height;

 const absX = ~~( x / 24 );
 const absZ = ~~( z / 24 );

   if(tiles[absX][absZ].height >= y){
    // hanfle the over event
   }
2
  • I see you have added a z, I'm struggeling to see how this works since I'm not sure what my layers are here, but I'll give it a shot
    – Jorg
    Commented Mar 6, 2018 at 21:36
  • @jorg this is basically a transpiled version of a similar java code i wrote. So i hadnt really the time to adopt it to the isometric perspective. Please ping me if you get stuck so that i can extend the answer... Commented Mar 7, 2018 at 6:17
5

It also matters what else is on the screen. Maths attempts work if your tiles are pretty much uniform. However if you are displaying various objects and want the user to pick them, it is far easier to have a canvas-sized map of identifiers.

function poly(ctx){var a=arguments;ctx.beginPath();ctx.moveTo(a[1],a[2]);
    for(var i=3;i<a.length;i+=2)ctx.lineTo(a[i],a[i+1]);ctx.closePath();ctx.fill();ctx.stroke();}
function circle(ctx,x,y,r){ctx.beginPath();ctx.arc(x,y,r,0,2*Math.PI);ctx.fill();ctx.stroke();}
function Tile(h,c,f){
    var cnv=document.createElement("canvas");cnv.width=100;cnv.height=h;
    var ctx=cnv.getContext("2d");ctx.lineWidth=3;ctx.lineStyle="black";
    ctx.fillStyle=c;poly(ctx,2,h-50,50,h-75,98,h-50,50,h-25);
    poly(ctx,50,h-25,2,h-50,2,h-25,50,h-2);
    poly(ctx,50,h-25,98,h-50,98,h-25,50,h-2);
    f(ctx);return ctx.getImageData(0,0,100,h);
}
function put(x,y,tile,image,id,map){
    var iw=image.width,tw=tile.width,th=tile.height,bdat=image.data,fdat=tile.data;
    for(var i=0;i<tw;i++)
        for(var j=0;j<th;j++){
            var ijtw4=(i+j*tw)*4,a=fdat[ijtw4+3];
            if(a!==0){
                var xiyjiw=x+i+(y+j)*iw;
                for(var k=0;k<3;k++)bdat[xiyjiw*4+k]=(bdat[xiyjiw*4+k]*(255-a)+fdat[ijtw4+k]*a)/255;
                bdat[xiyjiw*4+3]=255;
                map[xiyjiw]=id;
            }
        }
}
var cleanimage;
var pickmap;
function startup(){
    var water=Tile(77,"blue",function(){});
    var field=Tile(77,"lime",function(){});
    var tree=Tile(200,"lime",function(ctx){
        ctx.fillStyle="brown";poly(ctx,50,50,70,150,30,150);
        ctx.fillStyle="forestgreen";circle(ctx,60,40,30);circle(ctx,68,70,30);circle(ctx,32,60,30);
    });
    var sheep=Tile(200,"lime",function(ctx){
        ctx.fillStyle="white";poly(ctx,25,155,25,100);poly(ctx,75,155,75,100);
        circle(ctx,50,100,45);circle(ctx,50,80,30);
        poly(ctx,40,70,35,80);poly(ctx,60,70,65,80);
    });
    var cnv=document.getElementById("scape");
    cnv.width=500;cnv.height=400;
    var ctx=cnv.getContext("2d");
    cleanimage=ctx.getImageData(0,0,500,400);
    pickmap=new Uint8Array(500*400);
    var tiles=[water,field,tree,sheep];
    var map=[[[0,0],[1,1],[1,1],[1,1],[1,1]],
             [[0,0],[1,1],[1,2],[3,2],[1,1]],
             [[0,0],[1,1],[2,2],[3,2],[1,1]],
             [[0,0],[1,1],[1,1],[1,1],[1,1]],
             [[0,0],[0,0],[0,0],[0,0],[0,0]]];
    for(var x=0;x<5;x++)
        for(var y=0;y<5;y++){
            var desc=map[y][x],tile=tiles[desc[0]];
            put(200+x*50-y*50,200+x*25+y*25-tile.height-desc[1]*20,
            tile,cleanimage,x+1+(y+1)*10,pickmap);
        }
    ctx.putImageData(cleanimage,0,0);
}
var mx,my,pick;
function mmove(event){
    mx=Math.round(event.offsetX);
    my=Math.round(event.offsetY);
    if(mx>=0 && my>=0 && mx<cleanimage.width && my<cleanimage.height && pick!==pickmap[mx+my*cleanimage.width])
        requestAnimationFrame(redraw);
}
function redraw(){
    pick=pickmap[mx+my*cleanimage.width];
    document.getElementById("pick").innerHTML=pick;
    var ctx=document.getElementById("scape").getContext("2d");
    ctx.putImageData(cleanimage,0,0);
    if(pick!==0){
        var temp=ctx.getImageData(0,0,cleanimage.width,cleanimage.height);
        for(var i=0;i<pickmap.length;i++)
            if(pickmap[i]===pick)
                temp.data[i*4]=255;
        ctx.putImageData(temp,0,0);
    }
}
startup(); // in place of body.onload
<div id="pick">Move around</div>
<canvas id="scape" onmousemove="mmove(event)"></canvas>

Here the "id" is a simple x+1+(y+1)*10 (so it is nice when displayed) and fits into a byte (Uint8Array), which could go up to 15x15 display grid already, and there are wider types available too.

(Tried to draw it small, and it looked ok on the snippet editor screen but apparently it is still too large here)

7
  • It's a bit hard to read, but are you keeping a per-pixel map of the objects on the screen here?
    – Jorg
    Commented Mar 13, 2018 at 22:51
  • @Jorg yes, that is what happens here. function put() does practically everything: as CanvasRenderingContext2D.putImageData() does not handle "alpha" properly, an alternative had to be created anyway, and then it is the perfect place to update the id-map too whenever a non-transparent pixel is rendered for the current object.
    – tevemadar
    Commented Mar 14, 2018 at 11:31
  • While I appreciate the simplicity of your solution - and I think it has merit - I’m not sure it’s altogether very suitable with scenarios like this one which just draw parts of one image onto another. Would like to be proven wrong though
    – Jorg
    Commented Mar 14, 2018 at 14:53
  • Your doodle is fun though and I’m loving that it recognises shapes
    – Jorg
    Commented Mar 14, 2018 at 14:57
  • @Jorg I could only repeat the description: if you have uniform tiles, which just differ in color/texture, the more mathematical approach works well. If you need shapes, then it does not. Honestly said I found the landscape in the question a bit empty, that was why I brought up this aspect. It also matters what you need exactly, in my example user can not pick 23 at all, and picking 12 and 13 is not very convenient either.
    – tevemadar
    Commented Mar 14, 2018 at 15:44
4

I had same situation on a game. first I tried with mathematics, but when I found that the clients wants to change the map type every day, I changed the solution with some graphical solution and pass it to the designer of the team. I captured the mouse position by listening the SVG elements click.

the main graphic directly used to capture and translate the mouse position to my required pixel.

https://blog.lavrton.com/hit-region-detection-for-html5-canvas-and-how-to-listen-to-click-events-on-canvas-shapes-815034d7e9f8 https://code.sololearn.com/Wq2bwzSxSnjl/#html

4

Here is the grid input I would define for the sake of this discussion. The output should be some tile (coordinate_1, coordinate_2) based on visibility on the users screen of the mouse:

Locked Layers

I can offer two solutions from different perspectives, but you will need to convert this back into your problem domain. The first methodology is based on coloring tiles and can be more useful if the map is changing dynamically. The second solution is based on drawing coordinate bounding boxes based on the fact that tiles closer to the viewer like (0, 0) can never be occluded by tiles behind it (1,1).

Approach 1: Transparently Colored Tiles

The first approach is based on drawing and elaborated on here. I must give the credit to @haldagan for a particularly beautiful solution. In summary it relies on drawing a perfectly opaque layer on top of the original canvas and coloring every tile with a different color. This top layer should be subject to the same height transformations as the underlying layer. When the mouse hovers over a particular layer you can detect the color through canvas and thus the tile itself. This is the solution I would probably go with and this seems to be a not so rare issue in computer visualization and graphics (finding positions in a 3d isometric world).

Approach 2: Finding the Bounding Tile

This is based on the conjecture that the "front" row can never be occluded by "back" rows behind it. Furthermore, "closer to the screen" tiles cannot be occluded by tiles "farther from the screen". To make precise the meaning of "front", "back", "closer to the screen" and "farther from the screen", take a look at the following:

Definitions.

Based on this principle the approach is to build a set of polygons for each tile. So firstly we determine the coordinates on the canvas of just box (0, 0) after height scaling. Note that the height scale operation is simply a trapezoid stretched vertically based on height.

Then we determine the coordinates on the canvas of boxes (1, 0), (0, 1), (1, 1) after height scaling (we would need to subtract anything from those polygons which overlap with the polygon (0, 0)).

Proceed to build each boxes bounding coordinates by subtracting any occlusions from polygons closer to the screen, to eventually get coordinates of polygons for all boxes.

With these coordinates and some care you can ultimately determine which tile is pointed to by a binary search style through overlapping polygons by searching through bottom rows up.

4
  • I like the 'second canvas' solution for its simplicity, but it does not scale very well. it might be good enough for my purpose though. let's see if we can find a more mathematical approach first
    – Jorg
    Commented Mar 12, 2018 at 10:33
  • An alternative methodology may rely on ray tracing, but I am unable to formalize how such a projection would work and what information would be necessary from the grid. Commented Mar 12, 2018 at 17:30
  • plus 1 for the back row drawing. Commented Mar 13, 2018 at 2:23
  • @Jorg, yup, as mentioned in my old answer, this won't work for complex cases with big amount of moving objects, however this method can help to save some nerves, when you have a lot of objects of irregular shape on the scene. It's basically ray tracing without maths.
    – haldagan
    Commented Mar 13, 2018 at 6:42
0

Computer graphics is fun, right?

This is a special case of the more standard computational geometry "point location problem". You could also express it as a nearest neighbour search.

To make this look like a point location problem you just need to express your tiles as non-overlapping polygons in a 2D plane. If you want to keep your shapes in a 3D space (e.g. with a z buffer) this becomes the related "ray casting problem".

One source of good geometry algorithms is W. Randolf Franklin's website and turf.js contains an implementation of his PNPOLY algorithm.

For this special case we can be even faster than the general algorithms by treating our prior knowledge about the shape of the tiles as a coarse R-tree (a type of spatial index).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.