CODEWITHSUNDEEP
c++carraysmultidimensional-array
airplaneman19
airplaneman19

Reputation: 1159

Visiting all locations in a multidimensional array directly adjacent to some location?

I'm doing my first algorithm (A* Pathfinding) and part of it involves checking all nodes adjacent to a different node. Is there a quick and easy way to do this or must it be done manually for each node?

Edit:

By adjacent I mean this:

Each X is adjacent to the parent node, O

XXX  
XOX  
XXX

Upvotes: 2

Views: 473

Answers (2)

templatetypedef
templatetypedef

Reputation: 372972

There's a nice double-for-loop you can use:

for (int i = x - 1; i <= x + 1; i++) {
    for (int j = y - 1; j <= y + 1; j++) {
        /* Skip the point itself! */
        if (i == x && j == y) continue;

        /* Process the location here */
    }
}

This can also be generalized to only consider points adjacent by cardinal directions (i.e. directly up/down/left/right). To do that, you use a modification of the above for loop where you visit all eight neighbors, but then skip points that either

  • Are identically where you are (both i == x and j == y), or
  • Have neither x nor y in common with the start point (both i != x and j != y)

Interestingly, the above two tests can be rolled into one line: ((i == x) == (j == y)). This tests whether both values are the same (you're at the same place you started) or both values are different (you're on a diagonal):

for (int i = x - 1; i <= x + 1; i++) {
    for (int j = y - 1; j <= y + 1; j++) {
        if ((i == x) == (j == y)) continue;

        /* Process the location here */
    }
}

Of course, in both cases you should ensure that you're within the bounds of the world, but since I don't know how those are specified I'll leave it as an exercise to the reader. :-)

Hope this helps!

Upvotes: 1

Carl Norum
Carl Norum

Reputation: 225032

The adjacent entries in a 2D array are pretty easy to find. The adjacent entries to array[i][j] are:

array[i-1][j-1];
array[i-1][j];
array[i-1][j+1];
array[i][j-1];
array[i][j+1];
array[i+1][j-1];
array[i+1][j];
array[i+1][j+1];

You can generalize to higher-dimensioned arrays pretty easily. Watch out that you don't go past the bounds of your array!

Upvotes: 0

Related Questions