Way to efficiently "move" the end point of a PathInterpolator?

MindsEyeGames · February 21, 2024, 12:50am

(I do want to preface the following with: I realize I may be using this all very inefficiently! Please let me know if there’s a more optimal way to achieve what I’m trying to do )

So I’m finally updating to the package-based beta version (so that I can continue to receive updates) but I was wondering: is there a way to efficiently “move” the end of a PathInterpolator?

The TL,DR is that my game has a lot of physics-based movement, and I have a custom AI system where entities try to figure out where they “want” to move and make a best-effort attempt to get there.

To this end, entities with pathfinding internally use the Seeker component to request a path, and then apply a PathInterpolator - but as an optimization if their target has not moved very much/not much time is passed, they presume the most recent path is still effectively valid, and ideally would update the path’s end point to point to the adjusted target position (to ensure they continue walking exactly towards the goal).

Based on my understanding of the code, I don’t currently see a clean way to do this. I could edit the input path List, but it looks like the interpolator builds its own copy and I would need to basically rebuild the interpolator. Ideally I’d like to have an exposed “set” on the endPoint property, but AFAICT I can’t make this change myself due to the way Unity handles the package files.

Is there any chance we can have this feature added? (Or, if I’m just being crazy: is there a better way of doing all this?)

aron_granberg · February 21, 2024, 11:32am

Hi

It sounds like you’d rather want this new struct which is present in the beta: The PathTracer.

See PathTracer - A* Pathfinding Project

It is designed to store a path and continuously repair it if the agent gets pushed away, or if the destination changes. It’s used for the new FollowerEntity movement script.

This will be much better for your use case than to try to tweak the PathInterpolator, as that one doesn’t know how to repair the path so that it stays valid.

With the PathTracer, you can assign it a path, and then use the UpdateStart and UpdateEnd methods to repair it every frame.

MindsEyeGames · February 21, 2024, 1:41pm

Thank you for responding so quickly! (And for pointing that out - wasn’t aware of the PathTracer option!)

However, while I see that the PathTracer seems much more aligned with this use case, how should I use it to actually determine how to follow the path? The Interpolator Cursor provides a lot of convenient utility functions for actually using the path, and it’s not clear to me how to do that with the tracer.

TBH my use case is okay with slightly-inaccurate paths being made, since the nav stuff is kind of a fuzzy system on top of the physics-based movement (ex: entities can get shoved a bit off the navmesh - for example, into a fire - and make a best-effort attempt to get back on track).

aron_granberg · February 21, 2024, 1:41pm

Here’s an example of how to use the PathTracer:

using Pathfinding;
using Pathfinding.Drawing;
using Pathfinding.Util;
using Unity.Collections;
using Unity.Mathematics;
using UnityEngine;

/** Demonstrates how to use a PathTracer.
 *
 * The script will calculate a path to a point a few meters ahead of it, and then use the PathTracer to show the next 10 corners of the path in the scene view.
 * If you move the object around in the scene view, you'll see the path update in real time.
 */
public class PathTracerTest: MonoBehaviour {
	PathTracer tracer;

	/** Create a new movement plane that indicates that the agent moves in the XZ plane.
	 * This is the default for 3D games.
	 */
	NativeMovementPlane movementPlane => new NativeMovementPlane(Quaternion.identity);
	ABPath lastCalculatedPath;

	void OnEnable() {
		tracer = new PathTracer(Allocator.Persistent);
	}

	void OnDisable() {
		// Release all unmanaged memory from the path tracer, to avoid memory leaks
		tracer.Dispose();
	}

	void Start() {
		// Schedule a path calculation to a point ahead of this object
		var path = ABPath.Construct(transform.position, transform.position + transform.forward*10, (p) => {
			// This callback will be called when the path has been calculated
			var path = p as ABPath;

			if (path.error) {
				// The path could not be calculated
				Debug.LogError("Could not calculate path");
				return;
			}

			// Split the path into normal sequences of nodes, and off-mesh links
			var parts = Funnel.SplitIntoParts(path);

			// Assign the path to the PathTracer
			tracer.SetPath(parts, path.path, path.originalStartPoint, path.originalEndPoint, movementPlane, path.traversalProvider, path);
			lastCalculatedPath = path;
		});
		AstarPath.StartPath(path);
	}

	void Update () {
		if (lastCalculatedPath == null || !tracer.isCreated) return;

		// Repair the path to start from the transform's position
		// If you move the transform around in the scene view, you'll see the path update in real time
		tracer.UpdateStart(transform.position, PathTracer.RepairQuality.High, movementPlane, lastCalculatedPath.traversalProvider, lastCalculatedPath);

		// Get up to the next 10 corners of the path
		var buffer = new NativeList<float3>(Allocator.Temp);
		NativeArray<int> scratchArray = default;
		tracer.GetNextCorners(buffer, 10, ref scratchArray, Allocator.Temp, lastCalculatedPath.traversalProvider, lastCalculatedPath);

		// Draw the next 10 corners of the path in the scene view
		using(Draw.WithLineWidth(2)) {
			Draw.Polyline(buffer.AsArray(), Color.red);
		}

		// Release all temporary unmanaged memory
		buffer.Dispose();
		scratchArray.Dispose();
	}
}

Basically, you’ll want to move towards the next corner of the path all the time.

MindsEyeGames · February 22, 2024, 1:17pm

Sorry for the slow response - thank you for the example!

So after looking through the code, if I understand correctly calling UpdateStart/UpdateEnd causes the PathTracer to internally search the graph to update its actual path. It appears to do this on the same thread, unless it determines the point is not on the current graph node, in which case it does an off-thread search.

After calling those, I should check isStale to see if I should trigger a fresh path, which I can forward to the Tracer via SetPath whenever it completes.

I just had a few additional questions if you don’t mind!

My game uses a fair amount of NavMeshCuts for things like moving doors - this all works with that, right?
Is there a reason the PathTracer doesn’t have a “simpler” SetPath that accepts a Path instead of needing that manual Funnel.SplitIntoParts check?
Is there a way to avoid Funnel.SplitIntoParts? It doesn’t seem particularly heavy but still
Is it okay to delegate triggering the path triggering to a Seeker component? That make actually triggering the path logic much simpler, and it looks like all the important stuff is the same as in your example
Is there a reason I can’t just use a List<Vector3> to get the corners? Since actually using all the pathfinding results is going to happen in the same thread (I’m not using Entities/jobs in this game) it seems simpler for me to just use a shared List across all nav components

aron_granberg · February 22, 2024, 1:39pm

Yes. Though when a navmesh cut updates the graph, it will usually invalidate the path that the PathTracer is following. It will make an attempt to continue following the path, but isStale will become true, and you should recalculate the path asap.

Not really. Currently, the PathTracer is only used as an implementation detail of the FollowerEntity, so I have not put a lot of effort into making the API the simplest.

No, the PathTracer requires the path to be split into parts. I mean, if you are really sure that you are not using any off-mesh links, you can construct the path parts manually, but I don’t think this is worth it.

Should be completely fine.

Yes. Internally, it uses some burst code, which cannot handle managed objects like List<Vector3>. That’s why a NativeList<float3> needs to be used instead. But you can easily convert this to a List<Vector3> if you want. You probably want to get the next 2 or 3 corners, and then move towards corners[1] (as corners[0] will be the agent’s current position).

The PathTracer itself will always repair the path on the same thread. But if you schedule a path request after checking isStale, then that path request will run on a separate thread.

aron_granberg · February 22, 2024, 1:45pm

I’ll add this method in the next update:

/** Replaces the current path with the given path.
	*
	* \param path The path to follow.
	* \param movementPlane The movement plane of the agent.
	*/
public void SetPath(ABPath path, NativeMovementPlane movementPlane) {
	var parts = Funnel.SplitIntoParts(abPath);
	// Copy settings from the path's NNConstraint to the path tracer
	var nn = state.pathTracer.nnConstraint;
	nn.constrainTags = path.nnConstraint.constrainTags;
	nn.tags = path.nnConstraint.tags;
	nn.graphMask = path.nnConstraint.graphMask;
	nn.constrainWalkability = path.nnConstraint.constrainWalkability;
	nn.walkable = path.nnConstraint.walkable;

	SetPath(parts, path.path, path.originalStartPoint, path.originalEndPoint, movementPlane, path.traversalProvider, path);
	Pathfinding.Util.ListPool<Funnel.PathPart>.Release(ref parts);
}

MindsEyeGames · February 22, 2024, 2:05pm

Awesome - that’s super helpful! (In particular good to know I need to release the Funnel path parts, I almost added a memory leak!)

In terms of API user-friendliness: may I ask why PathTracer needs a Path reference continually passed-in? It seems like letting it just store a reference to the Path its actively working on is most useful for like ~99% of use cases I can think of

But aside from that, can I also request a convenience function:

public void GetNextCorners (NativeList<float3> buffer, int maxCorners, Path path) {
  NativeArray<int> scratchArray = default;
  var results = Tracer.GetNextCorners(buffer, maxCorners, ref scratchArray, Allocator.Temp, path.traversalProvider, path);
  scratchArray.Dispose();
}

(Just to minimize boilerplate around this function )

aron_granberg · February 22, 2024, 2:08pm

That one is not a memory leak. It just allows the pool to re-use the list later. If you just forget about it, it will be collected by the GC as usual.

This is a bit annoying. The only reason it is passed in is to provide it to the ITraversalProvider interface, which currently takes a Path instance. I want to get rid of this, as it doesn’t really make a lot of sense. If you don’t use a traversal provider, you can just pass null for both the traversal provider and the path.

Keep in mind that this is a bit inefficient if you are processing multiple movement scripts at once, as it needs to allocate the scratch array every time instead of being allowed to re-use it.

MindsEyeGames · February 22, 2024, 2:17pm

That makes sense - I’ll keep that in mind!

Also, I saw you just pushed a new version - I am unfortunately getting

Library\PackageCache\com.arongranberg.astar@4.3.96\Core\ECS\Components\ManagedState.cs(125,31): error CS1503: Argument 1: cannot convert from ‘Pathfinding.Path’ to ‘Pathfinding.ABPath’

MindsEyeGames · February 22, 2024, 2:26pm

Also, I’m running into a hard Editor Crash while trying to use the 4.3.95 version PathTracer

This is almost certainly an issue on my end! But I’m not sure where the problem is

=================================================================
	Native Crash Reporting
=================================================================
Got a UNKNOWN while executing native code. This usually indicates
a fatal error in the mono runtime or one of the native libraries 
used by your application.
=================================================================

=================================================================
	Managed Stacktrace:
=================================================================
	  at <unknown> <0xffffffff>
	  at Unity.Collections.LowLevel.Unsafe.UnsafeUtility:FreeTracked <0x00094>
	  at Array:Resize <0x00182>
	  at Unmanaged:Free <0x0004a>
	  at Unity.Collections.AllocatorManager:TryLegacy <0x00192>
	  at Unity.Collections.AllocatorManager:Try <0x0003a>
	  at AllocatorHandle:Try <0x0005a>
	  at Unity.Collections.AllocatorManager:FreeBlock <0x0005a>
	  at Unity.Collections.AllocatorManager:Free <0x00092>
	  at Unity.Collections.AllocatorManager:Free <0x0003a>
	  at Unity.Collections.AllocatorManager:Free <0x00032>
	  at Pathfinding.Util.NativeCircularBuffer`1:Grow <0x00182>
	  at Pathfinding.Util.NativeCircularBuffer`1:SpliceUninitializedAbsolute <0x00072>
	  at Pathfinding.Util.NativeCircularBuffer`1:SpliceAbsolute <0x00042>
	  at Pathfinding.Util.NativeCircularBuffer`1:Splice <0x00042>
	  at FunnelState:Splice <0x00032>
	  at Pathfinding.PathTracer:SetFunnelState <0x00362>
	  at Pathfinding.PathTracer:SetPath <0x0029a>
	  at AstarAINav:OnPathComplete <0x00512>
	  at Pathfinding.Seeker:OnPathComplete <0x001ef>
	  at Pathfinding.Seeker:OnPathComplete <0x0002a>
	  at Pathfinding.Path:ReturnPath <0x00028>
	  at Pathfinding.Path:Pathfinding.IPathInternals.ReturnPath <0x00017>
	  at Pathfinding.PathReturnQueue:ReturnPaths <0x002b2>
	  at AstarPath:Update <0x000b2>
	  at System.Object:runtime_invoke_void__this__ <0x00087>
=================================================================
Received signal SIGSEGV
Obtained 52 stack frames
0x00007ff660912fab (Unity) DynamicHeapAllocator::Deallocate
0x00007ff66092452f (Unity) DualThreadAllocator<DynamicHeapAllocator>::TryDeallocate
0x00007ff660913822 (Unity) MemoryManager::Deallocate
0x00007ff66091c2ea (Unity) free_alloc_internal
0x00007ff6601ffb97 (Unity) UnsafeUtility::Free
0x00007ff66006a797 (Unity) UnsafeUtility_CUSTOM_FreeTracked
0x000001c568bdce35 (Mono JIT Code) (wrapper managed-to-native) Unity.Collections.LowLevel.Unsafe.UnsafeUtility:FreeTracked (void*,Unity.Collections.Allocator)
0x000001c5688fe2d3 (Mono JIT Code) Unity.Collections.Memory/Unmanaged/Array:Resize (void*,long,long,Unity.Collections.AllocatorManager/AllocatorHandle,long,int) (at ./Library/PackageCache/com.unity.collections@2.1.4/Unity.Collections/Memory.cs:90)
0x000001c568bdcd7b (Mono JIT Code) Unity.Collections.Memory/Unmanaged:Free (void*,Unity.Collections.AllocatorManager/AllocatorHandle) (at ./Library/PackageCache/com.unity.collections@2.1.4/Unity.Collections/Memory.cs:28)
0x000001c568bcbd43 (Mono JIT Code) Unity.Collections.AllocatorManager:TryLegacy (Unity.Collections.AllocatorManager/Block&) (at ./Library/PackageCache/com.unity.collections@2.1.4/Unity.Collections/AllocatorManager.cs:1033)
0x000001c568bcba4b (Mono JIT Code) Unity.Collections.AllocatorManager:Try (Unity.Collections.AllocatorManager/Block&) (at ./Library/PackageCache/com.unity.collections@2.1.4/Unity.Collections/AllocatorManager.cs:1055)
0x000001c568bcb9bb (Mono JIT Code) Unity.Collections.AllocatorManager/AllocatorHandle:Try (Unity.Collections.AllocatorManager/Block&) (at ./Library/PackageCache/com.unity.collections@2.1.4/Unity.Collections/AllocatorManager.cs:540)
0x000001c568bdccbb (Mono JIT Code) Unity.Collections.AllocatorManager:FreeBlock<Unity.Collections.AllocatorManager/AllocatorHandle> (Unity.Collections.AllocatorManager/AllocatorHandle&,Unity.Collections.AllocatorManager/Block&) (at ./Library/PackageCache/com.unity.collections@2.1.4/Unity.Collections/AllocatorManager.cs:70)
0x000001c568bcc453 (Mono JIT Code) Unity.Collections.AllocatorManager:Free<Unity.Collections.AllocatorManager/AllocatorHandle> (Unity.Collections.AllocatorManager/AllocatorHandle&,void*,int,int,int) (at ./Library/PackageCache/com.unity.collections@2.1.4/Unity.Collections/AllocatorManager.cs:84)
0x000001c71a90c8db (Mono JIT Code) Unity.Collections.AllocatorManager:Free<Unity.Collections.AllocatorManager/AllocatorHandle, Unity.Mathematics.float3> (Unity.Collections.AllocatorManager/AllocatorHandle&,Unity.Mathematics.float3*,int) (at ./Library/PackageCache/com.unity.collections@2.1.4/Unity.Collections/AllocatorManager.cs:89)
0x000001c71a90c853 (Mono JIT Code) Unity.Collections.AllocatorManager:Free<Unity.Mathematics.float3> (Unity.Collections.AllocatorManager/AllocatorHandle,Unity.Mathematics.float3*,int) (at ./Library/PackageCache/com.unity.collections@2.1.4/Unity.Collections/AllocatorManager.cs:153)
0x000001c73cd4b1c3 (Mono JIT Code) Pathfinding.Util.NativeCircularBuffer`1<Unity.Mathematics.float3>:Grow () (at ./Library/PackageCache/com.arongranberg.astar@4.3.95/Core/Collections/NativeCircularBuffer.cs:270)
0x000001c73cd4af83 (Mono JIT Code) Pathfinding.Util.NativeCircularBuffer`1<Unity.Mathematics.float3>:SpliceUninitializedAbsolute (int,int,int) (at ./Library/PackageCache/com.arongranberg.astar@4.3.95/Core/Collections/NativeCircularBuffer.cs:200)
0x000001c73cd4ae13 (Mono JIT Code) Pathfinding.Util.NativeCircularBuffer`1<Unity.Mathematics.float3>:SpliceAbsolute (int,int,System.Collections.Generic.List`1<Unity.Mathematics.float3>) (at ./Library/PackageCache/com.arongranberg.astar@4.3.95/Core/Collections/NativeCircularBuffer.cs:185)
0x000001c73cd4ad83 (Mono JIT Code) Pathfinding.Util.NativeCircularBuffer`1<Unity.Mathematics.float3>:Splice (int,int,System.Collections.Generic.List`1<Unity.Mathematics.float3>) (at ./Library/PackageCache/com.arongranberg.astar@4.3.95/Core/Collections/NativeCircularBuffer.cs:178)
0x000001c73cd4acb3 (Mono JIT Code) Pathfinding.Funnel/FunnelState:Splice (int,int,System.Collections.Generic.List`1<Unity.Mathematics.float3>,System.Collections.Generic.List`1<Unity.Mathematics.float3>) (at ./Library/PackageCache/com.arongranberg.astar@4.3.95/Utilities/Funnel.cs:533)
0x000001c73cd49423 (Mono JIT Code) Pathfinding.PathTracer:SetFunnelState (Pathfinding.Funnel/PathPart) (at ./Library/PackageCache/com.arongranberg.astar@4.3.95/Utilities/PathTracer.cs:1546)
0x000001c73cd4870b (Mono JIT Code) Pathfinding.PathTracer:SetPath (System.Collections.Generic.List`1<Pathfinding.Funnel/PathPart>,System.Collections.Generic.List`1<Pathfinding.GraphNode>,UnityEngine.Vector3,UnityEngine.Vector3,Pathfinding.Util.NativeMovementPlane,Pathfinding.ITraversalProvider,Pathfinding.Path) (at ./Library/PackageCache/com.arongranberg.astar@4.3.95/Utilities/PathTracer.cs:1820)
0x000001c73cd47173 (Mono JIT Code) AstarAINav:OnPathComplete (Pathfinding.Path) (at D:/Dev/Unity Projects/Delver/Assets/Scripts/_AI/_Nav/AstarAINav.cs:177)
0x000001c73cd33ae0 (Mono JIT Code) Pathfinding.Seeker:OnPathComplete (Pathfinding.Path,bool,bool) (at ./Library/PackageCache/com.arongranberg.astar@4.3.95/Core/AI/Seeker.cs:357)
0x000001c73cd338ab (Mono JIT Code) Pathfinding.Seeker:OnPathComplete (Pathfinding.Path) (at ./Library/PackageCache/com.arongranberg.astar@4.3.95/Core/AI/Seeker.cs:317)
0x000001c73cd33859 (Mono JIT Code) Pathfinding.Path:ReturnPath () (at ./Library/PackageCache/com.arongranberg.astar@4.3.95/Core/Pathfinding/Path.cs:857)
0x000001c73cd33808 (Mono JIT Code) Pathfinding.Path:Pathfinding.IPathInternals.ReturnPath () (at ./Library/PackageCache/com.arongranberg.astar@4.3.95/Core/Pathfinding/Path.cs:1068)
0x000001c71dc3c473 (Mono JIT Code) Pathfinding.PathReturnQueue:ReturnPaths (bool) (at ./Library/PackageCache/com.arongranberg.astar@4.3.95/Core/Pathfinding/PathReturnQueue.cs:61)
0x000001c71fc7e293 (Mono JIT Code) AstarPath:Update () (at ./Library/PackageCache/com.arongranberg.astar@4.3.95/Core/AstarPath.cs:888)
0x000001c5c0cbea28 (Mono JIT Code) (wrapper runtime-invoke) object:runtime_invoke_void__this__ (object,intptr,intptr,intptr)
0x00007ff8a0a94bfe (mono-2.0-bdwgc) mono_jit_runtime_invoke (at C:/build/output/Unity-Technologies/mono/mono/mini/mini-runtime.c:3445)
0x00007ff8a09cd254 (mono-2.0-bdwgc) do_runtime_invoke (at C:/build/output/Unity-Technologies/mono/mono/metadata/object.c:3068)
0x00007ff8a09cd3cc (mono-2.0-bdwgc) mono_runtime_invoke (at C:/build/output/Unity-Technologies/mono/mono/metadata/object.c:3115)
0x00007ff66102f514 (Unity) scripting_method_invoke
0x00007ff66100d274 (Unity) ScriptingInvocation::Invoke
0x00007ff660ff4a64 (Unity) MonoBehaviour::CallMethodIfAvailable
0x00007ff660ff4b8a (Unity) MonoBehaviour::CallUpdateMethod
0x00007ff660a8817b (Unity) BaseBehaviourManager::CommonUpdate<BehaviourManager>
0x00007ff660a8f6da (Unity) BehaviourManager::Update
0x00007ff660cc417d (Unity) `InitPlayerLoopCallbacks'::`2'::UpdateScriptRunBehaviourUpdateRegistrator::Forward
0x00007ff660ca32ac (Unity) ExecutePlayerLoop
0x00007ff660ca3420 (Unity) ExecutePlayerLoop
0x00007ff660ca9cb5 (Unity) PlayerLoop
0x00007ff661c73faf (Unity) PlayerLoopController::InternalUpdateScene
0x00007ff661c80ddd (Unity) PlayerLoopController::UpdateSceneIfNeededFromMainLoop
0x00007ff661c7f0c1 (Unity) Application::TickTimer
0x00007ff6620f977a (Unity) MainMessageLoop
0x00007ff6620fe650 (Unity) WinMain
0x00007ff6634de0ae (Unity) __scrt_common_main_seh
0x00007ff93b157344 (KERNEL32) BaseThreadInitThunk
0x00007ff93b7626b1 (ntdll) RtlUserThreadStart

I’ve attached the relevant script that makes the pathfinding calls (along with the full editor log) - do you see any issues?

Crash - Editor.log.txt (930.1 KB)
AstarAINav.cs.txt (7.3 KB)

aron_granberg · February 22, 2024, 2:32pm

That’s weird. The only thing I can see which is perhaps suboptimal is that you are calling Tracer.Clear right before calling SetPath. This is not required.

Thanks! I’ll fix this asap. Apparently, my automated testing script was not compiling that code…

aron_granberg · February 22, 2024, 2:34pm

Ah. No, I see it now.

You are storing your PathTracer in an auto-property. This will result in C# copying the PathTracer every time you are doing something with it, instead of modifying the original. Since the PathTracer is a struct (required to make it work with ECS).
If you store it as a field instead, things will work.

MindsEyeGames · February 22, 2024, 3:21pm

Ah nice, that fixed it!

seriously, thank you so much for all the help

aron_granberg · February 22, 2024, 3:25pm

Great! I hope it will work for you.

If you want to support the development of the package even more, a review and/or rating in the asset store goes a long way