< Summary

Information
Class: Trailblazer.Pathing.SolidPartitionReachability
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Search/Reachability/SolidPartitionReachability.cs
Line coverage
95%
Covered lines: 182
Uncovered lines: 9
Coverable lines: 191
Total lines: 480
Line coverage: 95.2%
Branch coverage
82%
Covered branches: 123
Total branches: 150
Branch coverage: 82%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
get_State()100%11100%
get__lock()100%11100%
get__passablePartitions()100%11100%
get__componentRoots()100%11100%
get__componentQueue()100%11100%
get__activeSnapshotKey()100%11100%
set__activeSnapshotKey(...)100%11100%
get__hasActiveSnapshot()100%11100%
set__hasActiveSnapshot(...)100%11100%
get__activeSnapshotId()100%11100%
set__activeSnapshotId(...)100%11100%
get__activeSnapshotVersion()100%11100%
set__activeSnapshotVersion(...)100%11100%
get__snapshotBuildCount()100%11100%
set__snapshotBuildCount(...)100%11100%
get__version()100%11100%
set__version(...)100%210%
Invalidate()100%11100%
Invalidate(...)100%22100%
CaptureStats()100%11100%
IsProvablyUnreachable(...)66.66%2424100%
IsProvablyUnreachable(...)50%14855.55%
EnsureSnapshot(...)100%66100%
GetNextSnapshotId(...)50%22100%
BuildSnapshot(...)100%2424100%
AssignComponents(...)86.36%2222100%
HasReachableNeighborInComponent(...)100%1212100%
CanTraverse(...)66.66%6685.71%
CanTraverseFromMarkedStart(...)83.33%66100%
HasValidDiagonalLegs(...)83.33%121287.5%
HasValidDiagonalLegsFromMarkedStart(...)83.33%141275%
IsLegClear(...)75%44100%
IsMarkedLegClear(...)50%66100%
ContainsDirection(...)100%44100%
.ctor(...)100%11100%

File(s)

/home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Search/Reachability/SolidPartitionReachability.cs

#LineLine coverage
 1using FixedMathSharp;
 2using GridForge.Grids;
 3using GridForge.Spatial;
 4using SwiftCollections;
 5using System;
 6
 7namespace Trailblazer.Pathing;
 8
 9/// <summary>
 10/// Default-context facade for conservative solid-partition connectivity snapshots used for fast unreachable-route rejec
 11/// </summary>
 12internal static class SolidPartitionReachability
 13{
 1010814    private static SolidPartitionReachabilityState State => PathManager.ActiveState.ReachabilityState;
 15
 115316    private static object _lock => State.Lock;
 17
 18    private static SwiftDictionary<WorldVoxelIndex, SolidChartPartition> _passablePartitions =>
 80419        State.PassablePartitions;
 20
 49321    private static SwiftList<SolidChartPartition> _componentRoots => State.ComponentRoots;
 22
 18223    private static SwiftQueue<SolidChartPartition> _componentQueue => State.ComponentQueue;
 24
 25    private static ReachabilitySnapshotKey _activeSnapshotKey
 26    {
 108927        get => State.ActiveSnapshotKey;
 5828        set => State.ActiveSnapshotKey = value;
 29    }
 30
 31    private static bool _hasActiveSnapshot
 32    {
 115333        get => State.HasActiveSnapshot;
 5834        set => State.HasActiveSnapshot = value;
 35    }
 36
 37    private static int _activeSnapshotId
 38    {
 126139        get => State.ActiveSnapshotId;
 5840        set => State.ActiveSnapshotId = value;
 41    }
 42
 43    private static int _activeSnapshotVersion
 44    {
 114545        get => State.ActiveSnapshotVersion;
 11646        set => State.ActiveSnapshotVersion = value;
 47    }
 48
 49    private static long _snapshotBuildCount
 50    {
 6651        get => State.SnapshotBuildCount;
 5852        set => State.SnapshotBuildCount = value;
 53    }
 54
 55    private static int _version
 56    {
 241457        get => State.Version;
 058        set => State.Version = value;
 59    }
 60
 61    /// <summary>
 62    /// Clears cached connectivity snapshots after live solid topology changes.
 63    /// </summary>
 447064    internal static void Invalidate() => Invalidate(PathManager.ActiveState);
 65
 66    /// <summary>
 67    /// Clears cached connectivity snapshots on an explicit pathing state after live solid topology changes.
 68    /// </summary>
 69    internal static void Invalidate(PathingWorldState state)
 70    {
 447871        if (state == null)
 172            throw new ArgumentNullException(nameof(state));
 73
 447774        SolidPartitionReachabilityState reachabilityState = state.ReachabilityState;
 447775        lock (reachabilityState.Lock)
 76        {
 447777            unchecked { reachabilityState.Version++; }
 447778            reachabilityState.HasActiveSnapshot = false;
 447779            reachabilityState.ActiveSnapshotVersion = -1;
 447780        }
 447781    }
 82
 83    /// <summary>
 84    /// Captures reachability snapshot state for benchmarks and regression tests.
 85    /// </summary>
 86    internal static SolidPartitionReachabilityStats CaptureStats()
 87    {
 888        lock (_lock)
 89        {
 890            return new SolidPartitionReachabilityStats(
 891                _hasActiveSnapshot ? 1 : 0,
 892                _version,
 893                _snapshotBuildCount,
 894                _passablePartitions.Capacity,
 895                _componentRoots.Capacity,
 896                _componentQueue.Capacity);
 97        }
 898    }
 99
 100    /// <summary>
 101    /// Returns true only when the current solid-partition graph proves the request cannot reach its destination.
 102    /// </summary>
 103    internal static bool IsProvablyUnreachable(AStarPathRequest request)
 104    {
 1197105        if (request == null
 1197106            || request.AllowTraversalTransitions
 1197107            || request.AllowUnwalkableEndpoints
 1197108            || request.StartNode == null
 1197109            || request.EndNode == null
 1197110            || !request.StartNode.TryGetPartition(out SolidChartPartition? startPartition)
 1197111            || !request.EndNode.TryGetPartition(out SolidChartPartition? endPartition)
 1197112            || startPartition == null
 1197113            || endPartition == null
 1197114            || ReferenceEquals(startPartition, endPartition)
 1197115            || startPartition.Neighbors == null
 1197116            || endPartition.Neighbors == null)
 117        {
 52118            return false;
 119        }
 120
 1145121        ReachabilitySnapshotKey key = new(request.UnitSize, request.MaxClimbHeight);
 1145122        lock (_lock)
 123        {
 1145124            int snapshotId = EnsureSnapshot(key);
 1145125            return IsProvablyUnreachable(
 1145126                startPartition,
 1145127                endPartition,
 1145128                snapshotId,
 1145129                _version,
 1145130                request.MaxClimbHeight);
 131        }
 1145132    }
 133
 134    private static bool IsProvablyUnreachable(
 135        SolidChartPartition startPartition,
 136        SolidChartPartition endPartition,
 137        int snapshotId,
 138        int version,
 139        Fixed64 maxClimbHeight)
 140    {
 1145141        if (!endPartition.TryGetReachabilityComponent(snapshotId, version, out int endComponent))
 0142            return false;
 143
 1145144        if (endComponent == 0)
 0145            return true;
 146
 1145147        if (!startPartition.TryGetReachabilityComponent(snapshotId, version, out int startComponent))
 0148            return false;
 149
 1145150        if (startComponent > 0)
 1145151            return startComponent != endComponent;
 152
 153        // A* can expand from an oversized/low-clearance start voxel, but only into passable
 154        // neighboring partitions. If none of those neighbors are in the end component, no route exists.
 0155        return !HasReachableNeighborInComponent(startPartition, endComponent, snapshotId, version, maxClimbHeight);
 156    }
 157
 158    private static int EnsureSnapshot(ReachabilitySnapshotKey key)
 159    {
 1145160        if (!_hasActiveSnapshot || !_activeSnapshotKey.Equals(key))
 161        {
 58162            _activeSnapshotKey = key;
 58163            _activeSnapshotId = GetNextSnapshotId(_activeSnapshotId);
 58164            _activeSnapshotVersion = -1;
 58165            _hasActiveSnapshot = true;
 166        }
 167
 1145168        if (_activeSnapshotVersion == _version)
 1087169            return _activeSnapshotId;
 170
 58171        BuildSnapshot(_activeSnapshotId, key.UnitSize, key.MaxClimbHeight, _version);
 58172        _activeSnapshotVersion = _version;
 58173        _snapshotBuildCount++;
 58174        return _activeSnapshotId;
 175    }
 176
 177    private static int GetNextSnapshotId(int current)
 178    {
 179        unchecked
 180        {
 58181            int next = current + 1;
 58182            return next == 0 ? 1 : next;
 183        }
 184    }
 185
 186    private static void BuildSnapshot(
 187        int snapshotId,
 188        Fixed64 unitSize,
 189        Fixed64 maxClimbHeight,
 190        int version)
 191    {
 192        // Snapshot construction runs under the reachability lock, so these scratch containers
 193        // can be reused without exposing partition references after the build completes.
 58194        _passablePartitions.Clear();
 58195        _componentRoots.Clear();
 58196        _componentQueue.Clear();
 197
 198        try
 199        {
 58200            GridWorld world = PathManager.ActiveState.World;
 290201            foreach (NavigationChart chart in PathManager.AllCharts)
 202            {
 87203                if (chart == null || !PathManager.IsChartInitialized(chart.Name))
 204                    continue;
 205
 1292206                foreach ((Vector3d position, NavigationChartCell cell) in chart.GetAuthoredCells())
 207                {
 559208                    if (!cell.HasSolid
 559209                        || !world.TryGetVoxel(position, out Voxel? voxel)
 559210                        || voxel == null
 559211                        || !voxel.TryGetPartition(out SolidChartPartition? partition)
 559212                        || partition == null
 559213                        || partition.Neighbors == null)
 214                    {
 215                        continue;
 216                    }
 217
 502218                    partition.SetReachabilityComponent(snapshotId, version, 0);
 502219                    if (partition.IsImpassable(unitSize) || _passablePartitions.ContainsKey(partition.WorldIndex))
 220                        continue;
 221
 311222                    _passablePartitions[partition.WorldIndex] = partition;
 311223                    _componentRoots.Add(partition);
 224                }
 225            }
 226
 58227            AssignComponents(
 58228                snapshotId,
 58229                version,
 58230                _passablePartitions,
 58231                _componentRoots,
 58232                _componentQueue,
 58233                maxClimbHeight);
 58234        }
 235        finally
 236        {
 58237            _componentQueue.Clear();
 58238            _componentRoots.Clear();
 58239            _passablePartitions.Clear();
 58240        }
 58241    }
 242
 243    private static void AssignComponents(
 244        int snapshotId,
 245        int version,
 246        SwiftDictionary<WorldVoxelIndex, SolidChartPartition> passablePartitions,
 247        SwiftList<SolidChartPartition> componentRoots,
 248        SwiftQueue<SolidChartPartition> queue,
 249        Fixed64 maxClimbHeight)
 250    {
 58251        int componentId = 0;
 252
 738253        for (int i = 0; i < componentRoots.Count; i++)
 254        {
 311255            SolidChartPartition root = componentRoots[i];
 311256            if (!root.TryGetReachabilityComponent(snapshotId, version, out int existingComponent)
 311257                || existingComponent != 0)
 258            {
 259                continue;
 260            }
 261
 80262            componentId++;
 80263            root.SetReachabilityComponent(snapshotId, version, componentId);
 80264            queue.Enqueue(root);
 265
 391266            while (queue.Count > 0)
 267            {
 311268                SolidChartPartition current = queue.Dequeue();
 311269                SolidChartPartition?[]? neighbors = current.Neighbors;
 311270                if (neighbors == null)
 271                    continue;
 272
 16794273                for (int neighborIndex = 0; neighborIndex < neighbors.Length; neighborIndex++)
 274                {
 8086275                    SolidChartPartition? neighbor = neighbors[neighborIndex];
 8086276                    if (neighbor == null
 8086277                        || !passablePartitions.ContainsKey(neighbor.WorldIndex)
 8086278                        || !neighbor.TryGetReachabilityComponent(snapshotId, version, out int neighborComponent)
 8086279                        || neighborComponent != 0
 8086280                        || !CanTraverse(current, neighbor, (SpatialDirection)neighborIndex, passablePartitions, maxClimb
 281                    {
 282                        continue;
 283                    }
 284
 231285                    neighbor.SetReachabilityComponent(snapshotId, version, componentId);
 231286                    queue.Enqueue(neighbor);
 287                }
 288            }
 289        }
 58290    }
 291
 292    private static bool HasReachableNeighborInComponent(
 293        SolidChartPartition start,
 294        int targetComponent,
 295        int snapshotId,
 296        int version,
 297        Fixed64 maxClimbHeight)
 298    {
 3299        SolidChartPartition?[]? neighbors = start.Neighbors;
 3300        if (neighbors == null)
 1301            return false;
 302
 60303        for (int neighborIndex = 0; neighborIndex < neighbors.Length; neighborIndex++)
 304        {
 29305            SolidChartPartition? neighbor = neighbors[neighborIndex];
 29306            if (neighbor == null
 29307                || !neighbor.TryGetReachabilityComponent(snapshotId, version, out int neighborComponent)
 29308                || neighborComponent != targetComponent
 29309                || !CanTraverseFromMarkedStart(start, neighbor, (SpatialDirection)neighborIndex, snapshotId, version, ma
 310            {
 311                continue;
 312            }
 313
 1314            return true;
 315        }
 316
 1317        return false;
 318    }
 319
 320    private static bool CanTraverse(
 321        SolidChartPartition current,
 322        SolidChartPartition neighbor,
 323        SpatialDirection direction,
 324        SwiftDictionary<WorldVoxelIndex, SolidChartPartition> passablePartitions,
 325        Fixed64 maxClimbHeight)
 326    {
 259327        Fixed64 heightDifference = (current.VoxelPosition.y - neighbor.VoxelPosition.y).Abs();
 259328        if (heightDifference > maxClimbHeight)
 0329            return false;
 330
 259331        if (ContainsDirection(SpatialAwareness.PerpendicularDirections, direction))
 194332            return true;
 333
 65334        return ContainsDirection(SpatialAwareness.DiagonalDirections, direction)
 65335            && HasValidDiagonalLegs(current, direction, passablePartitions);
 336    }
 337
 338    private static bool CanTraverseFromMarkedStart(
 339        SolidChartPartition current,
 340        SolidChartPartition neighbor,
 341        SpatialDirection direction,
 342        int snapshotId,
 343        int version,
 344        Fixed64 maxClimbHeight)
 345    {
 4346        Fixed64 heightDifference = (current.VoxelPosition.y - neighbor.VoxelPosition.y).Abs();
 4347        if (heightDifference > maxClimbHeight)
 1348            return false;
 349
 3350        if (ContainsDirection(SpatialAwareness.PerpendicularDirections, direction))
 1351            return true;
 352
 2353        return ContainsDirection(SpatialAwareness.DiagonalDirections, direction)
 2354            && HasValidDiagonalLegsFromMarkedStart(current, direction, snapshotId, version);
 355    }
 356
 357    private static bool HasValidDiagonalLegs(
 358        SolidChartPartition current,
 359        SpatialDirection diagonal,
 360        SwiftDictionary<WorldVoxelIndex, SolidChartPartition> passablePartitions)
 361    {
 65362        (int dx, int dy, int dz) = SpatialAwareness.DirectionOffsets[(int)diagonal];
 363
 65364        if (dx != 0 && !IsLegClear(current, DiagonalTraversalLegs.ForXOffset(dx), passablePartitions))
 13365            return false;
 366
 52367        if (dy != 0 && !IsLegClear(current, DiagonalTraversalLegs.ForYOffset(dy), passablePartitions))
 0368            return false;
 369
 52370        if (dz != 0 && !IsLegClear(current, DiagonalTraversalLegs.ForZOffset(dz), passablePartitions))
 15371            return false;
 372
 37373        return true;
 374    }
 375
 376    private static bool HasValidDiagonalLegsFromMarkedStart(
 377        SolidChartPartition current,
 378        SpatialDirection diagonal,
 379        int snapshotId,
 380        int version)
 381    {
 2382        (int dx, int dy, int dz) = SpatialAwareness.DirectionOffsets[(int)diagonal];
 383
 2384        if (dx != 0 && !IsMarkedLegClear(current, DiagonalTraversalLegs.ForXOffset(dx), snapshotId, version))
 0385            return false;
 386
 2387        if (dy != 0 && !IsMarkedLegClear(current, DiagonalTraversalLegs.ForYOffset(dy), snapshotId, version))
 0388            return false;
 389
 2390        if (dz != 0 && !IsMarkedLegClear(current, DiagonalTraversalLegs.ForZOffset(dz), snapshotId, version))
 1391            return false;
 392
 1393        return true;
 394    }
 395
 396    private static bool IsLegClear(
 397        SolidChartPartition current,
 398        SpatialDirection legDirection,
 399        SwiftDictionary<WorldVoxelIndex, SolidChartPartition> passablePartitions)
 400    {
 117401        SolidChartPartition? leg = current.Neighbors?[(int)legDirection];
 117402        return leg != null && passablePartitions.ContainsKey(leg.WorldIndex);
 403    }
 404
 405    private static bool IsMarkedLegClear(
 406        SolidChartPartition current,
 407        SpatialDirection legDirection,
 408        int snapshotId,
 409        int version)
 410    {
 6411        SolidChartPartition? leg = current.Neighbors?[(int)legDirection];
 6412        return leg != null
 6413            && leg.TryGetReachabilityComponent(snapshotId, version, out int componentId)
 6414            && componentId > 0;
 415    }
 416
 417    private static bool ContainsDirection(SpatialDirection[] directions, SpatialDirection direction)
 418    {
 2788419        for (int i = 0; i < directions.Length; i++)
 420        {
 1327421            if (directions[i] == direction)
 262422                return true;
 423        }
 424
 67425        return false;
 426    }
 427
 428    /// <summary>
 429    /// Snapshot counters used by benchmarks and tests to verify reachability cache policy.
 430    /// </summary>
 431    internal readonly struct SolidPartitionReachabilityStats
 432    {
 433        internal SolidPartitionReachabilityStats(
 434            int activeSnapshotCount,
 435            int version,
 436            long snapshotBuildCount,
 437            int passablePartitionCapacity,
 438            int componentRootCapacity,
 439            int componentQueueCapacity)
 440        {
 8441            ActiveSnapshotCount = activeSnapshotCount;
 8442            Version = version;
 8443            SnapshotBuildCount = snapshotBuildCount;
 8444            PassablePartitionCapacity = passablePartitionCapacity;
 8445            ComponentRootCapacity = componentRootCapacity;
 8446            ComponentQueueCapacity = componentQueueCapacity;
 8447        }
 448
 449        /// <summary>
 450        /// Gets the number of snapshot keys currently retained by the reachability cache.
 451        /// </summary>
 452        internal int ActiveSnapshotCount { get; }
 453
 454        /// <summary>
 455        /// Gets the current topology version tracked by the reachability cache.
 456        /// </summary>
 457        internal int Version { get; }
 458
 459        /// <summary>
 460        /// Gets the number of connectivity snapshots built since process start.
 461        /// </summary>
 462        internal long SnapshotBuildCount { get; }
 463
 464        /// <summary>
 465        /// Gets the retained capacity of the passable-partition scratch map.
 466        /// </summary>
 467        internal int PassablePartitionCapacity { get; }
 468
 469        /// <summary>
 470        /// Gets the retained capacity of the component-root scratch list.
 471        /// </summary>
 472        internal int ComponentRootCapacity { get; }
 473
 474        /// <summary>
 475        /// Gets the retained capacity of the component queue.
 476        /// </summary>
 477        internal int ComponentQueueCapacity { get; }
 478    }
 479
 480}
Generated by: ReportGenerator 5.5.10.0
05/19/2026 - 21:06:44
GitHub | reportgenerator.io

Methods/Properties

get_State()
get__lock()
get__passablePartitions()
get__componentRoots()
get__componentQueue()
get__activeSnapshotKey()
set__activeSnapshotKey(Trailblazer.Pathing.ReachabilitySnapshotKey)
get__hasActiveSnapshot()
set__hasActiveSnapshot(System.Boolean)
get__activeSnapshotId()
set__activeSnapshotId(System.Int32)
get__activeSnapshotVersion()
set__activeSnapshotVersion(System.Int32)
get__snapshotBuildCount()
set__snapshotBuildCount(System.Int64)
get__version()
set__version(System.Int32)
Invalidate()
Invalidate(Trailblazer.Pathing.PathingWorldState)
CaptureStats()
IsProvablyUnreachable(Trailblazer.Pathing.AStarPathRequest)
IsProvablyUnreachable(Trailblazer.Pathing.SolidChartPartition,Trailblazer.Pathing.SolidChartPartition,System.Int32,System.Int32,FixedMathSharp.Fixed64)
EnsureSnapshot(Trailblazer.Pathing.ReachabilitySnapshotKey)
GetNextSnapshotId(System.Int32)
BuildSnapshot(System.Int32,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,System.Int32)
AssignComponents(System.Int32,System.Int32,SwiftCollections.SwiftDictionary`2<GridForge.Spatial.WorldVoxelIndex,Trailblazer.Pathing.SolidChartPartition>,SwiftCollections.SwiftList`1<Trailblazer.Pathing.SolidChartPartition>,SwiftCollections.SwiftQueue`1<Trailblazer.Pathing.SolidChartPartition>,FixedMathSharp.Fixed64)
HasReachableNeighborInComponent(Trailblazer.Pathing.SolidChartPartition,System.Int32,System.Int32,System.Int32,FixedMathSharp.Fixed64)
CanTraverse(Trailblazer.Pathing.SolidChartPartition,Trailblazer.Pathing.SolidChartPartition,GridForge.Spatial.SpatialDirection,SwiftCollections.SwiftDictionary`2<GridForge.Spatial.WorldVoxelIndex,Trailblazer.Pathing.SolidChartPartition>,FixedMathSharp.Fixed64)
CanTraverseFromMarkedStart(Trailblazer.Pathing.SolidChartPartition,Trailblazer.Pathing.SolidChartPartition,GridForge.Spatial.SpatialDirection,System.Int32,System.Int32,FixedMathSharp.Fixed64)
HasValidDiagonalLegs(Trailblazer.Pathing.SolidChartPartition,GridForge.Spatial.SpatialDirection,SwiftCollections.SwiftDictionary`2<GridForge.Spatial.WorldVoxelIndex,Trailblazer.Pathing.SolidChartPartition>)
HasValidDiagonalLegsFromMarkedStart(Trailblazer.Pathing.SolidChartPartition,GridForge.Spatial.SpatialDirection,System.Int32,System.Int32)
IsLegClear(Trailblazer.Pathing.SolidChartPartition,GridForge.Spatial.SpatialDirection,SwiftCollections.SwiftDictionary`2<GridForge.Spatial.WorldVoxelIndex,Trailblazer.Pathing.SolidChartPartition>)
IsMarkedLegClear(Trailblazer.Pathing.SolidChartPartition,GridForge.Spatial.SpatialDirection,System.Int32,System.Int32)
ContainsDirection(GridForge.Spatial.SpatialDirection[],GridForge.Spatial.SpatialDirection)
.ctor(System.Int32,System.Int32,System.Int64,System.Int32,System.Int32,System.Int32)