JAVA - How to code Node neighbours in a Grid ?

Question

I'm new to programming and as a school task I need to implement BFS, DFS and A* search algorithms in Java to search for a given Goal from a given start position in a Grid of given size, 4x4, 8x8, etc.

To begin with I don't know how to code the neighbors of all the nodes. For example in a 8x8 grid tile 1 has 2 and 9 as neighbors and Tile 12 has 4, 11, 13 and 20 as its neighbours but i'm struggling to code that. I need the neighbours part so that i can move from start position to other parts of gird legally by moving horizontally or vertically through the neighbours.

 1  2  3  4  5  6  7  8 
 9 10 11 12 13 14 15 16 
17 18 19 20 21 22 23 24 
25 26 27 28 29 30 31 32 
33 34 35 36 37 38 39 40 
41 42 43 44 45 46 47 48 
49 50 51 52 53 54 55 56 
57 58 59 60 61 62 63 64

my node class is:

class Node {
   int value;
   LinkedList<Node> neighbors;
   bool expanded;
}

Let's say i'm given a 8x8 grid right, So if i start the program with a grid of size 8x8 right :

1 - my main method will create an arrayList of nodes for example node

ArrayList<Node> test = new ArrayList<Node>();

and then using a for loop assign value to all the nodes in arrayList from 1 to 64 (if the grid size was 8x8).

BUT somehow i need to add the neighbors of each node, if anyone can give me some details i would really appreciate it.

Answer 1

Just do the math.

north = currentPos - gridSize;
east = currentPos + 1;
south = currentPos + gridSize;
west = currentPos - 1;

Of course check for negative values ;)

Answer 2

Let's say your Nodes are laid out in M rows and N columns. For simplicity, let nodes[r][c] be the reference to Node at row r and column c (zero-based indexing), currently with empty List<Node> neighbors that we want to build.

Here's one way to build them:

for (int r = 0; r < M; r++) {
  for (int c = 0; c < N; c++) {
    Node n = nodes[r][c];
    List<Node> neighbors = n.neighbors;
    if (r > 0) {     // has north
      neighbors.add(nodes[r-1][c]);
    }
    if (r < M - 1) { // has south
      neighbors.add(nodes[r+1][c]);
    }
    if (c > 0) {     // has west
      neighbors.add(nodes[r][c-1]);
    }
    if (c < N - 1) { // has east
      neighbors.add(nodes[r][c+1]);
    }
  }
}

---

my main method will create an ArrayList<Node>

It's so much easier to handle a grid in a 2-dimensional data structure, be it an array-of-array or list-of-list. If you insist on having a 1-D list, then instead of nodes[r][c], you call nodeAt(r, c) helper function:

Node nodeAt(int r, int c) {
   return nodesList.get(r * N + c);
}

This is a standard transformation from 2-D indexing to 1-D (assuming row-major order).