Algorithm to check all adjacent points

Question

I am trying to find the most efficient way to traverse all adjacent cells in a grid.

For example let's say I have a 2D Array represented as: vector <Item> grid;

and I have a point within this grid (represented by the blue cell): grid[x][y];

and I want it to traverse all the adjacent coordinates.

So for example if my point was (1,1) it would be able to traverse (0,0) (0,1) (0,2) (1,0) (1,2) (2,0) (2,1) (2,2) which are the 8 points which surround it (excluding the case for now when (x,y) is in a corner or at the edge of the grid).

What is the best way to do this in C++? my initial thought was to do Breadth-First Search, any thoughts?

I'm not sure I understand the question. Can't you just iterate over the structure, one tile at the time, and for each tile check its neighbors with the 8 coordinate offsets you've given? Am not sure how BFS comes in — Ted Klein Bergman
There are at most 8 adjacent cells in a 2D grid. Why are you concerned about efficiency for such a small number? Premature optimization? Better would be to find a readable way to traverse the neighbors. — JaMiT
Computers are really really good at doing simple things very very fast. You only get a performance boost over simple and stupid when smart eliminates the need to do work, and even then smart has to eliminate enough work to overcome the speed advantage that stupid starts with. In this case no matter what you do, you have to visit all 8 neighbors (but watch out for the edges!), so you can't eliminate any work. — user4581301

cigien cigien · Accepted Answer · 2020-09-25T18:29:46

Here's one way to iterate the neighbours:

for (int i : {-1, 0, 1})
  for (int j : {-1, 0, 1}) 
    if (i && j)
      std::cout << grid[x + i][y + j]; // prints all the neighbours

Make sure to account for the edges of the grid as well.

This is just a readable way to iterate neighbors. Don't worry about efficiency unless you've measured your code and discovered that this code is a performance bottleneck.

Algorithm to check all adjacent points

1 Answers