Improving Performance of Click Detection on a Staggered Column Isometric Grid

Find which tile was clicked in a isometric, staggered column system

If you know the center position of the cell, which of course you do since they are rendered, you simply normalize the coordinate against the cell to find out if it is inside:

var dx = Math.abs(x - cellCenterX),
    dy = Math.abs(y - cellCenterY);

if (dx / (cellWidth * 0.5) + dy / (cellHeight * 0.5) <= 1) { /* is inside */ };

Here is a full demo:

var cw = 64,    ch = 32,    cells = [],    maxH = 10,    maxV = 5,    toggle = true,        canvas = document.getElementById("canvas"),    ctx = canvas.getContext('2d');
// Using a cell object for convenience here:function Cell(posX, posY, x, y, w, h) {  this.posX = posX;            // some id....  this.posY = posY;            // some id....  this.x = x;                  // cells top position  this.y = y;  this.w = w;                  // width and height of cell  this.h = h;  this.centerX = x + w * 0.5;  // abs. center of cell  this.centerY = y + h * 0.5;}
// draw this cell:Cell.prototype.render = function(ctx, color) {  ctx.beginPath();  ctx.moveTo(this.centerX, this.y);  ctx.lineTo(this.x + this.w, this.centerY);  ctx.lineTo(this.centerX, this.y+this.h);  ctx.lineTo(this.x, this.centerY);  ctx.closePath();  ctx.fillStyle = color;  ctx.fill();  ctx.strokeStyle = "#000";  ctx.stroke();};
// check if x/y is inside this cellCell.prototype.isInCell = function(x, y) {
  var dx = Math.abs(x - this.centerX),      dy = Math.abs(y - this.centerY);
  return (dx / (this.w * 0.5) + dy / (this.h * 0.5) <= 1);};
// generate cell mapfor(var y = 0; y < maxV; y++) {  var dltX = toggle ? 0 : -cw * 0.5,      dltY = -ch * 0.5 * y;    toggle = !toggle;    for(var x = 0; x < maxH; x++) {      var c = new Cell(x, y, x * cw + dltX, y * ch + dltY, cw, ch);      cells.push(c);      c.render(ctx, "#9f0"); // green bg  }}
// test by clicking in cellcanvas.onclick = function(e) {    var r = canvas.getBoundingClientRect(),      x = e.clientX - r.left,      y = e.clientY - r.top,      i = 0, cell;    for(; cell = cells[i]; i++) {    if (cell.isInCell(x, y)) {      cell.render(ctx, "#f00"); // red bg if inside      out.innerHTML = "Cell pos: (" + cell.posX + "," + cell.posY + ") X: " + cell.x + " Y: " + cell.y;      break;    }  }};

<canvas id=canvas width=500 height=100></canvas><br><output id=out></output>

Click detection in a 2D isometric grid?

Here's what I came up with,

function posInGrid(x, y, length) {
xFromColCenter = x % length - length / 2;
yFromRowCenter = y % length - length / 2;
col = (x - xFromColCenter) / length;
row = (y - yFromRowCenter) / length;
if (yFromRowCenter < xFromColCenter) {
    if (yFromRowCenter < (-xFromColCenter))--row;
    else++col;
} else if (yFromRowCenter > xFromColCenter) {
    if (yFromRowCenter < (-xFromColCenter))--col;
    else++row;
}
return "Col:"+col+", Row:"+row+", xFC:"+xFromColCenter+", yFC:"+yFromRowCenter;
}

X and Y are the coords in the image, and length is the spacing of the grid.

Right now it returns a string, just for testing.. result should be row and col, and those are the coordinates I chose: your tile 1 has coords (1,0) tile 2 is(3,0), tile 10 is (0,1), tile 11 is (2,1). You could convert my coordinates to your numbered tiles in a line or two.

And a JSFiddle for testing http://jsfiddle.net/NHV3y/

Cheers.

EDIT: changed the return statement, had some variables I used for debugging left in.

Screen to staggered isometric grid algorithm

def subregion(px, py, r_x, r_y):
rx = int(r_x)
ry = int(r_y)
foo = px - py
bar = px + py
if foo < 0 and bar > 1:  # Top
    return [rx, ry]
elif foo < 0 and bar < 1:  # Left
    if r_y > 0:
        if py > 0.5:
            return [rx - 1, ry + 1]
        return [rx - 1, ry]
    else:
        return None
elif foo > 0 and bar > 1:  # Right
    if r_y > 0:
        if py > 0.5:
            return [rx, ry + 1]
        return [rx, ry]
    else:
        return None
elif foo > 0 and bar < 1:  # Bottom
    if r_y < 0:
        return [rx, ry]
    return [rx, ry + 1]

Mouse coordinates in a canvas to 30 degree isometric coordinates on a grid

I am not myself very well versed in algebra so there may be an even simpler solution but anyway...

What your function needs to do is to invert the transformation that occurred in the previous step in order to find back the original x and y values.

a = Math.round((x - y) * Math.sqrt(3) / 2 + canvasOffset);
b = Math.round((x + y) / 2);

From this we can retrieve the values (x - y) and (x + y) as being

(x - y) = (a - canvasOffset) / Math.sqrt(3) * 2;
(x + y) = b * 2;

Now that we have both (x - y) and (x + y) we can find x by adding up these two values and dividing by 2, the y value cancels itself.

And now it's easy to find y, since it's just (x + y) - x.

const pre = document.querySelector("pre");
const log = (txt) => pre.textContent = JSON.stringify(txt);

const canvas = document.querySelector("canvas");
const ctx = canvas.getContext("2d");
const gridRows = 10;
const gridCols = 10;
const tileSize = 40;

const gridWidth = gridCols * tileSize;
const gridHeight = gridRows * tileSize;

const canvasWidth = tileSize * (gridCols + gridRows) * Math.sqrt(3) / 2;
const canvasHeight = tileSize * (gridRows + gridCols) / 2;

const canvasOffset = tileSize * gridRows * Math.sqrt(3) / 2;

canvas.width = canvasWidth;
canvas.height = canvasHeight;

function carToIso(x, y) {
  // Convert cartesian (x, y) to isometric coordinates
  // I moved the scaling part here, it makes lees noise in the rest of the code
  // But feel free to change it back
  x *= tileSize;
  y *= tileSize;
  return [
    Math.round((x - y) * Math.sqrt(3) / 2 + canvasOffset),
    Math.round((x + y) / 2)
  ];
}

function isoToCar(a, b) {
  // Convert isometric (a, b) to cartesian coordinates
  const xMinusY = (a - canvasOffset) / Math.sqrt(3) * 2;
  const xPlusY = b * 2;
  const x = (xMinusY + xPlusY) / 2;
  const y = xPlusY - x;
  return [
    Math.floor(x / tileSize), // scaling is here too
    Math.floor(y / tileSize)
  ];
}

function drawGrid() {
  // Draw lines
  ctx.beginPath();
  ctx.lineWidth = 1;

  ctx.fillStyle = "red";

  // Rows
  for (let i = 0; i <= gridRows; ++i) {
    const [x1, y1] = carToIso(0, i);
    const [x2, y2] = carToIso(gridCols, i);
    ctx.moveTo(x1, y1);
    ctx.lineTo(x2, y2);
    ctx.fillText("r" + i, (x2 + x1) / 2, (y2 + y1) / 2);
  }

  // Columns
  for (let i = 0; i <= gridCols; ++i) {
    const [x1, y1] = carToIso(i, 0);
    const [x2, y2] = carToIso(i, gridRows);
    ctx.moveTo(x1, y1);
    ctx.lineTo(x2, y2);
    ctx.fillText("c" + i, (x2 + x1) / 2, (y2 + y1) / 2);
  }

  ctx.stroke();
}

function fillCell(x, y, color) {
  ctx.beginPath();
  ctx.moveTo(...carToIso(x, y));
  ctx.lineTo(...carToIso((x + 1), y));
  ctx.lineTo(...carToIso((x + 1), (y + 1)));
  ctx.lineTo(...carToIso(x, (y + 1)));
  ctx.fillStyle = "green";
  ctx.fill();
}

onmousemove = (evt) => {
  const {top, left} = canvas.getBoundingClientRect();
  const mouseX = evt.clientX - left;
  const mouseY = evt.clientY - top;
  const [gridX, gridY] = isoToCar(mouseX, mouseY);
  log({
    mouseX,
    mouseY,
    gridX,
    gridY
  });

  ctx.clearRect(0, 0, canvas.width, canvas.height);
  fillCell(gridX, gridY, "green");
  drawGrid();
};

drawGrid();

pre { position: absolute }

<pre></pre>
<canvas id="canvas"></canvas>

Getting tile from coordinates on staggered isometric grid

public static Point CoordToCell(Vector2 coord) {
    // Divide the cell coordinate the value again (or multiply by -4)
    // Then Math.Round() to eliminate any floating point inaccuracies
    var cellY = (int)Math.Round(coord.y / -0.25f);

    // Armed with the original Integer Y, we can undo the mutation of X (again, accounting for floating point inaccuracies)
    var cellX = (int)Math.Round(coord.x - ((cellY % 2) * 0.5f));

    return new Point() {
        x = cellX,
        y = cellY
    };
}

This should reverse the process. I've used Point as a generic container for an integer X and Y coordinate, you can replace this as appropriate.

The biggest issue in my opinion is that the X mutation was originally based on the integer value of Y, from which you then stored a floating point value. I couldn't find a way to reverse this without the Math.Round()s to coerce the floating point results back into integer values reliably.

Update Calculating the cell coordinates containing a given world coordinate:

Looking at how your world coordinates are arranged, we can see that the centres of each cell are on the diagonal lines given by:

y = ( x - i ) / 2 ... or ... x - 2y = i
y = ( j - x ) / 2 ...
or ... x + 2y = j

where i and j are integers. This diagram shows this for the x - 2y = i diagonals.

Diagram showing diagonal coordinates

Using these, we can take the world coordinates of a given point, work out i and j, then round them to the nearest integer to get the centre of the cell as i and j.

We can then use i and j to work out the x and y of the cell centre, and use the function I posted before to convert these back into cell coordinates.

public static Point CoordToCell(Vector2 coord)
{
    // Work out the diagonal i and j coordinates of the point.
    // i and j are in a diagonal coordinate system that allows us
    // to round them to get the centre of the cell.
    var i = Math.Round( coord.x - coord.y * 2 );
    var j = Math.Round( coord.x + coord.y * 2 );

    // With the i and j coordinates of the centre of the cell,
    // convert these back into the world coordinates of the centre
    var centreX = ( i + j ) / 2;
    var centreY = ( j - i ) / 4;

    // Now convert these centre world coordinates back into the
    // cell coordinates
    int cellY = (int)Math.Round(centreY * -4f);
    int cellX = (int)Math.Round(centreX - ((cellY % 2) * 0.5f));

    return new Point() {
        x = cellX,
        y = cellY
    };
}

I used the following coordinate points as test cases

{ x = 1.5f, y = -0.25f } => ( 1, 1 )        // Centre of 1, 1
{ x = 1.9f, y = -0.25f } => ( 1, 1 )        // Near the right of 1, 1
{ x = 1.5f, y = -0.374f } => ( 1, 1 )       // Near the bottom of 1, 1
{ x = 1.1f, y = -0.25f } => ( 1, 1 )        // Near the left of 1, 1
{ x = 1.5f, y = -0.126f } => ( 1, 1 )       // Near the top of 1, 1
{ x = 2.5f, y = -0.25f } => ( 2, 1 )        // Centre of 2, 1
{ x = 2f, y = -0.5f } => ( 2, 2 )           // Centre of 2, 2

Hope this helps

Staggered Isometric Pathfinder

Based on the given values, it looks like your H is not admissible. Since it takes 10 to get from (2,3) to (2,2), I assume it should take 10 to get from (2,2) to (3,1), but your H says it takes 20 (i.e. you overestimate).

One possible H is the direct distance to the target (either something like Manhattan distance or Euclidean).

At our first step, we explore all neighbours. Our G values will look like: (G = green, R = red)

Let's take H as something like Manhattan distance, where 14 is a diagonal jump and 10 is a move to a direct neighbour. This is actually be the perfect heuristic for this example, as it's exactly the same as the actual distance. This will be different once there are obstacles in the path.

Then we get H values as:

So our F values (= G + H) are:

Then you find the minimum, which is 20, explore all it's (unexplored) neighbours and find the minimum, which will be the goal in this case.

Note that it's a easy mistake to stop as soon as one of the neighbours is the target, rather than the node we are currently exploring. An admissible heuristic doesn't guarantee that we'll find the optimal path to the target if we do this.