# Diamond shaped selection on a staggered iso map

I have a staggered isometric tile map and want to do a selection that aligns with the diamond shape of the tiles.

This is what I mean:

So I got two points on screen and their map cell coordinates. How do I iterate over all tiles that are within the selection?

What I got to help with this is a method that gets the neighboring tiles.

First off, you should be storing all the tiles in a normal square grid. This will make tasks like this a no-brainer. The only place your tiles should actually be diamond shaped is on screen. Any selections on screen utilize a screenToWorld(x,y) function and any world drawing uses a worldToScreen(x,y) function. Then you can easily take your two points from the selection rectangle and convert them both with screenToWorld(x,y), then simply use them to step through your 2D array collecting tiles that are valid for selection.

If you're not reworking your entire coordinate system, you should at least make it consistent. Your x coordinates are shared by two adjacent tiles, while your y tiles are not.

See how going in the x direction it's red(5), red(5), blue(6), blue(6), red(7), red(7)? Then in the y direction it's blue(1), red(2), blue(3), red(4)?

This means it's very difficult to even iterate over the tiles in a consistent way.

• I don't want to change the coordinate space at this time. I would have to redo alot of the code. screenToWorld and worldToScreen are already implemented. – Chris Dec 9 '12 at 16:19
• Better change it now than later, you won't get happy with the tile adressing you use there. You could use your WorldToScreen and the tile offsets in the diagonal directions to temporarily convert to a iterable grid, but I would call that a hack. – Archy Dec 9 '12 at 16:27
• Well, the thing is, this is not for a game. I will use it for a pixel art site. So not much going on game logic wise. I thought this is the usual tile addressing for a staggerd map!? – Chris Dec 9 '12 at 16:31

I suggest changing the coordinate space too. But here is some untested code that should do the trick. p0Screen and p1Screen are the two points in screen space. ScreenX and ScreenY are two vectors that represent the screen space vector from one cell to the next in the two diagonal directions, eg 4/12 -> 4/11 for screenX and 4/12 -> 4/13 for screenY. The direction is not important as long as the length is correct.

In the inner loop you get the screen coordinate of each tile in the area.

Vec2Float p0Screen;
Vec2Float p1Screen;
Vec2Float screenX;
Vec2Float screenY;

Vec2Float deltaScreen = p1Screen - p0Screen;
float screenXLenRcp = 1.0f / screenX.GetLength();
float screenYLenRcp = 1.0f / screenY.GetLength();
Vec2Float screenXNorm = screenX * screenXLenRcp;
Vec2Float screenYNorm = screenY * screenYLenRcp;

Vec2Int delta;
delta.x = (int)(0.5f + dot( deltaScreen, screenXNorm ) * screenXLenRcp );
delta.y = (int)(0.5f + dot( deltaScreen, screenYNorm ) * screenYLenRcp );

Vec2Float deltaSign;
deltaSign.x = delta.x > 0 ? 1.0f : -1.0f;
deltaSign.y = delta.y > 0 ? 1.0f : -1.0f;

delta.x = abs( delta.x );
delta.y = abs( delta.y );

for( int y = 0; y <= delta.y; y++ )
{
float sy = (float)y * deltaSign.y;
Vec2Float screenDeltaY = sy * screenY;

for( int x = 0; x <= delta.x; x++ )
{
float sx = (float)x * deltaSign.x;
Vec2Float screenDeltaX = sx * screenX;
Vec2Float tileScreen = p0Screen + screenDeltaX + screenDeltaY;
}
}

• That's a lot of iterations. But if I align both selection points to the actual tile coordinates, I can use tile width and height as iteration steps, or am I on the wrong path? – Chris Dec 9 '12 at 18:16
• Its exactly as many iterations as you need, namely the amount of cells in your square. If you execute this for your example above you will get 5x6 iterations, or 6x5 depending on which screen x and which screen y vector you use. Its done in screen space as your world space is malformed and does not allow a simple iteration, as byte56 described in detail in his answer. If you unify the addressing as byte56 suggests you basically do the same, you just wouldn't have to calculate each cells screen space position first. – Archy Dec 9 '12 at 19:28
• Then there's something wrong with my values or the algorithm. I am getting much higher values for delta. Is the "dot()" a dot product? – Chris Dec 9 '12 at 20:00
• Yes, it is a dot product and yes it is to large. :) Should be fixed now. – Archy Dec 9 '12 at 20:16

I gave up on solving this with mathematics and chose a more algorithmic way to do it:

    stagStart = this.selection.start;
stagEnd = this.selection.end;

diaStart = this.staggeredToDiamond(this.selection.start);
diaEnd = this.staggeredToDiamond(this.selection.end);

//for calculating the distances we convert to diamond coordinates first
deltaX = Math.abs(diaStart.x - diaEnd.x) + 1;
deltaY = Math.abs(diaStart.y - diaEnd.y) + 1;

//direction for x axis traversal
if(diaEnd.x > diaStart.x) {
directionX = TileEngine.SOUTH_EAST;
} else {
directionX = TileEngine.NORTH_WEST;
}

//direction for y axis traversal
if(diaEnd.y > diaStart.y) {
directionY = TileEngine.SOUTH_WEST;
} else {
directionY = TileEngine.NORTH_EAST;
}

beginY = stagStart;

//walk along y axis since it's easy to iterate over
for(i = 0; i < deltaY; i++) {

currentX = beginY;
//draw along x axis
for(j = 0; j < deltaX; j++) {
tile = this.mapToScreen(currentX);
this.ctx.drawImage(this.tileset.tiles[3].image, tile.x, tile.y);
currentX = this.nextTile(currentX, directionX);
}

beginY = this.nextTile(beginY, directionY);
}

• Well, it's basically exactly the solution I posted. – Archy Jan 23 '13 at 12:46