xna - How can I improve my isometric tile-picking algorithm?

I've spent the last few days researching isometric tile-picking algorithms (converting screen-coordinates to tile-coordinates), and have obviously found a lot of the math beyond my grasp.

I have come fairly close and what I have is workable, but I would like to improve on this algorithm as it's a little off and seems to pick down and to the right of the mouse pointer.

I've uploaded a video to help visualize the current implementation: http://youtu.be/EqwWcq1zuaM

My isometric rendering algorithm is based on what is found at this stackoverflow question's answer, with the exception that my x and y axis' are inverted (x increased down-right, while y increased up-right).

Here is where I am converting from screen to tiles:

// these next few lines convert the mouse pointer position from screen 
// coordinates to tile-grid coordinates. cameraOffset captures the current
// mouse location and takes into consideration the camera's position on screen.

System.Drawing.Point cameraOffset = new System.Drawing.Point( 0, 0 );
cameraOffset.X = mouseLocation.X + (int)camera.Left;
cameraOffset.Y = ( mouseLocation.Y + (int)camera.Top );

// the camera-aware mouse coordinates are then further converted in an attempt
// to select only the "tile" portion of the grid tiles, instead of the entire
// rectangle. this algorithm gets close, but could use improvement.
mouseTileLocation.X = ( cameraOffset.X + 2 * cameraOffset.Y ) / Global.TileWidth;
mouseTileLocation.Y = -( ( 2 * cameraOffset.Y - cameraOffset.X ) / Global.TileWidth );

Things to make note of:

• 
  

  mouseLocation is a System.Drawing.Point that represents the screen coordinates of the mouse pointer.

  
  


• 
  

  cameraOffset is the screen position of the mouse pointer that includes the position of the game camera.

  
  


• 
  

  mouseTileLocation is a System.Drawing.Point that is supposed to represent the tile coordinates of the mouse pointer.

  
  
  

If you check out the above link to youtube, you'll notice that the picking algorithm is off a bit. How can I improve on this?

Answer

What you need is some good old fashioned matrix math.

Let's say you have two spaces:

• World space - where the tiles reside


• Screen space - where the mouse pointer is

You want to check the mouse coordinates against the tiles. But first, you will have to convert your mouse coordinates from screen coordinates to world coordinates.

That sounds harder than it is. Let's pretend the tiles are not laid out isometrically, but in a grid. Like this:

I've added numbers that represent the tiles in memory. For example, 0 would be m_Tiles[0].

Here, it's easy to see which tile is selected. In pseudocode:

vec2 pos = mouse.pos - tileset.pos_upperleft;
int index = ((pos.y / tileset.tile_height) * 2) + (pos.x / tileset.tile_width);

In this case, that gives us an index of 2, which is correct.

But watch what happens when we rotate the tileset 45 degrees:

Now we're selecting a different tile altogether! How can we fix this? Well, in two ways:

• Rotate the tileset to fit the screen coordinates (world space to screen space)


• Rotate the mouse coordinates to fit the world coordinates (screen space to world space)

We're going for the first method here. It's great for 2D selection because it allows us to keep the rest of the math the same.

First, let's build a matrix that defines the transformation of our tileset. We want to rotate the tileset by 45 degrees, so we'll take a 3x3 matrix (2D matrix) and add a rotation. Then we inverse the result. Think of it this way: to go from world space to screen space, we must rotate by 45 degrees. So to go the other way around, we must rotate by -45 degrees.

Now the code becomes:

mat3x3 transform = mat3x3.identity();

transform.rotate(45.0);
transform.inverse();

vec2 tileset_transformed_pos = transform * vec3(tileset.pos_upperleft.x, tileset.pos_upperleft.y, 1.0);

vec2 pos = mouse.pos - tileset_transformed_pos;
int index = ((pos.y / tileset.tile_height) * 2) + (pos.x / tileset.tile_width);

As you can see, we use the transform matrix to transform the upperleft corner of the tileset. Now the tileset coordinates are in the same space as the mouse coordinates.

But we're not there yet. The tiles are also squashed a bit. The same effect can be achieved by scaling the matrix by a certain amount:

Here I've scaled the whole tileset on the y-axis to 63%, which looks remarkably like an isometric projection. The full pseudo-code:

mat3x3 transform = mat3x3.identity();
transform.rotate(45.0);
transform.scale(1.0, 0.63);
transform.inverse();

vec2 tileset_transformed_pos = transform * vec3(tileset.pos_upperleft.x, tileset.pos_upperleft.y, 1.0);

vec2 pos = mouse.pos - tileset_transformed_pos;

int index = ((pos.y / tileset.tile_height) * 2) + (pos.x / tileset.tile_width);

Obviously you will have to tweak this a bit, but it should give you a sense of where to begin.