< Summary

Information
Class: Trailblazer.Pathing.VolumeSurveyor
Assembly: Trailblazer
File(s): /home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Search/Volume/VolumeSurveyor.cs
Line coverage
98%
Covered lines: 173
Uncovered lines: 2
Coverable lines: 175
Total lines: 370
Line coverage: 98.8%
Branch coverage
88%
Covered branches: 88
Total branches: 100
Branch coverage: 88%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.cctor()100%11100%
get_Shared()100%11100%
.ctor()100%11100%
FindPath(...)100%88100%
TracePath()100%88100%
ProcessNeighbors(...)100%66100%
TryProcessDirections(...)93.75%161690%
HasValidDiagonalLegs(...)92.85%141490%
IsLegClear(...)50%22100%
ProcessNeighbor(...)87.5%88100%
SetVoxelData(...)100%11100%
BuildRawPath()60%1010100%
BuildWaypoints()100%44100%
TrackRawPathChartOwners()100%22100%
AddVoxelChartOwners(...)80%1010100%
CalculatePathCost(...)100%11100%
CanTraverseVoxel(...)100%66100%
GetMovementCost(...)100%11100%
GetTraversalCostModifier(...)66.66%66100%
ClearWorkingState()100%11100%

File(s)

/home/runner/work/Trailblazer/Trailblazer/src/Trailblazer/Pathing/Search/Volume/VolumeSurveyor.cs

#LineLine coverage
 1using FixedMathSharp;
 2using GridForge.Grids;
 3using GridForge.Spatial;
 4using SwiftCollections;
 5using System;
 6using System.Linq;
 7using System.Runtime.CompilerServices;
 8using System.Threading;
 9
 10namespace Trailblazer.Pathing;
 11
 12internal struct VolumeVoxelMeta
 13{
 14    public int MovementCost;
 15
 16    public WorldVoxelIndex? NextTrailIndex;
 17}
 18
 19/// <summary>
 20/// Executes chart-optional A* pathfinding through raw voxel volume.
 21/// </summary>
 22public sealed class VolumeSurveyor
 23{
 124    private static readonly Lazy<VolumeSurveyor> _instance =
 125        new(() => new VolumeSurveyor(), LazyThreadSafetyMode.ExecutionAndPublication);
 26
 27    /// <summary>
 28    /// Gets the singleton instance of the VolumeSurveyor class.
 29    /// </summary>
 30    /// <remarks>
 31    /// Use this property to access the shared VolumeSurveyor instance throughout the application.
 32    /// This instance is thread-safe and intended for global use.
 33    /// </remarks>
 2534    public static VolumeSurveyor Shared => _instance.Value;
 35
 96536    private readonly SurveyorLock _scratchLock = new();
 37
 96538    private readonly PathHeap<Voxel> _heap = new();
 39
 40    // Key by stable voxel index so reconstruction is independent of GridForge voxel wrapper identity.
 96541    private readonly SwiftDictionary<WorldVoxelIndex, VolumeVoxelMeta> _meta = new();
 42
 96543    private readonly SwiftList<Voxel> _rawPath = new();
 44
 96545    private readonly SwiftList<AStarWaypoint> _waypoints = new();
 46
 96547    private readonly SwiftHashSet<string> _chartKeys = new();
 48
 49    private VolumePathRequest? _request;
 50
 51    /// <summary>
 52    /// Finds a navigable path through the volume based on the specified pathfinding request.
 53    /// </summary>
 54    /// <remarks>
 55    /// Returns an empty result if the request is null, has zero displacement, or does not specify
 56    /// valid endpoints. The method is thread-safe and synchronizes access to reusable scratch state.
 57    /// </remarks>
 58    /// <param name="request">The pathfinding request that defines the start and end points, as well as any constraints 
 59    /// path search. Cannot be null, must have valid endpoints, and must specify a non-zero displacement.</param>
 60    /// <returns>
 61    /// A VolumeSurveyResult containing the computed path and related metadata if a valid path is found; otherwise,
 62    /// VolumeSurveyResult.Empty.
 63    /// </returns>
 64    public VolumeSurveyResult FindPath(VolumePathRequest request)
 65    {
 14766        lock (_scratchLock)
 67        {
 14768            if (request == null || request.HasZeroDisplacement || !request.HasValidEndpoints)
 369                return VolumeSurveyResult.Empty;
 70
 14471            _request = request;
 14472            VolumePathRequest activeRequest = _request;
 73
 14474            ClearWorkingState();
 75
 14476            _meta[activeRequest.StartNode!.WorldIndex] = new VolumeVoxelMeta();
 14477            _heap.Add(activeRequest.StartNode!, 0);
 78
 14479            if (!TracePath())
 80            {
 581                ClearWorkingState();
 582                return VolumeSurveyResult.Empty;
 83            }
 84
 13985            BuildRawPath();
 13986            TrackRawPathChartOwners();
 13987            BuildWaypoints();
 88
 13989            VolumeSurveyResult result = VolumeSurveyResult.Create(
 13990                request.Context,
 13991                _waypoints.ToArray(),
 13992                _chartKeys.ToArray(),
 13993                request.RequestCacheKey);
 13994            ClearWorkingState();
 13995            return result;
 96        }
 14797    }
 98
 99    private bool TracePath()
 100    {
 144101        VolumePathRequest request = _request!;
 144102        int iterations = 0;
 144103        int searchSize = request.MaxPathSearchRange;
 104
 366105        while (_heap.RemoveFirst(out Voxel? current)
 366106            && current != null
 366107            && iterations++ < searchSize)
 108        {
 361109            if (ProcessNeighbors(current))
 139110                return true;
 111
 222112            _heap.SetClosed(current);
 222113        }
 114
 5115        return false;
 116    }
 117
 118    private bool ProcessNeighbors(Voxel current)
 119    {
 362120        if (!_meta.TryGetValue(current.WorldIndex, out VolumeVoxelMeta data))
 1121            return false;
 122
 361123        if (TryProcessDirections(
 361124            current,
 361125            SpatialAwareness.PerpendicularDirections,
 361126            data.MovementCost + AStarSurveyor.StraightCost))
 127        {
 128128            return true;
 129        }
 130
 233131        if (TryProcessDirections(
 233132            current,
 233133            SpatialAwareness.DiagonalDirections,
 233134            data.MovementCost + AStarSurveyor.DiagonalCost,
 233135            checkEdges: true))
 136        {
 11137            return true;
 138        }
 139
 222140        return false;
 141    }
 142
 143    private bool TryProcessDirections(
 144        Voxel current,
 145        SpatialDirection[] directions,
 146        int movementCost,
 147        bool checkEdges = false)
 148    {
 594149        if (!_request!.Context.World.TryGetGrid(current.GridIndex, out VoxelGrid? grid))
 0150            return false;
 151
 13611152        foreach (SpatialDirection dir in directions)
 153        {
 6281154            if (!current.TryGetNeighborFromDirection(grid!, dir, out Voxel? neighbor, useCache: true)
 6281155                || _heap.IsClosed(neighbor!))
 156            {
 157                continue;
 158            }
 159
 5980160            if (checkEdges && !HasValidDiagonalLegs(current, dir))
 161                continue;
 162
 1836163            if (CanTraverseVoxel(neighbor!) != true)
 164                continue;
 165
 738166            if (ProcessNeighbor(current, neighbor!, movementCost))
 139167                return true;
 168        }
 169
 455170        return false;
 171    }
 172
 173    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 174    private bool HasValidDiagonalLegs(Voxel current, SpatialDirection diagonal)
 175    {
 4348176        if (!_request!.Context.World.TryGetGrid(current.GridIndex, out VoxelGrid? grid))
 0177            return false;
 178
 4348179        (int dx, int dy, int dz) = SpatialAwareness.DirectionOffsets[(int)diagonal];
 180
 4348181        if (dx != 0 && !IsLegClear(grid!, current, DiagonalTraversalLegs.ForXOffset(dx)))
 1264182            return false;
 183
 3084184        if (dy != 0 && !IsLegClear(grid!, current, DiagonalTraversalLegs.ForYOffset(dy)))
 2452185            return false;
 186
 632187        if (dz != 0 && !IsLegClear(grid!, current, DiagonalTraversalLegs.ForZOffset(dz)))
 428188            return false;
 189
 204190        return true;
 191    }
 192
 193    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 194    private bool IsLegClear(VoxelGrid grid, Voxel current, SpatialDirection legDir)
 195    {
 6636196        return current.TryGetNeighborFromDirection(grid, legDir, out Voxel? leg, useCache: true)
 6636197            && CanTraverseVoxel(leg!);
 198    }
 199
 200    private bool ProcessNeighbor(Voxel current, Voxel neighbor, int movementCost)
 201    {
 739202        VolumePathRequest request = _request!;
 739203        int totalMovementCost = movementCost + GetTraversalCostModifier(neighbor);
 204
 739205        if (neighbor == request.EndNode)
 206        {
 139207            SetVoxelData(neighbor, current.WorldIndex, totalMovementCost);
 139208            return true;
 209        }
 210
 600211        int pathCost = CalculatePathCost(neighbor.WorldPosition, totalMovementCost);
 600212        if (!_heap.Contains(neighbor))
 213        {
 479214            SetVoxelData(neighbor, current.WorldIndex, totalMovementCost);
 479215            _heap.Add(neighbor, pathCost);
 216        }
 121217        else if (_meta.TryGetValue(neighbor.WorldIndex, out VolumeVoxelMeta neighborData)
 121218            && neighborData.MovementCost > totalMovementCost)
 219        {
 1220            SetVoxelData(neighbor, current.WorldIndex, totalMovementCost);
 1221            _heap.UpdatePathCost(neighbor, pathCost);
 1222            _heap.SortUp(neighbor);
 223        }
 224
 600225        return false;
 226    }
 227
 228    private void SetVoxelData(
 229        Voxel voxel,
 230        WorldVoxelIndex nextTrailIndex,
 231        int movementCost)
 232    {
 619233        _meta[voxel.WorldIndex] = new VolumeVoxelMeta()
 619234        {
 619235            MovementCost = movementCost,
 619236            NextTrailIndex = nextTrailIndex
 619237        };
 619238    }
 239
 240    private void BuildRawPath()
 241    {
 139242        VolumePathRequest request = _request!;
 139243        Voxel current = request.EndNode!;
 494244        while (current != request.StartNode)
 245        {
 355246            _rawPath.Insert(0, current);
 247
 355248            if (!_meta.TryGetValue(current.WorldIndex, out VolumeVoxelMeta data)
 355249                || !data.NextTrailIndex.HasValue)
 250                break;
 251
 355252            if (!request.Context.World.TryGetGridAndVoxel(data.NextTrailIndex.Value, out _, out Voxel? nextTrailVoxel)
 355253                || nextTrailVoxel == null)
 254                break;
 255
 355256            current = nextTrailVoxel;
 257        }
 258
 139259        _rawPath.Insert(0, request.StartNode!);
 139260    }
 261
 262    private void BuildWaypoints()
 263    {
 139264        _waypoints.EnsureCapacity(_rawPath.Count);
 265
 139266        Voxel start = _rawPath[0];
 139267        _waypoints.Add(new AStarWaypoint()
 139268        {
 139269            Position = start.WorldPosition,
 139270            PathCost = 0,
 139271            GlobalIndex = start.WorldIndex
 139272        });
 273
 139274        Vector3d lastDirection = Vector3d.Zero;
 710275        for (int i = 1; i < _rawPath.Count - 1; i++)
 276        {
 216277            Vector3d direction = (_rawPath[i + 1].WorldPosition - _rawPath[i].WorldPosition).Normalize();
 216278            if (!lastDirection.FuzzyEqual(direction))
 279            {
 131280                _waypoints.Add(new AStarWaypoint()
 131281                {
 131282                    Position = _rawPath[i].WorldPosition,
 131283                    PathCost = GetMovementCost(_rawPath[i]),
 131284                    GlobalIndex = _rawPath[i].WorldIndex
 131285                });
 286            }
 287
 216288            lastDirection = direction;
 289        }
 290
 139291        Voxel end = _rawPath.FromEnd(1);
 139292        _waypoints.Add(new AStarWaypoint()
 139293        {
 139294            Position = end.WorldPosition,
 139295            PathCost = GetMovementCost(end),
 139296            GlobalIndex = end.WorldIndex,
 139297            IsGoal = true
 139298        });
 139299    }
 300
 301    private void TrackRawPathChartOwners()
 302    {
 1266303        for (int i = 0; i < _rawPath.Count; i++)
 494304            AddVoxelChartOwners(_rawPath[i]);
 139305    }
 306
 307    private void AddVoxelChartOwners(Voxel voxel)
 308    {
 495309        if (voxel == null)
 1310            return;
 311
 494312        if (voxel.TryGetPartition(out SolidChartPartition? pathPartition) && pathPartition != null)
 101313            ChartOwnerUtility.AddOwners(_chartKeys, pathPartition.ChartOwners);
 314
 494315        if (voxel.TryGetPartition(out VolumeChartPartition? volumePartition) && volumePartition != null)
 488316            ChartOwnerUtility.AddOwners(_chartKeys, volumePartition.ChartOwners);
 494317    }
 318
 319    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 320    private int CalculatePathCost(Vector3d currentVoxel, int movementCost)
 321    {
 600322        VolumePathRequest request = _request!;
 600323        return movementCost + AStarSurveyor.CalculateHeuristic(
 600324            currentVoxel,
 600325            request.EndNode!.WorldPosition,
 600326            request.Heuristic);
 327    }
 328
 329    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 330    private bool CanTraverseVoxel(Voxel voxel)
 331    {
 8472332        VolumePathRequest request = _request!;
 8472333        if (voxel == request.StartNode)
 122334            return true;
 335
 8350336        if (voxel == request.EndNode && request.AllowUnwalkableEndpoints)
 16337            return VolumeMediumRules.Matches(request.Context.Pathing.State, voxel, request.Medium);
 338
 8334339        return VolumeVoxelFinder.IsTraversable(
 8334340            request.Context,
 8334341            voxel,
 8334342            request.UnitSize,
 8334343            request.Medium);
 344    }
 345
 346    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 347    private int GetMovementCost(Voxel voxel)
 348    {
 270349        return _meta[voxel.WorldIndex].MovementCost;
 350    }
 351
 352    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 353    private static int GetTraversalCostModifier(Voxel voxel)
 354    {
 739355        return voxel != null
 739356            && voxel.TryGetPartition(out VolumeChartPartition? volumePartition)
 739357            && volumePartition != null
 739358            ? volumePartition.PathCostModifier
 739359            : 0;
 360    }
 361
 362    private void ClearWorkingState()
 363    {
 288364        _heap.FastClear();
 288365        _meta.Clear();
 288366        _rawPath.FastClear();
 288367        _waypoints.FastClear();
 288368        _chartKeys.Clear();
 288369    }
 370}
Generated by: ReportGenerator 5.5.10.0
05/19/2026 - 21:06:44
GitHub | reportgenerator.io

Methods/Properties

.cctor()
get_Shared()
.ctor()
FindPath(Trailblazer.Pathing.VolumePathRequest)
TracePath()
ProcessNeighbors(GridForge.Grids.Voxel)
TryProcessDirections(GridForge.Grids.Voxel,GridForge.Spatial.SpatialDirection[],System.Int32,System.Boolean)
HasValidDiagonalLegs(GridForge.Grids.Voxel,GridForge.Spatial.SpatialDirection)
IsLegClear(GridForge.Grids.VoxelGrid,GridForge.Grids.Voxel,GridForge.Spatial.SpatialDirection)
ProcessNeighbor(GridForge.Grids.Voxel,GridForge.Grids.Voxel,System.Int32)
SetVoxelData(GridForge.Grids.Voxel,GridForge.Spatial.WorldVoxelIndex,System.Int32)
BuildRawPath()
BuildWaypoints()
TrackRawPathChartOwners()
AddVoxelChartOwners(GridForge.Grids.Voxel)
CalculatePathCost(FixedMathSharp.Vector3d,System.Int32)
CanTraverseVoxel(GridForge.Grids.Voxel)
GetMovementCost(GridForge.Grids.Voxel)
GetTraversalCostModifier(GridForge.Grids.Voxel)
ClearWorkingState()