Fastest way to get all adjacent tiles?

Question

What is the fastest way to get all adjacent tiles in a two-dimensional array of tiles, converted into a single-dimensional array?

If you don't know the answer, then the fastest way to do it in a two-dimensional array would be fine as well.

I tried the following, but it does 9 calculations, which is 1 too much when it comes to optimization.

for(int x = -1; x <= 1; x++) {
  for(int y = -1; y <= 1; y++) {
    if(x != 0 || y != 0) {
      Tile adjacent = Tiles[current.x + x, current.y + y];
    }
  }
}

Answer 1

What you are proposing is pretty much the fastest; as determining wether or not you are on the same tile would probably be more costly than just doing it. Doing it 9 times.

But as an alternative; consider if you will a space/time tradeoff.

Instead of doing this calculations at a critical time, do them when you are reading the map into memory; storing in each tile the location of their neighbours. It requires more space in memory per tile; but it does save time when doing lookups. If you have an application-wide enum (or similar) for directions, even better; then you could do something like:

aNeighboringTile = current.neighbors[NORTH];

The tradeoff can be tuned to use either cardinal neighbours only, or both cardinal and diagonal neighbours; the former being tighter and the latter being faster.

A question that you seriously need to consider, of course, is wether or not this is actually necessary, or if your current approach in practice is fast enough.

If you are already facing slowdowns due to the extra calculation; then it is likely that the only thing that will give any speedup is pre-calculating neighbors.

Edit: This can of course be compined with Gajet's suggestion to use a constant array of the index deltas to search to eliminate the extra calculations during generation/loading.

Answer 2

If I am iterating through a 3D array of tiles and I care about the neighbors, I maintain an index of each neighbor for quick access. I also store an empty row for neighbors outside of the array. Your code would only be more simple with a 2D array. I apologize for the mess, this is prototyping code. Most complex conditionals is only performed for the first cell of each row. It also has code for reading neighbors cells of neighboring arrays.

    static short empties[256] = {0};
    short *down, *up, *east, *west, *north, *south;
    short *tiles = this->tiles, *tile = this->tiles, *empty = &empties[0];
    int index = 0, skip; // Skip is cells skipped.

    for (int z = 0; z < SEGMENT_DEPTH; ++z)
    {
        down = (z == 0) ? empty : (tile - SEGMENT_WIDTH * SEGMENT_HEIGHT);
        up = (z == SEGMENT_DEPTH-1) ? empty : (tile + SEGMENT_WIDTH * SEGMENT_HEIGHT);

        for (int y = 0; y < SEGMENT_HEIGHT; ++y)
        {
            south = (y == 0) ? ( (this->south) ? &this->south->tiles[z * SEGMENT_WIDTH * SEGMENT_HEIGHT + SEGMENT_WIDTH * (SEGMENT_WIDTH-1)] : empty ) : (tile - SEGMENT_HEIGHT);
            north = (y == SEGMENT_HEIGHT-1) ? ( (this->north) ? &this->north->tiles[z * SEGMENT_WIDTH * SEGMENT_HEIGHT] : empty ) : (tile + SEGMENT_HEIGHT);
            skips = 0;

            for (int x = 0; x < SEGMENT_WIDTH; ++x, ++tile, ++skips)
            {
                if (*tile == 0)
                    continue; // skip empty tiles

                up += skips, down += skips, south += skips, north += skips;
                west = (x == 0) ? ( (this->west) ? &this->west->tiles[z * SEGMENT_WIDTH * SEGMENT_HEIGHT + y * SEGMENT_HEIGHT + SEGMENT_WIDTH - 1] : empty ) : (tile - 1);
                east = (x == SEGMENT_WIDTH-1) ? ( (this->east) ? &this->east->tiles[z * SEGMENT_WIDTH * SEGMENT_HEIGHT + y * SEGMENT_HEIGHT + 0] : empty ) : (tile + 1);                    
                skips = 0;

                if (*up != 0 && *down != 0 && *west != 0 && *east != 0 && *north != 0 && *south != 0)
                    continue;

                // . . . DO WORK HERE . . .

            }
            up += skips, down += skips;
        }

Answer 3

I normally use this:

    //- start at your left tile.
    int x = -1;  
    int y = 0;
    for (int i = 0; i < 4; i++) {

        USE THE (x,y) ADJACENT TILE HERE.
        Debug.Log(x + ", " + y);

        //- this will set x,y to the bottom tile.
        if (x == -1 && y == 0){
            x = 0;
            y = -1;
        }
        else {
            //- this will set x,y to the top tile.
            if (y == -1) {
                x = 0;
                y = 1;
            }
            //- this will set x,y to the right tile.
            else {
                x = 1;
                y = 0;
            }
        }

It's not the prettiest code, but it only uses 7 calculations. The first loop uses 1, the second loop uses 2, the third loop uses 2, and the fourth loop uses 2. After 4 loops, the output is (-1,0), (0,-1), (0,1), (1,0); all four directions around a center point of (0,0).

Answer 4

The reason it is checking 9 tiles is because it is also checking the middle tile. IT's funny, because I came up with the exact same solution. And you should be proud, as it's a fairly elegant one. anyway, the line that interests you is the if( ... !( rowOffset == 0 && colOffset === 0 )) this makes sure that you skip the "middle" tile. Heres a simple function that I wrote for a CS200 class. it returns all 8 surrounding tiles as an array. It's in Java, but it can easily be adapted to the language of your choice.

    String[] rtrn = new String[ 8 ];
    int index = 0;
    int offsetRow, offsetCol;

    // Offset the rows by -1, 0, 1
    for ( int rowOffset = -1; rowOffset <= 1; rowOffset++ ) {
        offsetRow = row + rowOffset;
        // Offset the columns by -1, 0, 1
        for ( int colOffset = -1; colOffset <= 1; colOffset++ ) {
            offsetCol = col + colOffset;
            // Make sure the coordinates are on the board &&   skip the "center" tile.
            if( !outOfBounds( arr, offsetRow, offsetCol ) && !( rowOffset == 0 && colOffset == 0 ) ) {
                // Set the next value in the return array
                rtrn[ index ] = arr[ offsetRow ][ offsetCol ];
                index++;
            }
        }
    }
    return rtrn;

here is the outOfBounds function

    // Below 0 or greater than the array bounds are a no-go
    boolean tooSmall = ( row < 0 || col < 0 );
    boolean tooBig   = ( row > ( arr.length - 1 ) || ( col > arr[ 0 ].length - 1 ) );

    return ( tooBig || tooSmall );