BPF — Best Path Finding

Overview

BPF is an Unreal Engine plugin (UE 4.26–5.7) that provides three production-ready weighted graph shortest-path algorithms — Dijkstra, A*, and Bellman-Ford — fully accessible from both C++ and Blueprints. It targets AI navigation, vehicle simulation, and educational games where players compare algorithm behavior in real time. All three algorithms share a common FPathResult structure that exposes path, cost, nodes visited, edges relaxed, and execution time, enabling direct side-by-side comparison in Blueprint.

Key Features

• Three algorithms in one plugin — Dijkstra (general non-negative weights), A* (spatial heuristic-guided), and Bellman-Ford (negative weights + negative-cycle detection)
• Full Blueprint exposure — UBPF_BlueprintLibrary wraps all algorithms and graph construction helpers under the BPF|Algorithms and BPF|Graph categories
• Shared FPathResult — unified output struct with path array, total cost, nodes visited, edges relaxed, and wall-clock execution time for algorithm comparison
• Cache-friendly priority queue — TBPFPriorityQueue<T> backed by a single contiguous TArray heap with Reserve() pre-allocation and Reset()-based reuse (no per-node allocations)
• Sparse adjacency list — FWeightedGraph uses TMap<int32, FWeightedEdgeArray> for O(V+E) memory vs O(V²) dense matrix
• Cross-version compatibility — BPF_VersionMacros.h abstracts TObjectPtr<> and constexpr availability across UE 4.26–5.7

Technical Decisions

All three algorithms operate on const& adjacency lists — no graph copying occurs at call time. The priority queue uses lazy deletion (duplicate entries discarded on pop) rather than a decrease-key operation, which avoids a secondary index structure at the cost of a bounded number of stale queue entries — acceptable given that the queue never exceeds O(E) entries. Bellman-Ford flattens the adjacency list into a single TArray<FBPFEdgeTuple> before the main relaxation loop, trading one upfront allocation for cache-friendly linear iteration across all V−1 passes. Explicit template instantiation (.cpp file, int32 only) keeps compile times low and binary size minimal while leaving the door open for FName or FGuid node types via one additional instantiation line.