Public Group

# Best algorithm to find Adjacent tiles?

This topic is 3518 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Does anyone know of a resource which shows the most efficient method of finding all 3/5/8 adjacent tiles depending on their grid position? For Example: Tile index 0 can only see 3 adjacent tiles: RIGHT, BOTTOM_RIGHT, BOTTOM since it's at the top left edge of the grid? So far I just have a loop that tests the 8 adjacents to determine if I should add the adjacent nodes to a list, but i'm curious if there is an optimal solution or example I can study to improve on what I have.
//N = Current Node (or Tile/Whatever)

for(int i=0; i<8; i++)
{
switch(i)
{
case RIGHT:
{
if((N%m_GridWidth) != (m_GridWidth-1))
{
int To = N+1;
}
}
break;

case BOTTOM_RIGHT:
//... and so on

//Perhaps a grid should have an bounding box region all round it to simplify the algo testing out of bounds edges?

[Edited by - Pickl3d on December 3, 2008 6:18:54 AM]

##### Share on other sites
Quote:
 Original post by Pickl3dDoes anyone know of a resource which shows the most efficient method of finding all 3/5/8 adjacent tiles depending on their grid position?

This is micro optimization problem where algorithmic improvements may actually harm run-time performance.

For computation of convolution kernel (for given pixel, work on n*m grid), I created an array of pointers and extended the grid by size of largest n and m.

Then the algorithm was something like this:
int * row1;int *row2;int *row3;for (int y = 0; y < height; y++) {  for (int x = 0; x < width; x++) {    // process elements in this order    // row1[x-1], row1[x], row1[x+1];    // row2[x-1], row2[x], row2[x+1];    // row3[x-1], row3[x], row3[x+1];  }  row1 = row2;  row2 = row3;  row3 = getRow(y+2);}

This doesn't require any checks whatsoever, but you need to put something into tiles outside of real grid.

Quote:
 So far I just have a loop that tests the 8 adjacents to determine if I should add the adjacent nodes to a list, but i'm curious if there is an optimal solution or example I can study to improve on what I have.

If you need to perform this test on a single tile, then you can't really optimize it, since AddEdgeIf will likely cost 100 or 1000 times more.

##### Share on other sites
Personally, I wouldn't use a switch-case (or if-else statement) here. If you analyze the situation a bit, you'll notice that you're doing the same for every neighboring cell: you're checking if it's inside the grid or not. You're duplicating this check 8 times, while instead, you could write it once and feed different data to it.

Take a look at the following:
int xOffsets[8] = {-1,  0,  1,  1,  1,  0, -1, -1};int yOffsets[8] = {-1, -1, -1,  0,  1,  1,  1,  0};for(int i = 0; i < 8; ++i)    if(ValidCell(cell.x + xOffsets, cell.y + yOffsets))        // Logic goes here

Other than that however, I wouldn't really worry about optimizing those checks. Sure, you could see if you're at an edge and reduce the number of checks, but these are literally border-cases, so you're adding extra checks that only gain you something in a few rare cases (and cost you something in all other cases).

EDIT: Ninja'd. :)

##### Share on other sites
Thanks for the examples guys, that is very clear using the indexing method.

+ rep!

1. 1
2. 2
3. 3
Rutin
22
4. 4
JoeJ
16
5. 5

• 14
• 29
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631775
• Total Posts
3002277
×