path: root/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/TileBuilder.cs

using System.Collections.Generic;
using Pathfinding.Graphs.Navmesh.Jobs;
using Pathfinding.Jobs;
using Pathfinding.Util;
using Pathfinding.Graphs.Navmesh.Voxelization.Burst;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;
using UnityEngine;
using UnityEngine.Profiling;
using UnityEngine.Assertions;

namespace Pathfinding.Graphs.Navmesh {
	/// <summary>
	/// Settings for building tile meshes in a recast graph.
	///
	/// See: <see cref="RecastGraph"/> for more documentation on the individual fields.
	/// See: <see cref="RecastBuilder"/>
	/// </summary>
	public struct TileBuilder {
		public float walkableClimb;
		public RecastGraph.CollectionSettings collectionSettings;
		public RecastGraph.RelevantGraphSurfaceMode relevantGraphSurfaceMode;
		public RecastGraph.DimensionMode dimensionMode;
		public RecastGraph.BackgroundTraversability backgroundTraversability;

		// TODO: Don't store in struct
		public int tileBorderSizeInVoxels;
		public float walkableHeight;
		public float maxSlope;
		// TODO: Specify in world units
		public int characterRadiusInVoxels;
		public int minRegionSize;
		public float maxEdgeLength;
		public float contourMaxError;
		public UnityEngine.SceneManagement.Scene scene;
		public TileLayout tileLayout;
		public IntRect tileRect;
		public List<RecastGraph.PerLayerModification> perLayerModifications;

		public class TileBuilderOutput : IProgress, System.IDisposable {
			public NativeReference<int> currentTileCounter;
			public TileMeshesUnsafe tileMeshes;
#if UNITY_EDITOR
			public List<(UnityEngine.Object, Mesh)> meshesUnreadableAtRuntime;
#endif

			public float Progress {
				get {
					var tileCount = tileMeshes.tileRect.Area;
					var currentTile = Mathf.Min(tileCount, currentTileCounter.Value);
					return tileCount > 0 ? currentTile / (float)tileCount : 0; // "Scanning tiles: " + currentTile + " of " + (tileCount) + " tiles...");
				}
			}

			public void Dispose () {
				tileMeshes.Dispose();
				if (currentTileCounter.IsCreated) currentTileCounter.Dispose();
#if UNITY_EDITOR
				if (meshesUnreadableAtRuntime != null) ListPool<(UnityEngine.Object, Mesh)>.Release(ref meshesUnreadableAtRuntime);
#endif
			}
		}

		public TileBuilder (RecastGraph graph, TileLayout tileLayout, IntRect tileRect) {
			this.tileLayout = tileLayout;
			this.tileRect = tileRect;
			// A walkableClimb higher than walkableHeight can cause issues when generating the navmesh since then it can in some cases
			// Both be valid for a character to walk under an obstacle and climb up on top of it (and that cannot be handled with navmesh without links)
			// The editor scripts also enforce this, but we enforce it here too just to be sure
			this.walkableClimb = Mathf.Min(graph.walkableClimb, graph.walkableHeight);
			this.collectionSettings = graph.collectionSettings;
			this.dimensionMode = graph.dimensionMode;
			this.backgroundTraversability = graph.backgroundTraversability;
			this.tileBorderSizeInVoxels = graph.TileBorderSizeInVoxels;
			this.walkableHeight = graph.walkableHeight;
			this.maxSlope = graph.maxSlope;
			this.characterRadiusInVoxels = graph.CharacterRadiusInVoxels;
			this.minRegionSize = Mathf.RoundToInt(graph.minRegionSize);
			this.maxEdgeLength = graph.maxEdgeLength;
			this.contourMaxError = graph.contourMaxError;
			this.relevantGraphSurfaceMode = graph.relevantGraphSurfaceMode;
			this.scene = graph.active.gameObject.scene;
			this.perLayerModifications = graph.perLayerModifications;
		}

		/// <summary>
		/// Number of extra voxels on each side of a tile to ensure accurate navmeshes near the tile border.
		/// The width of a tile is expanded by 2 times this value (1x to the left and 1x to the right)
		/// </summary>
		int TileBorderSizeInVoxels {
			get {
				return characterRadiusInVoxels + 3;
			}
		}

		float TileBorderSizeInWorldUnits {
			get {
				return TileBorderSizeInVoxels*tileLayout.cellSize;
			}
		}

		/// <summary>Get the world space bounds for all tiles, including an optional (graph space) padding around the tiles in the x and z axis</summary>
		public Bounds GetWorldSpaceBounds (float xzPadding = 0) {
			var graphSpaceBounds = tileLayout.GetTileBoundsInGraphSpace(tileRect.xmin, tileRect.ymin, tileRect.Width, tileRect.Height);
			graphSpaceBounds.Expand(new Vector3(2*xzPadding, 0, 2*xzPadding));
			return tileLayout.transform.Transform(graphSpaceBounds);
		}

		public RecastMeshGatherer.MeshCollection CollectMeshes (Bounds bounds) {
			Profiler.BeginSample("Find Meshes for rasterization");
			var mask = collectionSettings.layerMask;
			var tagMask = collectionSettings.tagMask;
			if (collectionSettings.collectionMode == RecastGraph.CollectionSettings.FilterMode.Layers) {
				tagMask = null;
			} else {
				mask = -1;
			}
			var meshGatherer = new RecastMeshGatherer(scene, bounds, collectionSettings.terrainHeightmapDownsamplingFactor, collectionSettings.layerMask, collectionSettings.tagMask, perLayerModifications, tileLayout.cellSize / collectionSettings.colliderRasterizeDetail);

			if (collectionSettings.rasterizeMeshes && dimensionMode == RecastGraph.DimensionMode.Dimension3D) {
				Profiler.BeginSample("Find meshes");
				meshGatherer.CollectSceneMeshes();
				Profiler.EndSample();
			}

			Profiler.BeginSample("Find RecastMeshObj components");
			meshGatherer.CollectRecastMeshObjs();
			Profiler.EndSample();

			if (collectionSettings.rasterizeTerrain && dimensionMode == RecastGraph.DimensionMode.Dimension3D) {
				Profiler.BeginSample("Find terrains");
				// Split terrains up into meshes approximately the size of a single chunk
				var desiredTerrainChunkSize = tileLayout.cellSize*math.max(tileLayout.tileSizeInVoxels.x, tileLayout.tileSizeInVoxels.y);
				meshGatherer.CollectTerrainMeshes(collectionSettings.rasterizeTrees, desiredTerrainChunkSize);
				Profiler.EndSample();
			}

			if (collectionSettings.rasterizeColliders || dimensionMode == RecastGraph.DimensionMode.Dimension2D) {
				Profiler.BeginSample("Find colliders");
				if (dimensionMode == RecastGraph.DimensionMode.Dimension3D) {
					meshGatherer.CollectColliderMeshes();
				} else {
					meshGatherer.Collect2DColliderMeshes();
				}
				Profiler.EndSample();
			}

			if (collectionSettings.onCollectMeshes != null) {
				Profiler.BeginSample("Custom mesh collection");
				collectionSettings.onCollectMeshes(meshGatherer);
				Profiler.EndSample();
			}

			Profiler.BeginSample("Finalizing");
			var result = meshGatherer.Finalize();
			Profiler.EndSample();

			// Warn if no meshes were found, but only if the tile rect covers the whole graph.
			// If it's just a partial update, the user is probably not interested in this warning,
			// as it is completely normal that there are some empty tiles.
			if (tileRect == new IntRect(0, 0, tileLayout.tileCount.x - 1, tileLayout.tileCount.y - 1) && result.meshes.Length == 0) {
				Debug.LogWarning("No rasterizable objects were found contained in the layers specified by the 'mask' variables");
			}

			Profiler.EndSample();
			return result;
		}

		/// <summary>A mapping from tiles to the meshes that each tile touches</summary>
		public struct BucketMapping {
			/// <summary>All meshes that should be voxelized</summary>
			public NativeArray<RasterizationMesh> meshes;
			/// <summary>Indices into the <see cref="meshes"/> array</summary>
			public NativeArray<int> pointers;
			/// <summary>
			/// For each tile, the range of pointers in <see cref="pointers"/> that correspond to that tile.
			/// This is a cumulative sum of the number of pointers in each bucket.
			///
			/// Bucket i will contain pointers in the range [i > 0 ? bucketRanges[i-1] : 0, bucketRanges[i]).
			///
			/// The length is the same as the number of tiles.
			/// </summary>
			public NativeArray<int> bucketRanges;
		}

		/// <summary>Creates a list for every tile and adds every mesh that touches a tile to the corresponding list</summary>
		BucketMapping PutMeshesIntoTileBuckets (RecastMeshGatherer.MeshCollection meshCollection, IntRect tileBuckets) {
			var bucketCount = tileBuckets.Width*tileBuckets.Height;
			var buckets = new NativeList<int>[bucketCount];
			var borderExpansion = TileBorderSizeInWorldUnits;

			for (int i = 0; i < buckets.Length; i++) {
				buckets[i] = new NativeList<int>(Allocator.Persistent);
			}

			var offset = -tileBuckets.Min;
			var clamp = new IntRect(0, 0, tileBuckets.Width - 1, tileBuckets.Height - 1);
			var meshes = meshCollection.meshes;
			for (int i = 0; i < meshes.Length; i++) {
				var mesh = meshes[i];
				var bounds = mesh.bounds;
				var rect = tileLayout.GetTouchingTiles(bounds, borderExpansion);
				rect = IntRect.Intersection(rect.Offset(offset), clamp);
				for (int z = rect.ymin; z <= rect.ymax; z++) {
					for (int x = rect.xmin; x <= rect.xmax; x++) {
						buckets[x + z*tileBuckets.Width].Add(i);
					}
				}
			}

			// Concat buckets
			int allPointersCount = 0;
			for (int i = 0; i < buckets.Length; i++) allPointersCount += buckets[i].Length;
			var allPointers = new NativeArray<int>(allPointersCount, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
			var bucketRanges = new NativeArray<int>(bucketCount, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
			allPointersCount = 0;
			for (int i = 0; i < buckets.Length; i++) {
				// If we have an empty bucket at the end of the array then allPointersCount might be equal to allPointers.Length which would cause an assert to trigger.
				// So for empty buckets don't call the copy method
				if (buckets[i].Length > 0) {
					NativeArray<int>.Copy(buckets[i].AsArray(), 0, allPointers, allPointersCount, buckets[i].Length);
				}
				allPointersCount += buckets[i].Length;
				bucketRanges[i] = allPointersCount;
				buckets[i].Dispose();
			}

			return new BucketMapping {
					   meshes = meshCollection.meshes,
					   pointers = allPointers,
					   bucketRanges = bucketRanges,
			};
		}

		public Promise<TileBuilderOutput> Schedule (DisposeArena arena) {
			var tileCount = tileRect.Area;
			Assert.IsTrue(tileCount > 0);

			var tileRectWidth = tileRect.Width;
			var tileRectDepth = tileRect.Height;

			// Find all meshes that could affect the graph
			var worldBounds = GetWorldSpaceBounds(TileBorderSizeInWorldUnits);
			if (dimensionMode == RecastGraph.DimensionMode.Dimension2D) {
				// In 2D mode, the bounding box of the graph only bounds it in the X and Y dimensions
				worldBounds.extents = new Vector3(worldBounds.extents.x, worldBounds.extents.y, float.PositiveInfinity);
			}
			var meshes = CollectMeshes(worldBounds);

			Profiler.BeginSample("PutMeshesIntoTileBuckets");
			var buckets = PutMeshesIntoTileBuckets(meshes, tileRect);
			Profiler.EndSample();

			Profiler.BeginSample("Allocating tiles");
			var tileMeshes = new NativeArray<TileMesh.TileMeshUnsafe>(tileCount, Allocator.Persistent, NativeArrayOptions.ClearMemory);

			int width = tileLayout.tileSizeInVoxels.x + tileBorderSizeInVoxels*2;
			int depth = tileLayout.tileSizeInVoxels.y + tileBorderSizeInVoxels*2;
			var cellHeight = tileLayout.CellHeight;
			// TODO: Move inside BuildTileMeshBurst
			var voxelWalkableHeight = (uint)(walkableHeight/cellHeight);
			var voxelWalkableClimb = Mathf.RoundToInt(walkableClimb/cellHeight);

			var tileGraphSpaceBounds = new NativeArray<Bounds>(tileCount, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);

			for (int z = 0; z < tileRectDepth; z++) {
				for (int x = 0; x < tileRectWidth; x++) {
					int tileIndex = x + z*tileRectWidth;
					var tileBounds = tileLayout.GetTileBoundsInGraphSpace(tileRect.xmin + x, tileRect.ymin + z);
					// Expand borderSize voxels on each side
					tileBounds.Expand(new Vector3(1, 0, 1)*TileBorderSizeInWorldUnits*2);
					tileGraphSpaceBounds[tileIndex] = tileBounds;
				}
			}

			Profiler.EndSample();
			Profiler.BeginSample("Scheduling jobs");

			var builders = new TileBuilderBurst[Mathf.Max(1, Mathf.Min(tileCount, Unity.Jobs.LowLevel.Unsafe.JobsUtility.JobWorkerCount + 1))];
			var currentTileCounter = new NativeReference<int>(0, Allocator.Persistent);
			JobHandle dependencies = default;

			var relevantGraphSurfaces = new NativeList<JobBuildRegions.RelevantGraphSurfaceInfo>(Allocator.Persistent);
			var c = RelevantGraphSurface.Root;
			while (c != null) {
				relevantGraphSurfaces.Add(new JobBuildRegions.RelevantGraphSurfaceInfo {
					position = c.transform.position,
					range = c.maxRange,
				});
				c = c.Next;
			}


			// Having a few long running jobs is bad because Unity cannot inject more high priority jobs
			// in between tile calculations. So we run each builder a number of times.
			// Each step will just calculate one tile.
			int tilesPerJob = Mathf.CeilToInt(Mathf.Sqrt(tileCount));
			// Number of tiles calculated if every builder runs once
			int tilesPerStep = tilesPerJob * builders.Length;
			// Round up to make sure we run the jobs enough times
			// We multiply by 2 to run a bit more jobs than strictly necessary.
			// This is to ensure that if one builder just gets a bunch of long running jobs
			// then the other builders can steal some work from it.
			int jobSteps = 2 * (tileCount + tilesPerStep - 1) / tilesPerStep;
			var jobTemplate = new JobBuildTileMeshFromVoxels {
				tileBuilder = builders[0],
				inputMeshes = buckets,
				tileGraphSpaceBounds = tileGraphSpaceBounds,
				voxelWalkableClimb = voxelWalkableClimb,
				voxelWalkableHeight = voxelWalkableHeight,
				voxelToTileSpace = Matrix4x4.Scale(new Vector3(tileLayout.cellSize, cellHeight, tileLayout.cellSize)) * Matrix4x4.Translate(-new Vector3(1, 0, 1)*TileBorderSizeInVoxels),
				cellSize = tileLayout.cellSize,
				cellHeight = cellHeight,
				maxSlope = Mathf.Max(maxSlope, 0.0001f), // Ensure maxSlope is not 0, as then horizontal surfaces can sometimes get excluded due to floating point errors
				dimensionMode = dimensionMode,
				backgroundTraversability = backgroundTraversability,
				graphToWorldSpace = tileLayout.transform.matrix,
				// Crop all tiles to ensure they are inside the graph bounds (even if the tiles did not line up perfectly with the bounding box).
				// Add the character radius, since it will be eroded away anyway, but subtract 1 voxel to ensure the nodes are strictly inside the bounding box
				graphSpaceLimits = new Vector2(tileLayout.graphSpaceSize.x + (characterRadiusInVoxels-1)*tileLayout.cellSize, tileLayout.graphSpaceSize.z + (characterRadiusInVoxels-1)*tileLayout.cellSize),
				characterRadiusInVoxels = characterRadiusInVoxels,
				tileBorderSizeInVoxels = tileBorderSizeInVoxels,
				minRegionSize = minRegionSize,
				maxEdgeLength = maxEdgeLength,
				contourMaxError = contourMaxError,
				maxTiles = tilesPerJob,
				relevantGraphSurfaces = relevantGraphSurfaces.AsArray(),
				relevantGraphSurfaceMode = this.relevantGraphSurfaceMode,
			};
			jobTemplate.SetOutputMeshes(tileMeshes);
			jobTemplate.SetCounter(currentTileCounter);
			int maximumVoxelYCoord = (int)(tileLayout.graphSpaceSize.y / cellHeight);
			for (int i = 0; i < builders.Length; i++) {
				jobTemplate.tileBuilder = builders[i] = new TileBuilderBurst(width, depth, (int)voxelWalkableHeight, maximumVoxelYCoord);
				var dep = new JobHandle();
				for (int j = 0; j < jobSteps; j++) {
					dep = jobTemplate.Schedule(dep);
				}
				dependencies = JobHandle.CombineDependencies(dependencies, dep);
			}
			JobHandle.ScheduleBatchedJobs();

			Profiler.EndSample();

			arena.Add(tileGraphSpaceBounds);
			arena.Add(relevantGraphSurfaces);
			arena.Add(buckets.bucketRanges);
			arena.Add(buckets.pointers);
			// Note: buckets.meshes references data in #meshes, so we don't have to dispose it separately
			arena.Add(meshes);

			// Dispose the mesh data after all jobs are completed.
			// Note that the jobs use pointers to this data which are not tracked by the safety system.
			for (int i = 0; i < builders.Length; i++) arena.Add(builders[i]);

			return new Promise<TileBuilderOutput>(dependencies, new TileBuilderOutput {
				tileMeshes = new TileMeshesUnsafe(tileMeshes, tileRect, new Vector2(tileLayout.TileWorldSizeX, tileLayout.TileWorldSizeZ)),
				currentTileCounter = currentTileCounter,
#if UNITY_EDITOR
				meshesUnreadableAtRuntime = meshes.meshesUnreadableAtRuntime,
#endif
			});
		}
	}
}