Understanding point graphs

Hi, I have used A* using a grid graph and everything worked as I expected. Now I am trying to use a PointGraph and sadly I am very confused.

I had the expectation that a point graph would be an almost completely abstracted creature. Something where I could define nodes and their connections and then ask questions like is node A connected to node K and find out how many hops it was (waypoints).

In my script I reference my point graph (I also have a gridGraph so I reference it as graphs[1]). Then I call createnodes(3) and I define some connections between them. When I look at my point graph in the unity editor it says that it has 0 nodes. I called scan() but no change.

How do I get A* to recognize the nodes I am adding?

In detail what I am doing is:

  • get a list of transforms. (3)
  • call aPointGraph.Createnodes(3)
  • add some connections all with cost 1.
  • set all nodes as walkable
    Unity editor says that my point graph has zero nodes. What step am I missing?

For some more testing I added a seeker and used the overload with mask to tell it to use my point graph. (for some reason the seeker continues to use the grid graph.
NavGraph = (1 << 0); <–grid graph at index 0 of graphs
EconGraph = (1 << 1); <–point graph at index 1 of graphs)

Sorry I know I am introducing a second question…

Any help very much appreciated.

1 Like

I think my seeker MUST be using the wrong graph. I added 4 nodes to my point graph and defined connections. When I ask the seeker to find a path from node[0] to node[2] it claims to have found a path with 6 waypoints in it. How can that be if I only have 4 nodes? It has to be using the wrong graph.

My Astar object graphs component has two graphs
Grid Graph
Point Graph
(in that order)

I am calling startpath like this:
seeker.StartPath(V3,V3,myCallBack,(1 << 1));

What could I be doing wrong?


Point graphs are not completely abstracted.
I think what you are looking for is creating a custom graph. I have a tutorial on that, even though I could have chosen an easier example (will have to rewrite it sometime), I hope it will help you on your way.

See http://arongranberg.com/astar/docs/writing-graph-generators.php

Thx Aron I had read that it was the most useful thing I had found but still left me wanting.

When I read it the first time I ignored the class definition as a Simple Graph and was focusing instead on how to generate my node array and populate it with nodes and connections.

Reading it again I am ever more confused. I created the class for a test like this:

using UnityEngine;
using System.Collections;
//Include generics to be able to use Generics
using System.Collections.Generic;
//Include the Pathfinding namespace to gain access to a lot of useful classes
using Pathfinding;

public class SimpleGraph : NavGraph {
private Seeker seeker;

public override void Scan (){
	Node[] nodes = CreateNodes(10);
	Vector3 nodePos;
	Node[] connections;
	int[] connectionCosts;
	for(int i = 0;i<10;i++){
		connections = new Node[1];
		connectionCosts = new int[1];
			connectionCosts[0]= 1;
		} else {
			connectionCosts[0]= 1;
		nodePos  = new Vector3(0,0,0);
		nodes[i].position = (Int3)nodePos;
		nodes[i].connections = connections;
		nodes[i].connectionCosts = connectionCosts;


And as it says when I go to the graphs component when I click add graph, it is there but greyed out. So…if I can’t add it to the graphs collection how can I seek on it? But perhaps more to the point, I would think that I want to create a graph based on a class called “Simple Graph”, not define that class. No?

And if I got to the point to seek on it, the seeker startpath takes V3’s as params. will that even work if I set all nodes to Vector3(0,0,0) ??


Are you sure you need a pathfinding library as large as this one? From the looks of your code, you want something either like a BFS search (about 30 lines of code) or a very simple Dijikstra search (less than 100 lines depending on how much you write yourself). If you don’t want nodes to have explicit positions and you only want to ask how many hops there are between two nodes. This pathfinding library is a bit overkill.

//Create 100 nodes with connections like a cyclic chain
List<List> nodeConns = new List<List> (100);
for (int i=0;i<nodeConns.Count;i++) {
nodeConns[i] = new List();
nodeConns[i].Add ((i+1) % nodeConns.Count);
nodeConns[i].Add ((i-1+nodeConns.Count) % nodeConns.Count);

//How many hops are there between these two nodes
int startNode = 4;
int endNode = 75;

List visited = new List(100);
for (int i=0;i<visited.Count;i++) visited[i] = -1;

Queue q;
q.Enqueue (startNode);
visited[startNode] = 0;

//Begin BFS search
while (q.Count > 0) {
int n = q.Dequeue ();
int l = visited[n];
if (n == endNode) {
Debug.Log (“Found end node after “+(l+1)+” steps”):
for (int i=0;i<nodeConns[n].Count;i++) {
if (visited[nodeConns[n][i] == -1) {
visited[nodeConns[n][i]] = l+1;
q.Enqueue (nodeConns[n][i]);

Debug.Log (“The end node could not be reached”);`

Hi thanks for the follow up. We are already using A* for another aspect of the game and it is working fine. In that situation we are navigating across terrain and it works as expected.

This is for a different aspect of the game which is connection dependent but not 3d space dependent.

As you are suggesting I implemented a basic Dijikstra class and it is working ok for now. It just would have been nice to have the extra features that A* already includes.

I did see a few other posts in the forum where people where in the same situation. Needing to path across a constructed network of nodes (buildings and streets, or pipes and valves or whatever.)

Could this not be an easy addition for the next version of A* ?


This was something I was struggling with for the past two days but finally managed to fix and though others might come across this too.

I placed a few nodes and added connections between them and tried to navigate using my generated graph.
Now on its own it would not work. After some deep digging into the code base, I found out there was some constraints that were causing pathfinding to fail. I have no idea why these constraints came up though.
First, different connections were in different areas. This was shown in the scene view when connections were different colors.
Afterwards I located the constraints tags in the astarclasses.cs file Lines 157 - 175 and changed all the constraints to false.
This fixed my problems and now my generated graph works like normal.

Thanks Aron for your great project!



Make sure that after you have updated the graph, call AstarPath.active.FloodFill (), that will ensure the areas are correct.