Skip to content

Game.Simulation.Flow.FluidFlowSolver

Assembly:
{{ Likely the main game assembly (e.g. Game.dll). The source file path is Game\Simulation\Flow\FluidFlowSolver.cs. }}

Namespace:
Game.Simulation.Flow

Type:
public struct FluidFlowSolver

Base:
System.ValueType (struct)

Summary:
{{ FluidFlowSolver is an in-memory, synchronous solver for computing flows through a network of nodes, edges and connections used by the game's fluid simulation. It implements a labeling + push-style flow algorithm (a variant of push-relabel / shortest-path augmenter) using NativeArray data structures and two NativeMinHeap queues: a label (distance) heap and a push (active vertex) heap. The solver operates on low-level graph primitives (Node, Edge, Connection) stored in NativeArray and mutates edge final flows and node excesses. The implementation uses Unity.Assertions (enabled under UNITY_ASSERTIONS) to validate invariants during execution. }}

Fields

  • public int m_SourceNode
    {{ Index of the source node in m_Nodes. This is the origin of flow in the network. Must be a valid index into m_Nodes. }}

  • public int m_SinkNode
    {{ Index of the sink node in m_Nodes. This is the sink/target of flow. Must be a valid index into m_Nodes. }}

  • public NativeArray<Node> m_Nodes
    {{ Array of Node structs representing vertices in the flow network. The solver expects Node to expose fields referenced in the code (m_FirstConnection, m_LastConnection, m_Height, m_Excess, m_Version, m_Distance, m_Predecessor, m_Enqueued). These arrays must be allocated and live for the solver's lifetime. }}

  • public NativeArray<Edge> m_Edges
    {{ Array of Edge structs representing edge data. The solver updates edge.m_FinalFlow and reads capacity via Edge.GetCapacity(backwards). Edge must also provide GetCapacity and be indexed by a Connection. }}

  • public NativeArray<Connection> m_Connections
    {{ Array of Connection structs representing directed endpoint references into edges and nodes. Connection is used to query residual capacities and outgoing/incoming final flows via helper methods: GetOutgoingResidualCapacity, GetIncomingResidualCapacity, GetOutgoingFinalFlow, GetOutgoingResidualCapacity, Reverse(), m_StartNode, m_EndNode, m_Edge, m_Backwards fields. The solver indexes connections by integer index. }}

  • public NativeMinHeap<LabelHeapData> m_LabelQueue
    {{ Min-heap prioritized by distance used by the labeling (multi-source shortest/least-cost) pass. Each entry is LabelHeapData(nodeIndex, distance). Must be initialized/allocated externally and empty before labeling. }}

  • public NativeMinHeap<PushHeapData> m_PushQueue
    {{ Min-heap prioritized by node height used to process active nodes (nodes with positive excess). Each entry is PushHeapData(nodeIndex, height). Must be initialized/allocated externally. }}

  • public bool m_Complete
    {{ Flag indicating whether solve has finished. When true, calling Solve will not progress further until state is reset or solver re-initialized. }}

  • public int m_CurrentVersion
    {{ Monotonic version used to tag nodes during a labeling sweep so the solver can detect stale node data without zeroing everything. Incremented every SolveStep. }}

  • public int m_StepCounter
    {{ Diagnostic counter incremented on Label and Push steps to count processed nodes/operations. Useful for profiling/debugging. }}

Properties

{{ This struct exposes no public C# properties. All state is held in public fields. }}

Constructors

  • public FluidFlowSolver()
    {{ Implicit default struct constructor. Important runtime initialization (e.g. InitializeState) must be called before use. The Native containers (m_Nodes, m_Edges, m_Connections, m_LabelQueue, m_PushQueue) must be assigned/allocated by the caller; the struct does not allocate them. }}

Methods

  • public void InitializeState()
    {{ Initialize solver runtime flags. Sets m_Complete = false and m_CurrentVersion = 0. Call before running Solve/SolveStep on a freshly configured solver. Does not touch arrays. }}

  • public void Preflow()
    {{ Performs a preflow from the sink: iterates connections of the sink node and augments final flows on reverse connections for any positive incoming residual capacity. This seeds node excesses/edge flows so later labeling/push steps can proceed. Used to initialize feasible preflow before normal solve passes. }}

  • public void LoadState(NativeReference<FluidFlowSolverState> solverState)
    {{ Loads minimal persisted solver state (m_Complete, m_CurrentVersion) from a NativeReference wrapper. Useful for pausing/resuming solver progress across frames or jobs. Only these two fields are saved/loaded; the rest of the runtime data must be preserved externally. }}

  • public void SaveState(NativeReference<FluidFlowSolverState> solverState)
    {{ Writes m_Complete and m_CurrentVersion into the provided NativeReference for later restore. }}

  • public void ResetNodes()
    {{ Resets runtime node values by calling the static ResetNodes(NativeArray) on m_Nodes. Sets node heights, excess, version, distance, predecessor and enqueued flags to zero/default. Use when starting fresh without reallocating node array. }}

  • public static void ResetNodes(NativeArray<Node> nodes)
    {{ Static helper that zeroes relevant per-node runtime fields for each node in the provided NativeArray. This avoids reallocation and is cheaper than reconstructing arrays. }}

  • public void ResetFlows()
    {{ Resets edge flow fields by calling static ResetFlows on m_Edges. Sets m_FinalFlow and m_TempFlow to 0 for every edge. }}

  • public static void ResetFlows(NativeArray<Edge> edges)
    {{ Static helper to zero final and temporary flows on all edges. Must be called to clear flows before a new solve if the edges array is reused. }}

  • public void Solve()
    {{ Runs the solver to completion: repeatedly calls SolveStep until m_Complete becomes true. This is a blocking, synchronous loop and may be expensive; use SolveStep for incremental frame-by-frame progression. }}

  • public void SolveStep()
    {{ Performs a single solver iteration: increments m_CurrentVersion, runs the Label() pass to compute distances/heights and populate the push heap, and then runs Push() if the push heap is non-empty. If PushQueue is empty after labeling, the solver sets m_Complete = true. This provides a single logical round of the algorithm and is appropriate for stepping across frames or fixed budgets. }}

  • private void Label()
    {{ Internal method that performs a Dijkstra-like labeling from the source node using m_LabelQueue. It:

  • Asserts that both heaps are empty at start.
  • Initializes the source node (distance = 0, height = 0, version set).
  • Extracts the nearest label repeatedly, relaxes outgoing connections with positive outgoing residual capacity (excluding connections that end at sink), computes a "length" cost via GetLength(connection) and updates node distance, predecessor, height and version.

  • If a node finishes labeling and has positive excess and is not enqueued, it is added to the m_PushQueue. The method updates m_StepCounter and uses m_CurrentVersion to avoid resetting nodes each pass. }}

  • private void Push()
    {{ Internal method processing active nodes from m_PushQueue:

  • Extracts nodes and, if their enqueued flag and height match the heap entry, attempts to push flow along the node's predecessor connection (which should point to a parent on the shortest/label graph).
  • It computes the amount to push (min(node.excess, GetMaxAdditionalOutgoingFlow(connection))) and calls AugmentOutgoingFinalFlow to update edges and node excesses.

  • Nodes to which flow is pushed (the predecessor node) are enqueued into the push queue if they were not already. This implements the actual augmentation/push work after labeling. }}

  • private int GetLength(Connection connection)
    {{ Computes a length/weight for a connection used in the label Dijkstra. The length depends on the outgoing final flow magnitude:

  • If outgoingFinalFlow > 1: 1 + ceil_log2(outgoingFinalFlow)
  • If outgoingFinalFlow < -1: 1 - ceil_log2(-outgoingFinalFlow)

  • Otherwise returns 1. This biases path lengths based on current flow magnitudes to prefer certain augmenting paths. }}

  • private int GetMaxAdditionalOutgoingFlow(Connection connection)
    {{ Computes the maximum additional flow that the connection can carry in terms of algorithmic step sizing. It inspects outgoingFinalFlow and outgoing residual capacity and computes a power-of-two sized ramp (using Mathf.NextPowerOfTwo) to determine the target threshold, then returns min(threshold - outgoingFinalFlow, outgoingResidualCapacity). This is used to push flow in chunked steps rather than 1-by-1. }}

  • private void AugmentOutgoingFinalFlow(in Connection connection, int flow)
    {{ Performs the actual update of node excesses and edge final flow:

  • Asserts flow >= 0.
  • Adds flow to start node excess, subtracts from end node excess.
  • Updates edge.m_FinalFlow by +/- flow depending on connection.m_Backwards.

  • Asserts that the resulting finalFlow does not exceed forward/backward capacities. This is the low-level atomic update for augmentations. }}

  • private ref Node GetNode(int index)
    {{ Fast ref accessor into m_Nodes via NativeArray.ElementAt(index). Useful for local mutating ref operations on Node entries. }}

  • private ref Edge GetEdge(int index)
    {{ Fast ref accessor into m_Edges via NativeArray.ElementAt(index). }}

  • private Connection GetConnection(int index)
    {{ Returns the Connection value at the given index from m_Connections. Connection is treated as a value type (struct) so returned by value. }}

Usage Example

// High-level example showing initialization and a single SolveStep.
// Make sure NativeArray/NativeMinHeap allocations and lifetimes are handled by the caller.

FluidFlowSolver solver = new FluidFlowSolver();

// m_Nodes, m_Edges, m_Connections, m_LabelQueue, m_PushQueue must be allocated/populated prior to use.
// Example (pseudocode, adapt to real types/allocators):
// solver.m_Nodes = new NativeArray<Node>(nodeCount, Allocator.TempJob);
// solver.m_Edges = new NativeArray<Edge>(edgeCount, Allocator.TempJob);
// solver.m_Connections = new NativeArray<Connection>(connCount, Allocator.TempJob);
// solver.m_LabelQueue = new NativeMinHeap<LabelHeapData>(maxHeapSize, Allocator.TempJob);
// solver.m_PushQueue = new NativeMinHeap<PushHeapData>(maxHeapSize, Allocator.TempJob);

solver.m_SourceNode = sourceIndex;
solver.m_SinkNode = sinkIndex;

// Prepare solver runtime state and clear previous flows / node runtime fields if reusing arrays:
solver.InitializeState();
FluidFlowSolver.ResetFlows(solver.m_Edges);
FluidFlowSolver.ResetNodes(solver.m_Nodes);

// Optionally preflow from sink to seed the network:
solver.Preflow();

// Run either to completion or step-by-step:
solver.SolveStep();
// or
// solver.Solve();

// Optionally persist minimal solver state:
NativeReference<FluidFlowSolverState> stateRef = new NativeReference<FluidFlowSolverState>(Allocator.TempJob);
solver.SaveState(stateRef);
// ... later ...
solver.LoadState(stateRef);

{{ Notes / Caveats: - The solver assumes the caller allocated and populated Node/Edge/Connection arrays and the two min-heaps. It does not allocate or free them. - Node/Edge/Connection definitions are not in this file; they must expose specific fields/methods used here (m_FirstConnection, m_LastConnection, GetOutgoingResidualCapacity, GetIncomingResidualCapacity, GetOutgoingFinalFlow, GetCapacity, m_FinalFlow, m_TempFlow, m_Backwards, Reverse(), etc.). - Assertions (Assert.*) are present and only active when UNITY_ASSERTIONS is defined; they help detect invalid graph states during development. - This solver is synchronous and mutates native arrays directly. If you plan to run in a Unity Job, ensure the native containers and access patterns are job-safe and you respect job schedules and dependencies. - For steady performance, Solver increments m_CurrentVersion each SolveStep to tag nodes instead of clearing entire arrays, reducing per-step zeroing cost. - Use SolveStep when you need to spread work across frames or limit per-frame CPU usage; use Solve to perform a blocking full solve. }}