Understanding runtime graph management

1

Hi,
I use A* Pathfinding for the first time so buckle up for noobish questions.

I’m trying to create a point graph where there are just lines between points and not areas. I just need to find path between my nodes and I don’t need a navigating agent.

My nodes are created and connected at runtime. The graph is pretty simple for now but I can’t manage to find path. I think there is something about unit conversion that I didn’t grasp.
Here is the code I use (A game object containing a Astar Path component with no graph in it is on the scene).

    private void Start()
    {
        AstarData data = AstarPath.active.astarData;
        pg = data.AddGraph(typeof(PointGraph)) as PointGraph;
        pg.raycast = false;
        pg.autoLinkNodes = false;
        pg.recursive = false;
        pg.drawGizmos = true;
        AstarPath.RegisterSafeUpdate(UpdateGraph);
    }

    private void Update()
    {
        Vector3 mouse_pos = Input.mousePosition;
        mouse_pos = Camera.main.ScreenToWorldPoint(mouse_pos);
        _mouse_pos = new Vector3(mouse_pos.x, 0.0f, mouse_pos.y);
        FindPath(new Vector3(0,0,0), _mouse_pos);
    }

    private void UpdateGraph()
    {
        PointNode A = pg.AddNode(new Int3(0,0,0));
        PointNode B = pg.AddNode(new Int3(1, 0, 1));
        PointNode C = pg.AddNode(new Int3(1, 0, -1));
        PointNode D = pg.AddNode(new Int3(2, 0, 2));
        PointNode E = pg.AddNode(new Int3(2, 0, -1));
        PointNode F = pg.AddNode(new Int3(-1, 0, 2));

        A.AddConnection(B, 1);
        A.AddConnection(C, 1);
        A.AddConnection(F, 1);

        B.AddConnection(C, 1);
        B.AddConnection(A, 1);
        B.AddConnection(E, 1);

        C.AddConnection(A, 1);
        C.AddConnection(B, 1);
        C.AddConnection(E, 1);

        D.AddConnection(E, 1);
        D.AddConnection(F, 1);

        E.AddConnection(D, 1);
        E.AddConnection(C, 1);
        E.AddConnection(B, 1);

        F.AddConnection(A, 1);
        F.AddConnection(D, 1);

    }

    private void FindPath(Vector3 pa, Vector3 pb)
    {
        AstarPath.StartPath(ABPath.Construct(pa, pb, OnPathComplete));
    }

    private void OnPathComplete(Path p)
    {
        _path = p;
    }

Even if set drawGizmos to true I can’t see the graph in the Scene view. So I written my own Gizmos viewer and here is what I get.

As you can see the central node (B) is never found and the bottom node © is very hard to reach, and can’t be reached even if you are on it.
What do I do wrong?

Thanks for your help.

1 Like
2

Hi

Note that Int3s store things using ints, so they are scaled by 1000 (so all your nodes are really close to each other). You can convert a vector3 to an Int3 using an explicit case (Int3)myVector3 and vice versa for the other direction.

Your connections also have too low costs compared to the distances between the nodes. This will break the assumptions by the A* algorithm (namely that the heuristic should be admissible, you can look it up on wikipedia, essentially it says that the cost between two nodes cannot be lower than the distance between those two nodes in Int3 space). If you need arbitrary (non-negative) costs then you can change the A* Inspector -> Settings -> Heuristic to Dijkstra (which is really just disabling the heuristic). This will make the path search slower, but it will work for any costs.

Best regards,
Aron Granberg

3

Hi Aron,
Thanks for your answer.
As I suspected it was a problem of conversion :sweat:
The problem was indeed that I was converting Int3 to Vector3 manually (without using the cast operator provided) so the scales were completely different.

However I can’t find Dijkstra in the list of the Heuristics… But I’ll set the distance between nodes as cost and it’ll work like a charm. Thanks for this great plugin.

4

Ah, sorry. It is just called ‘None’ in the heuristic list.

Great that it works now :slight_smile: