DSGraphExposed

Overview

DSGraphExposed is an Unreal Engine plugin (UE 4.26–5.7) that fills the engine’s missing general-purpose graph data structure by providing a reflection-compatible adjacency-list graph (FGraph) alongside BFS and DFS traversal and shortest-path algorithms, all callable directly from Blueprint. It targets gameplay systems that reason about relationships — AI state machines, quest dependency chains, crafting trees, room streaming priority, and social graphs — where flat arrays or maps cannot model connectivity efficiently.

Key Features

• BFS and DFS traversal — both algorithms return FGraphTraversalResult with visit order, per-node depth levels, and wall-clock execution time
• Shortest-path functions — FindShortestPathBFS (guaranteed optimal for unweighted graphs) and FindShortestPathDFS (exhaustive), each returning path array, edge count, and timing
• Full Blueprint exposure — UGraphBPLibrary wraps all algorithms and graph helpers (Create Empty Graph, Add Edge Directed/Undirected, Has Node, Get Neighbors) under UFUNCTION macros
• Reflection-compatible graph — FGraph uses TMap<int32, FArrayWrapper> to work around UE’s nested-container reflection limitation, making it serializable, replicatable, and editor-inspectable
• UE-native custom containers — TGraphStack<T> and TGraphQueue<T> backed by TArray with FORCEINLINE hot-path methods and front-index offset dequeue (no element shifting)
• GC-friendly value semantics — graph nodes are USTRUCT value types, keeping them off the garbage collector’s scan list and preventing GC pause spikes

Technical Decisions

The core design challenge was making a graph UPROPERTY-compatible: UE’s reflection system cannot handle TMap<int32, TArray<int32>> directly, so the inner array is wrapped in FArrayWrapper (a BlueprintType struct). The Blueprint layer converts between FGraph (with FArrayWrapper) and the raw TMap<int32, TArray<int32>> the template algorithms consume — one conversion at the boundary, zero overhead inside the algorithms. All traversals are iterative rather than recursive to keep stack usage bounded and avoid overflow on large graphs. Explicit template instantiation for int32 in the .cpp file keeps algorithm code out of the header, reducing compile times while leaving the door open for FString or custom node types via one additional instantiation line.