Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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];
    }
  }
}
share|improve this question
5  
I don't realy get what you meant but this might help first create an point ad[8] that has values {{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}}. then just use one for loop from 1 to 8 to check Tiles[x+ad[i].x][y+ad[i].y]. it'll eliminate that one calculate you are trying to avoid. –  Ali.S May 28 '11 at 18:36
3  
Premature optimization? –  Byte56 May 28 '11 at 21:21
1  
Shouldn't that || be an && in your if statement? Edit: nevermind, I was wrong. –  Tetrad May 28 '11 at 21:21
1  
@Tetrad no, that should be an ||, it could however be reduced to x || y. –  eBusiness May 29 '11 at 0:36
1  
@Qua (x != 0 || y != 0) => (x || y), that seems pretty basic to me, both code pieces will return 1 for every case but x=0, y=0. –  eBusiness May 29 '11 at 23:45

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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;
        }
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.