Graph

32 min read

Mutable adjacency list, immutable CSR, and a zero-copy grid adapter, all sharing one interface, so BFS, Dijkstra, topological sort, and component analysis run on any game graph you throw at them.

Summary

A graph is the right structure when the world is best described as a set of items with explicit relationships between them: AI states with allowed transitions, dialogue beats with branching options, quest objectives with prerequisite chains, rooms with shared doors, and so on. Lists, dictionaries, and grids all encode position; only a graph encodes connection. Scylla Core provides three graph representations, a shared interface contract, and a focused algorithms toolkit. The three representations are sufficient for the common shapes of game-graph problems without the overhead of a heavyweight general-purpose graph library.

The representations are:

  • ScyllaAdjacencyListGraph for graphs that mutate at runtime (add/remove nodes and edges).
  • ScyllaCSRGraph (Compressed Sparse Row graph) for graphs built once and queried often, where the CSR layout keeps neighbor data contiguous in memory and makes repeated traversal dramatically faster.
  • ScyllaGridGraphAdapter for treating a ScyllaSquareGrid, ScyllaHexGrid, or ScyllaTriGrid as a graph without duplicating data.

All three implement the same IScyllaReadOnlyGraph interface, so every shipped algorithm runs across all three without modification. The mutable graph additionally implements IScyllaMutableGraph. Each representation comes in three flavors: a non-generic form, a generic <TNodeData> form for attaching managed data to nodes, and a generic <TNodeData, TEdgeData> form for attaching data to both nodes and edges. The non-generic form is the right pick when nodes are pure integers and edges only need a float weight.

Every node carries an integer ID supplied by you and a ScyllaGraphNodeFlags value. The flags bitfield has a dedicated Walkable bit that algorithms honor, and 30 additional Tag0–Tag30 bits that can be used for anything a game needs (terrain type, zone, team, faction, hazard, etc.). Every edge carries a source ID, target ID, and a float weight. Graphs declare structural traits at construction time through the ScyllaGraphProperties bitfield: Directed vs undirected, Weighted vs unweighted, AllowsSelfLoops, AllowsParallelEdges, and Mutable. Algorithms read these flags rather than assuming shape.

The algorithms provided in ScyllaGraphAlgorithms cover the most common needs:

  • BFS (Breadth-First Search) and DFS (Depth-First Search) for visitor-based traversal and reachability.
  • Dijkstra for weighted single-source-single-target shortest paths returning a ScyllaGraphPath.
  • TopologicalSort for ordering a DAG (Directed Acyclic Graph).
  • ConnectedComponents for partitioning an undirected graph into components.
  • StronglyConnectedComponents using Tarjan’s algorithm for the directed equivalent.

A* and other heuristic variants are not part of Core; you write them on top of the IScyllaReadOnlyGraph surface, await the upcoming Scylla AI module, or bring in a third-party package.

Use the graph structures for:

  • AI state machines and behavior trees with explicit transition graphs.
  • Dialogue systems with branching beats and prerequisite gates.
  • Quest dependency graphs and tech trees.
  • Pathfinding on grids (via the grid adapter) and on hand-authored navigation graphs.
  • Dependency analysis: build orders, recipe trees, skill prerequisites.
  • Reachability and connectivity analysis on procedurally generated maps.
  • Any data model where nodes and edges are first-class and need standard graph algorithms.

Features

The features below apply across the three representations except where noted.

  • Three representations. Mutable adjacency list, immutable CSR, and a zero-copy grid adapter. All three implement the same read-only interface, so algorithms are written once and work everywhere.
  • Typed variants for node and edge data. Each representation ships in three flavors: non-generic (integer IDs, float weights only), <TNodeData> (attaches managed data per node), and <TNodeData, TEdgeData> (attaches data per node and per edge). Use the variant that matches your data model; you pay only for what the game actually stores.
  • Allocation-free interface. GetNeighborsNonAlloc(nodeID, Span<ScyllaGraphEdge>), CopyAllNodes(Span<ScyllaGraphNode>), and CopyAllEdges(Span<ScyllaGraphEdge>) accept caller-supplied buffers. The base contract never allocates a list per call.
  • Walkable bit plus 30 user tags. Every node carries a ScyllaGraphNodeFlags value. Bit 0 (Walkable) is honored by algorithms; bits 1-31 (Tag0–Tag30) are yours to assign any game-domain meaning. You can flip the flags at runtime to block or unblock parts of the graph without removing nodes.
  • Property-driven behavior. ScyllaGraphProperties declares whether the graph is Directed, Weighted, Mutable, AllowsSelfLoops, and AllowsParallelEdges. Algorithms inspect the flags rather than assuming shape.
  • Fluent builder. ScyllaAdjacencyListGraph.CreateBuilder() and ScyllaCSRGraph.CreateBuilder() expose Directed/Undirected/Weighted/Unweighted/AllowSelfLoops/AllowParallelEdges/WithCapacity/Synchronized setters. BuildConcrete returns the concrete type; Build returns the interface.
  • CSR bulk build. ScyllaCSRGraph accepts a full node and edge set in the builder and lays out the adjacency in CSR format. The result is read-only, cache-friendly, and significantly faster to query than the equivalent adjacency list.
  • Grid adapter factories. ScyllaGridGraphAdapter.FromSquareGrid, FromHexGrid, and FromTriGrid wrap an IScyllaGrid as a graph with no data duplication. Cell walkability and per-edge cost functions are supplied as optional delegates.
  • Six shipped algorithms. BFS, DFS, Dijkstra, TopologicalSort, ConnectedComponents, StronglyConnectedComponents. All operate on the IScyllaGraph/IScyllaReadOnlyGraph interfaces, so any representation works.
  • Reusable ScyllaGraphPath results. Dijkstra returns a ScyllaGraphPath object with NodeIDs, Length, TotalCost, IsValid, SourceID, and TargetID. The class is poolable: Reset() clears state while preserving capacity below a threshold.
  • Visitor predicate for traversal. BFS and DFS accept an optional Func<int, bool> visitor invoked on each visited node. Returning false early-stops the traversal.
  • Reusable visited buffer. BFS and DFS accept an optional ScyllaBitArray for the visited set, letting you reuse a single bit array across many calls without per-call allocation.
  • Synchronized wrappers. Every mutable graph exposes AsSynchronized(object syncRoot = null) returning a thread-safe wrapper backed by a lock; the builder’s Synchronized setter produces the same wrapper directly.
  • DOTS graph. ScyllaGraphDOTS is a [BurstCompile]-compatible struct graph that uses native containers and can be passed into Burst jobs. The trade-off is a smaller API surface than the managed adjacency list.

Representations

The choice of representation is dictated by mutability, query frequency, and whether the data already lives in a grid. Pick the row that matches your access pattern.

RepresentationMutabilityNotes
ScyllaAdjacencyListGraphMutable (add/remove nodes & edges)Default for graphs that change at runtime: AI transition graphs, dialogue trees during authoring, quest progress, dependency graphs that grow. Per-node neighbor lookup is O(degree); per-node random access is O(1).
ScyllaCSRGraphImmutable after Builder.Build()Default for graphs built once and queried often: baked navigation graphs, pre-computed level connectivity, tech trees loaded from data. CSR layout keeps node neighbors contiguous in memory; iteration is dramatically faster than adjacency-list when traversal is the hot path.
ScyllaGridGraphAdapter<TCoord, TCell>Reflects underlying grid mutationsDefault for pathfinding on a ScyllaSquareGrid, ScyllaHexGrid, or ScyllaTriGrid (see Grid). The adapter is a thin facade; it does not copy the cells. Cell walkability and edge cost are supplied as delegates. Three factory methods produce the right adapter without manual ID/coord mapping.
ScyllaGraphDOTSMutable (within job constraints)Burst-compatible struct graph backed by native containers. The right pick for graph operations inside Burst jobs. Use it when the managed ScyllaAdjacencyListGraph is a bottleneck and DOTS workflows are already part of the codebase.

The <TNodeData> and <TNodeData, TEdgeData> generic variants exist for the adjacency list and CSR representations. The grid adapter does not need them; per-cell data is already held by the underlying grid, and the adapter exposes the grid’s cell type through its <TCoord, TCell> parameters.

Recipes

These recipes cover every public surface in the graph structures. Each one is a self-contained answer to a specific game-development problem, so scan the names and jump to the one that matches what you are building. The first recipe creates the adjacency-list graph that several later recipes reuse, so start there if you are new to the API.

Build a runtime-editable graph for a game system

Problem. You want a graph that grows and shrinks as the game runs: rooms connecting after a door opens, an AI relation forming, a network mesh gaining a peer, dialogue options branching based on player choices. The adjacency list is the right shape for anything that mutates at runtime, and the fluent builder is the entry point. The builder defaults to directed, unweighted, no self-loops, no parallel edges; flip flags explicitly when the game model calls for something different.

Solution.

/* A directed, weighted graph with capacity hint of 32 nodes.
 * The right setup for a quest dependency graph or an AI state transition table. */
var graph = ScyllaAdjacencyListGraph.CreateBuilder()
    .Directed()                /* Default; included for clarity.                        */
    .Weighted()                /* Edge weights are stored and surfaced by algorithms.  */
    .WithCapacity(32)          /* Pre-allocate node storage; reduces reallocations.    */
    .Build();                  /* Returns IScyllaMutableGraph for interface coding.    */

/* Or build the concrete type when calling code needs the AsSynchronized helper.
 * Undirected/unweighted is the natural shape for a room-connectivity graph
 * where doors go both ways and the cost of crossing a threshold is uniform. */
var concrete = ScyllaAdjacencyListGraph.CreateBuilder()
    .Undirected()
    .Unweighted()
    .BuildConcrete();          /* Returns ScyllaAdjacencyListGraph directly. */

/* Positional constructor for callers that prefer it. */
var direct = new ScyllaAdjacencyListGraph(
    isDirected: true,
    isWeighted: true,
    capacity: 32,
    allowsSelfLoops: false,
    allowsParallelEdges: false);

Connect rooms, states, or objectives in the graph

Problem. You have your graph; now you need to populate it. Your node IDs probably already come from somewhere else in the project – a room entity ID, a quest ID, an AI state enum cast to int – and the natural thing is to use those IDs directly rather than remapping them. The graph takes that shape: you supply the ID, and the framework stores it.

Solution.

/* Add three nodes representing rooms in a dungeon.
 * Node IDs are supplied by the caller; the framework does not generate them.
 * Use whatever integer ID the room already has in your data model. */
graph.TryAddNode(nodeID: 0);
graph.TryAddNode(nodeID: 1);
graph.TryAddNode(nodeID: 2);

/* Add weighted directed edges (room connections with travel cost).
 * In a dungeon, this might encode a long corridor vs a shortcut. */
graph.TryAddEdge(fromID: 0, toID: 1, weight: 1.5f);
graph.TryAddEdge(fromID: 1, toID: 2, weight: 2.0f);
graph.TryAddEdge(fromID: 0, toID: 2, weight: 5.0f);

/* Remove an edge when the door gets locked or the path collapses. */
var removed = graph.TryRemoveEdge(fromID: 0, toID: 2);

/* Cheap containment probes - useful as a guard before adding. */
var hasNode = graph.ContainsNode(0);
var hasEdge = graph.ContainsEdge(0, 1);

/* Retrieve a specific edge when you need the weight or data. */
if (graph.TryGetEdge(fromID: 0, toID: 1, out var edge))
{
    Log.Info($"Travel cost: {edge.Weight}", LogCategory.Game);
}

Iterate a node’s connections without allocating

Problem. Almost every graph algorithm boils down to “for each neighbor of this node, do something”, and in a hot path – a pathfinder that runs every frame, a BFS that fans out across hundreds of nodes – allocation per call adds up. You need the neighbor list without a new array every time.

Solution. GetNeighborsNonAlloc(nodeID, Span<ScyllaGraphEdge>) writes outgoing edges into a caller-supplied span and returns how many were written. A return of -1 means the node ID is not in the graph; 0 means the node exists with no outgoing edges. Size the span to the maximum expected degree and reuse it across calls.

/* Allocate the span once at the largest expected degree.
 * Stack-allocating here avoids any heap pressure in the traversal loop. */
Span<ScyllaGraphEdge> outgoing = stackalloc ScyllaGraphEdge[16];

var count = graph.GetNeighborsNonAlloc(nodeID: 0, destination: outgoing);

if (count < 0)
{
    Log.Warning("Node 0 not in graph", LogCategory.Game);
}
else
{
    for (var i = 0; i < count; i++)
    {
        var edge = outgoing[i];
        ProcessConnection(edge.FromID, edge.ToID, edge.Weight);
    }
}

/* For typed edge graphs, use the typed Span<ScyllaGraphEdge<TEdgeData>> overload
   to receive per-edge data (e.g. door type, terrain modifier) alongside the descriptor. */

Block and tag nodes at runtime without rebuilding the graph

Problem. Say you need to skip a node dynamically during a graph search – a locked door, an enemy-controlled tile, a quest-gated area – without removing it and losing all its incident edges. You also want to tag nodes with game-domain metadata (burning, guarded, quest target) without a parallel data structure.

Solution. Every node has a ScyllaGraphNodeFlags value, a 32-bit bitfield with Walkable at bit 0 and Tag0–Tag30 at bits 1-31. Algorithms honor the Walkable bit when traversing; the tag bits are yours to use for any application meaning.

/* Block a node from graph algorithms by clearing its Walkable bit.
 * This is reversible at zero cost; no edges are touched. */
if (graph.TryGetNodeFlags(nodeID: 5, out var flags))
{
    var blocked = flags & ~ScyllaGraphNodeFlags.Walkable;
    graph.TrySetNodeFlags(nodeID: 5, flags: blocked);
}

/* Attach a user tag. Tag0..Tag30 are free for any game-domain meaning.
 * Here: Tag3 marks a node as a fire-damage zone. */
graph.TrySetNodeFlags(
    nodeID: 5,
    flags: ScyllaGraphNodeFlags.Walkable | ScyllaGraphNodeFlags.Tag3);

/* Test whether the tag is present before applying the hazard effect. */
if (graph.TryGetNodeFlags(5, out var f) && (f & ScyllaGraphNodeFlags.Tag3) != 0)
{
    ApplyFireDamage();
}

/* Strip all tags while preserving the Walkable bit - useful when a status
 * effect wears off and you want to reset the node cleanly. */
if (graph.TryGetNodeFlags(5, out var current))
{
    graph.TrySetNodeFlags(5, current & ~ScyllaGraphNodeFlags.TagMask);
}

Snapshot the whole graph for serialization or debug visualization

Problem. There’s always a debug visualizer, a save-file writer, or a testing utility that needs the entire graph at once, not one node at a time. You want to pull every node and edge into flat arrays without allocating temporary collections inside the graph.

Solution. CopyAllNodes(Span<ScyllaGraphNode>) and CopyAllEdges(Span<ScyllaGraphEdge>) write the entire node or edge set into caller-supplied spans without allocating. These are the right primitives for serialization, debug dumps, and bulk transforms.

/* Take a snapshot of the entire graph - the natural shape for a save-file writer
 * or for a runtime visualization overlay that draws edges as lines in the world. */
var nodes = new ScyllaGraphNode[graph.NodeCount];
var edges = new ScyllaGraphEdge[graph.EdgeCount];

var nodeCount = graph.CopyAllNodes(nodes);
var edgeCount = graph.CopyAllEdges(edges);

for (var i = 0; i < nodeCount; i++)
{
    var node = nodes[i];
    SerializeNode(node.ID, node.Flags);
}

for (var i = 0; i < edgeCount; i++)
{
    var edge = edges[i];
    SerializeEdge(edge.FromID, edge.ToID, edge.Weight);
}

Bake a navigation graph for fast repeated pathfinding queries

Problem. Your game bakes its navigation graph once at level load – maybe from authored waypoints, maybe from a Voronoi partition of the level – and then runs hundreds or thousands of pathfinding queries against it every second. The graph never changes between bakes. What you need is a representation optimized for query speed, not for mutation.

Solution. A CSR graph is the right pick for that. You supply the full node and edge set to the builder, then Build() produces a packed, immutable representation with O(1) neighbor iteration and excellent cache locality. The same algorithms that run on the adjacency list run on the CSR graph without any changes.

/* Build a baked navigation graph from authored waypoints.
 * Add all nodes and edges through the builder, then Build() once. */
var navGraph = ScyllaCSRGraph.CreateBuilder()
    .Directed()
    .Weighted()
    .AddNode(0)
    .AddNode(1, flags: ScyllaGraphNodeFlags.Walkable)
    .AddNode(2)
    .AddNode(3)
    .AddEdge(fromID: 0, toID: 1, weight: 1.0f)
    .AddEdge(fromID: 0, toID: 2, weight: 2.5f)
    .AddEdge(fromID: 1, toID: 3, weight: 1.0f)
    .AddEdge(fromID: 2, toID: 3, weight: 0.5f)
    .Build();

/* The same algorithms that work on the adjacency list work here unchanged. */
var path = ScyllaGraphAlgorithms.Dijkstra(navGraph, sourceID: 0, targetID: 3);

/* You can also snapshot an existing mutable graph into CSR once the construction
 * phase is done - bake the runtime-built graph into a fast query structure. */
var snapshot = ScyllaCSRGraph.CreateFromGraph(graph);

Run graph algorithms on an existing tile grid

Problem. Your game’s level data already lives in a tile grid – a ScyllaSquareGrid holding terrain types, a hex map carrying biome data – and you want to run pathfinding or connectivity analysis on it without duplicating the tile data into a separate graph structure.

Solution. The grid adapter wraps your grid as an IScyllaReadOnlyGraph with no data copy. The factory methods handle the coord-to-node-ID mapping automatically; you supply walkability and cost as optional delegates. Every algorithm that runs on a hand-built graph runs on the adapter without modification.

/* A square grid with int cells, where 0 means walkable floor and 1 means wall.
 * This might be your dungeon layout coming in from a ProceduralMapGenerator run. */
var layout = new SquareGridLayout(cellWidth: 1f, cellHeight: 1f);
var dungeon = new ScyllaSquareGrid<int>(width: 32, height: 32, layout: layout);

/* Mark some walls. */
dungeon[new SquareCoord(5, 5)] = 1;
dungeon[new SquareCoord(5, 6)] = 1;

/* Wrap the grid as a graph. The factory handles the coord/ID mapping automatically.
 * The cost function here is uniform; replace it with terrain costs for a tactics game. */
var pathGraph = ScyllaGridGraphAdapter<SquareCoord, int>.FromSquareGrid(
    grid: dungeon,
    isWalkable: cell => cell == 0,
    costFunction: (a, b) => 1f,
    adjacency: SquareAdjacency.VonNeumann);

/* Pathfind with Dijkstra. Node IDs are produced by the factory's coord-to-ID function. */
var startID = pathGraph.CoordToNodeID(new SquareCoord(0, 0));
var goalID  = pathGraph.CoordToNodeID(new SquareCoord(31, 31));
var path    = ScyllaGraphAlgorithms.Dijkstra(pathGraph, sourceID: startID, targetID: goalID);

if (path.IsValid)
{
    /* Walk back through the node IDs to recover the SquareCoord sequence for display. */
    foreach (var nodeID in path.NodeIDs)
    {
        var coord = pathGraph.NodeIDToCoord(nodeID);
        HighlightTile(coord);
    }
}

/* Hex and triangle grids have parallel factories - the same pattern, different grid type. */
var hexAdapter = ScyllaGridGraphAdapter<HexCoord, TerrainType>.FromHexGrid(
    grid: hexMap,
    isWalkable: t => t != TerrainType.Mountain);

var triAdapter = ScyllaGridGraphAdapter<TriCoord, int>.FromTriGrid(
    grid: triMap,
    isWalkable: t => t == 0);

Flood-fill a dungeon region or search for a reachable target

Problem. You want to explore outward from a starting point – flood-filling a connected dungeon region to count tiles, spreading fire or gas across a map, or scanning for the nearest reachable exit without committing to the full Dijkstra cost. BFS (Breadth-First Search) and DFS (Depth-First Search) both cover this; the difference is BFS visits in order of increasing hop count (closest first), while DFS exhausts a branch before backtracking.

Solution. Both algorithms accept an optional visitor predicate; returning false from the visitor stops the traversal early. Both also accept an optional ScyllaBitArray for the visited set so you can reuse a single allocation across many traversal calls.

/* Simple reachability scan. The visitor returns true to keep going. */
var visitedCount = ScyllaGraphAlgorithms.BFS(
    graph: pathGraph,
    sourceID: startID,
    visitor: nodeID =>
    {
        Log.Info($"Reached tile {nodeID}", LogCategory.Game);
        return true;
    });

/* Early-stop BFS when the target is found - the first time BFS reaches a node
 * in an unweighted graph it has already found the shortest hop-count path. */
var found = false;
ScyllaGraphAlgorithms.BFS(
    graph: pathGraph,
    sourceID: startID,
    visitor: nodeID =>
    {
        if (nodeID == goalID)
        {
            found = true;
            return false;  /* Stop traversal. */
        }
        return true;
    });

/* DFS with a reusable visited bit array allocated once at startup.
 * Clearing before each call is cheaper than allocating a new array per traversal.
 * This pattern is useful when you run many connectivity checks per frame. */
var visited = new ScyllaBitArray(pathGraph.NodeCount);
visited.Clear();
ScyllaGraphAlgorithms.DFS(
    graph: pathGraph,
    sourceID: startID,
    visited: visited,
    visitor: null);  /* No visitor: just populate the visited set for inspection. */

Find the shortest path for a unit moving across weighted terrain

Problem. “Reachable from here” is not enough when your tactics game needs to find the cheapest route for a soldier crossing mixed terrain – roads cost 1, forests cost 3, rivers cost 5. You want the minimum-total-cost path, not just the minimum hop count.

Solution. Dijkstra runs a single-source, single-target weighted shortest path and returns a ScyllaGraphPath. The path is invalid (and empty) when the target is unreachable. The total cost and ordered node sequence are both on the returned object.

/* Find the cheapest route from room 0 to room 2 in a dungeon where
 * different corridors have different traversal costs. */
var path = ScyllaGraphAlgorithms.Dijkstra(
    graph: graph,
    sourceID: 0,
    targetID: 2);

if (path.IsValid)
{
    Log.Info($"Path cost: {path.TotalCost}", LogCategory.Game);
    Log.Info($"Steps: {path.Length - 1}", LogCategory.Game);

    /* Walk the node sequence to move the unit, highlight tiles, or animate the camera. */
    foreach (var nodeID in path.NodeIDs)
    {
        MoveUnitToNode(nodeID);
    }
}
else
{
    /* Target is unreachable from source, or one of them is not in the graph. */
    Log.Warning("No path found", LogCategory.Game);
}

Compute a tech-tree or quest dependency order

Problem. You need to walk a set of prerequisites in the right order: unlock techs in a strategy game so prerequisites always come before what they enable, sequence tutorial steps so Step 3 only appears after Step 1 and Step 2, load content chunks in the right dependency order at startup. A topological sort on a DAG gives you that sequence.

Solution. TopologicalSort produces a node ordering where every directed edge points from an earlier node to a later one. It works only on directed acyclic graphs and returns false when a cycle exists – which is usually a data authoring error worth reporting clearly.

/* A quest dependency graph: quest 2 requires quest 0; quest 3 requires quests 1 and 2.
 * Directed means the edge "0 -> 2" reads as "quest 0 unlocks quest 2". */
var deps = ScyllaAdjacencyListGraph.CreateBuilder()
    .Directed()
    .Unweighted()
    .Build();

deps.TryAddNode(0);
deps.TryAddNode(1);
deps.TryAddNode(2);
deps.TryAddNode(3);

deps.TryAddEdge(0, 2);     /* quest 0 unlocks quest 2 */
deps.TryAddEdge(1, 3);     /* quest 1 unlocks quest 3 */
deps.TryAddEdge(2, 3);     /* quest 2 unlocks quest 3 */

if (ScyllaGraphAlgorithms.TopologicalSort(deps, out var order))
{
    /* order is something like [0, 1, 2, 3] or [1, 0, 2, 3].
     * Any valid topological ordering satisfies the prerequisites. */
    foreach (var questID in order)
    {
        UnlockQuest(questID);
    }
}
else
{
    /* A cycle was detected; the data has a circular dependency.
     * Surface this at level-load or tool time, not silently at runtime. */
    Log.Error("Quest graph has a cycle - check authoring data", LogCategory.Game);
}

Detect isolated dungeon regions or mutually-locked AI state cycles

Problem. Two related but different questions come up when you’re analyzing graph structure. For an undirected connectivity question – “are these two rooms actually connected after the dungeon generator ran?” or “how many isolated islands are there in this level?” – you need connected components. For a directed cycle question – “which AI states form a loop where the agent can stay forever?” or “which crafting recipes form a dependency loop?” – you need strongly connected components (SCCs), where every node in the component can reach every other.

Solution. ConnectedComponents partitions an undirected graph into disjoint groups and returns a ScyllaDisjointSet plus a node-ID-to-index map. StronglyConnectedComponents is the directed equivalent using Tarjan’s algorithm (a depth-first search approach that finds all nodes mutually reachable from each other), writing the per-node component assignment into a ScyllaMap<int, int>.

/* Undirected connectivity: count disconnected regions after dungeon generation.
 * A result of 1 means the whole dungeon is reachable from any room. */
var components = ScyllaGraphAlgorithms.ConnectedComponents(
    graph: pathGraph,
    out var nodeIDMapping);

var regionCount = components.SetCount;
Log.Info($"Dungeon has {regionCount} disconnected region(s)", LogCategory.Game);

/* Directed strong connectivity: which AI states form mutual transition cycles?
 * A large SCC in a behavior graph means the agent can cycle those states indefinitely. */
var sccCount = ScyllaGraphAlgorithms.StronglyConnectedComponents(
    graph: aiTransitions,
    out var componentIDs);

foreach (var entry in componentIDs)
{
    Log.Info($"AI state {entry.Key} is in SCC {entry.Value}", LogCategory.Game);
}

Attach room or door data directly to graph nodes and edges

Problem. Your room graph is growing and you keep a parallel Dictionary<int, Room> next to the graph to look up room objects by node ID. It works, but every add and remove needs to happen in both places, and serialization touches two structures instead of one. The typed graph variants solve this by carrying payload data directly.

Solution. The <TNodeData> variant attaches a typed object to each node; the <TNodeData, TEdgeData> variant also attaches data to each edge. The API mirrors the non-generic surface and adds TryGetNodeData/TrySetNodeData plus, for edge-typed graphs, TryGetEdgeData/TrySetEdgeData and a typed GetNeighborsNonAlloc overload.

/* Per-node data: store a Room object with each node.
 * Insertion, removal, and lookup are all on one structure. */
var roomGraph = new ScyllaAdjacencyListGraph<string>(
    isDirected: false,
    isWeighted: false);

roomGraph.TryAddNode(nodeID: 0, data: "Foyer");
roomGraph.TryAddNode(nodeID: 1, data: "Library");
roomGraph.TryAddNode(nodeID: 2, data: "Cellar");

roomGraph.TryAddEdge(0, 1);
roomGraph.TryAddEdge(1, 2);

if (roomGraph.TryGetNodeData(1, out var roomName))
{
    Log.Info($"Node 1 is the {roomName}", LogCategory.Game);
}

/* Per-edge data: store a DoorType on each edge.
 * The pathfinder can now check whether a door is locked before traversing. */
public enum DoorType { Open, Locked, Hidden }

var doorGraph = new ScyllaAdjacencyListGraph<string, DoorType>(isDirected: false, isWeighted: true);

doorGraph.TryAddNode(0, data: "Foyer");
doorGraph.TryAddNode(1, data: "Library");

doorGraph.TryAddEdge(fromID: 0, toID: 1, weight: 1f, data: DoorType.Locked);

if (doorGraph.TryGetEdgeData(0, 1, out var doorType) && doorType == DoorType.Locked)
{
    Log.Info("Player needs a key for the Library door", LogCategory.Game);
}

Share a graph safely between the main thread and pathfinding jobs

Problem. Your project offloads pathfinding to a background thread to keep the main thread free for rendering, but gameplay code on the main thread occasionally adds or removes edges – doors opening, routes collapsing. Without synchronization, concurrent access corrupts the graph state.

Solution. Adjacency-list graphs expose AsSynchronized(object syncRoot = null), which returns a thread-safe wrapper backed by a lock. The builder’s Synchronized setter produces the same wrapper directly. The wrapper implements IScyllaMutableGraph, so every consumer of the interface continues to work without changes.

/* Wrap an existing graph after the fact. */
var synced = graph.AsSynchronized();

/* Or build with synchronization from the start.
 * The result is IScyllaMutableGraph backed by a SynchronizedScyllaAdjacencyListGraph. */
var shared = ScyllaAdjacencyListGraph.CreateBuilder()
    .Directed()
    .Weighted()
    .Synchronized()
    .Build();

API Sketch

The public surface spans four representations and the algorithms toolkit. Every helper accepts the IScyllaReadOnlyGraph or IScyllaGraph interface, so any representation works without modification.

namespace Scylla.Core.Structures
{
    /* ------------------------------------------------------------------ */
    /* INTERFACES                                                         */
    /* ------------------------------------------------------------------ */

    public interface IScyllaGraph : IScyllaCollection
    {
        int NodeCount { get; }
        int EdgeCount { get; }
        ScyllaGraphProperties Properties { get; }
        bool ContainsNode(int nodeID);
        bool ContainsEdge(int fromID, int toID);
        int GetNeighborCount(int nodeID);
        int GetNeighborsNonAlloc(int nodeID, Span<ScyllaGraphEdge> destination);
    }

    public interface IScyllaReadOnlyGraph : IScyllaGraph
    {
        bool TryGetEdge(int fromID, int toID, out ScyllaGraphEdge edge);
        bool TryGetNodeFlags(int nodeID, out ScyllaGraphNodeFlags flags);
        int CopyAllNodes(Span<ScyllaGraphNode> destination);
        int CopyAllEdges(Span<ScyllaGraphEdge> destination);
    }

    public interface IScyllaMutableGraph : IScyllaReadOnlyGraph
    {
        bool TryAddNode(int nodeID, ScyllaGraphNodeFlags flags = ScyllaGraphNodeFlags.Walkable);
        bool TryRemoveNode(int nodeID);
        bool TryAddEdge(int fromID, int toID, float weight = 1.0f);
        bool TryRemoveEdge(int fromID, int toID);
        bool TrySetNodeFlags(int nodeID, ScyllaGraphNodeFlags flags);
        void EnsureCapacity(int minNodeCapacity);
    }

    public interface IScyllaReadOnlyGraph<TNodeData> : IScyllaReadOnlyGraph
    {
        bool TryGetNodeData(int nodeID, out TNodeData data);
    }

    public interface IScyllaReadOnlyGraph<TNodeData, TEdgeData> : IScyllaReadOnlyGraph<TNodeData>
    {
        bool TryGetEdgeData(int fromID, int toID, out TEdgeData data);
        int GetNeighborsNonAlloc(int nodeID, Span<ScyllaGraphEdge<TEdgeData>> destination);
    }

    public interface IScyllaMutableGraph<TNodeData> : IScyllaReadOnlyGraph<TNodeData>, IScyllaMutableGraph
    {
        bool TryAddNode(int nodeID, TNodeData data, ScyllaGraphNodeFlags flags = ScyllaGraphNodeFlags.Walkable);
        bool TrySetNodeData(int nodeID, TNodeData data);
    }

    public interface IScyllaMutableGraph<TNodeData, TEdgeData> : IScyllaReadOnlyGraph<TNodeData, TEdgeData>, IScyllaMutableGraph<TNodeData>
    {
        bool TryAddEdge(int fromID, int toID, float weight, TEdgeData data);
        bool TrySetEdgeData(int fromID, int toID, TEdgeData data);
    }

    /* ------------------------------------------------------------------ */
    /* DESCRIPTORS                                                        */
    /* ------------------------------------------------------------------ */

    public readonly struct ScyllaGraphNode : IEquatable<ScyllaGraphNode>
    {
        public int ID { get; }
        public ScyllaGraphNodeFlags Flags { get; }
    }

    public readonly struct ScyllaGraphEdge : IEquatable<ScyllaGraphEdge>
    {
        public int FromID { get; }
        public int ToID { get; }
        public float Weight { get; }
    }

    public readonly struct ScyllaGraphEdge<TEdgeData> : IEquatable<ScyllaGraphEdge<TEdgeData>>
    {
        public int FromID { get; }
        public int ToID { get; }
        public float Weight { get; }
        public TEdgeData Data { get; }
    }

    [Flags] public enum ScyllaGraphProperties : uint
    {
        None = 0, Directed = 1, Weighted = 2, AllowsSelfLoops = 4, AllowsParallelEdges = 8, Mutable = 16
    }

    [Flags] public enum ScyllaGraphNodeFlags : uint
    {
        None = 0, Walkable = 1u << 0,
        Tag0 = 1u << 1, Tag1 = 1u << 2, /* ... */ Tag30 = 1u << 31,
        TagMask = 0xFFFFFFFEu
    }

    /* ------------------------------------------------------------------ */
    /* ADJACENCY LIST                                                     */
    /* ------------------------------------------------------------------ */

    public sealed class ScyllaAdjacencyListGraph : IScyllaMutableGraph
    {
        public ScyllaAdjacencyListGraph(
            bool isDirected = true,
            bool isWeighted = false,
            int capacity = 16,
            bool allowsSelfLoops = false,
            bool allowsParallelEdges = false);

        /* IScyllaMutableGraph surface inherited (ContainsNode, TryAddNode, TryAddEdge, etc.) */

        public void Clear();
        public SynchronizedScyllaAdjacencyListGraph AsSynchronized(object syncRoot = null);
        public NodeEnumerator GetEnumerator();
        public static Builder CreateBuilder();
    }

    public sealed class ScyllaAdjacencyListGraph<TNodeData> : IScyllaMutableGraph<TNodeData> { /* + TryGetNodeData, TrySetNodeData, TryAddNode(int, TNodeData, ...) */ }
    public sealed class ScyllaAdjacencyListGraph<TNodeData, TEdgeData> : IScyllaMutableGraph<TNodeData, TEdgeData> { /* + per-edge data API */ }

    /* ------------------------------------------------------------------ */
    /* CSR                                                                */
    /* ------------------------------------------------------------------ */

    public sealed class ScyllaCSRGraph : IScyllaReadOnlyGraph
    {
        public static ScyllaCSRGraph CreateFromGraph(IScyllaReadOnlyGraph source);
        public static Builder CreateBuilder();
        public void Clear();
        /* IScyllaReadOnlyGraph surface inherited */
    }

    public sealed class ScyllaCSRGraph<TNodeData> : IScyllaReadOnlyGraph<TNodeData> { /* + typed node data */ }
    public sealed class ScyllaCSRGraph<TNodeData, TEdgeData> : IScyllaReadOnlyGraph<TNodeData, TEdgeData> { /* + typed node + edge data */ }

    /* ------------------------------------------------------------------ */
    /* GRID ADAPTER                                                       */
    /* ------------------------------------------------------------------ */

    public sealed class ScyllaGridGraphAdapter<TCoord, TCell> : IScyllaReadOnlyGraph
    {
        public ScyllaGridGraphAdapter(
            IScyllaGrid<TCoord, TCell> grid,
            Func<TCoord, int> coordToNodeID,
            Func<int, TCoord> nodeIDToCoord,
            Func<TCoord, TCoord[], int> getNeighborCoords,
            int maxNeighbors,
            int nodeCount,
            Func<TCell, bool> isWalkable = null,
            Func<TCoord, TCoord, float> costFunction = null);

        public static ScyllaGridGraphAdapter<SquareCoord, TCell> FromSquareGrid(
            ScyllaSquareGrid<TCell> grid,
            Func<TCell, bool> isWalkable = null,
            Func<SquareCoord, SquareCoord, float> costFunction = null,
            SquareAdjacency adjacency = SquareAdjacency.VonNeumann);

        public static ScyllaGridGraphAdapter<HexCoord, TCell> FromHexGrid(
            ScyllaHexGrid<TCell> grid,
            Func<TCell, bool> isWalkable = null,
            Func<HexCoord, HexCoord, float> costFunction = null);

        public static ScyllaGridGraphAdapter<TriCoord, TCell> FromTriGrid(
            ScyllaTriGrid<TCell> grid,
            Func<TCell, bool> isWalkable = null,
            Func<TriCoord, TriCoord, float> costFunction = null);

        /* IScyllaReadOnlyGraph surface inherited.
           CoordToNodeID and NodeIDToCoord delegates are exposed for round-tripping. */
    }

    /* ------------------------------------------------------------------ */
    /* DOTS                                                               */
    /* ------------------------------------------------------------------ */

    [BurstCompile]
    public struct ScyllaGraphDOTS : IDisposable
    {
        /* Burst-compatible struct graph with NativeContainer storage.
           Provides node/edge add, remove, neighbor iteration, and a fluent Builder.
           Use for graph operations inside Burst jobs. */
        public sealed class Builder { /* ... */ }
    }

    /* ------------------------------------------------------------------ */
    /* PATH RESULT                                                        */
    /* ------------------------------------------------------------------ */

    public sealed class ScyllaGraphPath
    {
        public IReadOnlyList<int> NodeIDs { get; }
        public int Length { get; }
        public float TotalCost { get; }
        public bool IsValid { get; }
        public int SourceID { get; }
        public int TargetID { get; }

        public ScyllaGraphPath();
        public ScyllaGraphPath(int capacity);
        public static ScyllaGraphPath CreateInvalid();
        public static ScyllaGraphPath CreateFromNodes(IList<int> nodeIDs, float totalCost);
        public void Reset();
        /* Mutation methods for algorithm authors. */
    }

    /* ------------------------------------------------------------------ */
    /* ALGORITHMS                                                         */
    /* ------------------------------------------------------------------ */

    public static class ScyllaGraphAlgorithms
    {
        public static int  BFS(IScyllaGraph graph, int sourceID, Func<int, bool> visitor = null);
        public static int  BFS(IScyllaGraph graph, int sourceID, ScyllaBitArray visited, Func<int, bool> visitor = null);
        public static int  DFS(IScyllaGraph graph, int sourceID, Func<int, bool> visitor = null);
        public static int  DFS(IScyllaGraph graph, int sourceID, ScyllaBitArray visited, Func<int, bool> visitor = null);
        public static ScyllaGraphPath Dijkstra(IScyllaGraph graph, int sourceID, int targetID);
        public static bool TopologicalSort(IScyllaGraph graph, out int[] result);
        public static ScyllaDisjointSet ConnectedComponents(IScyllaReadOnlyGraph graph, out ScyllaMap<int, int> nodeIDMapping);
        public static int  StronglyConnectedComponents(IScyllaReadOnlyGraph graph, out ScyllaMap<int, int> componentIDs);
    }
}

See the API reference for full signatures, remarks, and exception contracts on every member.

Properties and flags reference

ScyllaGraphProperties

FlagEffect
NoneUndirected, unweighted, immutable graph that disallows self-loops and parallel edges. Bare-minimum configuration.
DirectedEach edge has a distinct source and target; traversal follows the stored direction only. Absent the flag, edges are undirected and the graph exposes both endpoints.
WeightedEdges carry meaningful Weight values. Absent the flag, all weights are treated as 1.0f regardless of stored value. Required for Dijkstra to produce meaningful results.
AllowsSelfLoopsEdges where FromID == ToID are allowed. Absent the flag, TryAddEdge returns false for such inputs. Use for state machines that can stay in a state, or any model where a node can have a self-cost.
AllowsParallelEdgesMultiple edges between the same (FromID, ToID) are allowed. Absent the flag, the second add for the same pair returns false. Use for multigraphs (multiple independent routes between the same two endpoints).
MutableGraph supports structural mutation via IScyllaMutableGraph. Absent on built CSR graphs.

ScyllaGraphNodeFlags

FlagEffect
NoneNo bits set. Algorithms treat the node as impassable because Walkable is clear.
WalkableBit 0. Algorithms (BFS, DFS, Dijkstra, …) traverse through this node. Clear the bit to dynamically block without removing.
Tag0–Tag30Bits 1-31. Application-defined. The framework never reads or sets these bits; assign any game-domain meaning.
TagMask0xFFFFFFFEu. Bitmask covering all 31 tag bits. Use to test or clear all tags while preserving the Walkable bit.

Adjacency list builder

SetterDefaultEffect
Directed/UndirectedDirectedSets the Directed property flag.
Weighted/UnweightedUnweightedSets the Weighted property flag. Weighted graphs are required for Dijkstra.
AllowSelfLoops(bool)falseSets the AllowsSelfLoops flag.
AllowParallelEdges(bool)falseSets the AllowsParallelEdges flag.
WithCapacity(int)16Pre-allocates node storage. Reduces reallocations during bulk inserts.
Synchronized(object)offWraps the result in SynchronizedScyllaAdjacencyListGraph. Optional syncRoot lets you share the lock with other code.

CSR builder

Same shape as the adjacency-list builder, with additional AddNode(nodeID, flags = Walkable) and AddEdge(fromID, toID, weight = 1.0f) setters for collecting the graph contents inline.

Best Practices

  • Pick the representation by mutation pattern, not by node count. A mutable adjacency list is the right pick whenever the graph changes at runtime, even when small. A CSR graph is the right pick whenever the graph is built once and queried often, even when large. The grid adapter is the right pick whenever the data already lives in a ScyllaSquareGrid, ScyllaHexGrid, or ScyllaTriGrid.
  • Reach for IScyllaReadOnlyGraph in algorithm code. Every shipped algorithm accepts the interface, and code written against it works on all three representations without modification. Concrete dependencies belong in the level loader and the renderer.
  • Use BFS for unweighted shortest path, Dijkstra for weighted. BFS in O(V + E) outperforms Dijkstra in O((V + E) log V) when all edges have the same cost, and the result is identical.
  • Block nodes by clearing Walkable, not by removing them. A removed node loses all incident edges and forces a rebuild when the block is lifted. Clearing the Walkable flag is reversible at zero cost.
  • Document the meaning of each TagN bit at the top of the consuming module. The framework treats tag bits as opaque; your project owns the meaning. A comment like // Tag3 = burning, Tag4 = guarded, Tag5 = quest target at the head of the AI code is the only canonical mapping.
  • Pre-allocate the neighbor span at the worst-case degree. GetNeighborsNonAlloc silently truncates when the span is too short, so size for the maximum expected out-degree at the call site and reuse across calls.
  • Reuse the visited bit array across BFS/DFS calls. The two-argument overloads of BFS and DFS accept a ScyllaBitArray. Allocate once at startup, Clear per call, and pay no per-traversal allocation cost.
  • Build CSR graphs from data, not from runtime mutation. The point of CSR is the bake step; if the graph changes often enough that rebuilding is a hot path, switch back to the adjacency list.
  • Reach for the grid adapter factories first. FromSquareGrid, FromHexGrid, and FromTriGrid set up coord-to-ID and neighbor delegates automatically. The eight-argument constructor exists for cases where the factory’s defaults are wrong, and those cases are rare.
  • Hold SyncRoot for compound operations. The synchronized wrapper protects each call but not sequences. lock (shared.SyncRoot) { ... } is the only safe pattern when a transaction touches more than one method on the same graph.
  • Treat ScyllaGraphPath as poolable. The class exposes Reset() and a capacity constructor. For projects that issue Dijkstra calls every frame, allocate a single path object and reset it between calls rather than churning the GC.
  • Validate algorithm preconditions explicitly. Dijkstra wants non-negative weights; topological sort wants a DAG. Neither validates at the boundary; your calling code is responsible for checking the data before invoking the algorithm.

Pitfalls

Updated on July 9, 2026