| | | 1 | | //======================================================================= |
| | | 2 | | // NavigationSearchFinalizationRules.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 | | |
| | | 8 | | using System; |
| | | 9 | | using FixedMathSharp; |
| | | 10 | | |
| | | 11 | | namespace Trailblazer.Pathing; |
| | | 12 | | |
| | | 13 | | internal static class NavigationSearchFinalizationRules |
| | | 14 | | { |
| | | 15 | | internal static bool IsEpochCurrent( |
| | | 16 | | bool epochRequired, |
| | | 17 | | ulong expectedEpoch, |
| | | 18 | | ulong currentEpoch) => |
| | 24061 | 19 | | !epochRequired || currentEpoch == expectedEpoch; |
| | | 20 | | |
| | | 21 | | internal static NavigationEndpointResolutionStatus ResolveEndpointStatus( |
| | | 22 | | NavigationEndpointResolutionStatus status, |
| | | 23 | | bool dependenciesWereRead, |
| | | 24 | | bool dependenciesAreCurrent, |
| | | 25 | | bool epochIsCurrent) => |
| | 1337 | 26 | | !epochIsCurrent || (dependenciesWereRead && !dependenciesAreCurrent) |
| | 1337 | 27 | | ? NavigationEndpointResolutionStatus.Stale |
| | 1337 | 28 | | : status; |
| | | 29 | | |
| | | 30 | | internal static NavigationEndpointResolutionStatus ResolveEndpointCursorStatus( |
| | | 31 | | bool hasResult) => |
| | 1315 | 32 | | hasResult |
| | 1315 | 33 | | ? NavigationEndpointResolutionStatus.Success |
| | 1315 | 34 | | : NavigationEndpointResolutionStatus.InvalidEndpoint; |
| | | 35 | | |
| | | 36 | | internal static bool TryResolveTraversalTerminalStatus( |
| | | 37 | | NavigationTraversalEdgeAdvanceStatus traversalStatus, |
| | | 38 | | out NavigationSurfaceAStarStatus terminalStatus) |
| | | 39 | | { |
| | | 40 | | switch (traversalStatus) |
| | | 41 | | { |
| | | 42 | | case NavigationTraversalEdgeAdvanceStatus.BudgetExceeded: |
| | 7 | 43 | | terminalStatus = NavigationSurfaceAStarStatus.BudgetExceeded; |
| | 7 | 44 | | return true; |
| | | 45 | | case NavigationTraversalEdgeAdvanceStatus.CapacityExceeded: |
| | 4 | 46 | | terminalStatus = NavigationSurfaceAStarStatus.CapacityExceeded; |
| | 4 | 47 | | return true; |
| | | 48 | | case NavigationTraversalEdgeAdvanceStatus.CostOverflow: |
| | 3 | 49 | | terminalStatus = NavigationSurfaceAStarStatus.CostOverflow; |
| | 3 | 50 | | return true; |
| | | 51 | | case NavigationTraversalEdgeAdvanceStatus.Stale: |
| | 1 | 52 | | terminalStatus = NavigationSurfaceAStarStatus.Stale; |
| | 1 | 53 | | return true; |
| | | 54 | | default: |
| | 9880 | 55 | | terminalStatus = NavigationSurfaceAStarStatus.Pending; |
| | 9880 | 56 | | return false; |
| | | 57 | | } |
| | | 58 | | } |
| | | 59 | | |
| | | 60 | | internal static NavigationTraversalEdgeAdvanceStatus ResolveTraversalEpochStatus( |
| | | 61 | | NavigationTraversalEdgeAdvanceStatus traversalStatus, |
| | | 62 | | bool epochIsCurrent) => |
| | 18884 | 63 | | epochIsCurrent |
| | 18884 | 64 | | ? traversalStatus |
| | 18884 | 65 | | : NavigationTraversalEdgeAdvanceStatus.Stale; |
| | | 66 | | |
| | | 67 | | internal static NavigationSurfaceAStarStatus ResolveAStarEpochStatus( |
| | | 68 | | NavigationSurfaceAStarStatus status, |
| | | 69 | | bool epochIsCurrent) => |
| | 1258 | 70 | | epochIsCurrent |
| | 1258 | 71 | | ? status |
| | 1258 | 72 | | : NavigationSurfaceAStarStatus.Stale; |
| | | 73 | | |
| | | 74 | | internal static NavigationSurfaceAStarStatus ResolveBlockedTraversalStatus( |
| | | 75 | | bool requiresConnectionProgress, |
| | | 76 | | int remainingConnectionLegs, |
| | | 77 | | int remainingEvaluatedEdges) => |
| | 166 | 78 | | (requiresConnectionProgress |
| | 166 | 79 | | ? remainingConnectionLegs |
| | 166 | 80 | | : remainingEvaluatedEdges) == 0 |
| | 166 | 81 | | ? NavigationSurfaceAStarStatus.BudgetExceeded |
| | 166 | 82 | | : NavigationSurfaceAStarStatus.Pending; |
| | | 83 | | |
| | | 84 | | internal static NavigationSurfaceAStarStatus ResolveIncompleteLookupStatus( |
| | | 85 | | int remainingLookupProbes) => |
| | 13 | 86 | | remainingLookupProbes == 0 |
| | 13 | 87 | | ? NavigationSurfaceAStarStatus.BudgetExceeded |
| | 13 | 88 | | : NavigationSurfaceAStarStatus.Pending; |
| | | 89 | | |
| | | 90 | | internal static bool ShouldConsumeTraversalSurfacePoint( |
| | | 91 | | bool hasSurfacePoint, |
| | | 92 | | NavigationTraversalEdgeAdvanceStatus traversalStatus) => |
| | 3858 | 93 | | hasSurfacePoint |
| | 3858 | 94 | | && traversalStatus != NavigationTraversalEdgeAdvanceStatus.Stale; |
| | | 95 | | |
| | | 96 | | internal static bool TryGetEuclideanHeuristic( |
| | | 97 | | bool hasFootAnchor, |
| | | 98 | | Vector3d footAnchor, |
| | | 99 | | Vector3d targetFootAnchor, |
| | | 100 | | out Fixed64 heuristic) |
| | | 101 | | { |
| | 873 | 102 | | if (hasFootAnchor |
| | 873 | 103 | | && NavigationDistanceMath.TryFloor( |
| | 873 | 104 | | footAnchor, |
| | 873 | 105 | | targetFootAnchor, |
| | 873 | 106 | | out heuristic)) |
| | | 107 | | { |
| | 871 | 108 | | return true; |
| | | 109 | | } |
| | 2 | 110 | | heuristic = Fixed64.Zero; |
| | 2 | 111 | | return false; |
| | | 112 | | } |
| | | 113 | | |
| | | 114 | | internal static bool ShouldAcceptSimplificationRay( |
| | | 115 | | NavigationCellAddress actualEnd, |
| | | 116 | | NavigationCellAddress candidateEnd, |
| | | 117 | | Fixed64 traversalCost, |
| | | 118 | | Fixed64 rawCost) => |
| | 26 | 119 | | actualEnd == candidateEnd |
| | 26 | 120 | | && traversalCost <= rawCost; |
| | | 121 | | |
| | | 122 | | internal static bool TryAdmitSimplification( |
| | | 123 | | int pathNodeCount, |
| | | 124 | | int remainingSimplificationRays, |
| | | 125 | | int componentCount, |
| | | 126 | | int pageCount, |
| | | 127 | | NavigationWorkMeter meter, |
| | | 128 | | out int lookupReservation) |
| | | 129 | | { |
| | 205 | 130 | | lookupReservation = 0; |
| | 205 | 131 | | if (pathNodeCount < 2) |
| | 2 | 132 | | return false; |
| | 203 | 133 | | if (remainingSimplificationRays == 0) |
| | 121 | 134 | | return false; |
| | 82 | 135 | | return TrySetFinalizationLookupReservation( |
| | 82 | 136 | | componentCount, |
| | 82 | 137 | | pageCount, |
| | 82 | 138 | | meter, |
| | 82 | 139 | | out lookupReservation); |
| | | 140 | | } |
| | | 141 | | |
| | | 142 | | internal static bool TryPrepareDependencyMerge( |
| | | 143 | | bool epochIsCurrent, |
| | | 144 | | NavigationDependencyWorkspace target, |
| | | 145 | | NavigationDependencyWorkspace source, |
| | | 146 | | NavigationWorkMeter meter, |
| | | 147 | | int priorLookupReservation, |
| | | 148 | | out int enlargedLookupReservation) |
| | | 149 | | { |
| | 33 | 150 | | enlargedLookupReservation = 0; |
| | 33 | 151 | | if (!epochIsCurrent) |
| | 1 | 152 | | return false; |
| | 32 | 153 | | if (!target.TryCountMissing( |
| | 32 | 154 | | source, |
| | 32 | 155 | | meter, |
| | 32 | 156 | | out int missingComponents, |
| | 32 | 157 | | out int missingPages)) |
| | | 158 | | { |
| | 1 | 159 | | return false; |
| | | 160 | | } |
| | 31 | 161 | | if (!target.CanFit(missingComponents, missingPages)) |
| | 1 | 162 | | return false; |
| | 30 | 163 | | if (!TrySetFinalizationLookupReservation( |
| | 30 | 164 | | target.ComponentCount + missingComponents, |
| | 30 | 165 | | target.PageCount + missingPages, |
| | 30 | 166 | | meter, |
| | 30 | 167 | | out enlargedLookupReservation)) |
| | | 168 | | { |
| | 1 | 169 | | return false; |
| | | 170 | | } |
| | 29 | 171 | | int appendProbeCount = source.ComponentCount + source.PageCount; |
| | 29 | 172 | | if (meter.TryConsumeLookupProbes(appendProbeCount)) |
| | 27 | 173 | | return true; |
| | 2 | 174 | | meter.TrySetLookupReservationFloor(priorLookupReservation); |
| | 2 | 175 | | return false; |
| | | 176 | | } |
| | | 177 | | |
| | | 178 | | internal static bool TryCombineLookupReservation( |
| | | 179 | | int comparisonCount, |
| | | 180 | | int componentCount, |
| | | 181 | | int pageCount, |
| | | 182 | | out int reservation) |
| | | 183 | | { |
| | | 184 | | try |
| | | 185 | | { |
| | 120 | 186 | | reservation = checked(comparisonCount + componentCount + pageCount); |
| | 118 | 187 | | return true; |
| | | 188 | | } |
| | 2 | 189 | | catch (OverflowException) |
| | | 190 | | { |
| | 2 | 191 | | reservation = 0; |
| | 2 | 192 | | return false; |
| | | 193 | | } |
| | 120 | 194 | | } |
| | | 195 | | |
| | | 196 | | internal static bool TryGetFinalizationLookupReservation( |
| | | 197 | | int componentCount, |
| | | 198 | | int pageCount, |
| | | 199 | | out int reservation) |
| | | 200 | | { |
| | | 201 | | try |
| | | 202 | | { |
| | 118 | 203 | | int comparisonCount = NavigationDependencySortWork.GetMaximumComparisonCount( |
| | 118 | 204 | | componentCount, |
| | 118 | 205 | | pageCount); |
| | 115 | 206 | | return TryCombineLookupReservation( |
| | 115 | 207 | | comparisonCount, |
| | 115 | 208 | | componentCount, |
| | 115 | 209 | | pageCount, |
| | 115 | 210 | | out reservation); |
| | | 211 | | } |
| | 3 | 212 | | catch (OverflowException) |
| | | 213 | | { |
| | 3 | 214 | | reservation = 0; |
| | 3 | 215 | | return false; |
| | | 216 | | } |
| | 118 | 217 | | } |
| | | 218 | | |
| | | 219 | | private static bool TrySetFinalizationLookupReservation( |
| | | 220 | | int componentCount, |
| | | 221 | | int pageCount, |
| | | 222 | | NavigationWorkMeter meter, |
| | | 223 | | out int reservation) => |
| | 112 | 224 | | TryGetFinalizationLookupReservation( |
| | 112 | 225 | | componentCount, |
| | 112 | 226 | | pageCount, |
| | 112 | 227 | | out reservation) |
| | 112 | 228 | | && meter.TrySetLookupReservationFloor(reservation); |
| | | 229 | | } |