Calculate neighbouring horizontal & vertical nodes in a grid

Haxe
#1

Hi!

I’m trying to figure out the best solution to calculate neighbouring nodes in a 2 dimensional grid.
Let’s say that i have a grid of 5x5, where i iterate through the rows and colums and push a node into a list of nodes.

class Node extends Sprite 
{
	public var id: Int;
	public var neighbours: List<Node>;
	public function new(id: Int) 
	{
		super();
		this.id = id;
		this.neighbours = new List();
	}
	
}

var nodes: List = new List<Node>();
var id = 0;
for (row in 0...map.length) {
	for (cell in 0...map[row].length) {
		id++;
		var node = new Node(id);
        nodes.push(node);
	}
}

How would you approach finding the vertical and horizontal node and add it to the node’s neighbour?
My initial thought was something like this, but i still have to iterate through the grid i Imagine.

for (node in nodes) {
		for (n in nodes) {
                      // if n is vertically | | horizontally adjacent in the grid relative to node, add n to node.neighbours 
                      node.neighbours.add(n)
		}
	}

Thank you!

#2

Perhaps something like this?

private var grid:Array<Array<Node>>;

// generate grid, then for each node...

var indexX = node.indexX;
var indexY = node.indexY;

if (indexY > 0) node.neighbors.add (grid[indexX][indexY - 1]);
if (indexY < grid[indexX].length - 1) node.neighbors.add (grid[indexX][indexY + 1]);
if (indexX > 0) node.neighbors.add (grid[indexX - 1][indexY]);
if (indexX < grid.length - 1) node.neighbors.add (grid[indexX + 1][indexY]);

If each node remembers it’s index in the grid, and if you use a data structure where you can look up nodes by indices (Map is okay, but don’t loop over Map often, otherwise Array is better). it should make it simpler to find neighbors if you keep track of the index of each node.

#3

Brilliant suggestion!

After a bit of tweaking I managed to get it to work perfectly.
Thank you!

1 Like