If a Job is calculating multiple paths from one starting point to multiple destinations packed together such that they reside in the same PolygonId, is NavMeshQuery smart enough to “cache” the polygon path from the starting point to one of the destinations, reusing it for the other destinations?
No, NavMeshQuery is currently not caching nor reusing the path or any temporary data when starting a new path search. It is erasing its own memory.
1 Like
May I request that you look into caching polygon paths when a NavMeshQuery is used in the same job multiple times to calculate paths with closely clustered destinations? I actually wrote a job that does so, though it’s messy and bloated due to not having access to lower level APIs. Maybe you’ll find it helpful should you ever consider adding that feature? Something like NavMeshQuery.CalculateBatchPath(NativeArray destinations, int maxWaypointsPerPath, ref NativeArray allPaths)
[BurstCompile]
private struct PolygonPathJob : IJob
{
public Entity userEntity;
public NavMeshQuery query;
public float middleOfEnvironment;
public float heightOfEnvironment;
[ReadOnly]
public ComponentDataFromEntity<VantageComponent> vantageFromEntity;
[ReadOnly]
public ComponentDataFromEntity<Translation> translationFromEntity;
[ReadOnly]
public BufferFromEntity<DestinationsLocationElement> destinationsFromEntity;
[ReadOnly]
public NativeHashMap<float2, PolygonId> destinationsToPolygons;
public EntityCommandBuffer ecb;
public void Execute()
{
var userDestinations = destinationsFromEntity[userEntity].AsNativeArray();
var numUserDestinations = userDestinations.Length;
var uniqueDestinationsPolygons = new NativeHashMap<PolygonId, bool>(numUserDestinations, Allocator.Temp);
for (var i = 0; i < numUserDestinations; i++)
{
uniqueDestinationsPolygons.TryAdd(destinationsToPolygons[userDestinations[i].potentialDestination], true);
}
var destinationPolygons = uniqueDestinationsPolygons.GetKeyArray(Allocator.Temp);
var numDestinationPolygons = destinationPolygons.Length;
var destinationPolygonsSorted = new NativeArray<PolygonProximityContainer>(numDestinationPolygons, Allocator.Temp);
var destinationPolygonsSuccesses = new NativeArray<bool>(numDestinationPolygons, Allocator.Temp);
var destinationPolygonToContainer = new NativeHashMap<PolygonId, PolygonProximityContainer>(numDestinationPolygons, Allocator.Temp);
var userVantageEntity = vantageFromEntity[userEntity].vantageEntity;
var userVantagePosition = translationFromEntity[userVantageEntity].Value;
for (var i = 0; i < numDestinationPolygons; i++)
{
var polygon = destinationPolygons[i];
var mapLocation = query.CreateLocation(userVantagePosition, polygon);
destinationPolygonsSorted[i] = new PolygonProximityContainer
{
polygon = polygon,
distanceFromStart = ((float3)mapLocation.position).DistanceFrom(userVantagePosition),
point = mapLocation.position
};
destinationPolygonToContainer.TryAdd(polygon, destinationPolygonsSorted[i]);
}
destinationPolygonsSorted.Sort(new DestinationPolygonsComparator());
var destinationPolygonToSortedIndex =
new NativeHashMap<PolygonId, int>(numDestinationPolygons, Allocator.Temp);
for (var i = 0; i < numDestinationPolygons; i++)
{
var destinationPolygonContainer = destinationPolygonsSorted[i];
destinationPolygonToSortedIndex.TryAdd(destinationPolygonContainer.polygon, i);
}
var unprocessedSortedDestinationPolygons =
new NativeList<PolygonProximityContainer>(numDestinationPolygons, Allocator.Temp);
unprocessedSortedDestinationPolygons.AddRange(destinationPolygonsSorted);
var userStartLocation = query.MapLocation(
userVantagePosition.To2D().To3D(middleOfEnvironment),
new Vector3(1, heightOfEnvironment, 1),
HUMANOID_AGENT_TYPE
);
var destinationsPaths = new NativeArray<PolygonId>(MAX_NUM_POLYGONS_PER_PATH * numUserDestinations, Allocator.Temp);
while (unprocessedSortedDestinationPolygons.Length > 0)
{
var polygonContainer = unprocessedSortedDestinationPolygons[0];
var polygonContainerIndex = destinationPolygonToSortedIndex[polygonContainer.polygon];
unprocessedSortedDestinationPolygons.RemoveAt(0);
var destinationPolygon = polygonContainer.polygon;
uniqueDestinationsPolygons.Remove(destinationPolygon);
var userDestination = polygonContainer.point;
var userDestinationLocation = query.CreateLocation(userDestination, destinationPolygon);
var pathBuffer = new NativeArray<PolygonId>(MAX_NUM_POLYGONS_PER_PATH, Allocator.Temp);
var success = CalculatePath(userStartLocation, userDestinationLocation, ref pathBuffer);
destinationPolygonsSuccesses[polygonContainerIndex] = success;
for (var j = 0; j < MAX_NUM_POLYGONS_PER_PATH; j++)
{
var polygonInPath = pathBuffer[j];
if (polygonInPath.Equals(default))
{
break;
}
destinationsPaths[polygonContainerIndex * MAX_NUM_POLYGONS_PER_PATH + j] = polygonInPath;
// if the polygon in the path is the same as another destination
if (uniqueDestinationsPolygons.ContainsKey(polygonInPath))
{
// WARNING: this mutates uniqueDestinationsPolygons
uniqueDestinationsPolygons.Remove(polygonInPath);
var polygonContainerInPath = destinationPolygonToContainer[polygonInPath];
unprocessedSortedDestinationPolygons.Remove(polygonContainerInPath);
var onTheWayPolygonContainerIndex = destinationPolygonsSorted.IndexOf(polygonContainerInPath);
destinationPolygonsSuccesses[onTheWayPolygonContainerIndex] = true;
var onTheWayPolygonStart = onTheWayPolygonContainerIndex * MAX_NUM_POLYGONS_PER_PATH;
for (var k = 0; k < j; k++)
{
var polygonIndex = k;
var polygonInPathIndex = destinationPolygonsSorted.IndexOf(destinationPolygonToContainer[polygonInPath]);
var onTheWayPolygonInPath = pathBuffer[polygonIndex];
destinationsPaths[onTheWayPolygonStart + polygonIndex] = onTheWayPolygonInPath;
}
}
}
}
var pathSuccess = false;
var straightPath = new NativeArray<NavMeshLocation>(MAX_WAYPOINTS_PER_PATH, Allocator.Temp);
var straightPathFlags = new NativeArray<StraightPathFlags>(MAX_WAYPOINTS_PER_PATH, Allocator.Temp);
var vertexSides = new NativeArray<float>(MAX_WAYPOINTS_PER_PATH, Allocator.Temp);
var straightPathLength = 0;
for (var i = 0; i < numUserDestinations; i++)
{
var userDestination = userDestinations[i].potentialDestination;
var userDestination3D = userDestination.To3D();
var destinationPolygon = destinationsToPolygons[userDestination];
var containerIndex = destinationPolygonToSortedIndex[destinationPolygon];
if (destinationPolygonsSuccesses[containerIndex])
{
pathSuccess = true;
var polygonPath = destinationsPaths.Slice(
containerIndex * MAX_NUM_POLYGONS_PER_PATH,
MAX_NUM_POLYGONS_PER_PATH
);
var polygonPathValid = polygonPath.SliceNonDefault(out var numValidPolygons);
PathUtils.FindStraightPath(
query,
userVantagePosition,
userDestination3D,
polygonPathValid,
numValidPolygons,
ref straightPath,
ref straightPathFlags,
ref vertexSides,
ref straightPathLength,
MAX_WAYPOINTS_PER_PATH
);
ecb.SetComponent(userEntity, new MovementPlanningDestination
{
destinationLocation = ((float3)straightPath[straightPathLength - 1].position).xz
});
var userPaths = ecb.SetBuffer<MovementPlanningWaypointsElement>(userEntity);
for (var j = 0; j < straightPathLength; j++)
{
userPaths.Add(new MovementPlanningWaypointsElement
{
waypoint = ((float3)straightPath[j].position).xz
});
}
break;
}
}
ecb.SetComponent(userEntity, new MovementPlanningStatus
{
success = pathSuccess
});
}
private struct DestinationPolygonsComparator : IComparer<PolygonProximityContainer>
{
public int Compare(PolygonProximityContainer x, PolygonProximityContainer y)
{
return (int)-(x.distanceFromStart - y.distanceFromStart);
}
}
private struct PolygonProximityContainer : IEquatable<PolygonProximityContainer>
{
public PolygonId polygon;
public float distanceFromStart;
public float3 point;
public bool Equals(PolygonProximityContainer other)
{
return polygon.Equals(other.polygon);
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private bool CalculatePath(NavMeshLocation start, NavMeshLocation end, ref NativeArray<PolygonId> pathBuffer)
{
var status = query.BeginFindPath(start, end, -1);
while (true)
{
switch (status)
{
case PathQueryStatus.InProgress:
status = query.UpdateFindPath(MAX_ITERATIONS_PER_PATH, out int currentIterations);
break;
case PathQueryStatus.Success:
var finalStatus = query.EndFindPath(out int pathLength);
var pathResult = query.GetPathResult(pathBuffer);
return true;
case PathQueryStatus.Failure:
return false;
default:
return false;
}
}
}
}
1 Like