Grid graph nodes, how to add neighbour information?

General Grid graph
1
  • A* version: [5.44]
  • Unity version: [6]

Hi,

I’m using a grid graph with 4 connections and have the need to find all the surrounding nodes (all 8 of them if they exist) on a very very regular basis no matter the walkability etc. My grid is not huge and never changes.

I’ve already added a couple of extra bools etc. to the GraphNode class that are used/set at runtime but it would be soo helpful if either when Scanning or afterwards I could add a List/Array to the GraphNode that held all the existing neigbouring nodes (or just their Vector3 would work too).

Being able to use “node.neigbours” would be a lot quicker and easier on the gpu than manualy doing it (as I am now) multiple times per frame but can’t figure how to go about it. I could add it at runtime but it’d be nice if the information was already embedded beforehand.

Custom rules don’t seem to be of help on this one and looking through the scanning process was above my head to be honest.

Any help where to start appreciated.

2

Hi

You can use GridNode.GetNeighbourAlongDirection for this:

Or GraphNode.GetConnections (gets all of them).

Or you can check if the node has a connection in a particular direction using GridNode.HasConnectionInDirection ( HasConnectionInDirection - A* Pathfinding Project )

[EDIT] Just saw that this was regardless of walkability. This cannot be done from the node directly. But you can use GridGraph.GetNode(x,z).

3

Hi,

Thanks for that but rather than calling a function every time I step on a node (thousands of times per game) I was hoping to be able to call that function once with an editor script for every node and store a list of neigbours on that node for future reference as the neighbours will never ever change. It just seemed like it’d cut out a lot of cpu work.

Cheers :slight_smile:

4

One might think that, but honestly it’s pretty good to call the function.

Storing 8 neighbours for each node is around 80 bytes. That would almost double the memory usage of the graph, which has its own consequences.

5

Thanks again,

I’ll trust your judgement as you know this thing inside out, more than I ever will :slight_smile:

I think I managed to half figured it out, I’ll compare its performance out of curiosity at some point, I went with the node positions rather than the node itself and just stuck a Vector3 List<> in the GraphNode script and the below code in a start function on another script.

 var gg = AstarPath.active.data.gridGraph;

 gg.GetNodes(node =>
 {
     node.GetConnections(connectedTo =>
     {
         node.neighbours.Add((Vector3)connectedTo.position);
     });
 });