Efficiently getting isometric grid positions within a bounding box

Question

I have an isometric grid system who's coordinates start from [0,0] in the left hand corner of the grid (The corner shown in the above image) with x incrementing towards the bottom of the image and y incrementing towards the top (so [0, height] would be the top corner and [width, 0] would be the bottom corner in a diamond shape with width and height being the size of the grid ie. 200 x 200 squares)

Anyways what I need help with is getting an array of isometric grid positions that are contained within the blue box shown in the image. Short of iterating over every x,y screen pos and getting the corresponding grid position (See this question I posed earlier on how to convert from a screen position to a grid positon Get row/column on isometric grid.) i'm not sure how to achieve this effeciently.

There was a question I found earlier that is almost exactly the same Link here. The answer was to render the grid to an image with different colors for each grid square and then detect what colors were present under the square, I have implemented this solution but it is quite slow! I'm almost thinking checking the grid position for each pixel in the selection box would be faster. Why oh why is javascript so slow at looping!

I really need a mathematical solution to this problem based on my coordinate system but I can't seem to come up with something that works (and handles the selection box going off the grid as well)

Please let me know if you need more information.

Edit: Unfortunately the supplied answers haven't worked so far, as the selection is like having a diamond selected area on a square grid, there is really no top left, bottom right corner to iterate through unless I missed the point of the answers? I have optimized the render approach but on a large selection, it still adds a noticeable drop in frames as it loops through all the pixel checking color and getting the corresponding square

Answer 1

Linear algebra is the answer. There are two coordinate systems of interest here: screen coordinates and isometric coordinates. Converting the corners of the selected region from screen coordinates to isometric coordinates will greatly help you.

Let theta be the angle between the x and y axes of the isometric coordinates, measured on the screen and unit be the pixel length of one step in the isometric coordinates. Then

var c = Math.cos(theta/2);
var s = Math.sin(theta/2);
var origin = [oX, oY]; //the pixel coordinates of (0, 0)
var unit = 20;
var iso2Screen = function(iso) {
  var screenX = origin[0] + unit * (iso[0] * c + iso[1] * c);
  var screenY = origin[1] + unit * (iso[0] * -s + iso[1] * s);
  return [screenX, screenY];
}

Inverting this relationship, we get

var screen2Iso = function(screen) {
  var isoX = ((screen[0] - origin[0]) / c - (screen[1] - origin[1]) / s) / unit;
  var isoY = ((screen[0] - origin[0]) / c + (screen[1] - origin[1]) / s) / unit;

Now convert the screen coordinates of each corner of the selection box to isometric coordinates and get the minimum and maximum x and y.

var cornersScreen = ...//4-element array of 2-element arrays
var cornersIso = [];
for(var i = 0; i < 4; i++) {
  cornersIso.push(screen2Iso(cornersScreen[i]));
}
var minX, maxX, minY, maxY;
minX = Math.min(cornersIso[0][0], cornersIso[1][0], cornersIso[2][0], cornersIso[3][0]);
maxX = Math.max(cornersIso[0][0], cornersIso[1][0], cornersIso[2][0], cornersIso[3][0]);
minY = Math.min(cornersIso[0][1], cornersIso[1][1], cornersIso[2][1], cornersIso[3][1]);
maxY = Math.max(cornersIso[0][1], cornersIso[1][1], cornersIso[2][1], cornersIso[3][1]);

All the selected isometric points lie inside of the isometric box [minX, maxX] x [minY, maxY], but not all of the points in that box are inside the selection.

You could do a lot of different things to weed out the points in that box that are not in the selection; I'd suggest iterating over integer values of the isometric x and y, converting the isometric coordinates to screen coordinates, and then testing to see if that screen coordinate lies within the selection box, to wit:

var sMinX, sMaxX, sMinY, sMaxY;
sMinX = Math.min(cornersScreen[0][0], cornersScreen[1][0], cornersScreen[2][0], cornersScreen[3][0]);
sMaxX = Math.max(cornersScreen[0][0], cornersScreen[1][0], cornersScreen[2][0], cornersScreen[3][0]);
sMinY = Math.min(cornersScreen[0][1], cornersScreen[1][1], cornersScreen[2][1], cornersScreen[3][1]);
sMaxY = Math.max(cornersScreen[0][1], cornersScreen[1][1], cornersScreen[2][1], cornersScreen[3][1]);
var selectedPoints = [];
for(var x = Math.floor(minX); x <= Math.ceil(maxX); x++) {
  for(var y = Math.floor(minY); x <= Math.ceil(maxY); y++) {
    var iso = [x,y];
    var screen = iso2Screen(iso);
    if(screen[0] >= sMinX && screen[0] <= sMaxX && screen[1] >= sMinY && screen[1] <= sMaxY) {
      selectedPoints.push(iso);
    }
  }
}

Answer 2

I'm student doing XNA games for hobby. I'm working on classical 2D game based on squares (Project Squared). This game of yours reminded me on my work so I decided to help you.

I think it should be done using math, not graphics as you mentioned.

First you should know which square (position on grid) is on start of "blue box" (probably selection box) and end of selection. So now you know an beginning and ending of your list.

Since in your game squares probably have static size (or you zoom camera, but never increase width/height) you can calculate which squares are in your selection box easily.

Now, you know that your squares are 45° moved r/l.

(I'm talking about XNA like coordsys - up left 0,0)

If ( selectedStartSquare.selectionY <= square.height )
    startY = selectedStartSquare.selectionY
else startY = selectedStartSquare.selectionY + 1; 

if (selectedEndSquare.selectionY > square.height)
    endY = -||-.selectionY
else endY = -||- + 1;

this will give you the start and end height indexes of squares. Same thing you need to do for X indexes.

Now you have all you need to get all squares. Go through X from selectedStartSquare.X to endX and trough Y with for loop from selectedStartSquare.Y to endY but change start every time ( startYIndex++ every loop)

This is just a close example since I never worked with Isometric games. This will probably need some tweaking but I "think!!" this should work. (Wrote this before sleep and without even a paper since I was in bed already... good luck)

Sorry for my English, I'm from Croatia so...

Answer 3

I think Aleksander has a very good idea on how to solve your problem.

Here is an alternative:

An easy way to reduce the number of grid squares to check is to find the coordinates of the corners of the blue box in grid coords. In your example you would only need to check the squares where 1<x<13 and 3<y<16.

alvaro gives a short and concise answer on how to check if a point is inside a box.

Answer 4

Considering the regular layout of the tiles, can't you simply start from the top left corner of the selector box, hittest to find which tile, and then move along to the next tile according to how they are spaced.

For example, if your tiles are 32x16, you would start at the corner, and move along 32, then when you reach the end, go along the next row.

eg, in a strange kind of pseudocode...

var altRow = false;
var selectedTiles = [];
for (int y = selectorBox.top; y < selectorBox.top+selectorBox.height; y+=TILE_HEIGHT/2) {
    for (int x = selectorBox.left ; x < selectorBox.left+selectorBox.width; x+= TILE_WIDTH) {
        selectedTiles.add(tileAtPoint(x + (altRow ? - TILE_WIDTH/2 : 0), y);
    }
    altRow = !altRow;
}

Answer 5

My approach which I didn't see anyone else do: 1. Transform your selecting rectangle to the grid (get the tile position of each of the corners) 2. Now we have a 2d problem, which is: find all points within the transformed rhombus.

This could be done with similar to: http://en.wikipedia.org/wiki/Flood_fill

But maybe something like this is better:

1. Start at the topmost
2. Go down
3. Go right until we encounter the edge (can be calculated from the rombus line)
4. Do the same thing but go left.
5. Go to 2 until we are at the middle
6. Go right and down.
7. Go right until we encouter the edge
8. Go left and down.
9. Go left until we encouter the edge
10. Go to 6 until we are at the bottom

At every tile we visit we add that one.

Now the only problem left is to determine if we have encountered an edge...

Answer 6

I assume you can get the coordinates of the selection box's corners mapped to the iso grid squares. This gives you a plotting problem with a simple algebraic test for solution. If we start with the corners in iso-squares (x1,y1) and (x2,y2), we know we need to test along the lines with slope 1 and -1 that go through these points,

so the four lines are y-y1=x-x1, y-y1=x1-x,y-y2=x-x2,y-y2=x2-x. They meet at the iso-squares containing the corners of the selection box you began with.

If we assume for convenience that x2 and y2 are larger than x1 and y1 respectively, we need only iterate over the iso-grid for values from x1 to x2, and y1 to y2, accepting only iso-squares whose y-coordinates are less than the both of the "larger" lines, and smaller than the two "smaller" lines.