Pathfinding with connected nodes?

Behavior & Navigation Navigation
1

Hi, I’m currently making a game and I would like to implement a pathfinding algorithm into it. I understand the algorithm I intend to use (A* or Dijkstra’s) but I just don’t know how I would implement it into Unity. For instance, how would I check if “Node 1” is connected to “Node 2” but not “Node 4”? How would I implement weighted edges to determine which path is faster? How would I program the AI to not be allowed to skip “Node 3” to get to “Node 4” from “Node 1”. Sorry if this is a nooby question, Cheers.

(Here’s a link to a diagram showing my nodes: Imgur: The magic of the Internet)

2

Well your entire node structure should be abstracted into some data class independent of Graphics (and thus Unity). If you understand A* you should be able to program a pathfinding method that figures out paths in your connected graph. You can then layer on some graphics based on your graph, and how to move GameObjects from node to node.

You’d need some kind of script that can read from the low level data of the graph and display it using Unity onto the screen. You can use A* to get a path and have some kind of function that converts NodeA into worldspace co-ordinates… and you just follow the path that A* returns.

Though this quote:

suggests your actually unclear about how to setup the data for the graph.

Here is some sample code:

public class Node
{
    List<Edge> edges;

    public List<Edge> Edges
    {
        get { return edges; }
    }

    public Node()
    {
        edges = new List<Edge>();
    }

    // Add a node from scratch
    void AddNode(float weight)
    {
        Node node = new Node();
        this.AddNode(node, weight);
    }
    // Add a pre-made node
    void AddNode(Node dest, float weight)
    {
        Edge edge = new Edge(this, dest,weight);
        edges.Add(edge);
        dest.Edges.Add(edge);
    }
}
public class Edge {
    float weight;
    Node A;
    Node B;

    public Edge(Node a, Node b, float weight)
    {
        A = a;
        B = b;
        this.weight = weight;
    }
  
}

That should give you a rough framework to make a connected graph. You can add more methods as you need them to access various things. You could have a Graph class that used this Node and Edge classes to hold all them, with various methods to traverse them or sort them. But this alone is enough to connect all the nodes together with weighted edges between them.