< Summary

Information
Class: Trailblazer.Pathing.NavigationFlowFieldWork
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Search/Flow/NavigationFlowFieldWork.cs
Line coverage
100%
Covered lines: 436
Uncovered lines: 0
Coverable lines: 436
Total lines: 817
Line coverage: 100%
Branch coverage
100%
Covered branches: 174
Total branches: 174
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.ctor(...)100%1818100%
Advance(...)100%7676100%
Dispose()100%22100%
ReleaseRuntimeState()100%11100%
TryBeginCurrent(...)100%1818100%
ApplyIncoming()100%1818100%
AdvanceTransitionReplay(...)100%1818100%
ResolvePostEnumerationStatus(...)100%22100%
ResolveFinalPublication(...)100%22100%
TryRecordPage(...)100%11100%
TryRecordStateDependencies(...)100%22100%
Finish(...)100%11100%
TryBeginTransitionCount()100%11100%
TryBeginDependencySort()100%22100%
CompareSelectedEdge(...)100%11100%
CreateSelectedEdge(...)100%11100%
SetSelectedEdge(...)100%11100%
TrySeedTargetMedium(...)100%1212100%
CaptureWorldDependency(...)100%22100%
IsWorldCurrent()100%22100%

File(s)

/home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Search/Flow/NavigationFlowFieldWork.cs

#LineLine coverage
 1//=======================================================================
 2// NavigationFlowFieldWork.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024-present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9using FixedMathSharp;
 10using GridForge.Grids;
 11
 12namespace Trailblazer.Pathing;
 13
 14/// <summary>Builds one bounded weighted destination-centric flow-field prefix.</summary>
 15internal sealed class NavigationFlowFieldWork : IDisposable
 16{
 17    private enum Stage : byte
 18    {
 19        Search = 0,
 20        CountTransitions = 1,
 21        ReplayTransitions = 2,
 22        SortDependencies = 3,
 23        CaptureDependencies = 4,
 24        BuildPayload = 5,
 25        SortPayloadNodes = 6,
 26        SortPayloadLookup = 7
 27    }
 28
 29    private NavigationResolvedPathQuery? _query;
 30    private GridWorld? _world;
 31    private NavigationWorldGraph? _graph;
 32    private readonly NavigationFlowFieldWorkspace _workspace;
 33    private readonly NavigationWorkMeter _meter;
 34    private readonly long _maximumPayloadBytes;
 35    private NavigationFlowFieldOpenHeap _heap;
 36    private NavigationIncomingTraversalEdgeEnumerator _incoming;
 37    private NavigationTraversalEdgeEnumerator _replayEdges;
 38    private NavigationDependencySortWork _dependencySort;
 39    private NavigationFlowPayloadSortWork _payloadSort;
 40    private NavigationDependencyStampWork? _dependencyStamp;
 41    private NavigationFlowFieldNode[]? _payloadNodes;
 42    private NavigationTransitionInstruction[]? _payloadTransitionInstructions;
 43    private int[]? _payloadLookup;
 44    private NavigationFlowFieldStatus _resultStatus;
 45    private Stage _stage;
 46    private int _currentSlot;
 47    private int _postNodeOrdinal;
 48    private int _transitionOrdinal;
 49    private readonly ulong _worldChangeSequence;
 50    private bool _hasCurrent;
 51    private bool _replayActive;
 52    private bool _originSettled;
 53    private bool _isComplete;
 54    private bool _requiresWorldStamp;
 55    private Fixed64 _coverageThreshold;
 56
 73657    internal NavigationFlowFieldWork(
 73658        GridWorld world,
 73659        NavigationResolvedPathQuery query,
 73660        NavigationFlowFieldWorkspace workspace,
 73661        long maximumPayloadBytes = long.MaxValue)
 62    {
 73663        SwiftThrowHelper.ThrowIfNull(world, nameof(world));
 73664        SwiftThrowHelper.ThrowIfNull(query, nameof(query));
 73665        SwiftThrowHelper.ThrowIfNull(workspace, nameof(workspace));
 66
 73667        _query = query;
 73668        _world = world;
 73669        _graph = query.Graph;
 73670        _workspace = workspace;
 73671        _workspace.ResetSearch();
 73672        _meter = query.Meter;
 73673        _maximumPayloadBytes = maximumPayloadBytes;
 73674        _worldChangeSequence = query.WorldChangeSequence;
 73675        _requiresWorldStamp = query.RequiresWorldStamp
 73676            || query.StartMedium == TraversalMedium.Gas
 73677            || query.StartMedium == TraversalMedium.Liquid;
 73678        _heap = new NavigationFlowFieldOpenHeap(workspace);
 73679        _resultStatus = NavigationFlowFieldStatus.Success;
 80
 73681        if (!TryRecordPage(query.Start.Node)
 73682            || !TryRecordPage(query.End.Node))
 83        {
 184            Finish(NavigationFlowFieldStatus.CapacityExceeded);
 185            return;
 86        }
 73587        if (!query.Query.AllowTransitions
 73588            && !_graph.AreInSameSurfaceComponent(
 73589                query.Start.Address,
 73590                query.StartMedium,
 73591                query.End.Address,
 73592                query.StartMedium))
 93        {
 194            Finish(NavigationFlowFieldStatus.NoPath);
 195            return;
 96        }
 97
 73498        if (!TrySeedTargetMedium(TraversalMedium.Solid)
 73499            || !TrySeedTargetMedium(TraversalMedium.Gas)
 734100            || !TrySeedTargetMedium(TraversalMedium.Liquid))
 101        {
 5102            Finish(NavigationFlowFieldStatus.CapacityExceeded);
 5103            return;
 104        }
 729105    }
 106
 107    internal NavigationFlowFieldStatus Status { get; private set; }
 108
 109    internal NavigationFlowFieldPayload? Result { get; private set; }
 110
 111    internal NavigationFlowFieldStatus Advance(
 112        int lookupStepLimit,
 113        int nodeStepLimit,
 114        int edgeStepLimit,
 115        int connectionStepLimit)
 116    {
 1227117        SwiftThrowHelper.ThrowIfNegative(lookupStepLimit, nameof(lookupStepLimit));
 1227118        SwiftThrowHelper.ThrowIfNegative(nodeStepLimit, nameof(nodeStepLimit));
 1227119        SwiftThrowHelper.ThrowIfNegative(edgeStepLimit, nameof(edgeStepLimit));
 1227120        SwiftThrowHelper.ThrowIfNegative(connectionStepLimit, nameof(connectionStepLimit));
 1227121        if (Status != NavigationFlowFieldStatus.Pending)
 1122            return Status;
 1226123        int lookupRemaining = lookupStepLimit;
 1226124        int nodeRemaining = nodeStepLimit;
 1226125        int edgeRemaining = edgeStepLimit;
 1226126        int connectionRemaining = connectionStepLimit;
 127
 128        while (true)
 129        {
 37625130            if (!IsWorldCurrent())
 2131                return Finish(NavigationFlowFieldStatus.Stale);
 37623132            if (_stage == Stage.Search)
 133            {
 32599134                if (!_hasCurrent)
 135                {
 4626136                    if (!TryBeginCurrent(ref nodeRemaining))
 389137                        return Status;
 4237138                    if (_stage != Stage.Search)
 139                        continue;
 140                }
 31500141                NavigationTraversalEdgeAdvanceStatus edgeStatus =
 31500142                    _incoming.AdvanceOne(
 31500143                        _meter,
 31500144                        _workspace.EndpointWorkspace.Dependencies,
 31500145                        ref edgeRemaining,
 31500146                        ref connectionRemaining);
 31500147                CaptureWorldDependency(_incoming.RequiresWorldStamp);
 31500148                edgeStatus = ResolvePostEnumerationStatus(
 31500149                    IsWorldCurrent(),
 31500150                    edgeStatus);
 31500151                if (edgeStatus == NavigationTraversalEdgeAdvanceStatus.Pending)
 152                    continue;
 9724153                if (edgeStatus == NavigationTraversalEdgeAdvanceStatus.Complete)
 154                {
 3516155                    _hasCurrent = false;
 3516156                    continue;
 157                }
 6208158                if (edgeStatus == NavigationTraversalEdgeAdvanceStatus.Blocked)
 31159                    return Status;
 6177160                if (edgeStatus != NavigationTraversalEdgeAdvanceStatus.Edge)
 3161                    return Finish(NavigationGuideStatusMapper.ToFlowField(edgeStatus));
 6174162                NavigationFlowFieldStatus applied = ApplyIncoming();
 6174163                if (applied != NavigationFlowFieldStatus.Pending)
 3164                    return applied;
 165                continue;
 166            }
 167
 5024168            if (_stage == Stage.CountTransitions)
 169            {
 4043170                while (_postNodeOrdinal < _workspace.SettledCount
 4043171                    && nodeRemaining > 0)
 172                {
 3318173                    int slot = _workspace.SettledSlots[_postNodeOrdinal++];
 3318174                    if (_workspace.GetRecord(slot).SelectedIsTransition)
 12175                        _transitionOrdinal++;
 3318176                    nodeRemaining--;
 177                }
 725178                if (_postNodeOrdinal < _workspace.SettledCount)
 15179                    return Status;
 710180                _payloadTransitionInstructions = _transitionOrdinal == 0
 710181                    ? Array.Empty<NavigationTransitionInstruction>()
 710182                    : new NavigationTransitionInstruction[_transitionOrdinal];
 710183                _postNodeOrdinal = 0;
 710184                _transitionOrdinal = 0;
 710185                _stage = Stage.ReplayTransitions;
 710186                continue;
 187            }
 188
 4299189            if (_stage == Stage.ReplayTransitions)
 190            {
 722191                NavigationFlowFieldStatus replay = AdvanceTransitionReplay(
 722192                    ref nodeRemaining,
 722193                    ref edgeRemaining,
 722194                    ref connectionRemaining);
 722195                if (replay != NavigationFlowFieldStatus.Pending)
 4196                    return replay;
 718197                if (_stage == Stage.ReplayTransitions)
 13198                    return Status;
 199                continue;
 200            }
 201
 3577202            if (_stage == Stage.SortDependencies)
 203            {
 716204                int lookupBefore = _meter.LookupProbes;
 716205                bool complete = _dependencySort.Advance(_meter, lookupRemaining);
 716206                lookupRemaining -= _meter.LookupProbes - lookupBefore;
 716207                if (!complete)
 208                {
 12209                    return _meter.RemainingLookupProbes == 0
 12210                        ? Finish(NavigationFlowFieldStatus.BudgetExceeded)
 12211                        : Status;
 212                }
 704213                _stage = Stage.CaptureDependencies;
 704214                continue;
 215            }
 216
 2861217            if (_stage == Stage.CaptureDependencies)
 218            {
 707219                _dependencyStamp ??= new NavigationDependencyStampWork(
 707220                    _graph!,
 707221                    _query!.AreaPolicy,
 707222                    _workspace.DependencyComponents,
 707223                    _workspace.DependencyComponentCount,
 707224                    _workspace.DependencyPages,
 707225                    _workspace.DependencyPageCount,
 707226                    _workspace.EndpointWorkspace.Dependencies
 707227                        .HasTransitionDependency);
 707228                int lookupBefore = _meter.LookupProbes;
 707229                bool complete = _dependencyStamp.Advance(_meter, lookupRemaining);
 707230                lookupRemaining -= _meter.LookupProbes - lookupBefore;
 707231                if (!complete)
 232                {
 4233                    return _meter.RemainingLookupProbes == 0
 4234                        ? Finish(NavigationFlowFieldStatus.BudgetExceeded)
 4235                        : Status;
 236                }
 703237                _payloadNodes = new NavigationFlowFieldNode[_workspace.SettledCount];
 703238                _payloadLookup = new int[_workspace.SettledCount];
 703239                _stage = Stage.BuildPayload;
 703240                continue;
 241            }
 242
 2154243            if (_stage == Stage.BuildPayload)
 244            {
 3882245                while (_postNodeOrdinal < _workspace.SettledCount && nodeRemaining > 0)
 246                {
 3174247                    int slot = _workspace.SettledSlots[_postNodeOrdinal];
 3174248                    ref NavigationFlowFieldSearchNode record =
 3174249                        ref _workspace.GetRecord(slot);
 3174250                    _payloadNodes![_postNodeOrdinal] = new NavigationFlowFieldNode(
 3174251                        record.Address,
 3174252                        _workspace.GetNode(slot).Medium,
 3174253                        record.IntegrationCost,
 3174254                        record.SelectedEdge,
 3174255                        record.SelectedIsTransition
 3174256                            ? _transitionOrdinal++
 3174257                            : -1);
 3174258                    _payloadLookup![_postNodeOrdinal] = _postNodeOrdinal;
 3174259                    _postNodeOrdinal++;
 3174260                    nodeRemaining--;
 261                }
 708262                if (_postNodeOrdinal < _workspace.SettledCount)
 5263                    return Status;
 703264                _payloadSort = new NavigationFlowPayloadSortWork(
 703265                    _payloadNodes!,
 703266                    _payloadLookup!,
 703267                    sortNodes: true);
 703268                _stage = Stage.SortPayloadNodes;
 703269                continue;
 270            }
 271
 1446272            if (_stage == Stage.SortPayloadNodes)
 273            {
 724274                int lookupBefore = _meter.LookupProbes;
 724275                bool complete = _payloadSort.Advance(_meter, lookupRemaining);
 724276                lookupRemaining -= _meter.LookupProbes - lookupBefore;
 724277                if (!complete)
 278                {
 23279                    return _meter.RemainingLookupProbes == 0
 23280                        ? Finish(NavigationFlowFieldStatus.BudgetExceeded)
 23281                        : Status;
 282                }
 701283                _payloadSort = new NavigationFlowPayloadSortWork(
 701284                    _payloadNodes!,
 701285                    _payloadLookup!,
 701286                    sortNodes: false);
 701287                _stage = Stage.SortPayloadLookup;
 701288                continue;
 289            }
 290
 722291            int finalLookupBefore = _meter.LookupProbes;
 722292            bool lookupComplete = _payloadSort.Advance(_meter, lookupRemaining);
 722293            lookupRemaining -= _meter.LookupProbes - finalLookupBefore;
 722294            if (!lookupComplete)
 295            {
 22296                return _meter.RemainingLookupProbes == 0
 22297                    ? Finish(NavigationFlowFieldStatus.BudgetExceeded)
 22298                    : Status;
 299            }
 700300            NavigationResolvedPathQuery resolved = _query!;
 700301            Result = new NavigationFlowFieldPayload(
 700302                new NavigationFlowFieldPayloadKey(
 700303                    resolved.Query,
 700304                    resolved.End.Address,
 700305                    resolved.StartMedium,
 700306                    resolved.TargetMedia),
 700307                _payloadNodes!,
 700308                _payloadLookup!,
 700309                _payloadTransitionInstructions!,
 700310                _dependencyStamp!.Result,
 700311                _isComplete,
 700312                _requiresWorldStamp ? _worldChangeSequence : null);
 700313            NavigationFlowFieldPayload? result = Result;
 700314            NavigationFlowFieldStatus resultStatus = ResolveFinalPublication(
 700315                IsWorldCurrent(),
 700316                _resultStatus,
 700317                ref result);
 700318            Result = result;
 700319            return Finish(resultStatus);
 320        }
 321    }
 322
 323    public void Dispose()
 324    {
 737325        NavigationResolvedPathQuery? query = _query;
 737326        _query = null;
 737327        query?.Dispose();
 737328        ReleaseRuntimeState();
 737329    }
 330
 331    private void ReleaseRuntimeState()
 332    {
 1463333        _graph = null;
 1463334        _world = null;
 1463335        _incoming = default;
 1463336        _replayEdges = default;
 1463337        _dependencySort = default;
 1463338        _dependencyStamp = null;
 1463339        _payloadNodes = null;
 1463340        _payloadTransitionInstructions = null;
 1463341        _payloadLookup = null;
 1463342        _payloadSort = default;
 1463343    }
 344
 345    private bool TryBeginCurrent(ref int nodeRemaining)
 346    {
 4626347        if (!_heap.TryPeek(out int nextSlot))
 348        {
 372349            _isComplete = true;
 372350            _resultStatus = _originSettled
 372351                ? NavigationFlowFieldStatus.Success
 372352                : NavigationFlowFieldStatus.NoPath;
 372353            return TryBeginTransitionCount();
 354        }
 4254355        if (_originSettled
 4254356            && _workspace.GetRecord(nextSlot).IntegrationCost > _coverageThreshold)
 357        {
 338358            _isComplete = false;
 338359            _resultStatus = NavigationFlowFieldStatus.Success;
 338360            return TryBeginTransitionCount();
 361        }
 3916362        if (nodeRemaining == 0)
 363        {
 387364            if (_meter.RemainingExpandedNodes == 0)
 1365                Finish(NavigationFlowFieldStatus.BudgetExceeded);
 387366            return false;
 367        }
 3529368        if (!_meter.TryConsumeExpandedNodes(1))
 369        {
 1370            Finish(NavigationFlowFieldStatus.BudgetExceeded);
 1371            return false;
 372        }
 3528373        nodeRemaining--;
 3528374        _currentSlot = _heap.Pop();
 3528375        ref NavigationFlowFieldSearchNode current =
 3528376            ref _workspace.GetRecord(_currentSlot);
 3528377        current.Closed = true;
 3528378        _workspace.SettledSlots[_workspace.SettledCount++] = _currentSlot;
 3528379        NavigationMediumStateRef currentState = _workspace.GetNode(_currentSlot);
 3528380        if (currentState.Equals(new NavigationMediumStateRef(
 3528381                _query!.Start.Node,
 3528382                _query.StartMedium)))
 383        {
 707384            if (!Fixed64.TryAdd(
 707385                    current.IntegrationCost,
 707386                    _query.Query.FlowField.ExtraIntegrationCost,
 707387                    out _coverageThreshold))
 388            {
 1389                Finish(NavigationFlowFieldStatus.CostOverflow);
 1390                return false;
 391            }
 706392            _originSettled = true;
 393        }
 3527394        _incoming = new NavigationIncomingTraversalEdgeEnumerator(
 3527395            _world!,
 3527396            _graph!,
 3527397            currentState,
 3527398            _query.Query.Agent,
 3527399            _query.AreaPolicy,
 3527400            _workspace.RayWorkspace,
 3527401            _query.Query.AllowTransitions);
 3527402        _hasCurrent = true;
 3527403        return true;
 404    }
 405
 406    private NavigationFlowFieldStatus ApplyIncoming()
 407    {
 6174408        NavigationMediumStateRef predecessorState = _incoming.CurrentPredecessor;
 6174409        if (!TryRecordStateDependencies(predecessorState))
 1410            return Finish(NavigationFlowFieldStatus.CapacityExceeded);
 6173411        ref NavigationFlowFieldSearchNode current =
 6173412            ref _workspace.GetRecord(_currentSlot);
 6173413        if (!Fixed64.TryAdd(
 6173414                current.IntegrationCost,
 6173415                _incoming.CurrentCost,
 6173416                out Fixed64 candidate))
 417        {
 1418            return Finish(NavigationFlowFieldStatus.CostOverflow);
 419        }
 6172420        if (!_workspace.TryGetOrAdd(
 6172421                predecessorState,
 6172422                out int predecessorSlot,
 6172423                out bool added))
 424        {
 1425            return Finish(NavigationFlowFieldStatus.CapacityExceeded);
 426        }
 6171427        ref NavigationFlowFieldSearchNode predecessor =
 6171428            ref _workspace.GetRecord(predecessorSlot);
 6171429        if (added)
 430        {
 3181431            _graph!.TryGetNodeAddress(predecessorState.Node, out predecessor.Address);
 3181432            predecessor.IntegrationCost = candidate;
 3181433            SetSelectedEdge(ref predecessor, current.Address, currentState: _workspace.GetNode(_currentSlot));
 3181434            predecessor.HeapIndex = -1;
 3181435            _heap.Push(predecessorSlot);
 3181436            return Status;
 437        }
 2990438        if (predecessor.Closed)
 2849439            return Status;
 141440        if (candidate > predecessor.IntegrationCost)
 106441            return Status;
 35442        if (candidate == predecessor.IntegrationCost)
 443        {
 25444            if (predecessor.SelectedEdge.IsValid
 25445                && CompareSelectedEdge(
 25446                    CreateSelectedEdge(current.Address, _workspace.GetNode(_currentSlot)),
 25447                    predecessor.SelectedEdge) < 0)
 448            {
 8449                SetSelectedEdge(ref predecessor, current.Address, _workspace.GetNode(_currentSlot));
 450            }
 25451            return Status;
 452        }
 10453        predecessor.IntegrationCost = candidate;
 10454        SetSelectedEdge(ref predecessor, current.Address, _workspace.GetNode(_currentSlot));
 10455        _heap.DecreaseKey(predecessorSlot);
 10456        return Status;
 457    }
 458
 459    private NavigationFlowFieldStatus AdvanceTransitionReplay(
 460        ref int nodeRemaining,
 461        ref int edgeRemaining,
 462        ref int connectionRemaining)
 463    {
 4060464        while (_postNodeOrdinal < _workspace.SettledCount)
 465        {
 3352466            int slot = _workspace.SettledSlots[_postNodeOrdinal];
 3352467            ref NavigationFlowFieldSearchNode record = ref _workspace.GetRecord(slot);
 3352468            if (!record.SelectedIsTransition)
 469            {
 3316470                if (nodeRemaining == 0)
 10471                    return Status;
 3306472                nodeRemaining--;
 3306473                _postNodeOrdinal++;
 3306474                continue;
 475            }
 36476            NavigationMediumStateRef source = _workspace.GetNode(slot);
 36477            if (!_replayActive)
 478            {
 13479                if (nodeRemaining == 0)
 1480                    return Status;
 12481                nodeRemaining--;
 12482                _replayEdges = new NavigationTraversalEdgeEnumerator(
 12483                    _world!,
 12484                    _graph!,
 12485                    source,
 12486                    _query!.Query.Agent,
 12487                    _query.AreaPolicy,
 12488                    _workspace.RayWorkspace,
 12489                    allowTransitions: true,
 12490                    emittedSurfaceOrdinal: -1);
 12491                _replayActive = true;
 492            }
 35493            NavigationTraversalEdgeAdvanceStatus status = _replayEdges.AdvanceOne(
 35494                _meter,
 35495                _workspace.EndpointWorkspace.Dependencies,
 35496                ref edgeRemaining,
 35497                ref connectionRemaining);
 35498            CaptureWorldDependency(_replayEdges.RequiresWorldStamp);
 35499            status = ResolvePostEnumerationStatus(IsWorldCurrent(), status);
 35500            if (status == NavigationTraversalEdgeAdvanceStatus.Pending)
 501                continue;
 15502            if (status == NavigationTraversalEdgeAdvanceStatus.Blocked)
 2503                return Status;
 13504            if (status != NavigationTraversalEdgeAdvanceStatus.Edge)
 1505                return Finish(NavigationGuideStatusMapper.ToFlowField(status));
 12506            int selectedOrdinal = record.SelectedEdge.CanonicalOutgoingOrdinal;
 12507            if (_replayEdges.CurrentOrdinal < selectedOrdinal)
 508                continue;
 10509            NavigationMediumStateRef target = _replayEdges.CurrentTarget;
 10510            _payloadTransitionInstructions![_transitionOrdinal++] =
 10511                new NavigationTransitionInstruction(
 10512                    _replayEdges.CurrentTransitionIdentityKind,
 10513                    _replayEdges.CurrentTransitionOwnerMapId,
 10514                    _replayEdges.CurrentTransitionId,
 10515                    _replayEdges.CurrentTransitionType,
 10516                    record.Address,
 10517                    record.SelectedEdge.Target,
 10518                    source.Medium,
 10519                    target.Medium,
 10520                    _replayEdges.CurrentTransitionSourceAction,
 10521                    _replayEdges.CurrentTransitionDestinationAction,
 10522                    _replayEdges.CurrentTransitionHints);
 10523            _replayEdges = default;
 10524            _replayActive = false;
 10525            _postNodeOrdinal++;
 526        }
 708527        _postNodeOrdinal = 0;
 708528        _transitionOrdinal = 0;
 708529        TryBeginDependencySort();
 708530        return Status;
 531    }
 532
 533    internal static NavigationTraversalEdgeAdvanceStatus ResolvePostEnumerationStatus(
 534        bool worldCurrent,
 31551535        NavigationTraversalEdgeAdvanceStatus status) => worldCurrent
 31551536        ? status
 31551537        : NavigationTraversalEdgeAdvanceStatus.Stale;
 538
 539    internal static NavigationFlowFieldStatus ResolveFinalPublication(
 540        bool worldCurrent,
 541        NavigationFlowFieldStatus status,
 542        ref NavigationFlowFieldPayload? payload)
 543    {
 704544        if (worldCurrent)
 702545            return status;
 2546        payload = null;
 2547        return NavigationFlowFieldStatus.Stale;
 548    }
 549
 550    private bool TryRecordPage(NavigationNodeRef node)
 551    {
 1471552        _graph!.TryGetNodeAddress(node, out NavigationCellAddress address);
 1471553        return _workspace.TryRecordPage(
 1471554            address.MapId,
 1471555            node.CellSlot / NavigationSemanticPage.SlotCount);
 556    }
 557
 558    private bool TryRecordStateDependencies(NavigationMediumStateRef state)
 559    {
 6174560        _graph!.TryGetNodeAddress(state.Node, out NavigationCellAddress address);
 6174561        if (!_workspace.TryRecordPage(
 6174562                address.MapId,
 6174563                state.Node.CellSlot / NavigationSemanticPage.SlotCount))
 564        {
 1565            return false;
 566        }
 6173567        _graph.TryGetSurfaceComponent(
 6173568            address,
 6173569            state.Medium,
 6173570            out NavigationSurfaceComponentKey component,
 6173571            out _);
 6173572        return _workspace.TryRecordComponent(component);
 573    }
 574
 575    private NavigationFlowFieldStatus Finish(NavigationFlowFieldStatus status)
 576    {
 726577        Status = status;
 726578        _query!.ReleaseLease();
 726579        ReleaseRuntimeState();
 726580        return Status;
 581    }
 582
 583    private bool TryBeginTransitionCount()
 584    {
 710585        _stage = Stage.CountTransitions;
 710586        return true;
 587    }
 588
 589    private bool TryBeginDependencySort()
 590    {
 708591        long maximumRetainedBytes =
 708592            NavigationFlowFieldPayload.GetMaximumRetainedBytes(
 708593                _workspace.SettledCount,
 708594                _payloadTransitionInstructions!.Length,
 708595                _workspace.DependencyComponentCount,
 708596                _workspace.DependencyPageCount);
 708597        if (maximumRetainedBytes > _maximumPayloadBytes)
 598        {
 3599            Finish(NavigationFlowFieldStatus.CapacityExceeded);
 3600            return false;
 601        }
 705602        _dependencySort = new NavigationDependencySortWork(
 705603            _workspace.DependencyComponents,
 705604            _workspace.DependencyComponentCount,
 705605            _workspace.DependencyPages,
 705606            _workspace.DependencyPageCount);
 705607        _stage = Stage.SortDependencies;
 705608        return true;
 609    }
 610
 611    private static int CompareSelectedEdge(
 612        NavigationSelectedEdgeRef left,
 613        NavigationSelectedEdgeRef right) =>
 24614        left.CanonicalOutgoingOrdinal.CompareTo(right.CanonicalOutgoingOrdinal);
 615
 616    private NavigationSelectedEdgeRef CreateSelectedEdge(
 617        NavigationCellAddress target,
 3223618        NavigationMediumStateRef targetState) => new(
 3223619        target,
 3223620        targetState.Medium,
 3223621        _incoming.CurrentOrdinal);
 622
 623    private void SetSelectedEdge(
 624        ref NavigationFlowFieldSearchNode record,
 625        NavigationCellAddress target,
 626        NavigationMediumStateRef currentState)
 627    {
 3199628        record.SelectedEdge = CreateSelectedEdge(target, currentState);
 3199629        record.SelectedIsTransition =
 3199630            _incoming.CurrentKind == NavigationTraversalEdgeKind.Transition;
 3199631    }
 632
 633    private bool TrySeedTargetMedium(TraversalMedium medium)
 634    {
 2195635        if (medium is TraversalMedium.Gas or TraversalMedium.Liquid)
 636        {
 1461637            if ((_query!.TargetMedia & NavigationCell.ToMedia(medium)) != 0)
 29638                _requiresWorldStamp = true;
 639        }
 2195640        if ((_query!.End.Media & NavigationCell.ToMedia(medium)) == 0)
 1457641            return true;
 738642        _graph!.TryGetSurfaceComponent(
 738643            _query.End.Address,
 738644            medium,
 738645            out NavigationSurfaceComponentKey component,
 738646            out _);
 738647        var state = new NavigationMediumStateRef(_query.End.Node, medium);
 738648        if (!_workspace.TryRecordComponent(component)
 738649            || !_workspace.TryGetOrAdd(state, out int slot, out _))
 650        {
 5651            return false;
 652        }
 733653        ref NavigationFlowFieldSearchNode destination =
 733654            ref _workspace.GetRecord(slot);
 733655        destination.Address = _query.End.Address;
 733656        destination.IntegrationCost = Fixed64.Zero;
 733657        destination.HeapIndex = -1;
 733658        _heap.Push(slot);
 733659        return true;
 660    }
 661
 662    private void CaptureWorldDependency(bool requiresWorldStamp)
 663    {
 31535664        if (requiresWorldStamp)
 769665            _requiresWorldStamp = true;
 31535666    }
 667
 668    private bool IsWorldCurrent() =>
 69860669        !_requiresWorldStamp
 69860670        || _world!.ChangeSequence == _worldChangeSequence;
 671
 672}
 673
 674/// <summary>Canonically heap-sorts flow nodes or lookup ordinals with bounded comparisons.</summary>
 675internal struct NavigationFlowPayloadSortWork
 676{
 677    private enum SiftStage : byte
 678    {
 679        None = 0,
 680        ChooseChild = 1,
 681        CompareRoot = 2
 682    }
 683
 684    private readonly NavigationFlowFieldNode[] _nodes;
 685    private readonly int[] _lookup;
 686    private readonly bool _sortNodes;
 687    private SiftStage _siftStage;
 688    private int _heapSize;
 689    private int _buildIndex;
 690    private int _sortEnd;
 691    private int _siftRoot;
 692    private int _siftCandidate;
 693    private bool _building;
 694
 695    internal NavigationFlowPayloadSortWork(
 696        NavigationFlowFieldNode[] nodes,
 697        int[] lookup,
 698        bool sortNodes)
 699    {
 700        _nodes = nodes;
 701        _lookup = lookup;
 702        _sortNodes = sortNodes;
 703        _siftStage = SiftStage.None;
 704        _heapSize = nodes.Length;
 705        _buildIndex = (nodes.Length / 2) - 1;
 706        _sortEnd = nodes.Length - 1;
 707        _siftRoot = 0;
 708        _siftCandidate = 0;
 709        _building = true;
 710    }
 711
 712    internal bool Advance(NavigationWorkMeter meter, int lookupStepLimit)
 713    {
 714        int remaining = Math.Min(lookupStepLimit, meter.RemainingLookupProbes);
 715        while (true)
 716        {
 717            if (_siftStage == SiftStage.None)
 718            {
 719                if (_building)
 720                {
 721                    if (_buildIndex < 0)
 722                    {
 723                        _building = false;
 724                        continue;
 725                    }
 726                    BeginSift(_buildIndex--);
 727                    continue;
 728                }
 729                if (_sortEnd <= 0)
 730                    return true;
 731                Swap(0, _sortEnd);
 732                _heapSize = _sortEnd--;
 733                BeginSift(0);
 734                continue;
 735            }
 736            if (_siftStage == SiftStage.ChooseChild)
 737            {
 738                int left = checked((_siftRoot * 2) + 1);
 739                if (left >= _heapSize)
 740                {
 741                    _siftStage = SiftStage.None;
 742                    continue;
 743                }
 744                _siftCandidate = left;
 745                int right = left + 1;
 746                if (right < _heapSize)
 747                {
 748                    if (!TryConsumeComparison(meter, ref remaining))
 749                        return false;
 750                    if (Compare(left, right) < 0)
 751                        _siftCandidate = right;
 752                }
 753                _siftStage = SiftStage.CompareRoot;
 754                continue;
 755            }
 756            if (!TryConsumeComparison(meter, ref remaining))
 757                return false;
 758            if (Compare(_siftRoot, _siftCandidate) >= 0)
 759            {
 760                _siftStage = SiftStage.None;
 761                continue;
 762            }
 763            Swap(_siftRoot, _siftCandidate);
 764            _siftRoot = _siftCandidate;
 765            _siftStage = SiftStage.ChooseChild;
 766        }
 767    }
 768
 769    private void BeginSift(int root)
 770    {
 771        _siftRoot = root;
 772        _siftStage = SiftStage.ChooseChild;
 773    }
 774
 775    private int Compare(int left, int right)
 776    {
 777        if (!_sortNodes)
 778        {
 779            NavigationFlowFieldNode lookupLeft = _nodes[_lookup[left]];
 780            NavigationFlowFieldNode lookupRight = _nodes[_lookup[right]];
 781            int lookupComparison = lookupLeft.Address.CompareTo(lookupRight.Address);
 782            return lookupComparison != 0
 783                ? lookupComparison
 784                : ((int)lookupLeft.Medium).CompareTo((int)lookupRight.Medium);
 785        }
 786        NavigationFlowFieldNode leftNode = _nodes[left];
 787        NavigationFlowFieldNode rightNode = _nodes[right];
 788        int comparison = leftNode.IntegrationCost.CompareTo(
 789            rightNode.IntegrationCost);
 790        if (comparison != 0)
 791            return comparison;
 792        comparison = leftNode.Address.CompareTo(rightNode.Address);
 793        return comparison != 0
 794            ? comparison
 795            : ((int)leftNode.Medium).CompareTo((int)rightNode.Medium);
 796    }
 797
 798    private void Swap(int left, int right)
 799    {
 800        if (_sortNodes)
 801        {
 802            (_nodes[left], _nodes[right]) = (_nodes[right], _nodes[left]);
 803            return;
 804        }
 805        (_lookup[left], _lookup[right]) = (_lookup[right], _lookup[left]);
 806    }
 807
 808    private static bool TryConsumeComparison(
 809        NavigationWorkMeter meter,
 810        ref int remaining)
 811    {
 812        if (remaining == 0 || !meter.TryConsumeLookupProbes(1))
 813            return false;
 814        remaining--;
 815        return true;
 816    }
 817}
Generated by: ReportGenerator 5.5.11.0
09/02/2026 - 04:28:06
GitHub | reportgenerator.io

Methods/Properties

.ctor(GridForge.Grids.GridWorld,Trailblazer.Pathing.NavigationResolvedPathQuery,Trailblazer.Pathing.NavigationFlowFieldWorkspace,System.Int64)
Advance(System.Int32,System.Int32,System.Int32,System.Int32)
Dispose()
ReleaseRuntimeState()
TryBeginCurrent(System.Int32&)
ApplyIncoming()
AdvanceTransitionReplay(System.Int32&,System.Int32&,System.Int32&)
ResolvePostEnumerationStatus(System.Boolean,Trailblazer.Pathing.NavigationTraversalEdgeAdvanceStatus)
ResolveFinalPublication(System.Boolean,Trailblazer.Pathing.NavigationFlowFieldStatus,Trailblazer.Pathing.NavigationFlowFieldPayload&)
TryRecordPage(Trailblazer.Pathing.NavigationNodeRef)
TryRecordStateDependencies(Trailblazer.Pathing.NavigationMediumStateRef)
Finish(Trailblazer.Pathing.NavigationFlowFieldStatus)
TryBeginTransitionCount()
TryBeginDependencySort()
CompareSelectedEdge(Trailblazer.Pathing.NavigationSelectedEdgeRef,Trailblazer.Pathing.NavigationSelectedEdgeRef)
CreateSelectedEdge(Trailblazer.Pathing.NavigationCellAddress,Trailblazer.Pathing.NavigationMediumStateRef)
SetSelectedEdge(Trailblazer.Pathing.NavigationFlowFieldSearchNode&,Trailblazer.Pathing.NavigationCellAddress,Trailblazer.Pathing.NavigationMediumStateRef)
TrySeedTargetMedium(Trailblazer.TraversalMedium)
CaptureWorldDependency(System.Boolean)
IsWorldCurrent()