| | | 1 | | //======================================================================= |
| | | 2 | | // GridTracer.NavigationBody.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 System.Collections.Generic; |
| | | 10 | | using FixedMathSharp; |
| | | 11 | | using FixedMathSharp.Geometry; |
| | | 12 | | using GridForge.Configuration; |
| | | 13 | | using GridForge.Grids; |
| | | 14 | | using GridForge.Grids.Storage; |
| | | 15 | | using GridForge.Grids.Topology; |
| | | 16 | | using GridForge.Spatial; |
| | | 17 | | using SwiftCollections; |
| | | 18 | | |
| | | 19 | | namespace GridForge.Utility; |
| | | 20 | | |
| | | 21 | | /// <content>Provides bounded swept navigation-body coverage.</content> |
| | | 22 | | public static partial class GridTracer |
| | | 23 | | { |
| | | 24 | | /// <summary>Writes the canonical cells required by one direct upright-body sweep.</summary> |
| | | 25 | | /// <remarks> |
| | | 26 | | /// The start and end bodies must have closed-set contact with the declared source and target |
| | | 27 | | /// prisms respectively; exact endpoint tangency is admitted for that identity check. |
| | | 28 | | /// A prism is claimed only when its planar and vertical interiors overlap the swept body at |
| | | 29 | | /// one shared continuous parameter. Boundary-only coincidence and tangency are excluded. |
| | | 30 | | /// Grid, address, output, and combined candidate-work ceilings are independent. |
| | | 31 | | /// </remarks> |
| | | 32 | | public static GridNavigationBodyTraceReport TraceNavigationBodyInto( |
| | | 33 | | GridWorld world, |
| | | 34 | | WorldVoxelIndex source, |
| | | 35 | | WorldVoxelIndex target, |
| | | 36 | | Vector3d startFoot, |
| | | 37 | | Vector3d endFoot, |
| | | 38 | | Fixed64 horizontalRadius, |
| | | 39 | | Fixed64 bodyHeight, |
| | | 40 | | SwiftList<GridNavigationBodyTraceCell> results, |
| | | 41 | | GridNavigationBodyTraceScratch scratch, |
| | | 42 | | int gridCandidateLimit, |
| | | 43 | | int addressCandidateLimit, |
| | | 44 | | int outputLimit, |
| | | 45 | | long candidateWorkLimit) => |
| | 90 | 46 | | TraceNavigationBodyInto(world, source, target, startFoot, endFoot, horizontalRadius, bodyHeight, |
| | 90 | 47 | | results, scratch, gridCandidateLimit, addressCandidateLimit, outputLimit, candidateWorkLimit, |
| | 90 | 48 | | excludedGridSpawnTokens: null); |
| | | 49 | | |
| | | 50 | | /// <summary>Writes upright-body coverage while excluding the supplied exact grid generations.</summary> |
| | | 51 | | /// <remarks> |
| | | 52 | | /// Supply <see cref="VoxelGrid.SpawnToken"/> values from the given world and keep the set unchanged until the trace |
| | | 53 | | /// An excluded generation cannot provide prism coverage or cell dependency evidence. Its broad-phase |
| | | 54 | | /// candidate still counts toward the grid and combined limits, with no address work charged. |
| | | 55 | | /// An excluded source or target invalidates the trace. An old token never excludes a replacement grid. |
| | | 56 | | /// The optional `excludedGridCandidates` list is cleared first and receives the configuration keys |
| | | 57 | | /// of excluded grids encountered during candidate traversal. An aborted trace can leave only a prefix. |
| | | 58 | | /// </remarks> |
| | | 59 | | public static GridNavigationBodyTraceReport TraceNavigationBodyInto( |
| | | 60 | | GridWorld world, |
| | | 61 | | WorldVoxelIndex source, |
| | | 62 | | WorldVoxelIndex target, |
| | | 63 | | Vector3d startFoot, |
| | | 64 | | Vector3d endFoot, |
| | | 65 | | Fixed64 horizontalRadius, |
| | | 66 | | Fixed64 bodyHeight, |
| | | 67 | | SwiftList<GridNavigationBodyTraceCell> results, |
| | | 68 | | GridNavigationBodyTraceScratch scratch, |
| | | 69 | | int gridCandidateLimit, |
| | | 70 | | int addressCandidateLimit, |
| | | 71 | | int outputLimit, |
| | | 72 | | long candidateWorkLimit, |
| | | 73 | | SwiftPackedSet<long>? excludedGridSpawnTokens, |
| | | 74 | | SwiftList<GridConfigurationKey>? excludedGridCandidates = null) |
| | | 75 | | { |
| | 106 | 76 | | ChronicleGuard.ThrowIfNull(results, nameof(results)); |
| | 106 | 77 | | ChronicleGuard.ThrowIfNull(scratch, nameof(scratch)); |
| | 106 | 78 | | ChronicleGuard.ThrowIfNegative(gridCandidateLimit, nameof(gridCandidateLimit)); |
| | 105 | 79 | | ChronicleGuard.ThrowIfNegative(addressCandidateLimit, nameof(addressCandidateLimit)); |
| | 104 | 80 | | ChronicleGuard.ThrowIfNegative(outputLimit, nameof(outputLimit)); |
| | 103 | 81 | | if (candidateWorkLimit < 0L) |
| | 1 | 82 | | throw new ArgumentOutOfRangeException(nameof(candidateWorkLimit)); |
| | | 83 | | |
| | 102 | 84 | | results.Clear(); |
| | 102 | 85 | | scratch.Clear(); |
| | 102 | 86 | | excludedGridCandidates?.Clear(); |
| | 102 | 87 | | if (world == null |
| | 102 | 88 | | || !world.IsActive |
| | 102 | 89 | | || horizontalRadius < Fixed64.Zero |
| | 102 | 90 | | || bodyHeight <= Fixed64.Zero |
| | 102 | 91 | | || (excludedGridSpawnTokens != null |
| | 102 | 92 | | && (excludedGridSpawnTokens.Contains(source.GridSpawnToken) |
| | 102 | 93 | | || excludedGridSpawnTokens.Contains(target.GridSpawnToken)))) |
| | | 94 | | { |
| | 7 | 95 | | return CreateNavigationBodyTraceReport( |
| | 7 | 96 | | GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry, |
| | 7 | 97 | | 0, |
| | 7 | 98 | | 0, |
| | 7 | 99 | | results, |
| | 7 | 100 | | default); |
| | | 101 | | } |
| | | 102 | | |
| | 95 | 103 | | if (!Fixed64.TryAdd(startFoot.Y, bodyHeight, out Fixed64 startTop) |
| | 95 | 104 | | || !Fixed64.TryAdd(endFoot.Y, bodyHeight, out Fixed64 endTop) |
| | 95 | 105 | | || !TryCreateNavigationBodyBounds( |
| | 95 | 106 | | startFoot, |
| | 95 | 107 | | endFoot, |
| | 95 | 108 | | startTop, |
| | 95 | 109 | | endTop, |
| | 95 | 110 | | horizontalRadius, |
| | 95 | 111 | | out Vector3d queryMin, |
| | 95 | 112 | | out Vector3d queryMax)) |
| | | 113 | | { |
| | 8 | 114 | | return CreateNavigationBodyTraceReport( |
| | 8 | 115 | | GridNavigationBodyTraceStatus.ArithmeticOverflow, |
| | 8 | 116 | | 0, |
| | 8 | 117 | | 0, |
| | 8 | 118 | | results, |
| | 8 | 119 | | default); |
| | | 120 | | } |
| | | 121 | | |
| | | 122 | | // Closed bounds reject only disjoint prisms; exact continuous overlap remains the narrow phase. |
| | 87 | 123 | | TopologyVoxelAabb bodyBounds = new TopologyVoxelAabb(queryMin, queryMax); |
| | 87 | 124 | | world.EnterReadLock(); |
| | | 125 | | try |
| | | 126 | | { |
| | 87 | 127 | | if (!world.TryGetGrid(source, out VoxelGrid? sourceGridValue) |
| | 87 | 128 | | || !world.TryGetGrid(target, out VoxelGrid? targetGridValue)) |
| | | 129 | | { |
| | 1 | 130 | | return FailNavigationBodyTrace( |
| | 1 | 131 | | results, |
| | 1 | 132 | | GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry, |
| | 1 | 133 | | 0, |
| | 1 | 134 | | 0, |
| | 1 | 135 | | default); |
| | | 136 | | } |
| | | 137 | | |
| | 86 | 138 | | VoxelGrid sourceGrid = sourceGridValue!; |
| | 86 | 139 | | VoxelGrid targetGrid = targetGridValue!; |
| | 86 | 140 | | if (!GridCellGeometry.TryCreatePrism( |
| | 86 | 141 | | sourceGrid.Configuration.TopologyKind, |
| | 86 | 142 | | sourceGrid.Configuration.TopologyMetrics, |
| | 86 | 143 | | sourceGrid.GetWorldPosition(source.VoxelIndex), |
| | 86 | 144 | | source, |
| | 86 | 145 | | out GridCellPrism sourcePrism) |
| | 86 | 146 | | || !GridCellGeometry.TryCreatePrism( |
| | 86 | 147 | | targetGrid.Configuration.TopologyKind, |
| | 86 | 148 | | targetGrid.Configuration.TopologyMetrics, |
| | 86 | 149 | | targetGrid.GetWorldPosition(target.VoxelIndex), |
| | 86 | 150 | | target, |
| | 86 | 151 | | out GridCellPrism targetPrism)) |
| | | 152 | | { |
| | 2 | 153 | | return FailNavigationBodyTrace( |
| | 2 | 154 | | results, |
| | 2 | 155 | | GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry, |
| | 2 | 156 | | 0, |
| | 2 | 157 | | 0, |
| | 2 | 158 | | default); |
| | | 159 | | } |
| | | 160 | | |
| | 84 | 161 | | if (!HasClosedNavigationBodyPrismContact( |
| | 84 | 162 | | sourcePrism, |
| | 84 | 163 | | startFoot, |
| | 84 | 164 | | startTop, |
| | 84 | 165 | | horizontalRadius) |
| | 84 | 166 | | || !HasClosedNavigationBodyPrismContact( |
| | 84 | 167 | | targetPrism, |
| | 84 | 168 | | endFoot, |
| | 84 | 169 | | endTop, |
| | 84 | 170 | | horizontalRadius)) |
| | | 171 | | { |
| | 5 | 172 | | return FailNavigationBodyTrace( |
| | 5 | 173 | | results, |
| | 5 | 174 | | GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry, |
| | 5 | 175 | | 0, |
| | 5 | 176 | | 0, |
| | 5 | 177 | | default); |
| | | 178 | | } |
| | | 179 | | |
| | 79 | 180 | | Span<GridCellPrism> closurePrisms = stackalloc GridCellPrism[8]; |
| | 79 | 181 | | int closureCount = GetNavigationClosure( |
| | 79 | 182 | | sourceGrid, |
| | 79 | 183 | | sourcePrism, |
| | 79 | 184 | | targetPrism, |
| | 79 | 185 | | closurePrisms); |
| | 79 | 186 | | if (closureCount == 0) |
| | | 187 | | { |
| | 2 | 188 | | return FailNavigationBodyTrace( |
| | 2 | 189 | | results, |
| | 2 | 190 | | GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry, |
| | 2 | 191 | | 0, |
| | 2 | 192 | | 0, |
| | 2 | 193 | | default); |
| | | 194 | | } |
| | | 195 | | |
| | 77 | 196 | | if (!TryExpandNavigationBodyBounds( |
| | 77 | 197 | | queryMin, |
| | 77 | 198 | | queryMax, |
| | 77 | 199 | | world.MaxTopologyCellEdge, |
| | 77 | 200 | | out Vector3d candidateMin, |
| | 77 | 201 | | out Vector3d candidateMax)) |
| | | 202 | | { |
| | 7 | 203 | | return FailNavigationBodyTrace( |
| | 7 | 204 | | results, |
| | 7 | 205 | | GridNavigationBodyTraceStatus.ArithmeticOverflow, |
| | 7 | 206 | | 0, |
| | 7 | 207 | | 0, |
| | 7 | 208 | | default); |
| | | 209 | | } |
| | | 210 | | |
| | 70 | 211 | | bool gridWorkLimitIsTighter = candidateWorkLimit < gridCandidateLimit; |
| | 70 | 212 | | int effectiveGridLimit = gridWorkLimitIsTighter |
| | 70 | 213 | | ? (int)candidateWorkLimit |
| | 70 | 214 | | : gridCandidateLimit; |
| | 70 | 215 | | if (!world.CollectGridCandidates( |
| | 70 | 216 | | candidateMin, |
| | 70 | 217 | | candidateMax, |
| | 70 | 218 | | scratch.CandidateGrids, |
| | 70 | 219 | | effectiveGridLimit)) |
| | | 220 | | { |
| | 5 | 221 | | return FailNavigationBodyTrace( |
| | 5 | 222 | | results, |
| | 5 | 223 | | gridWorkLimitIsTighter |
| | 5 | 224 | | ? GridNavigationBodyTraceStatus.CandidateWorkLimitExceeded |
| | 5 | 225 | | : GridNavigationBodyTraceStatus.GridCandidateLimitExceeded, |
| | 5 | 226 | | scratch.CandidateGrids.Count, |
| | 5 | 227 | | 0, |
| | 5 | 228 | | default); |
| | | 229 | | } |
| | | 230 | | |
| | 65 | 231 | | SortGridIndices(world, scratch.CandidateGrids); |
| | 65 | 232 | | long remainingWork = candidateWorkLimit - scratch.CandidateGrids.Count; |
| | 65 | 233 | | bool workLimitIsTighter = remainingWork < addressCandidateLimit; |
| | 65 | 234 | | int effectiveAddressLimit = workLimitIsTighter |
| | 65 | 235 | | ? (int)remainingWork |
| | 65 | 236 | | : addressCandidateLimit; |
| | 65 | 237 | | int addressCandidateCount = 0; |
| | 316 | 238 | | for (int gridOrdinal = 0; gridOrdinal < scratch.CandidateGrids.Count; gridOrdinal++) |
| | | 239 | | { |
| | 98 | 240 | | VoxelGrid grid = world.ActiveGrids[scratch.CandidateGrids[gridOrdinal]]; |
| | 98 | 241 | | if (excludedGridSpawnTokens != null && excludedGridSpawnTokens.Contains(grid.SpawnToken)) |
| | | 242 | | { |
| | 6 | 243 | | excludedGridCandidates?.Add(grid.Configuration.ToGridKey()); |
| | 4 | 244 | | continue; |
| | | 245 | | } |
| | 92 | 246 | | if (!TopologyVoxelRangeUtility.TryGetPrismCandidateRange( |
| | 92 | 247 | | grid, |
| | 92 | 248 | | queryMin, |
| | 92 | 249 | | queryMax, |
| | 92 | 250 | | out VoxelIndex minimum, |
| | 92 | 251 | | out VoxelIndex maximum)) |
| | | 252 | | { |
| | | 253 | | continue; |
| | | 254 | | } |
| | | 255 | | |
| | 590 | 256 | | for (int x = minimum.x; x <= maximum.x; x++) |
| | | 257 | | { |
| | 914 | 258 | | for (int y = minimum.y; y <= maximum.y; y++) |
| | | 259 | | { |
| | 1884 | 260 | | for (int z = minimum.z; z <= maximum.z; z++) |
| | | 261 | | { |
| | 693 | 262 | | if (addressCandidateCount >= effectiveAddressLimit) |
| | | 263 | | { |
| | 4 | 264 | | return FailNavigationBodyTrace( |
| | 4 | 265 | | results, |
| | 4 | 266 | | workLimitIsTighter |
| | 4 | 267 | | ? GridNavigationBodyTraceStatus.CandidateWorkLimitExceeded |
| | 4 | 268 | | : GridNavigationBodyTraceStatus.AddressLimitExceeded, |
| | 4 | 269 | | scratch.CandidateGrids.Count, |
| | 4 | 270 | | addressCandidateCount, |
| | 4 | 271 | | default); |
| | | 272 | | } |
| | | 273 | | |
| | 689 | 274 | | addressCandidateCount++; |
| | 689 | 275 | | VoxelIndex index = new(x, y, z); |
| | 689 | 276 | | WorldVoxelIndex cell = new( |
| | 689 | 277 | | world.SpawnToken, |
| | 689 | 278 | | grid.GridIndex, |
| | 689 | 279 | | grid.SpawnToken, |
| | 689 | 280 | | index); |
| | 689 | 281 | | if (!GridCellGeometry.TryCreatePrism( |
| | 689 | 282 | | grid.Configuration.TopologyKind, |
| | 689 | 283 | | grid.Configuration.TopologyMetrics, |
| | 689 | 284 | | grid.GetWorldPosition(index), |
| | 689 | 285 | | cell, |
| | 689 | 286 | | out GridCellPrism prism)) |
| | | 287 | | { |
| | 1 | 288 | | return FailNavigationBodyTrace( |
| | 1 | 289 | | results, |
| | 1 | 290 | | GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry, |
| | 1 | 291 | | scratch.CandidateGrids.Count, |
| | 1 | 292 | | addressCandidateCount, |
| | 1 | 293 | | default); |
| | | 294 | | } |
| | | 295 | | |
| | 688 | 296 | | bool hasPositiveOverlap = bodyBounds.Overlaps(prism.GetAabb(), Fixed64.Zero) |
| | 688 | 297 | | && GridCellGeometry.HasPositiveNavigationBodyPrismOverlap( |
| | 688 | 298 | | prism, |
| | 688 | 299 | | startFoot, |
| | 688 | 300 | | endFoot, |
| | 688 | 301 | | horizontalRadius, |
| | 688 | 302 | | bodyHeight); |
| | 688 | 303 | | bool isClosure = IsNavigationClosurePrism( |
| | 688 | 304 | | prism, |
| | 688 | 305 | | closurePrisms, |
| | 688 | 306 | | closureCount); |
| | 688 | 307 | | if (!hasPositiveOverlap && !isClosure) |
| | | 308 | | continue; |
| | | 309 | | |
| | 339 | 310 | | scratch.AddressCandidates.Add(new GridNavigationBodyTraceCandidate( |
| | 339 | 311 | | grid, |
| | 339 | 312 | | index, |
| | 339 | 313 | | prism, |
| | 339 | 314 | | hasPositiveOverlap, |
| | 339 | 315 | | isClosure)); |
| | | 316 | | } |
| | | 317 | | } |
| | | 318 | | } |
| | | 319 | | } |
| | | 320 | | |
| | 60 | 321 | | GridCoveredAddressRunStamp runStamp = SnapshotNavigationBodyCandidates( |
| | 60 | 322 | | world, |
| | 60 | 323 | | scratch.AddressCandidates); |
| | 60 | 324 | | scratch.AddressCandidates.SortInPlace( |
| | 60 | 325 | | default(GridNavigationBodyTraceCandidateComparer)); |
| | 60 | 326 | | if (!HasNavigationBodyUnionCoverage( |
| | 60 | 327 | | sourceGrid, |
| | 60 | 328 | | source.VoxelIndex, |
| | 60 | 329 | | targetGrid, |
| | 60 | 330 | | target.VoxelIndex, |
| | 60 | 331 | | startFoot, |
| | 60 | 332 | | endFoot, |
| | 60 | 333 | | horizontalRadius, |
| | 60 | 334 | | bodyHeight, |
| | 60 | 335 | | bodyBounds, |
| | 60 | 336 | | scratch.AddressCandidates, |
| | 60 | 337 | | scratch.UnionMembers)) |
| | | 338 | | { |
| | 2 | 339 | | return FailNavigationBodyTrace( |
| | 2 | 340 | | results, |
| | 2 | 341 | | GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry, |
| | 2 | 342 | | scratch.CandidateGrids.Count, |
| | 2 | 343 | | addressCandidateCount, |
| | 2 | 344 | | default); |
| | | 345 | | } |
| | 58 | 346 | | int alternativeEvidenceCount = CountMissingNavigationBodyAlternativeEvidence( |
| | 58 | 347 | | scratch.AddressCandidates, |
| | 58 | 348 | | sourceGrid, |
| | 58 | 349 | | source.VoxelIndex, |
| | 58 | 350 | | targetGrid, |
| | 58 | 351 | | target.VoxelIndex); |
| | 58 | 352 | | if (scratch.UnionMembers.Count > outputLimit |
| | 58 | 353 | | || alternativeEvidenceCount > outputLimit - scratch.UnionMembers.Count) |
| | | 354 | | { |
| | 2 | 355 | | return FailNavigationBodyTrace( |
| | 2 | 356 | | results, |
| | 2 | 357 | | GridNavigationBodyTraceStatus.OutputLimitExceeded, |
| | 2 | 358 | | scratch.CandidateGrids.Count, |
| | 2 | 359 | | addressCandidateCount, |
| | 2 | 360 | | default); |
| | | 361 | | } |
| | | 362 | | |
| | 56 | 363 | | bool hasMissingPhysicalCell = false; |
| | 610 | 364 | | for (int i = 0; i < scratch.UnionMembers.Count; i++) |
| | | 365 | | { |
| | 249 | 366 | | GridNavigationBodyTraceCandidate candidate = |
| | 249 | 367 | | scratch.AddressCandidates[scratch.UnionMembers[i]]; |
| | 249 | 368 | | hasMissingPhysicalCell |= !candidate.IsPhysicallyPresent; |
| | 249 | 369 | | results.Add(new GridNavigationBodyTraceCell( |
| | 249 | 370 | | new WorldVoxelIndex( |
| | 249 | 371 | | world.SpawnToken, |
| | 249 | 372 | | candidate.Grid.GridIndex, |
| | 249 | 373 | | candidate.Grid.SpawnToken, |
| | 249 | 374 | | candidate.Index), |
| | 249 | 375 | | candidate.Grid.Configuration.ToGridKey(), |
| | 249 | 376 | | candidate.IsPhysicallyPresent, |
| | 249 | 377 | | candidate.GridLastChangeSequence, |
| | 249 | 378 | | GridNavigationBodyTraceCellRole.RequiredCoverage)); |
| | | 379 | | } |
| | | 380 | | |
| | 56 | 381 | | if (hasMissingPhysicalCell) |
| | | 382 | | { |
| | 12 | 383 | | AppendMissingNavigationBodyAlternativeEvidence( |
| | 12 | 384 | | world, |
| | 12 | 385 | | scratch.AddressCandidates, |
| | 12 | 386 | | results, |
| | 12 | 387 | | sourceGrid, |
| | 12 | 388 | | source.VoxelIndex, |
| | 12 | 389 | | targetGrid, |
| | 12 | 390 | | target.VoxelIndex); |
| | | 391 | | } |
| | | 392 | | |
| | 56 | 393 | | results.SortInPlace(default(GridNavigationBodyTraceCellComparer)); |
| | 56 | 394 | | return CreateNavigationBodyTraceReport( |
| | 56 | 395 | | hasMissingPhysicalCell |
| | 56 | 396 | | ? GridNavigationBodyTraceStatus.IncompletePhysicalCoverage |
| | 56 | 397 | | : GridNavigationBodyTraceStatus.Complete, |
| | 56 | 398 | | scratch.CandidateGrids.Count, |
| | 56 | 399 | | addressCandidateCount, |
| | 56 | 400 | | results, |
| | 56 | 401 | | runStamp); |
| | | 402 | | } |
| | | 403 | | finally |
| | | 404 | | { |
| | 87 | 405 | | world.ExitReadLock(); |
| | 87 | 406 | | scratch.Clear(); |
| | 87 | 407 | | } |
| | 87 | 408 | | } |
| | | 409 | | |
| | | 410 | | private static bool HasClosedNavigationBodyPrismContact( |
| | | 411 | | in GridCellPrism prism, |
| | | 412 | | Vector3d foot, |
| | | 413 | | Fixed64 bodyTop, |
| | | 414 | | Fixed64 horizontalRadius) |
| | | 415 | | { |
| | 163 | 416 | | if (foot.Y > prism.VerticalMax || bodyTop < prism.VerticalMin) |
| | 1 | 417 | | return false; |
| | | 418 | | |
| | 162 | 419 | | Span<Vector2d> offsets = stackalloc Vector2d[6]; |
| | 162 | 420 | | Vector2d planarOrigin = new(prism.Center.X, prism.Center.Z); |
| | 1684 | 421 | | for (int i = 0; i < prism.FootprintVertexCount; i++) |
| | 680 | 422 | | offsets[i] = prism.GetFootprintVertex(i) - planarOrigin; |
| | | 423 | | |
| | 162 | 424 | | return FixedConvex2dRelations.TryGetCircleContact( |
| | 162 | 425 | | new Vector2d(foot.X, foot.Z), |
| | 162 | 426 | | Fixed64.Zero, |
| | 162 | 427 | | horizontalRadius, |
| | 162 | 428 | | planarOrigin, |
| | 162 | 429 | | Fixed64.Zero, |
| | 162 | 430 | | offsets[..prism.FootprintVertexCount], |
| | 162 | 431 | | out _, |
| | 162 | 432 | | out _, |
| | 162 | 433 | | out _, |
| | 162 | 434 | | out _, |
| | 162 | 435 | | out _); |
| | | 436 | | } |
| | | 437 | | |
| | | 438 | | private static int GetNavigationClosure( |
| | | 439 | | VoxelGrid sourceGrid, |
| | | 440 | | in GridCellPrism source, |
| | | 441 | | in GridCellPrism target, |
| | | 442 | | Span<GridCellPrism> closure) |
| | | 443 | | { |
| | 79 | 444 | | Span<VoxelIndex> offsets = stackalloc VoxelIndex[8]; |
| | 79 | 445 | | VoxelIndex targetOffset = default; |
| | 79 | 446 | | bool foundTarget = AreSameNavigationBodyPrism(source, target); |
| | 602 | 447 | | for (int slot = 0; !foundTarget && slot < sourceGrid.Topology.NeighborSlotCount; slot++) |
| | | 448 | | { |
| | 223 | 449 | | VoxelIndex offset = sourceGrid.Topology.GetNeighborOffset(slot); |
| | 223 | 450 | | if (!Vector3d.TryAdd( |
| | 223 | 451 | | source.Center, |
| | 223 | 452 | | sourceGrid.Topology.GetWorldOffset((offset.x, offset.y, offset.z)), |
| | 223 | 453 | | out Vector3d center) |
| | 223 | 454 | | || !GridCellGeometry.TryCreatePrism( |
| | 223 | 455 | | sourceGrid.Configuration.TopologyKind, |
| | 223 | 456 | | sourceGrid.Configuration.TopologyMetrics, |
| | 223 | 457 | | center, |
| | 223 | 458 | | default, |
| | 223 | 459 | | out GridCellPrism neighbor)) |
| | | 460 | | { |
| | 1 | 461 | | return 0; |
| | | 462 | | } |
| | 222 | 463 | | if (AreSameNavigationBodyPrism(neighbor, target)) |
| | | 464 | | { |
| | 25 | 465 | | targetOffset = offset; |
| | 25 | 466 | | foundTarget = true; |
| | | 467 | | } |
| | | 468 | | } |
| | 78 | 469 | | if (!foundTarget) |
| | 1 | 470 | | return 0; |
| | | 471 | | |
| | | 472 | | int closureCount; |
| | 77 | 473 | | if (targetOffset == default) |
| | | 474 | | { |
| | 52 | 475 | | offsets[0] = default; |
| | 52 | 476 | | closureCount = 1; |
| | | 477 | | } |
| | 25 | 478 | | else if (sourceGrid.Configuration.TopologyKind == GridTopologyKind.RectangularPrism) |
| | | 479 | | { |
| | 23 | 480 | | RectangularDirection direction = RectangularDirectionUtility.GetDirectionFromOffset( |
| | 23 | 481 | | (targetOffset.x, targetOffset.y, targetOffset.z)); |
| | 23 | 482 | | closureCount = RectangularDirectionUtility.CopyNavigationClosureOffsets(direction, offsets); |
| | | 483 | | } |
| | | 484 | | else |
| | | 485 | | { |
| | 2 | 486 | | closureCount = HexDirectionUtility.CopyNavigationClosureOffsets(targetOffset, offsets); |
| | | 487 | | } |
| | | 488 | | |
| | 418 | 489 | | for (int i = 0; i < closureCount; i++) |
| | | 490 | | { |
| | 132 | 491 | | VoxelIndex offset = offsets[i]; |
| | 132 | 492 | | bool usesTargetPlanarCoordinates = offset.x != 0 || offset.z != 0; |
| | 132 | 493 | | Vector3d center = sourceGrid.Configuration.TopologyKind == GridTopologyKind.RectangularPrism |
| | 132 | 494 | | ? new Vector3d( |
| | 132 | 495 | | offset.x == 0 ? source.Center.X : target.Center.X, |
| | 132 | 496 | | offset.y == 0 ? source.Center.Y : target.Center.Y, |
| | 132 | 497 | | offset.z == 0 ? source.Center.Z : target.Center.Z) |
| | 132 | 498 | | : new Vector3d( |
| | 132 | 499 | | usesTargetPlanarCoordinates ? target.Center.X : source.Center.X, |
| | 132 | 500 | | offset.y == 0 ? source.Center.Y : target.Center.Y, |
| | 132 | 501 | | usesTargetPlanarCoordinates ? target.Center.Z : source.Center.Z); |
| | | 502 | | |
| | | 503 | | // Every coordinate comes from one of the two already validated endpoint prisms. |
| | 132 | 504 | | _ = GridCellGeometry.TryCreatePrism( |
| | 132 | 505 | | sourceGrid.Configuration.TopologyKind, |
| | 132 | 506 | | sourceGrid.Configuration.TopologyMetrics, |
| | 132 | 507 | | center, |
| | 132 | 508 | | default, |
| | 132 | 509 | | out closure[i]); |
| | | 510 | | } |
| | | 511 | | |
| | 77 | 512 | | return closureCount; |
| | | 513 | | } |
| | | 514 | | |
| | | 515 | | private static bool IsNavigationClosurePrism( |
| | | 516 | | in GridCellPrism prism, |
| | | 517 | | ReadOnlySpan<GridCellPrism> closure, |
| | | 518 | | int count) |
| | | 519 | | { |
| | 9080 | 520 | | for (int i = 0; i < count; i++) |
| | | 521 | | { |
| | 2801 | 522 | | if (AreSameNavigationBodyPrism(prism, closure[i])) |
| | 433 | 523 | | return true; |
| | | 524 | | } |
| | | 525 | | |
| | 1739 | 526 | | return false; |
| | | 527 | | } |
| | | 528 | | |
| | | 529 | | private static GridCoveredAddressRunStamp SnapshotNavigationBodyCandidates( |
| | | 530 | | GridWorld world, |
| | | 531 | | SwiftList<GridNavigationBodyTraceCandidate> candidates) |
| | | 532 | | { |
| | | 533 | | GridCoveredAddressRunStamp runStamp; |
| | 261 | 534 | | lock (world.ChangeSyncRoot) |
| | | 535 | | { |
| | 261 | 536 | | runStamp = new GridCoveredAddressRunStamp( |
| | 261 | 537 | | world.SpawnToken, |
| | 261 | 538 | | world.Version, |
| | 261 | 539 | | world.ChangeSequence); |
| | 3932 | 540 | | for (int i = 0; i < candidates.Count; i++) |
| | | 541 | | { |
| | 1705 | 542 | | GridNavigationBodyTraceCandidate candidate = candidates[i]; |
| | 1705 | 543 | | bool isPresent = candidate.Grid.StorageKind == GridStorageKind.Dense |
| | 1705 | 544 | | || candidate.Grid.TryGetVoxel(candidate.Index, out _); |
| | 1705 | 545 | | candidates[i] = candidate.WithPhysicalEvidence( |
| | 1705 | 546 | | isPresent, |
| | 1705 | 547 | | candidate.Grid.LastChangeSequence); |
| | | 548 | | } |
| | 261 | 549 | | } |
| | | 550 | | |
| | 261 | 551 | | return runStamp; |
| | | 552 | | } |
| | | 553 | | |
| | | 554 | | private static bool TryCreateNavigationBodyBounds( |
| | | 555 | | Vector3d startFoot, |
| | | 556 | | Vector3d endFoot, |
| | | 557 | | Fixed64 startTop, |
| | | 558 | | Fixed64 endTop, |
| | | 559 | | Fixed64 radius, |
| | | 560 | | out Vector3d minimum, |
| | | 561 | | out Vector3d maximum) |
| | | 562 | | { |
| | 92 | 563 | | minimum = default; |
| | 92 | 564 | | maximum = default; |
| | 92 | 565 | | return Fixed64.TrySubtract(FixedMath.Min(startFoot.X, endFoot.X), radius, out Fixed64 minX) |
| | 92 | 566 | | && Fixed64.TrySubtract(FixedMath.Min(startFoot.Z, endFoot.Z), radius, out Fixed64 minZ) |
| | 92 | 567 | | && Fixed64.TryAdd(FixedMath.Max(startFoot.X, endFoot.X), radius, out Fixed64 maxX) |
| | 92 | 568 | | && Fixed64.TryAdd(FixedMath.Max(startFoot.Z, endFoot.Z), radius, out Fixed64 maxZ) |
| | 92 | 569 | | && AssignNavigationBodyBounds( |
| | 92 | 570 | | minX, |
| | 92 | 571 | | FixedMath.Min(startFoot.Y, endFoot.Y), |
| | 92 | 572 | | minZ, |
| | 92 | 573 | | maxX, |
| | 92 | 574 | | FixedMath.Max(startTop, endTop), |
| | 92 | 575 | | maxZ, |
| | 92 | 576 | | out minimum, |
| | 92 | 577 | | out maximum); |
| | | 578 | | } |
| | | 579 | | |
| | | 580 | | private static bool AssignNavigationBodyBounds( |
| | | 581 | | Fixed64 minX, |
| | | 582 | | Fixed64 minY, |
| | | 583 | | Fixed64 minZ, |
| | | 584 | | Fixed64 maxX, |
| | | 585 | | Fixed64 maxY, |
| | | 586 | | Fixed64 maxZ, |
| | | 587 | | out Vector3d minimum, |
| | | 588 | | out Vector3d maximum) |
| | | 589 | | { |
| | 87 | 590 | | minimum = new Vector3d(minX, minY, minZ); |
| | 87 | 591 | | maximum = new Vector3d(maxX, maxY, maxZ); |
| | 87 | 592 | | return true; |
| | | 593 | | } |
| | | 594 | | |
| | | 595 | | private static bool TryExpandNavigationBodyBounds( |
| | | 596 | | Vector3d minimum, |
| | | 597 | | Vector3d maximum, |
| | | 598 | | Fixed64 expansion, |
| | | 599 | | out Vector3d expandedMinimum, |
| | | 600 | | out Vector3d expandedMaximum) |
| | | 601 | | { |
| | 77 | 602 | | if (!Fixed64.TrySubtract(minimum.X, expansion, out Fixed64 minX) |
| | 77 | 603 | | || !Fixed64.TrySubtract(minimum.Y, expansion, out Fixed64 minY) |
| | 77 | 604 | | || !Fixed64.TrySubtract(minimum.Z, expansion, out Fixed64 minZ) |
| | 77 | 605 | | || !Fixed64.TryAdd(maximum.X, expansion, out Fixed64 maxX) |
| | 77 | 606 | | || !Fixed64.TryAdd(maximum.Y, expansion, out Fixed64 maxY) |
| | 77 | 607 | | || !Fixed64.TryAdd(maximum.Z, expansion, out Fixed64 maxZ)) |
| | | 608 | | { |
| | 7 | 609 | | expandedMinimum = default; |
| | 7 | 610 | | expandedMaximum = default; |
| | 7 | 611 | | return false; |
| | | 612 | | } |
| | | 613 | | |
| | 70 | 614 | | expandedMinimum = new Vector3d(minX, minY, minZ); |
| | 70 | 615 | | expandedMaximum = new Vector3d(maxX, maxY, maxZ); |
| | 70 | 616 | | return true; |
| | | 617 | | } |
| | | 618 | | |
| | | 619 | | private static bool HasNavigationBodyUnionCoverage( |
| | | 620 | | VoxelGrid sourceGrid, |
| | | 621 | | VoxelIndex source, |
| | | 622 | | VoxelGrid targetGrid, |
| | | 623 | | VoxelIndex target, |
| | | 624 | | Vector3d startFoot, |
| | | 625 | | Vector3d endFoot, |
| | | 626 | | Fixed64 horizontalRadius, |
| | | 627 | | Fixed64 bodyHeight, |
| | | 628 | | TopologyVoxelAabb bodyBounds, |
| | | 629 | | SwiftList<GridNavigationBodyTraceCandidate> candidates, |
| | | 630 | | SwiftList<int> unionMembers) |
| | | 631 | | { |
| | 60 | 632 | | int sourceCandidate = FindNavigationBodyCandidate(candidates, sourceGrid, source); |
| | 60 | 633 | | int targetCandidate = FindNavigationBodyCandidate(candidates, targetGrid, target); |
| | | 634 | | // A connected body intersects a connected set of interiors in the source topology's |
| | | 635 | | // exact lattice. Closing every positive-overlap neighbor therefore proves containment; |
| | | 636 | | // exact coincident prisms let aligned adjacent grids continue the same lattice. |
| | 60 | 637 | | AddNavigationBodyUnionMember(candidates, unionMembers, sourceCandidate); |
| | 60 | 638 | | if (targetCandidate != sourceCandidate |
| | 60 | 639 | | && AreSameNavigationBodyPrism( |
| | 60 | 640 | | candidates[sourceCandidate].Prism, |
| | 60 | 641 | | candidates[targetCandidate].Prism)) |
| | | 642 | | { |
| | 2 | 643 | | AddNavigationBodyUnionMember(candidates, unionMembers, targetCandidate); |
| | | 644 | | } |
| | 654 | 645 | | for (int memberOrdinal = 0; memberOrdinal < unionMembers.Count; memberOrdinal++) |
| | | 646 | | { |
| | 269 | 647 | | GridCellPrism member = candidates[unionMembers[memberOrdinal]].Prism; |
| | 14264 | 648 | | for (int slot = 0; slot < sourceGrid.Topology.NeighborSlotCount; slot++) |
| | | 649 | | { |
| | 6865 | 650 | | VoxelIndex offset = sourceGrid.Topology.GetNeighborOffset(slot); |
| | | 651 | | // Candidate bounds were expanded by the world's maximum topology edge, so every |
| | | 652 | | // immediate neighbor of a selected member is exactly representable here. |
| | 6865 | 653 | | _ = Vector3d.TryAdd( |
| | 6865 | 654 | | member.Center, |
| | 6865 | 655 | | sourceGrid.Topology.GetWorldOffset((offset.x, offset.y, offset.z)), |
| | 6865 | 656 | | out Vector3d neighborCenter); |
| | 6865 | 657 | | _ = GridCellGeometry.TryCreatePrism( |
| | 6865 | 658 | | sourceGrid.Configuration.TopologyKind, |
| | 6865 | 659 | | sourceGrid.Configuration.TopologyMetrics, |
| | 6865 | 660 | | neighborCenter, |
| | 6865 | 661 | | default, |
| | 6865 | 662 | | out GridCellPrism neighbor); |
| | | 663 | | |
| | 6865 | 664 | | int matchingCandidate = FindBestMatchingNavigationBodyPrism( |
| | 6865 | 665 | | candidates, |
| | 6865 | 666 | | neighbor, |
| | 6865 | 667 | | sourceCandidate, |
| | 6865 | 668 | | targetCandidate); |
| | 6865 | 669 | | bool overlapsBody = matchingCandidate >= 0 |
| | 6865 | 670 | | ? candidates[matchingCandidate].HasPositiveOverlap |
| | 6865 | 671 | | : bodyBounds.Overlaps(neighbor.GetAabb(), Fixed64.Zero) |
| | 6865 | 672 | | && GridCellGeometry.HasPositiveNavigationBodyPrismOverlap( |
| | 6865 | 673 | | neighbor, |
| | 6865 | 674 | | startFoot, |
| | 6865 | 675 | | endFoot, |
| | 6865 | 676 | | horizontalRadius, |
| | 6865 | 677 | | bodyHeight); |
| | 6865 | 678 | | if (overlapsBody && matchingCandidate < 0) |
| | 2 | 679 | | return false; |
| | 6863 | 680 | | if (matchingCandidate >= 0 |
| | 6863 | 681 | | && !candidates[matchingCandidate].IsVisited) |
| | | 682 | | { |
| | 207 | 683 | | AddNavigationBodyUnionMember(candidates, unionMembers, matchingCandidate); |
| | | 684 | | } |
| | | 685 | | } |
| | | 686 | | } |
| | | 687 | | |
| | 58 | 688 | | return true; |
| | | 689 | | } |
| | | 690 | | |
| | | 691 | | private static int FindNavigationBodyCandidate( |
| | | 692 | | SwiftList<GridNavigationBodyTraceCandidate> candidates, |
| | | 693 | | VoxelGrid grid, |
| | | 694 | | VoxelIndex index) |
| | | 695 | | { |
| | 1954 | 696 | | for (int i = 0; ; i++) |
| | | 697 | | { |
| | 1954 | 698 | | GridNavigationBodyTraceCandidate candidate = candidates[i]; |
| | 1954 | 699 | | if (candidate.Grid == grid && candidate.Index == index) |
| | 522 | 700 | | return i; |
| | | 701 | | } |
| | | 702 | | } |
| | | 703 | | |
| | | 704 | | private static int FindBestMatchingNavigationBodyPrism( |
| | | 705 | | SwiftList<GridNavigationBodyTraceCandidate> candidates, |
| | | 706 | | in GridCellPrism prism, |
| | | 707 | | int sourceCandidate, |
| | | 708 | | int targetCandidate) |
| | | 709 | | { |
| | 17686 | 710 | | if (AreSameNavigationBodyPrism(candidates[sourceCandidate].Prism, prism)) |
| | 1358 | 711 | | return sourceCandidate; |
| | 16328 | 712 | | if (AreSameNavigationBodyPrism(candidates[targetCandidate].Prism, prism)) |
| | 181 | 713 | | return targetCandidate; |
| | | 714 | | |
| | 16147 | 715 | | if (!FindNavigationBodyPrismRange(candidates, prism, out int start, out int end)) |
| | 11025 | 716 | | return -1; |
| | | 717 | | |
| | 5122 | 718 | | int best = start; |
| | 10566 | 719 | | for (int i = start + 1; i < end; i++) |
| | | 720 | | { |
| | 161 | 721 | | if (IsPreferredNavigationBodyCandidate(candidates[i], candidates[best])) |
| | 17 | 722 | | best = i; |
| | | 723 | | } |
| | | 724 | | |
| | 5122 | 725 | | return best; |
| | | 726 | | } |
| | | 727 | | |
| | | 728 | | private static bool IsPreferredNavigationBodyCandidate( |
| | | 729 | | GridNavigationBodyTraceCandidate candidate, |
| | | 730 | | GridNavigationBodyTraceCandidate current) |
| | | 731 | | { |
| | 161 | 732 | | if (candidate.IsPhysicallyPresent != current.IsPhysicallyPresent) |
| | 27 | 733 | | return candidate.IsPhysicallyPresent; |
| | | 734 | | |
| | 134 | 735 | | return CompareGridIdentity(candidate.Grid, current.Grid) < 0; |
| | | 736 | | } |
| | | 737 | | |
| | | 738 | | private static bool AreSameNavigationBodyPrism( |
| | | 739 | | in GridCellPrism first, |
| | 37706 | 740 | | in GridCellPrism second) => CompareNavigationBodyPrisms(first, second) == 0; |
| | | 741 | | |
| | | 742 | | private static int CompareNavigationBodyPrisms( |
| | | 743 | | in GridCellPrism first, |
| | | 744 | | in GridCellPrism second) |
| | | 745 | | { |
| | 117934 | 746 | | int comparison = (int)first.TopologyKind - (int)second.TopologyKind; |
| | 117934 | 747 | | if (comparison != 0) |
| | 42 | 748 | | return comparison; |
| | 117892 | 749 | | comparison = first.Center.X.CompareTo(second.Center.X); |
| | 117892 | 750 | | if (comparison != 0) |
| | 67697 | 751 | | return comparison; |
| | 50195 | 752 | | comparison = first.Center.Y.CompareTo(second.Center.Y); |
| | 50195 | 753 | | if (comparison != 0) |
| | 11322 | 754 | | return comparison; |
| | 38873 | 755 | | comparison = first.Center.Z.CompareTo(second.Center.Z); |
| | 38873 | 756 | | if (comparison != 0) |
| | 26012 | 757 | | return comparison; |
| | 12861 | 758 | | comparison = first.VerticalMin.CompareTo(second.VerticalMin); |
| | 12861 | 759 | | if (comparison != 0) |
| | 3 | 760 | | return comparison; |
| | 12858 | 761 | | comparison = first.PlanarInradius.CompareTo(second.PlanarInradius); |
| | 12858 | 762 | | if (comparison != 0) |
| | 3 | 763 | | return comparison; |
| | | 764 | | |
| | 129558 | 765 | | for (int i = 0; i < first.FootprintVertexCount; i++) |
| | | 766 | | { |
| | 51931 | 767 | | Vector2d firstVertex = first.GetFootprintVertex(i); |
| | 51931 | 768 | | Vector2d secondVertex = second.GetFootprintVertex(i); |
| | 51931 | 769 | | comparison = firstVertex.X.CompareTo(secondVertex.X); |
| | 51931 | 770 | | if (comparison != 0) |
| | 3 | 771 | | return comparison; |
| | 51928 | 772 | | comparison = firstVertex.Y.CompareTo(secondVertex.Y); |
| | 51928 | 773 | | if (comparison != 0) |
| | 4 | 774 | | return comparison; |
| | | 775 | | } |
| | | 776 | | |
| | 12848 | 777 | | return 0; |
| | | 778 | | } |
| | | 779 | | |
| | | 780 | | private static bool FindNavigationBodyPrismRange( |
| | | 781 | | SwiftList<GridNavigationBodyTraceCandidate> candidates, |
| | | 782 | | in GridCellPrism prism, |
| | | 783 | | out int start, |
| | | 784 | | out int end) |
| | | 785 | | { |
| | 16147 | 786 | | int low = 0; |
| | 16147 | 787 | | int high = candidates.Count; |
| | 68999 | 788 | | while (low < high) |
| | | 789 | | { |
| | 52852 | 790 | | int middle = low + ((high - low) >> 1); |
| | 52852 | 791 | | if (CompareNavigationBodyPrisms(candidates[middle].Prism, prism) < 0) |
| | 21493 | 792 | | low = middle + 1; |
| | | 793 | | else |
| | 31359 | 794 | | high = middle; |
| | | 795 | | } |
| | | 796 | | |
| | 16147 | 797 | | start = low; |
| | 16147 | 798 | | if (start >= candidates.Count |
| | 16147 | 799 | | || CompareNavigationBodyPrisms(candidates[start].Prism, prism) != 0) |
| | | 800 | | { |
| | 11025 | 801 | | end = start; |
| | 11025 | 802 | | return false; |
| | | 803 | | } |
| | | 804 | | |
| | 5122 | 805 | | low = start + 1; |
| | 5122 | 806 | | high = candidates.Count; |
| | 16699 | 807 | | while (low < high) |
| | | 808 | | { |
| | 11577 | 809 | | int middle = low + ((high - low) >> 1); |
| | 11577 | 810 | | if (CompareNavigationBodyPrisms(candidates[middle].Prism, prism) <= 0) |
| | 161 | 811 | | low = middle + 1; |
| | | 812 | | else |
| | 11416 | 813 | | high = middle; |
| | | 814 | | } |
| | | 815 | | |
| | 5122 | 816 | | end = low; |
| | 5122 | 817 | | return true; |
| | | 818 | | } |
| | | 819 | | |
| | | 820 | | private static void AddNavigationBodyUnionMember( |
| | | 821 | | SwiftList<GridNavigationBodyTraceCandidate> candidates, |
| | | 822 | | SwiftList<int> unionMembers, |
| | | 823 | | int candidateIndex) |
| | | 824 | | { |
| | 1647 | 825 | | candidates[candidateIndex] = candidates[candidateIndex].WithVisited(); |
| | 1647 | 826 | | unionMembers.Add(candidateIndex); |
| | 1647 | 827 | | } |
| | | 828 | | |
| | | 829 | | private static void AppendMissingNavigationBodyAlternativeEvidence( |
| | | 830 | | GridWorld world, |
| | | 831 | | SwiftList<GridNavigationBodyTraceCandidate> candidates, |
| | | 832 | | SwiftList<GridNavigationBodyTraceCell> results, |
| | | 833 | | VoxelGrid sourceGrid, |
| | | 834 | | VoxelIndex source, |
| | | 835 | | VoxelGrid targetGrid, |
| | | 836 | | VoxelIndex target) |
| | | 837 | | { |
| | 124 | 838 | | for (int start = 0; start < candidates.Count;) |
| | | 839 | | { |
| | 86 | 840 | | int end = GetNavigationBodyPrismGroupEnd(candidates, start); |
| | 86 | 841 | | if (!IsMissingNavigationBodyAlternativeGroup( |
| | 86 | 842 | | candidates, |
| | 86 | 843 | | start, |
| | 86 | 844 | | end, |
| | 86 | 845 | | sourceGrid, |
| | 86 | 846 | | source, |
| | 86 | 847 | | targetGrid, |
| | 86 | 848 | | target)) |
| | | 849 | | { |
| | 69 | 850 | | start = end; |
| | 69 | 851 | | continue; |
| | | 852 | | } |
| | | 853 | | |
| | 74 | 854 | | for (int candidateIndex = start; candidateIndex < end; candidateIndex++) |
| | | 855 | | { |
| | 20 | 856 | | GridNavigationBodyTraceCandidate candidate = candidates[candidateIndex]; |
| | 20 | 857 | | if (candidate.IsVisited) |
| | | 858 | | continue; |
| | | 859 | | |
| | 3 | 860 | | candidates[candidateIndex] = candidate.WithVisited(); |
| | 3 | 861 | | results.Add(new GridNavigationBodyTraceCell( |
| | 3 | 862 | | new WorldVoxelIndex( |
| | 3 | 863 | | world.SpawnToken, |
| | 3 | 864 | | candidate.Grid.GridIndex, |
| | 3 | 865 | | candidate.Grid.SpawnToken, |
| | 3 | 866 | | candidate.Index), |
| | 3 | 867 | | candidate.Grid.Configuration.ToGridKey(), |
| | 3 | 868 | | isPhysicallyPresent: false, |
| | 3 | 869 | | candidate.GridLastChangeSequence, |
| | 3 | 870 | | GridNavigationBodyTraceCellRole.PhysicalAlternativeDependency)); |
| | | 871 | | } |
| | | 872 | | |
| | 17 | 873 | | start = end; |
| | | 874 | | } |
| | 19 | 875 | | } |
| | | 876 | | |
| | | 877 | | private static int CountMissingNavigationBodyAlternativeEvidence( |
| | | 878 | | SwiftList<GridNavigationBodyTraceCandidate> candidates, |
| | | 879 | | VoxelGrid sourceGrid, |
| | | 880 | | VoxelIndex source, |
| | | 881 | | VoxelGrid targetGrid, |
| | | 882 | | VoxelIndex target) |
| | | 883 | | { |
| | 255 | 884 | | int count = 0; |
| | 2145 | 885 | | for (int start = 0; start < candidates.Count;) |
| | | 886 | | { |
| | 1635 | 887 | | int end = GetNavigationBodyPrismGroupEnd(candidates, start); |
| | 1635 | 888 | | if (IsMissingNavigationBodyAlternativeGroup( |
| | 1635 | 889 | | candidates, |
| | 1635 | 890 | | start, |
| | 1635 | 891 | | end, |
| | 1635 | 892 | | sourceGrid, |
| | 1635 | 893 | | source, |
| | 1635 | 894 | | targetGrid, |
| | 1635 | 895 | | target)) |
| | | 896 | | { |
| | 80 | 897 | | for (int candidateIndex = start; candidateIndex < end; candidateIndex++) |
| | 22 | 898 | | count += candidates[candidateIndex].IsVisited ? 0 : 1; |
| | | 899 | | } |
| | | 900 | | |
| | 1635 | 901 | | start = end; |
| | | 902 | | } |
| | | 903 | | |
| | 255 | 904 | | return count; |
| | | 905 | | } |
| | | 906 | | |
| | | 907 | | private static int GetNavigationBodyPrismGroupEnd( |
| | | 908 | | SwiftList<GridNavigationBodyTraceCandidate> candidates, |
| | | 909 | | int start) |
| | | 910 | | { |
| | 1721 | 911 | | GridCellPrism prism = candidates[start].Prism; |
| | 1721 | 912 | | int end = start + 1; |
| | 1778 | 913 | | while (end < candidates.Count |
| | 1778 | 914 | | && CompareNavigationBodyPrisms(candidates[end].Prism, prism) == 0) |
| | | 915 | | { |
| | 57 | 916 | | end++; |
| | | 917 | | } |
| | | 918 | | |
| | 1721 | 919 | | return end; |
| | | 920 | | } |
| | | 921 | | |
| | | 922 | | private static bool IsMissingNavigationBodyAlternativeGroup( |
| | | 923 | | SwiftList<GridNavigationBodyTraceCandidate> candidates, |
| | | 924 | | int start, |
| | | 925 | | int end, |
| | | 926 | | VoxelGrid sourceGrid, |
| | | 927 | | VoxelIndex source, |
| | | 928 | | VoxelGrid targetGrid, |
| | | 929 | | VoxelIndex target) |
| | | 930 | | { |
| | 1721 | 931 | | bool hasMissingSelectedNonEndpoint = false; |
| | 3542 | 932 | | for (int candidateIndex = start; candidateIndex < end; candidateIndex++) |
| | | 933 | | { |
| | 1732 | 934 | | GridNavigationBodyTraceCandidate candidate = candidates[candidateIndex]; |
| | 1732 | 935 | | if (candidate.IsPhysicallyPresent) |
| | 1682 | 936 | | return false; |
| | 50 | 937 | | hasMissingSelectedNonEndpoint |= candidate.IsVisited |
| | 50 | 938 | | && !IsNavigationBodyEndpoint( |
| | 50 | 939 | | candidate, |
| | 50 | 940 | | sourceGrid, |
| | 50 | 941 | | source, |
| | 50 | 942 | | targetGrid, |
| | 50 | 943 | | target); |
| | | 944 | | } |
| | | 945 | | |
| | 39 | 946 | | return hasMissingSelectedNonEndpoint; |
| | | 947 | | } |
| | | 948 | | |
| | | 949 | | private static bool IsNavigationBodyEndpoint( |
| | | 950 | | GridNavigationBodyTraceCandidate candidate, |
| | | 951 | | VoxelGrid sourceGrid, |
| | | 952 | | VoxelIndex source, |
| | | 953 | | VoxelGrid targetGrid, |
| | | 954 | | VoxelIndex target) => |
| | 39 | 955 | | (candidate.Grid == sourceGrid && candidate.Index == source) |
| | 39 | 956 | | || (candidate.Grid == targetGrid && candidate.Index == target); |
| | | 957 | | |
| | | 958 | | private static GridNavigationBodyTraceReport CreateNavigationBodyTraceReport( |
| | | 959 | | GridNavigationBodyTraceStatus status, |
| | | 960 | | int gridCandidateCount, |
| | | 961 | | int addressCandidateCount, |
| | | 962 | | SwiftList<GridNavigationBodyTraceCell> results, |
| | | 963 | | GridCoveredAddressRunStamp runStamp) => |
| | 471 | 964 | | new( |
| | 471 | 965 | | status, |
| | 471 | 966 | | gridCandidateCount, |
| | 471 | 967 | | addressCandidateCount, |
| | 471 | 968 | | gridCandidateCount + (long)addressCandidateCount, |
| | 471 | 969 | | results.Count, |
| | 471 | 970 | | runStamp); |
| | | 971 | | |
| | | 972 | | private static GridNavigationBodyTraceReport FailNavigationBodyTrace( |
| | | 973 | | SwiftList<GridNavigationBodyTraceCell> results, |
| | | 974 | | GridNavigationBodyTraceStatus status, |
| | | 975 | | int gridCandidateCount, |
| | | 976 | | int addressCandidateCount, |
| | | 977 | | GridCoveredAddressRunStamp runStamp) |
| | | 978 | | { |
| | 196 | 979 | | results.Clear(); |
| | 196 | 980 | | return CreateNavigationBodyTraceReport( |
| | 196 | 981 | | status, |
| | 196 | 982 | | gridCandidateCount, |
| | 196 | 983 | | addressCandidateCount, |
| | 196 | 984 | | results, |
| | 196 | 985 | | runStamp); |
| | | 986 | | } |
| | | 987 | | |
| | | 988 | | private readonly struct GridNavigationBodyTraceCandidateComparer : |
| | | 989 | | IComparer<GridNavigationBodyTraceCandidate> |
| | | 990 | | { |
| | | 991 | | public int Compare( |
| | | 992 | | GridNavigationBodyTraceCandidate first, |
| | | 993 | | GridNavigationBodyTraceCandidate second) => |
| | 1673 | 994 | | CompareNavigationBodyPrisms(first.Prism, second.Prism); |
| | | 995 | | } |
| | | 996 | | |
| | | 997 | | private readonly struct GridNavigationBodyTraceCellComparer : |
| | | 998 | | IComparer<GridNavigationBodyTraceCell> |
| | | 999 | | { |
| | | 1000 | | public int Compare( |
| | | 1001 | | GridNavigationBodyTraceCell first, |
| | | 1002 | | GridNavigationBodyTraceCell second) => |
| | 3093 | 1003 | | CompareNavigationBodyTraceCells(first, second); |
| | | 1004 | | } |
| | | 1005 | | |
| | | 1006 | | private static int CompareNavigationBodyTraceCells( |
| | | 1007 | | GridNavigationBodyTraceCell first, |
| | | 1008 | | GridNavigationBodyTraceCell second) |
| | | 1009 | | { |
| | 3093 | 1010 | | int comparison = CompareConfigurationKeys(first.ConfigurationKey, second.ConfigurationKey); |
| | 3093 | 1011 | | return comparison != 0 |
| | 3093 | 1012 | | ? comparison |
| | 3093 | 1013 | | : first.Cell.VoxelIndex.CompareTo(second.Cell.VoxelIndex); |
| | | 1014 | | } |
| | | 1015 | | } |