Diamond shaped selection on a staggered iso map

Question

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.

Answer 1

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.

Answer 2

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;
    }  
}

Answer 3

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);
    }