Sign in to follow this  

Best algorithm to find Adjacent tiles?

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

If you intended to correct an error in the post then please contact us.

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;
	AddEdgeIf(N,To, NavGraph);
  }
 }
 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 this post


Link to post
Share on other sites
Quote:
Original post by Pickl3d
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?


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 this post


Link to post
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[i], cell.y + yOffsets[i]))
// 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 this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this