JAVA - How to code Node neighbours in a Grid?
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.
Let's say your Node
s 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 anArrayList<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).
精彩评论