diff options
Diffstat (limited to 'Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs')
18 files changed, 1046 insertions, 0 deletions
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildNodes.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildNodes.cs new file mode 100644 index 0000000..841c86d --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildNodes.cs @@ -0,0 +1,92 @@ +using Pathfinding.Jobs; +using Pathfinding.Util; +using Unity.Collections; +using Unity.Jobs; +using UnityEngine; +using UnityEngine.Profiling; + +namespace Pathfinding.Graphs.Navmesh.Jobs { + /// <summary> + /// Builds nodes and tiles and prepares them for pathfinding. + /// + /// Takes input from a <see cref="TileBuilder"/> job and outputs a <see cref="BuildNodeTilesOutput"/>. + /// + /// This job takes the following steps: + /// - Calculate connections between nodes inside each tile + /// - Create node and tile objects + /// - Connect adjacent tiles together + /// </summary> + public struct JobBuildNodes { + AstarPath astar; + uint graphIndex; + public uint initialPenalty; + public bool recalculateNormals; + public float maxTileConnectionEdgeDistance; + Matrix4x4 graphToWorldSpace; + TileLayout tileLayout; + + public class BuildNodeTilesOutput : IProgress, System.IDisposable { + public TileBuilder.TileBuilderOutput dependency; + public NavmeshTile[] tiles; + + public float Progress => dependency.Progress; + + public void Dispose () { + } + } + + internal JobBuildNodes(RecastGraph graph, TileLayout tileLayout) { + this.astar = graph.active; + this.tileLayout = tileLayout; + this.graphIndex = graph.graphIndex; + this.initialPenalty = graph.initialPenalty; + this.recalculateNormals = graph.RecalculateNormals; + this.maxTileConnectionEdgeDistance = graph.MaxTileConnectionEdgeDistance; + this.graphToWorldSpace = tileLayout.transform.matrix; + } + + public Promise<BuildNodeTilesOutput> Schedule (DisposeArena arena, Promise<TileBuilder.TileBuilderOutput> dependency) { + var input = dependency.GetValue(); + var tileRect = input.tileMeshes.tileRect; + UnityEngine.Assertions.Assert.AreEqual(input.tileMeshes.tileMeshes.Length, tileRect.Area); + var tiles = new NavmeshTile[tileRect.Area]; + var tilesGCHandle = System.Runtime.InteropServices.GCHandle.Alloc(tiles); + var nodeConnections = new NativeArray<JobCalculateTriangleConnections.TileNodeConnectionsUnsafe>(tileRect.Area, Allocator.Persistent); + + var calculateConnectionsJob = new JobCalculateTriangleConnections { + tileMeshes = input.tileMeshes.tileMeshes, + nodeConnections = nodeConnections, + }.Schedule(dependency.handle); + + var tileWorldSize = new Vector2(tileLayout.TileWorldSizeX, tileLayout.TileWorldSizeZ); + var createTilesJob = new JobCreateTiles { + tileMeshes = input.tileMeshes.tileMeshes, + tiles = tilesGCHandle, + tileRect = tileRect, + graphTileCount = tileLayout.tileCount, + graphIndex = graphIndex, + initialPenalty = initialPenalty, + recalculateNormals = recalculateNormals, + graphToWorldSpace = this.graphToWorldSpace, + tileWorldSize = tileWorldSize, + }.Schedule(dependency.handle); + + var applyConnectionsJob = new JobWriteNodeConnections { + nodeConnections = nodeConnections, + tiles = tilesGCHandle, + }.Schedule(JobHandle.CombineDependencies(calculateConnectionsJob, createTilesJob)); + + Profiler.BeginSample("Scheduling ConnectTiles"); + var connectTilesDependency = JobConnectTiles.ScheduleBatch(tilesGCHandle, applyConnectionsJob, tileRect, tileWorldSize, maxTileConnectionEdgeDistance); + Profiler.EndSample(); + + arena.Add(tilesGCHandle); + arena.Add(nodeConnections); + + return new Promise<BuildNodeTilesOutput>(connectTilesDependency, new BuildNodeTilesOutput { + dependency = input, + tiles = tiles, + }); + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildNodes.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildNodes.cs.meta new file mode 100644 index 0000000..c8446f5 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildNodes.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: bd51eca97d285874d997d22edd420a27 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVertices.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVertices.cs new file mode 100644 index 0000000..f68ed2b --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVertices.cs @@ -0,0 +1,105 @@ +using Pathfinding.Util; +using Unity.Burst; +using Unity.Collections; +using Unity.Collections.LowLevel.Unsafe; +using Unity.Jobs; +using UnityEngine; + +namespace Pathfinding.Graphs.Navmesh.Jobs { + /// <summary> + /// Builds tiles from raw mesh vertices and indices. + /// + /// This job takes the following steps: + /// - Transform all vertices using the <see cref="meshToGraph"/> matrix. + /// - Remove duplicate vertices + /// - If <see cref="recalculateNormals"/> is enabled: ensure all triangles are laid out in the clockwise direction. + /// </summary> + [BurstCompile(FloatMode = FloatMode.Default)] + public struct JobBuildTileMeshFromVertices : IJob { + public NativeArray<Vector3> vertices; + public NativeArray<int> indices; + public Matrix4x4 meshToGraph; + public NativeArray<TileMesh.TileMeshUnsafe> outputBuffers; + public bool recalculateNormals; + + + [BurstCompile(FloatMode = FloatMode.Fast)] + public struct JobTransformTileCoordinates : IJob { + public NativeArray<Vector3> vertices; + public NativeArray<Int3> outputVertices; + public Matrix4x4 matrix; + + public void Execute () { + for (int i = 0; i < vertices.Length; i++) { + outputVertices[i] = (Int3)matrix.MultiplyPoint3x4(vertices[i]); + } + } + } + + public struct BuildNavmeshOutput : IProgress, System.IDisposable { + public NativeArray<TileMesh.TileMeshUnsafe> tiles; + + public float Progress => 0.0f; + + public void Dispose () { + for (int i = 0; i < tiles.Length; i++) tiles[i].Dispose(); + tiles.Dispose(); + } + } + + public static Promise<BuildNavmeshOutput> Schedule (NativeArray<Vector3> vertices, NativeArray<int> indices, Matrix4x4 meshToGraph, bool recalculateNormals) { + if (vertices.Length > NavmeshBase.VertexIndexMask) throw new System.ArgumentException("Too many vertices in the navmesh graph. Provided " + vertices.Length + ", but the maximum number of vertices per tile is " + NavmeshBase.VertexIndexMask + ". You can raise this limit by enabling ASTAR_RECAST_LARGER_TILES in the A* Inspector Optimizations tab"); + + var outputBuffers = new NativeArray<TileMesh.TileMeshUnsafe>(1, Allocator.Persistent); + + var job = new JobBuildTileMeshFromVertices { + vertices = vertices, + indices = indices, + meshToGraph = meshToGraph, + outputBuffers = outputBuffers, + recalculateNormals = recalculateNormals, + }.Schedule(); + return new Promise<BuildNavmeshOutput>(job, new BuildNavmeshOutput { + tiles = outputBuffers, + }); + } + + public void Execute () { + var int3vertices = new NativeArray<Int3>(vertices.Length, Allocator.Temp); + var tags = new NativeArray<int>(indices.Length / 3, Allocator.Temp, NativeArrayOptions.ClearMemory); + + new JobTransformTileCoordinates { + vertices = vertices, + outputVertices = int3vertices, + matrix = meshToGraph, + }.Execute(); + + unsafe { + UnityEngine.Assertions.Assert.IsTrue(this.outputBuffers.Length == 1); + var tile = (TileMesh.TileMeshUnsafe*) this.outputBuffers.GetUnsafePtr(); + var outputVertices = &tile->verticesInTileSpace; + var outputTriangles = &tile->triangles; + var outputTags = &tile->tags; + *outputVertices = new UnsafeAppendBuffer(0, 4, Allocator.Persistent); + *outputTriangles = new UnsafeAppendBuffer(0, 4, Allocator.Persistent); + *outputTags = new UnsafeAppendBuffer(0, 4, Allocator.Persistent); + new MeshUtility.JobRemoveDuplicateVertices { + vertices = int3vertices, + triangles = indices, + tags = tags, + outputVertices = outputVertices, + outputTriangles = outputTriangles, + outputTags = outputTags, + }.Execute(); + + if (recalculateNormals) { + var verticesSpan = outputVertices->AsUnsafeSpan<Int3>(); + var trianglesSpan = outputTriangles->AsUnsafeSpan<int>(); + MeshUtility.MakeTrianglesClockwise(ref verticesSpan, ref trianglesSpan); + } + } + + int3vertices.Dispose(); + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVertices.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVertices.cs.meta new file mode 100644 index 0000000..b7f6886 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVertices.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: a22b53fa064d9344988e2a86b73851b1 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs new file mode 100644 index 0000000..a6ca868 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs @@ -0,0 +1,288 @@ +using Pathfinding.Jobs; +using Pathfinding.Util; +using Pathfinding.Graphs.Navmesh.Voxelization.Burst; +using Unity.Burst; +using Unity.Collections; +using Unity.Collections.LowLevel.Unsafe; +using Unity.Jobs; +using UnityEngine; +using Unity.Profiling; + +namespace Pathfinding.Graphs.Navmesh.Jobs { + /// <summary> + /// Scratch space for building navmesh tiles using voxelization. + /// + /// This uses quite a lot of memory, so it is used by a single worker thread for multiple tiles in order to minimize allocations. + /// </summary> + public struct TileBuilderBurst : IArenaDisposable { + public LinkedVoxelField linkedVoxelField; + public CompactVoxelField compactVoxelField; + public NativeList<ushort> distanceField; + public NativeQueue<Int3> tmpQueue1; + public NativeQueue<Int3> tmpQueue2; + public NativeList<VoxelContour> contours; + public NativeList<int> contourVertices; + public VoxelMesh voxelMesh; + + public TileBuilderBurst (int width, int depth, int voxelWalkableHeight, int maximumVoxelYCoord) { + linkedVoxelField = new LinkedVoxelField(width, depth, maximumVoxelYCoord); + compactVoxelField = new CompactVoxelField(width, depth, voxelWalkableHeight, Allocator.Persistent); + tmpQueue1 = new NativeQueue<Int3>(Allocator.Persistent); + tmpQueue2 = new NativeQueue<Int3>(Allocator.Persistent); + distanceField = new NativeList<ushort>(0, Allocator.Persistent); + contours = new NativeList<VoxelContour>(Allocator.Persistent); + contourVertices = new NativeList<int>(Allocator.Persistent); + voxelMesh = new VoxelMesh { + verts = new NativeList<Int3>(Allocator.Persistent), + tris = new NativeList<int>(Allocator.Persistent), + areas = new NativeList<int>(Allocator.Persistent), + }; + } + + void IArenaDisposable.DisposeWith (DisposeArena arena) { + arena.Add(linkedVoxelField); + arena.Add(compactVoxelField); + arena.Add(distanceField); + arena.Add(tmpQueue1); + arena.Add(tmpQueue2); + arena.Add(contours); + arena.Add(contourVertices); + arena.Add(voxelMesh); + } + } + + /// <summary> + /// Builds tiles from a polygon soup using voxelization. + /// + /// This job takes the following steps: + /// - Voxelize the input meshes + /// - Filter and process the resulting voxelization in various ways to remove unwanted artifacts and make it better suited for pathfinding. + /// - Extract a walkable surface from the voxelization. + /// - Triangulate this surface and create navmesh tiles from it. + /// + /// This job uses work stealing to distribute the work between threads. The communication happens using a shared queue and the <see cref="currentTileCounter"/> atomic variable. + /// </summary> + [BurstCompile(CompileSynchronously = true)] + // TODO: [BurstCompile(FloatMode = FloatMode.Fast)] + public struct JobBuildTileMeshFromVoxels : IJob { + public TileBuilderBurst tileBuilder; + [ReadOnly] + public TileBuilder.BucketMapping inputMeshes; + [ReadOnly] + public NativeArray<Bounds> tileGraphSpaceBounds; + public Matrix4x4 voxelToTileSpace; + + /// <summary> + /// Limits of the graph space bounds for the whole graph on the XZ plane. + /// + /// Used to crop the border tiles to exactly the limits of the graph's bounding box. + /// </summary> + public Vector2 graphSpaceLimits; + + [NativeDisableUnsafePtrRestriction] + public unsafe TileMesh.TileMeshUnsafe* outputMeshes; + + /// <summary>Max number of tiles to process in this job</summary> + public int maxTiles; + + public int voxelWalkableClimb; + public uint voxelWalkableHeight; + public float cellSize; + public float cellHeight; + public float maxSlope; + public RecastGraph.DimensionMode dimensionMode; + public RecastGraph.BackgroundTraversability backgroundTraversability; + public Matrix4x4 graphToWorldSpace; + public int characterRadiusInVoxels; + public int tileBorderSizeInVoxels; + public int minRegionSize; + public float maxEdgeLength; + public float contourMaxError; + [ReadOnly] + public NativeArray<JobBuildRegions.RelevantGraphSurfaceInfo> relevantGraphSurfaces; + public RecastGraph.RelevantGraphSurfaceMode relevantGraphSurfaceMode; + + [NativeDisableUnsafePtrRestriction] + public unsafe int* currentTileCounter; + + public void SetOutputMeshes (NativeArray<TileMesh.TileMeshUnsafe> arr) { + unsafe { + outputMeshes = (TileMesh.TileMeshUnsafe*)arr.GetUnsafeReadOnlyPtr(); + } + } + + public void SetCounter (NativeReference<int> counter) { + unsafe { + // Note: The pointer cast is only necessary when using early versions of the collections package. + currentTileCounter = (int*)counter.GetUnsafePtr(); + } + } + + private static readonly ProfilerMarker MarkerVoxelize = new ProfilerMarker("Voxelize"); + private static readonly ProfilerMarker MarkerFilterLedges = new ProfilerMarker("FilterLedges"); + private static readonly ProfilerMarker MarkerFilterLowHeightSpans = new ProfilerMarker("FilterLowHeightSpans"); + private static readonly ProfilerMarker MarkerBuildCompactField = new ProfilerMarker("BuildCompactField"); + private static readonly ProfilerMarker MarkerBuildConnections = new ProfilerMarker("BuildConnections"); + private static readonly ProfilerMarker MarkerErodeWalkableArea = new ProfilerMarker("ErodeWalkableArea"); + private static readonly ProfilerMarker MarkerBuildDistanceField = new ProfilerMarker("BuildDistanceField"); + private static readonly ProfilerMarker MarkerBuildRegions = new ProfilerMarker("BuildRegions"); + private static readonly ProfilerMarker MarkerBuildContours = new ProfilerMarker("BuildContours"); + private static readonly ProfilerMarker MarkerBuildMesh = new ProfilerMarker("BuildMesh"); + private static readonly ProfilerMarker MarkerConvertAreasToTags = new ProfilerMarker("ConvertAreasToTags"); + private static readonly ProfilerMarker MarkerRemoveDuplicateVertices = new ProfilerMarker("RemoveDuplicateVertices"); + private static readonly ProfilerMarker MarkerTransformTileCoordinates = new ProfilerMarker("TransformTileCoordinates"); + + public void Execute () { + for (int k = 0; k < maxTiles; k++) { + // Grab the next tile index that we should calculate + int i; + unsafe { + i = System.Threading.Interlocked.Increment(ref UnsafeUtility.AsRef<int>(currentTileCounter)) - 1; + } + if (i >= tileGraphSpaceBounds.Length) return; + + tileBuilder.linkedVoxelField.ResetLinkedVoxelSpans(); + if (dimensionMode == RecastGraph.DimensionMode.Dimension2D && backgroundTraversability == RecastGraph.BackgroundTraversability.Walkable) { + tileBuilder.linkedVoxelField.SetWalkableBackground(); + } + + var bucketStart = i > 0 ? inputMeshes.bucketRanges[i-1] : 0; + var bucketEnd = inputMeshes.bucketRanges[i]; + MarkerVoxelize.Begin(); + new JobVoxelize { + inputMeshes = inputMeshes.meshes, + bucket = inputMeshes.pointers.GetSubArray(bucketStart, bucketEnd - bucketStart), + voxelWalkableClimb = voxelWalkableClimb, + voxelWalkableHeight = voxelWalkableHeight, + cellSize = cellSize, + cellHeight = cellHeight, + maxSlope = maxSlope, + graphTransform = graphToWorldSpace, + graphSpaceBounds = tileGraphSpaceBounds[i], + graphSpaceLimits = graphSpaceLimits, + voxelArea = tileBuilder.linkedVoxelField, + }.Execute(); + MarkerVoxelize.End(); + + + + MarkerFilterLedges.Begin(); + new JobFilterLedges { + field = tileBuilder.linkedVoxelField, + voxelWalkableClimb = voxelWalkableClimb, + voxelWalkableHeight = voxelWalkableHeight, + cellSize = cellSize, + cellHeight = cellHeight, + }.Execute(); + MarkerFilterLedges.End(); + + MarkerFilterLowHeightSpans.Begin(); + new JobFilterLowHeightSpans { + field = tileBuilder.linkedVoxelField, + voxelWalkableHeight = voxelWalkableHeight, + }.Execute(); + MarkerFilterLowHeightSpans.End(); + + MarkerBuildCompactField.Begin(); + new JobBuildCompactField { + input = tileBuilder.linkedVoxelField, + output = tileBuilder.compactVoxelField, + }.Execute(); + MarkerBuildCompactField.End(); + + MarkerBuildConnections.Begin(); + new JobBuildConnections { + field = tileBuilder.compactVoxelField, + voxelWalkableHeight = (int)voxelWalkableHeight, + voxelWalkableClimb = voxelWalkableClimb, + }.Execute(); + MarkerBuildConnections.End(); + + MarkerErodeWalkableArea.Begin(); + new JobErodeWalkableArea { + field = tileBuilder.compactVoxelField, + radius = characterRadiusInVoxels, + }.Execute(); + MarkerErodeWalkableArea.End(); + + MarkerBuildDistanceField.Begin(); + new JobBuildDistanceField { + field = tileBuilder.compactVoxelField, + output = tileBuilder.distanceField, + }.Execute(); + MarkerBuildDistanceField.End(); + + MarkerBuildRegions.Begin(); + new JobBuildRegions { + field = tileBuilder.compactVoxelField, + distanceField = tileBuilder.distanceField, + borderSize = tileBorderSizeInVoxels, + minRegionSize = Mathf.RoundToInt(minRegionSize), + srcQue = tileBuilder.tmpQueue1, + dstQue = tileBuilder.tmpQueue2, + relevantGraphSurfaces = relevantGraphSurfaces, + relevantGraphSurfaceMode = relevantGraphSurfaceMode, + cellSize = cellSize, + cellHeight = cellHeight, + graphTransform = graphToWorldSpace, + graphSpaceBounds = tileGraphSpaceBounds[i], + }.Execute(); + MarkerBuildRegions.End(); + + MarkerBuildContours.Begin(); + new JobBuildContours { + field = tileBuilder.compactVoxelField, + maxError = contourMaxError, + maxEdgeLength = maxEdgeLength, + buildFlags = VoxelUtilityBurst.RC_CONTOUR_TESS_WALL_EDGES | VoxelUtilityBurst.RC_CONTOUR_TESS_TILE_EDGES, + cellSize = cellSize, + outputContours = tileBuilder.contours, + outputVerts = tileBuilder.contourVertices, + }.Execute(); + MarkerBuildContours.End(); + + MarkerBuildMesh.Begin(); + new JobBuildMesh { + contours = tileBuilder.contours, + contourVertices = tileBuilder.contourVertices, + mesh = tileBuilder.voxelMesh, + field = tileBuilder.compactVoxelField, + }.Execute(); + MarkerBuildMesh.End(); + + unsafe { + TileMesh.TileMeshUnsafe* outputTileMesh = outputMeshes + i; + *outputTileMesh = new TileMesh.TileMeshUnsafe { + verticesInTileSpace = new UnsafeAppendBuffer(0, 4, Allocator.Persistent), + triangles = new UnsafeAppendBuffer(0, 4, Allocator.Persistent), + tags = new UnsafeAppendBuffer(0, 4, Allocator.Persistent), + }; + + MarkerConvertAreasToTags.Begin(); + new JobConvertAreasToTags { + areas = tileBuilder.voxelMesh.areas, + }.Execute(); + MarkerConvertAreasToTags.End(); + + MarkerRemoveDuplicateVertices.Begin(); + new MeshUtility.JobRemoveDuplicateVertices { + vertices = tileBuilder.voxelMesh.verts.AsArray(), + triangles = tileBuilder.voxelMesh.tris.AsArray(), + tags = tileBuilder.voxelMesh.areas.AsArray(), + outputTags = &outputTileMesh->tags, + outputVertices = &outputTileMesh->verticesInTileSpace, + outputTriangles = &outputTileMesh->triangles, + }.Execute(); + MarkerRemoveDuplicateVertices.End(); + + MarkerTransformTileCoordinates.Begin(); + new JobTransformTileCoordinates { + vertices = &outputTileMesh->verticesInTileSpace, + matrix = voxelToTileSpace, + }.Execute(); + MarkerTransformTileCoordinates.End(); + } + } + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs.meta new file mode 100644 index 0000000..4e77298 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: 20aeb827260a74a4492e7687fdebb14f +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCalculateTriangleConnections.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCalculateTriangleConnections.cs new file mode 100644 index 0000000..b0da1ed --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCalculateTriangleConnections.cs @@ -0,0 +1,73 @@ +using Unity.Burst; +using Unity.Collections; +using Unity.Jobs; +using Unity.Mathematics; +using UnityEngine.Assertions; + +namespace Pathfinding.Graphs.Navmesh.Jobs { + /// <summary> + /// Calculates node connections between triangles within each tile. + /// Connections between tiles are handled at a later stage in <see cref="JobConnectTiles"/>. + /// </summary> + [BurstCompile] + public struct JobCalculateTriangleConnections : IJob { + [ReadOnly] + public NativeArray<TileMesh.TileMeshUnsafe> tileMeshes; + [WriteOnly] + public NativeArray<TileNodeConnectionsUnsafe> nodeConnections; + + public struct TileNodeConnectionsUnsafe { + /// <summary>Stream of packed connection edge infos (from <see cref="Connection.PackShapeEdgeInfo"/>)</summary> + public Unity.Collections.LowLevel.Unsafe.UnsafeAppendBuffer neighbours; + /// <summary>Number of neighbours for each triangle</summary> + public Unity.Collections.LowLevel.Unsafe.UnsafeAppendBuffer neighbourCounts; + } + + public void Execute () { + Assert.AreEqual(tileMeshes.Length, nodeConnections.Length); + + var nodeRefs = new NativeParallelHashMap<int2, uint>(128, Allocator.Temp); + bool duplicates = false; + for (int ti = 0; ti < tileMeshes.Length; ti++) { + nodeRefs.Clear(); + var tile = tileMeshes[ti]; + var numIndices = tile.triangles.Length / sizeof(int); + var neighbours = new Unity.Collections.LowLevel.Unsafe.UnsafeAppendBuffer(numIndices * 2 * 4, 4, Allocator.Persistent); + var neighbourCounts = new Unity.Collections.LowLevel.Unsafe.UnsafeAppendBuffer(numIndices * 4, 4, Allocator.Persistent); + const int TriangleIndexBits = 28; + unsafe { + Assert.IsTrue(numIndices % 3 == 0); + var triangles = (int*)tile.triangles.Ptr; + for (int i = 0, j = 0; i < numIndices; i += 3, j++) { + duplicates |= !nodeRefs.TryAdd(new int2(triangles[i+0], triangles[i+1]), (uint)j | (0 << TriangleIndexBits)); + duplicates |= !nodeRefs.TryAdd(new int2(triangles[i+1], triangles[i+2]), (uint)j | (1 << TriangleIndexBits)); + duplicates |= !nodeRefs.TryAdd(new int2(triangles[i+2], triangles[i+0]), (uint)j | (2 << TriangleIndexBits)); + } + + for (int i = 0; i < numIndices; i += 3) { + var cnt = 0; + for (int edge = 0; edge < 3; edge++) { + if (nodeRefs.TryGetValue(new int2(triangles[i+((edge+1) % 3)], triangles[i+edge]), out var match)) { + var other = match & ((1 << TriangleIndexBits) - 1); + var otherEdge = (int)(match >> TriangleIndexBits); + neighbours.Add(other); + var edgeInfo = Connection.PackShapeEdgeInfo((byte)edge, (byte)otherEdge, true, true, true); + neighbours.Add((int)edgeInfo); + cnt += 1; + } + } + neighbourCounts.Add(cnt); + } + } + nodeConnections[ti] = new TileNodeConnectionsUnsafe { + neighbours = neighbours, + neighbourCounts = neighbourCounts, + }; + } + + if (duplicates) { + UnityEngine.Debug.LogWarning("Duplicate triangle edges were found in the input mesh. These have been removed. Are you sure your mesh is suitable for being used as a navmesh directly?\nThis could be caused by the mesh's normals not being consistent."); + } + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCalculateTriangleConnections.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCalculateTriangleConnections.cs.meta new file mode 100644 index 0000000..4bc3c35 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCalculateTriangleConnections.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: 30417132dbc15504abbdf1b70224c006 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConnectTiles.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConnectTiles.cs new file mode 100644 index 0000000..0782ecf --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConnectTiles.cs @@ -0,0 +1,159 @@ +using Unity.Collections; +using Unity.Jobs; +using Unity.Jobs.LowLevel.Unsafe; +using Unity.Mathematics; +using UnityEngine; + +namespace Pathfinding.Graphs.Navmesh.Jobs { + /// <summary> + /// Connects adjacent tiles together. + /// + /// This only creates connections between tiles. Connections internal to a tile should be handled by <see cref="JobCalculateTriangleConnections"/>. + /// + /// Use the <see cref="ScheduleBatch"/> method to connect a bunch of tiles efficiently using maximum parallelism. + /// </summary> + public struct JobConnectTiles : IJob { + /// <summary>GCHandle referring to a NavmeshTile[] array of size tileRect.Width*tileRect.Height</summary> + public System.Runtime.InteropServices.GCHandle tiles; + public int coordinateSum; + public int direction; + public int zOffset; + public int zStride; + Vector2 tileWorldSize; + IntRect tileRect; + /// <summary>Maximum vertical distance between two tiles to create a connection between them</summary> + public float maxTileConnectionEdgeDistance; + + static readonly Unity.Profiling.ProfilerMarker ConnectTilesMarker = new Unity.Profiling.ProfilerMarker("ConnectTiles"); + + /// <summary> + /// Schedule jobs to connect all the given tiles with each other while exploiting as much parallelism as possible. + /// tilesHandle should be a GCHandle referring to a NavmeshTile[] array of size tileRect.Width*tileRect.Height. + /// </summary> + public static JobHandle ScheduleBatch (System.Runtime.InteropServices.GCHandle tilesHandle, JobHandle dependency, IntRect tileRect, Vector2 tileWorldSize, float maxTileConnectionEdgeDistance) { + // First connect all tiles with an EVEN coordinate sum + // This would be the white squares on a chess board. + // Then connect all tiles with an ODD coordinate sum (which would be all black squares on a chess board). + // This will prevent the different threads that do all + // this in parallel from conflicting with each other. + // The directions are also done separately + // first they are connected along the X direction and then along the Z direction. + // Looping over 0 and then 1 + + int workers = Mathf.Max(1, JobsUtility.JobWorkerCount); + var handles = new NativeArray<JobHandle>(workers, Allocator.Temp); + for (int coordinateSum = 0; coordinateSum <= 1; coordinateSum++) { + for (int direction = 0; direction <= 1; direction++) { + for (int i = 0; i < workers; i++) { + handles[i] = new JobConnectTiles { + tiles = tilesHandle, + tileRect = tileRect, + tileWorldSize = tileWorldSize, + coordinateSum = coordinateSum, + direction = direction, + maxTileConnectionEdgeDistance = maxTileConnectionEdgeDistance, + zOffset = i, + zStride = workers, + }.Schedule(dependency); + } + dependency = JobHandle.CombineDependencies(handles); + } + } + + return dependency; + } + + /// <summary> + /// Schedule jobs to connect all the given tiles inside innerRect with tiles that are outside it, while exploiting as much parallelism as possible. + /// tilesHandle should be a GCHandle referring to a NavmeshTile[] array of size tileRect.Width*tileRect.Height. + /// </summary> + public static JobHandle ScheduleRecalculateBorders (System.Runtime.InteropServices.GCHandle tilesHandle, JobHandle dependency, IntRect tileRect, IntRect innerRect, Vector2 tileWorldSize, float maxTileConnectionEdgeDistance) { + var w = innerRect.Width; + var h = innerRect.Height; + + // Note: conservative estimate of number of handles. There may be fewer in reality. + var allDependencies = new NativeArray<JobHandle>(2*w + 2*math.max(0, h - 2), Allocator.Temp); + int count = 0; + for (int z = 0; z < h; z++) { + for (int x = 0; x < w; x++) { + // Check if the tile is on the border of the inner rect + if (!(x == 0 || z == 0 || x == w - 1 || z == h - 1)) continue; + + var tileX = innerRect.xmin + x; + var tileZ = innerRect.ymin + z; + + // For a corner tile, the jobs need to run sequentially + var dep = dependency; + for (int direction = 0; direction < 4; direction++) { + var nx = tileX + (direction == 0 ? 1 : direction == 1 ? -1 : 0); + var nz = tileZ + (direction == 2 ? 1 : direction == 3 ? -1 : 0); + if (innerRect.Contains(nx, nz) || !tileRect.Contains(nx, nz)) { + continue; + } + + dep = new JobConnectTilesSingle { + tiles = tilesHandle, + tileIndex1 = tileX + tileZ * tileRect.Width, + tileIndex2 = nx + nz * tileRect.Width, + tileWorldSize = tileWorldSize, + maxTileConnectionEdgeDistance = maxTileConnectionEdgeDistance, + }.Schedule(dep); + } + + allDependencies[count++] = dep; + } + } + return JobHandle.CombineDependencies(allDependencies); + } + + public void Execute () { + var tiles = (NavmeshTile[])this.tiles.Target; + + var tileRectDepth = tileRect.Height; + var tileRectWidth = tileRect.Width; + for (int z = zOffset; z < tileRectDepth; z += zStride) { + for (int x = 0; x < tileRectWidth; x++) { + if ((x + z) % 2 == coordinateSum) { + int tileIndex1 = x + z * tileRectWidth; + int tileIndex2; + if (direction == 0 && x < tileRectWidth - 1) { + tileIndex2 = x + 1 + z * tileRectWidth; + } else if (direction == 1 && z < tileRectDepth - 1) { + tileIndex2 = x + (z + 1) * tileRectWidth; + } else { + continue; + } + + ConnectTilesMarker.Begin(); + NavmeshBase.ConnectTiles(tiles[tileIndex1], tiles[tileIndex2], tileWorldSize.x, tileWorldSize.y, maxTileConnectionEdgeDistance); + ConnectTilesMarker.End(); + } + } + } + } + } + + /// <summary> + /// Connects two adjacent tiles together. + /// + /// This only creates connections between tiles. Connections internal to a tile should be handled by <see cref="JobCalculateTriangleConnections"/>. + /// </summary> + struct JobConnectTilesSingle : IJob { + /// <summary>GCHandle referring to a NavmeshTile[] array of size tileRect.Width*tileRect.Height</summary> + public System.Runtime.InteropServices.GCHandle tiles; + /// <summary>Index of the first tile in the <see cref="tiles"/> array</summary> + public int tileIndex1; + /// <summary>Index of the second tile in the <see cref="tiles"/> array</summary> + public int tileIndex2; + /// <summary>Size of a tile in world units</summary> + public Vector2 tileWorldSize; + /// <summary>Maximum vertical distance between two tiles to create a connection between them</summary> + public float maxTileConnectionEdgeDistance; + + public void Execute () { + var tiles = (NavmeshTile[])this.tiles.Target; + + NavmeshBase.ConnectTiles(tiles[tileIndex1], tiles[tileIndex2], tileWorldSize.x, tileWorldSize.y, maxTileConnectionEdgeDistance); + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConnectTiles.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConnectTiles.cs.meta new file mode 100644 index 0000000..766f092 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConnectTiles.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: dd00a18824d04764783722c547fb60f7 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs new file mode 100644 index 0000000..2197d9c --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs @@ -0,0 +1,23 @@ +using Pathfinding.Graphs.Navmesh.Voxelization.Burst; +using Unity.Burst; +using Unity.Collections; +using Unity.Collections.LowLevel.Unsafe; +using Unity.Jobs; + +namespace Pathfinding.Graphs.Navmesh.Jobs { + /// <summary>Convert recast region IDs to the tags that should be applied to the nodes</summary> + [BurstCompile] + public struct JobConvertAreasToTags : IJob { + public NativeList<int> areas; + + public void Execute () { + unsafe { + for (int i = 0; i < areas.Length; i++) { + var area = areas[i]; + // The user supplied IDs start at 1 because 0 is reserved for NotWalkable + areas[i] = (area & VoxelUtilityBurst.TagReg) != 0 ? (area & VoxelUtilityBurst.TagRegMask) - 1 : 0; + } + } + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs.meta new file mode 100644 index 0000000..3b4daad --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobConvertAreasToTags.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: 229fdb01207c1ab4796deea78744e136 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCreateTiles.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCreateTiles.cs new file mode 100644 index 0000000..44368b3 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCreateTiles.cs @@ -0,0 +1,115 @@ +using Pathfinding.Util; +using Unity.Collections; +using Unity.Jobs; +using UnityEngine; +using UnityEngine.Assertions; +using UnityEngine.Profiling; + +namespace Pathfinding.Graphs.Navmesh.Jobs { + /// <summary> + /// Builds tiles optimized for pathfinding, from a list of <see cref="TileMesh.TileMeshUnsafe"/>. + /// + /// This job takes the following steps: + /// - Transform all vertices using the <see cref="graphToWorldSpace"/> matrix. + /// - Remove duplicate vertices + /// - If <see cref="recalculateNormals"/> is enabled: ensure all triangles are laid out in the clockwise direction. + /// </summary> + public struct JobCreateTiles : IJob { + /// <summary>An array of <see cref="TileMesh.TileMeshUnsafe"/> of length tileRect.Width*tileRect.Height</summary> + [ReadOnly] + public NativeArray<TileMesh.TileMeshUnsafe> tileMeshes; + + /// <summary> + /// An array of <see cref="NavmeshTile"/> of length tileRect.Width*tileRect.Height. + /// This array will be filled with the created tiles. + /// </summary> + public System.Runtime.InteropServices.GCHandle tiles; + + /// <summary>Graph index of the graph that these nodes will be added to</summary> + public uint graphIndex; + + /// <summary> + /// Number of tiles in the graph. + /// + /// This may be much bigger than the <see cref="tileRect"/> that we are actually processing. + /// For example if a graph update is performed, the <see cref="tileRect"/> will just cover the tiles that are recalculated, + /// while <see cref="graphTileCount"/> will contain all tiles in the graph. + /// </summary> + public Int2 graphTileCount; + + /// <summary> + /// Rectangle of tiles that we are processing. + /// + /// (xmax, ymax) must be smaller than graphTileCount. + /// If for examples <see cref="graphTileCount"/> is (10, 10) and <see cref="tileRect"/> is {2, 3, 5, 6} then we are processing tiles (2, 3) to (5, 6) inclusive. + /// </summary> + public IntRect tileRect; + + /// <summary>Initial penalty for all nodes in the tile</summary> + public uint initialPenalty; + + /// <summary> + /// If true, all triangles will be guaranteed to be laid out in clockwise order. + /// If false, their original order will be preserved. + /// </summary> + public bool recalculateNormals; + + /// <summary>Size of a tile in world units along the graph's X and Z axes</summary> + public Vector2 tileWorldSize; + + /// <summary>Matrix to convert from graph space to world space</summary> + public Matrix4x4 graphToWorldSpace; + + public void Execute () { + var tiles = (NavmeshTile[])this.tiles.Target; + Assert.AreEqual(tileMeshes.Length, tiles.Length); + Assert.AreEqual(tileRect.Area, tileMeshes.Length); + Assert.IsTrue(tileRect.xmax < graphTileCount.x); + Assert.IsTrue(tileRect.ymax < graphTileCount.y); + + var tileRectWidth = tileRect.Width; + var tileRectDepth = tileRect.Height; + + for (int z = 0; z < tileRectDepth; z++) { + for (int x = 0; x < tileRectWidth; x++) { + var tileIndex = z*tileRectWidth + x; + // If we are just updating a part of the graph we still want to assign the nodes the proper global tile index + var graphTileIndex = (z + tileRect.ymin)*graphTileCount.x + (x + tileRect.xmin); + var mesh = tileMeshes[tileIndex]; + + // Convert tile space to graph space and world space + var verticesInGraphSpace = mesh.verticesInTileSpace.AsUnsafeSpan<Int3>().Clone(Allocator.Persistent); + var verticesInWorldSpace = verticesInGraphSpace.Clone(Allocator.Persistent); + var tileSpaceToGraphSpaceOffset = (Int3) new Vector3(tileWorldSize.x * (x + tileRect.xmin), 0, tileWorldSize.y * (z + tileRect.ymin)); + for (int i = 0; i < verticesInGraphSpace.Length; i++) { + var v = verticesInGraphSpace[i] + tileSpaceToGraphSpaceOffset; + verticesInGraphSpace[i] = v; + verticesInWorldSpace[i] = (Int3)graphToWorldSpace.MultiplyPoint3x4((Vector3)v); + } + + // Create a new navmesh tile and assign its settings + var triangles = mesh.triangles.AsUnsafeSpan<int>().Clone(Allocator.Persistent); + var tile = new NavmeshTile { + x = x + tileRect.xmin, + z = z + tileRect.ymin, + w = 1, + d = 1, + tris = triangles, + vertsInGraphSpace = verticesInGraphSpace, + verts = verticesInWorldSpace, + bbTree = new BBTree(triangles, verticesInGraphSpace), + nodes = new TriangleMeshNode[triangles.Length/3], + // Leave empty for now, it will be filled in later + graph = null, + }; + + Profiler.BeginSample("CreateNodes"); + NavmeshBase.CreateNodes(tile, tile.tris, graphTileIndex, graphIndex, mesh.tags.AsUnsafeSpan<uint>(), false, null, initialPenalty, false); + Profiler.EndSample(); + + tiles[tileIndex] = tile; + } + } + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCreateTiles.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCreateTiles.cs.meta new file mode 100644 index 0000000..3f72140 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobCreateTiles.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: b86cf43938afd654a8f1b711e55977d7 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobTransformTileCoordinates.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobTransformTileCoordinates.cs new file mode 100644 index 0000000..b5b1a67 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobTransformTileCoordinates.cs @@ -0,0 +1,32 @@ +using Unity.Burst; +using Unity.Collections.LowLevel.Unsafe; +using Unity.Jobs; +using UnityEngine; + +namespace Pathfinding.Graphs.Navmesh.Jobs { + /// <summary> + /// Transforms vertices from voxel coordinates to tile coordinates. + /// + /// This essentially constitutes multiplying the vertices by the <see cref="matrix"/>. + /// + /// Note: The input space is in raw voxel coordinates, the output space is in tile coordinates stored in millimeters (as is typical for the Int3 struct. See <see cref="Int3.Precision"/>). + /// </summary> + [BurstCompile(FloatMode = FloatMode.Fast)] + public struct JobTransformTileCoordinates : IJob { + /// <summary>Element type Int3</summary> + public unsafe UnsafeAppendBuffer* vertices; + public Matrix4x4 matrix; + + public void Execute () { + unsafe { + int vertexCount = vertices->Length / UnsafeUtility.SizeOf<Int3>(); + for (int i = 0; i < vertexCount; i++) { + // Transform from voxel indices to a proper Int3 coordinate, then convert it to a Vector3 float coordinate + var vPtr1 = (Int3*)vertices->Ptr + i; + var p = new Vector3(vPtr1->x, vPtr1->y, vPtr1->z); + *vPtr1 = (Int3)matrix.MultiplyPoint3x4(p); + } + } + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobTransformTileCoordinates.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobTransformTileCoordinates.cs.meta new file mode 100644 index 0000000..291734c --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobTransformTileCoordinates.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: ff97d8db3ca9a074dbfbd83fa5ad16be +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs new file mode 100644 index 0000000..ea8ef05 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs @@ -0,0 +1,60 @@ +using Pathfinding.Util; +using Unity.Collections; +using Unity.Jobs; +using UnityEngine.Assertions; +using UnityEngine.Profiling; + +namespace Pathfinding.Graphs.Navmesh.Jobs { + /// <summary> + /// Writes connections to each node in each tile. + /// + /// It also calculates the connection costs between nodes. + /// + /// This job is run after all tiles have been built and the connections have been calculated. + /// + /// See: <see cref="JobCalculateTriangleConnections"/> + /// </summary> + public struct JobWriteNodeConnections : IJob { + /// <summary>Connections for each tile</summary> + [ReadOnly] + public NativeArray<JobCalculateTriangleConnections.TileNodeConnectionsUnsafe> nodeConnections; + /// <summary>Array of <see cref="NavmeshTile"/></summary> + public System.Runtime.InteropServices.GCHandle tiles; + + public void Execute () { + var tiles = (NavmeshTile[])this.tiles.Target; + Assert.AreEqual(nodeConnections.Length, tiles.Length); + + for (int i = 0; i < tiles.Length; i++) { + Profiler.BeginSample("CreateConnections"); + var connections = nodeConnections[i]; + Apply(tiles[i].nodes, connections); + connections.neighbourCounts.Dispose(); + connections.neighbours.Dispose(); + Profiler.EndSample(); + } + } + + void Apply (TriangleMeshNode[] nodes, JobCalculateTriangleConnections.TileNodeConnectionsUnsafe connections) { + var neighbourCountsReader = connections.neighbourCounts.AsReader(); + var neighboursReader = connections.neighbours.AsReader(); + + for (int i = 0; i < nodes.Length; i++) { + var node = nodes[i]; + var neighbourCount = neighbourCountsReader.ReadNext<int>(); + var conns = node.connections = ArrayPool<Connection>.ClaimWithExactLength(neighbourCount); + for (int j = 0; j < neighbourCount; j++) { + var otherIndex = neighboursReader.ReadNext<int>(); + var shapeEdgeInfo = (byte)neighboursReader.ReadNext<int>(); + var other = nodes[otherIndex]; + var cost = (node.position - other.position).costMagnitude; + conns[j] = new Connection( + other, + (uint)cost, + shapeEdgeInfo + ); + } + } + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs.meta new file mode 100644 index 0000000..91359d9 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobWriteNodeConnections.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: eea3ec9fc5dd8604c9902e09277d86d2 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: |