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