< Summary

Information
Class: Trailblazer.Pathing.NavigationSurfaceComponentBuildWork
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Graph/NavigationSurfaceComponentBuildWork.cs
Line coverage
100%
Covered lines: 305
Uncovered lines: 0
Coverable lines: 305
Total lines: 504
Line coverage: 100%
Branch coverage
100%
Covered branches: 134
Total branches: 134
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%44100%
get_Result()100%11100%
get_RetainedBytes()100%44100%
get_PersistentPageCount()100%22100%
Advance(...)100%5454100%
TryBeginNextComponent(...)100%1212100%
AddNeighbor(...)100%44100%
AdvanceVolumeNode(...)100%1212100%
AddVolumeNeighbor(...)100%22100%
AdvanceIncrementalPreparation(...)100%2222100%
AddDomainRoot(...)100%22100%
BeginSealComponent()100%11100%
AdvanceSealComponent(...)100%1010100%
GetArrayBytes(...)100%22100%
GetStampSetBytes(...)100%22100%
Align8(...)100%11100%
RecordPersistentCopies(...)100%22100%
GetRetainedCopiedPersistentNodes()100%11100%

File(s)

/home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Graph/NavigationSurfaceComponentBuildWork.cs

#LineLine coverage
 1//=======================================================================
 2// NavigationSurfaceComponentBuildWork.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;
 9
 10namespace Trailblazer.Pathing;
 11
 12/// <summary>Builds exact weak surface components with bounded node and edge progress.</summary>
 13internal sealed class NavigationSurfaceComponentBuildWork
 14{
 15    private const int NavigationCellAddressBytes = 24;
 16    private const int MaximumUnmeteredRootProbes = 1_024;
 17
 18    private readonly NavigationWorldGraph _graph;
 19    private readonly NavigationWorldGraph _previousGraph;
 20    private readonly NavigationSurfaceComponentKeySet _affectedKeys;
 21    private readonly NavigationCellAddressSet _seedAddresses;
 22    private readonly NavigationAddressStampSet _visited;
 23    private readonly NavigationAddressStampSet _domain;
 24    private readonly NavigationCellAddress[] _queue;
 25    private readonly NavigationCellAddress[] _rootScratch;
 26    private NavigationPagedSequence<NavigationCellAddress>.Builder? _memberBuilder;
 27    private NavigationSurfaceComponent? _sealingComponent;
 28    private NavigationPagedSequence<NavigationCellAddress>.Enumerator _sealingMembers;
 164729    private NavigationSurfaceComponentIndex _result = NavigationSurfaceComponentIndex.Empty;
 30    private NavigationSurfaceEdgeEnumerator _outgoing;
 31    private NavigationIncomingSurfaceEdgeEnumerator _incoming;
 32    private NavigationAutomaticSeamIndex.EndpointEnumerator _volumeSeams;
 33    private int _queueRead;
 34    private int _queueWrite;
 35    private int _memberCount;
 36    private NavigationCellAddress _representative;
 37    private bool _componentActive;
 38    private bool _nodeActive;
 39    private bool _outgoingComplete;
 40    private int _primaryDirectionOrdinal;
 41    private int _primaryDirectionCount;
 164742    private TraversalMedium _medium = TraversalMedium.Solid;
 164743    private bool _certified = true;
 44    private int _affectedKeyOrdinal;
 45    private NavigationSurfaceComponentKeySet.Enumerator _affectedKeyEnumerator;
 46    private int _seedOrdinal;
 47    private int _rootCount;
 48    private int _rootOrdinal;
 49    private NavigationSurfaceComponent? _removedComponent;
 50    private NavigationPagedSequence<NavigationCellAddress>.Enumerator _removedMembers;
 51    private NavigationCellAddress _pendingRemovedMember;
 52    private bool _hasPendingRemovedMember;
 53    private bool _removedRecord;
 54    private bool _incrementalPreparationComplete;
 55    private int _copiedPersistentNodes;
 56    private long _newComponentPayloadBytes;
 57    private int _newComponentPayloadPages;
 58    private bool _ownsResultRoot;
 59    private bool _sealingRecordAdded;
 60    private bool _hasPendingSealingMember;
 61    private NavigationCellAddress _pendingSealingMember;
 62
 164763    internal NavigationSurfaceComponentBuildWork(
 164764        NavigationWorldGraph graph,
 164765        NavigationWorldGraph previousGraph,
 164766        NavigationSurfaceComponentKeySet affectedKeys,
 164767        NavigationCellAddressSet seedAddresses,
 164768        int affectedAddressCapacity)
 69    {
 164770        SwiftThrowHelper.ThrowIfNull(graph, nameof(graph));
 164771        SwiftThrowHelper.ThrowIfNull(previousGraph, nameof(previousGraph));
 164772        SwiftThrowHelper.ThrowIfNull(affectedKeys, nameof(affectedKeys));
 164773        SwiftThrowHelper.ThrowIfNull(seedAddresses, nameof(seedAddresses));
 164774        _graph = graph;
 164775        _previousGraph = previousGraph;
 164776        _affectedKeys = affectedKeys;
 164777        _affectedKeyEnumerator = affectedKeys.GetEnumerator();
 164778        _seedAddresses = seedAddresses;
 164779        SwiftThrowHelper.ThrowIfArgumentOutOfRange(
 164780            affectedAddressCapacity < seedAddresses.Count,
 164781            affectedAddressCapacity,
 164782            nameof(affectedAddressCapacity));
 164783        int capacity = affectedAddressCapacity;
 164784        int stampCapacity = Math.Max(1, capacity);
 164785        _visited = new NavigationAddressStampSet(stampCapacity);
 164786        _domain = new NavigationAddressStampSet(stampCapacity);
 164787        _queue = capacity == 0
 164788            ? Array.Empty<NavigationCellAddress>()
 164789            : new NavigationCellAddress[capacity];
 164790        _rootScratch = capacity == 0
 164791            ? Array.Empty<NavigationCellAddress>()
 164792            : new NavigationCellAddress[capacity];
 164793        _result = previousGraph.SurfaceComponents;
 164794    }
 95
 96    internal bool IsComplete { get; private set; }
 97
 162298    internal NavigationSurfaceComponentIndex Result => _result;
 99
 8681100    internal long RetainedBytes => checked(
 8681101        152L
 8681102        + GetArrayBytes(_queue.Length, NavigationCellAddressBytes)
 8681103        + GetArrayBytes(_rootScratch.Length, NavigationCellAddressBytes)
 8681104        + GetStampSetBytes(Math.Max(1, _queue.Length))
 8681105        + GetStampSetBytes(Math.Max(1, _queue.Length))
 8681106        + (_memberBuilder?.RetainedBytes ?? 0L)
 8681107        + (_ownsResultRoot ? 64L : 0L)
 8681108        + ((long)GetRetainedCopiedPersistentNodes() * 64L)
 8681109        + _newComponentPayloadBytes);
 110
 8910111    internal int PersistentPageCount => checked(
 8910112        1
 8910113        + (_memberBuilder?.PersistentPageCount ?? 0)
 8910114        + (_ownsResultRoot ? 1 : 0)
 8910115        + GetRetainedCopiedPersistentNodes()
 8910116        + _newComponentPayloadPages);
 117
 118    internal bool Advance(MaintenanceWorkMeter meter)
 119    {
 4052120        SwiftThrowHelper.ThrowIfNull(meter, nameof(meter));
 4052121        if (IsComplete)
 140122            return true;
 123
 3912124        if (!_incrementalPreparationComplete
 3912125            && !AdvanceIncrementalPreparation(meter))
 126        {
 94127            return false;
 128        }
 129
 3818130        int unmeteredRootProbes = 0;
 846687131        while (!IsComplete)
 132        {
 846666133            if (_sealingComponent != null)
 134            {
 2036135                if (!AdvanceSealComponent(meter))
 79136                    return false;
 137                continue;
 138            }
 844630139            if (!_componentActive)
 140            {
 3670141                if (!TryBeginNextComponent(ref unmeteredRootProbes))
 1709142                    return IsComplete;
 143            }
 144
 842921145            if (!_nodeActive)
 146            {
 56419147                if (_queueRead == _queueWrite)
 148                {
 1958149                    BeginSealComponent();
 1958150                    continue;
 151                }
 54461152                if (!meter.TryConsumeComponentNodes(1))
 1490153                    return false;
 52971154                NavigationCellAddress currentAddress = _queue[_queueRead++];
 52971155                _memberBuilder!.Append(currentAddress);
 52971156                _memberCount++;
 52971157                if (_memberCount == 1 || currentAddress.CompareTo(_representative) < 0)
 1972158                    _representative = currentAddress;
 52971159                bool found = _graph.TryGetNodeRef(currentAddress, out NavigationNodeRef current);
 160                System.Diagnostics.Debug.Assert(found);
 52971161                if (_medium != TraversalMedium.Solid)
 162                {
 1192163                    _primaryDirectionOrdinal = 0;
 1192164                    _primaryDirectionCount = _graph.GetPrimaryDirectionCount(current);
 1192165                    _volumeSeams = _graph.AutomaticSeams.GetActiveEndpointEnumerator(
 1192166                        currentAddress);
 1192167                    _nodeActive = true;
 1192168                    continue;
 169                }
 51779170                _outgoing = _graph.EnumerateStructuralSurfaceEdges(current);
 51779171                _incoming = _graph.EnumerateIncomingStructuralSurfaceEdges(current);
 51779172                _outgoingComplete = false;
 51779173                _nodeActive = true;
 174            }
 175
 838281176            if (_medium != TraversalMedium.Solid)
 177            {
 1582178                if (!AdvanceVolumeNode(meter))
 390179                    return false;
 180                continue;
 181            }
 182
 836699183            int remainingEdges = meter.RemainingSurfaceComponentEdges;
 836699184            if (!_outgoingComplete)
 185            {
 323503186                NavigationSurfaceEdgeAdvanceStatus status =
 323503187                    _outgoing.AdvanceOne(meter, ref remainingEdges);
 323503188                if (status == NavigationSurfaceEdgeAdvanceStatus.Blocked)
 47189                    return false;
 323456190                if (status == NavigationSurfaceEdgeAdvanceStatus.Pending)
 191                    continue;
 158574192                if (status == NavigationSurfaceEdgeAdvanceStatus.Edge)
 193                {
 106796194                    NavigationGraphEdge edge = _outgoing.Current;
 106796195                    if (edge.Kind == NavigationGraphEdgeKind.Explicit)
 196                    {
 4366197                        _certified &= edge.ExplicitConnection.IsLowerBoundCertified;
 198                    }
 102430199                    else if (edge.Kind == NavigationGraphEdgeKind.Seam)
 200                    {
 391201                        _certified &= edge.AutomaticSeam.Portal.FaceKind
 391202                            == GridForge.Grids.Topology.VoxelContactFaceKind.Vertical;
 203                    }
 106796204                    AddNeighbor(edge.Target);
 106795205                    continue;
 206                }
 51778207                _outgoingComplete = true;
 208            }
 209
 564974210            NavigationSurfaceEdgeAdvanceStatus incomingStatus =
 564974211                _incoming.AdvanceOne(meter, ref remainingEdges);
 564974212            if (incomingStatus == NavigationSurfaceEdgeAdvanceStatus.Blocked)
 80213                return false;
 564894214            if (incomingStatus == NavigationSurfaceEdgeAdvanceStatus.Pending)
 215                continue;
 158573216            if (incomingStatus == NavigationSurfaceEdgeAdvanceStatus.Edge)
 217            {
 106795218                NavigationIncomingSurfaceEdge edge = _incoming.Current;
 106795219                if (edge.ForwardEdge.Kind == NavigationGraphEdgeKind.Explicit)
 220                {
 4366221                    _certified &= edge.ForwardEdge.ExplicitConnection.IsLowerBoundCertified;
 222                }
 102429223                else if (edge.ForwardEdge.Kind == NavigationGraphEdgeKind.Seam)
 224                {
 391225                    _certified &= edge.ForwardEdge.AutomaticSeam.Portal.FaceKind
 391226                        == GridForge.Grids.Topology.VoxelContactFaceKind.Vertical;
 227                }
 106795228                AddNeighbor(edge.Predecessor);
 106795229                continue;
 230            }
 51778231            _outgoing = default;
 51778232            _incoming = default;
 51778233            _nodeActive = false;
 234        }
 21235        return true;
 236    }
 237
 238    private bool TryBeginNextComponent(ref int unmeteredRootProbes)
 239    {
 3243240        while (true)
 241        {
 164011242            while (_rootOrdinal < _rootCount)
 243            {
 159147244                if (unmeteredRootProbes++ == MaximumUnmeteredRootProbes)
 88245                    return false;
 159059246                NavigationCellAddress address = _rootScratch[_rootOrdinal++];
 159059247                bool exists = _graph.TryGetStructuralMediumStateRef(
 159059248                    address,
 159059249                    _medium,
 159059250                    out _);
 159059251                if (!exists
 159059252                    || _result.TryGet(address, _medium, out _)
 159059253                    || !_visited.Add(address))
 254                {
 255                    continue;
 256                }
 1961257                _queueRead = 0;
 1961258                _queueWrite = 1;
 1961259                _memberCount = 0;
 1961260                _memberBuilder = new NavigationPagedSequence<NavigationCellAddress>.Builder(
 1961261                    NavigationCellAddressBytes);
 1961262                _certified = true;
 1961263                _queue[0] = address;
 1961264                _componentActive = true;
 1961265                return true;
 266            }
 4864267            if (_medium == TraversalMedium.Liquid)
 268            {
 1621269                IsComplete = true;
 1621270                return false;
 271            }
 3243272            _medium++;
 3243273            _visited.Reset();
 3243274            _rootOrdinal = 0;
 3243275            unmeteredRootProbes = 0;
 276        }
 277    }
 278
 279    private void AddNeighbor(NavigationNodeRef neighbor)
 280    {
 213591281        bool found = _graph.TryGetNodeAddress(neighbor, out NavigationCellAddress address);
 282        System.Diagnostics.Debug.Assert(found);
 213591283        if (!_graph.TryGetStructuralMediumStateRef(
 213591284                address,
 213591285                TraversalMedium.Solid,
 213591286                out _)
 213591287            || !_visited.Add(address))
 288        {
 163421289            return;
 290        }
 50170291        SwiftThrowHelper.ThrowIfTrue(
 50170292            !_domain.Contains(address),
 50170293            message: "Surface-component closure omitted a structurally adjacent prior component.");
 50169294        _queue[_queueWrite++] = address;
 50169295    }
 296
 297    private bool AdvanceVolumeNode(MaintenanceWorkMeter meter)
 298    {
 9122299        while (_primaryDirectionOrdinal < _primaryDirectionCount)
 300        {
 7866301            if (!meter.TryConsumeSurfaceComponentEdges(1))
 325302                return false;
 7541303            int ordinal = _primaryDirectionOrdinal++;
 7541304            NavigationCellAddress current = _queue[_queueRead - 1];
 7541305            bool found = _graph.TryGetStructuralMediumStateRef(
 7541306                current,
 7541307                _medium,
 7541308                out NavigationMediumStateRef source);
 309            System.Diagnostics.Debug.Assert(found);
 7541310            if (_graph.TryGetStructuralPrimaryMediumNeighbor(
 7541311                    source,
 7541312                    ordinal,
 7541313                    out NavigationMediumStateRef neighbor))
 314            {
 2819315                found = _graph.TryGetNodeAddress(
 2819316                    neighbor.Node,
 2819317                    out NavigationCellAddress address);
 318                System.Diagnostics.Debug.Assert(found);
 2819319                AddVolumeNeighbor(address);
 320            }
 321        }
 322
 1321323        while (meter.RemainingSurfaceComponentEdges > 0)
 324        {
 1256325            if (!_volumeSeams.MoveNext())
 326            {
 1191327                _volumeSeams = default;
 1191328                _nodeActive = false;
 1191329                return true;
 330            }
 65331            meter.TryConsumeSurfaceComponentEdges(1);
 65332            NavigationCellAddress destination = _volumeSeams.Current.Destination;
 65333            if (_graph.TryGetStructuralMediumStateRef(destination, _medium, out _))
 52334                AddVolumeNeighbor(destination);
 335        }
 65336        return false;
 337    }
 338
 339    private void AddVolumeNeighbor(NavigationCellAddress address)
 340    {
 2871341        if (!_visited.Add(address))
 2028342            return;
 843343        SwiftThrowHelper.ThrowIfTrue(
 843344            !_domain.Contains(address),
 843345            message: "Medium-component closure omitted a positive-face neighbor.");
 842346        _queue[_queueWrite++] = address;
 842347    }
 348
 349    private bool AdvanceIncrementalPreparation(MaintenanceWorkMeter meter)
 350    {
 1942351        while (_affectedKeyOrdinal < _affectedKeys.Count || _removedComponent != null)
 352        {
 221353            if (_removedComponent == null)
 354            {
 203355                bool hasNext = _affectedKeyEnumerator.MoveNext();
 356                System.Diagnostics.Debug.Assert(
 357                    hasNext,
 358                    "The immutable affected-key count matches its enumerator.");
 203359                _affectedKeyOrdinal++;
 203360                NavigationSurfaceComponentKey key = _affectedKeyEnumerator.Current;
 203361                _previousGraph.SurfaceComponents.TryGet(key, out _removedComponent);
 362                System.Diagnostics.Debug.Assert(
 363                    _removedComponent != null,
 364                    "Affected keys originate from the previous component root.");
 203365                _removedMembers = _removedComponent.Members.GetEnumerator();
 203366                _removedRecord = false;
 367            }
 221368            if (!_removedRecord)
 369            {
 209370                if (!meter.TryConsumeDependencyEntries(1))
 7371                    return false;
 202372                _result = _result.RemoveComponentRecord(
 202373                    _removedComponent,
 202374                    out int copiedPersistentNodes);
 202375                RecordPersistentCopies(copiedPersistentNodes);
 202376                _removedRecord = true;
 377            }
 17012378            while (true)
 379            {
 17226380                if (!_hasPendingRemovedMember)
 381                {
 17214382                    if (!_removedMembers.MoveNext())
 383                        break;
 17012384                    _pendingRemovedMember = _removedMembers.Current;
 17012385                    _hasPendingRemovedMember = true;
 386                }
 17024387                if (!meter.TryConsumeDependencyEntries(1))
 12388                    return false;
 17012389                _result = _result.RemoveMembership(
 17012390                    _pendingRemovedMember,
 17012391                    _removedComponent.Key,
 17012392                    out int copiedPersistentNodes);
 17012393                RecordPersistentCopies(copiedPersistentNodes);
 17012394                AddDomainRoot(_pendingRemovedMember);
 17012395                _hasPendingRemovedMember = false;
 396            }
 202397            _removedComponent = null;
 398        }
 42088399        while (_seedOrdinal < _seedAddresses.Count)
 400        {
 40442401            if (!meter.TryConsumeDependencyEntries(1))
 75402                return false;
 40367403            AddDomainRoot(_seedAddresses.GetAt(_seedOrdinal++));
 404        }
 1646405        _incrementalPreparationComplete = true;
 1646406        if (_rootCount == 0)
 21407            IsComplete = true;
 1646408        return true;
 409    }
 410
 411    private void AddDomainRoot(NavigationCellAddress address)
 412    {
 57379413        if (!_domain.Add(address))
 4293414            return;
 53086415        _rootScratch[_rootCount++] = address;
 53086416    }
 417
 418    private void BeginSealComponent()
 419    {
 1958420        NavigationPagedSequence<NavigationCellAddress> sequence = _memberBuilder!.Seal();
 1958421        _memberBuilder = null;
 1958422        var key = new NavigationSurfaceComponentKey(_representative, _medium);
 1958423        _sealingComponent = new NavigationSurfaceComponent(
 1958424            key,
 1958425            _graph.GraphVersion,
 1958426            sequence,
 1958427            _certified);
 1958428        _sealingMembers = sequence.GetEnumerator();
 1958429        _sealingRecordAdded = false;
 1958430        _hasPendingSealingMember = false;
 1958431        _newComponentPayloadBytes = checked(
 1958432            _newComponentPayloadBytes + _sealingComponent.RetainedBytes);
 1958433        _newComponentPayloadPages = checked(
 1958434            _newComponentPayloadPages + _sealingComponent.PersistentPageCount);
 1958435    }
 436
 437    private bool AdvanceSealComponent(MaintenanceWorkMeter meter)
 438    {
 2036439        if (!_sealingRecordAdded)
 440        {
 1973441            if (!meter.TryConsumeDependencyEntries(1))
 15442                return false;
 1958443            _result = _result.AddComponentRecord(
 1958444                _sealingComponent!,
 1958445                out int copiedPersistentNodes);
 1958446            RecordPersistentCopies(copiedPersistentNodes);
 1958447            _sealingRecordAdded = true;
 448        }
 52967449        while (true)
 450        {
 54988451            if (!_hasPendingSealingMember)
 452            {
 54925453                if (!_sealingMembers.MoveNext())
 454                    break;
 52968455                _pendingSealingMember = _sealingMembers.Current;
 52968456                _hasPendingSealingMember = true;
 457            }
 53031458            if (!meter.TryConsumeDependencyEntries(1))
 64459                return false;
 52967460            _result = _result.AddMembership(
 52967461                _pendingSealingMember,
 52967462                _sealingComponent!.Key,
 52967463                out int copiedPersistentNodes);
 52967464            RecordPersistentCopies(copiedPersistentNodes);
 52967465            _hasPendingSealingMember = false;
 466        }
 1957467        _sealingComponent = null;
 1957468        _componentActive = false;
 1957469        _nodeActive = false;
 1957470        _queueRead = 0;
 1957471        _queueWrite = 0;
 1957472        _memberCount = 0;
 1957473        return true;
 474    }
 475
 52086476    private static long GetArrayBytes(int count, int elementBytes) => count == 0
 52086477        ? 0L
 52086478        : Align8(checked(24L + ((long)count * elementBytes)));
 479
 480    private static long GetStampSetBytes(int capacity)
 481    {
 17362482        int tableSize = 1;
 17362483        int required = checked(capacity * 2);
 128996484        while (tableSize < required)
 111634485            tableSize = checked(tableSize * 2);
 17362486        return checked(
 17362487            48L
 17362488            + GetArrayBytes(tableSize, NavigationCellAddressBytes)
 17362489            + GetArrayBytes(tableSize, 8));
 490    }
 491
 52042492    private static long Align8(long value) => checked((value + 7L) & ~7L);
 493
 494    private void RecordPersistentCopies(int count)
 495    {
 72139496        _ownsResultRoot = true;
 72139497        if (count == 0)
 267498            return;
 71872499        _copiedPersistentNodes = checked(_copiedPersistentNodes + count);
 71872500    }
 501
 502    private int GetRetainedCopiedPersistentNodes() =>
 17591503        Math.Min(_copiedPersistentNodes, _result.PersistentMapNodeCount);
 504}
Generated by: ReportGenerator 5.5.11.0
09/02/2026 - 04:28:06
GitHub | reportgenerator.io

Methods/Properties

.ctor(Trailblazer.Pathing.NavigationWorldGraph,Trailblazer.Pathing.NavigationWorldGraph,Trailblazer.Pathing.NavigationSurfaceComponentKeySet,Trailblazer.Pathing.NavigationCellAddressSet,System.Int32)
get_Result()
get_RetainedBytes()
get_PersistentPageCount()
Advance(Trailblazer.Pathing.MaintenanceWorkMeter)
TryBeginNextComponent(System.Int32&)
AddNeighbor(Trailblazer.Pathing.NavigationNodeRef)
AdvanceVolumeNode(Trailblazer.Pathing.MaintenanceWorkMeter)
AddVolumeNeighbor(Trailblazer.Pathing.NavigationCellAddress)
AdvanceIncrementalPreparation(Trailblazer.Pathing.MaintenanceWorkMeter)
AddDomainRoot(Trailblazer.Pathing.NavigationCellAddress)
BeginSealComponent()
AdvanceSealComponent(Trailblazer.Pathing.MaintenanceWorkMeter)
GetArrayBytes(System.Int32,System.Int32)
GetStampSetBytes(System.Int32)
Align8(System.Int64)
RecordPersistentCopies(System.Int32)
GetRetainedCopiedPersistentNodes()