UGTK / Toolkit / Utility Systems / Graph System Completed

Graph System

Summary

The Graph System is a generic, serializable graph data structure (Graph<T>) built from Node<T> and weighted Edge<T>. It offers traversal (BFS / DFS) and pathfinding (Dijkstra and A*), plus grid/strategy helpers like reachable-within-cost and farthest-nodes.

Modules Dependencies

This module has no hard UGTK dependencies (pure C# data structure).

Setup

No scene setup, no component, no prefab: it is a plain C# data structure, so there is nothing to show in a GIF. Instantiate Graph<T> from code and populate it with nodes and edges.

The classes live in the global namespace (Graph<T>, Node<T>, Edge<T>), so no using is needed — but those are very common names: watch out for collisions with other packages.

How To Use

var graph = new Graph<string>();
graph.AddNode("A");
graph.AddNode("B");
graph.AddNode("C");
graph.AddEdge("A", "B", 1);
graph.AddEdge("B", "C", 5);

graph.Bfs("A");                                  // logs the BFS order
graph.DFS("A");                                  // logs the DFS order

List<Node<string>> path = graph.FindShortestPathByDijkstra("A", "C");
List<Node<string>> aStar = graph.AStar("A", "C"); // uses HeuristicCostEstimate (override for a real heuristic)

var reachable = graph.GetReachableNodesWithinCost(graph.GetNodeContainsValue("A"), 3);

For A, subclass Graph<T> and override HeuristicCostEstimate(node1, node2) to provide a real heuristic (the base returns 0, making A behave like Dijkstra). Nodes can be marked non-traversable via Node<T> (BecomeUntraversable() / BecomeTraversable() / IsTraversable()), which A*, reachable and farthest queries respect.

Good to know:

Bfs and DFS only log. They walk the graph and Debug.Log the order — they return nothing. They are inspection tools, not building blocks: for real traversal use the pathfinding methods or write your own walk over GetNodeList().
Out of the box A* == Dijkstra, because the base heuristic returns 0. Overriding HeuristicCostEstimate is not optional if you want the speed-up: on a grid, Manhattan or Euclidean distance between the two node values is the usual choice.
Edges are weighted with int. No fractional costs: scale your costs (×10, ×100) if you need decimals.
Dijkstra ignores traversability, while AStar, GetReachableNodesWithinCost and GetFarthestNodes respect it. If you use non-traversable nodes as walls, use A*, not Dijkstra.
Nodes are matched by value. The T-based overloads look the node up by its value, so T must have sensible equality (a struct, a string, or a class that overrides Equals), and values must be unique.
The structure is undirected: AddEdge(a, b, w) connects both ways.

Testing Scene

Open Debug/GraphSystemScene.unity. It holds one object, GraphSystemTest, carrying Mn_GraphSystemTest. Everything happens in the Inspector: right-click the component header and the seven entries of its context menu appear. No play mode, no wiring.

What to do, in order:

Build Grid — a 5×5 grid of nodes named "x,y", wired to their four neighbours with weight 1. Twenty-five nodes, forty edges.
Find Path Dijkstra and Find Path AStar — both return nine nodes for a cost of 8. On a uniform grid the two agree; A* gets there having visited fewer nodes, which is the whole point of the heuristic.
Find Reachable — every node within Movement Budget steps. With a budget of 3 that is ten nodes, and it is the call a tactics game uses to paint the movement range.
Block Node — closes the node named in Node To Block, 2,0 by default, which sits on the straight path.
Find Path AStar again — the route now goes 0,0 → 1,0 → 1,1 → 2,1 → 3,1 → 4,1 → …, around the closed node, at the same cost of 8. Blocking changes the shape of the graph without rebuilding it.
Unblock Node puts it back.

Two things worth knowing, both visible here. Traversability is a property of the node, not of the edges, so closing a door costs one call and no rebuild. And the search does not check the start node: block the node you are standing on and the path still comes back, because the algorithm starts from it rather than entering it.

Technical Info

Graph\<T>: the graph container — add/remove nodes & edges, search, BFS/DFS, Dijkstra, A*, and utility queries (GetReachableNodesWithinCost, GetFarthestNodes, GetNodeList).
Node\<T>: a graph node holding a value, its edges and a traversable flag.
Edge\<T>: a weighted connection between two nodes.