Player-based pathfinding

I have a navmesh-based game using a RecastGraph with RichAI and Seekers to move AI and players along it. All works pretty well :wink:
But I want to give the option to block specific cells (a collection of nodes) to only be walkable by a player having a building on it (let’s say for visualization, a wall surrounds the whole cell).
If the wall is owned by Player A, only units from Player A should be able to walk over these nodes.

So I tried first a custom ITraversalProvider, which basically does:

        public class FactionTraversalProvider : ITraversalProvider
        {
            public uint? Id { get; private set; }

            public FactionTraversalProvider(uint? id)
            {
                Id = id;
            }

            public bool CanTraverse(Path path, GraphNode node)
            {
                unchecked
                {
                    if (!(node.Walkable && (path.enabledTags >> (int)node.Tag & 0x1) != 0))
                        return false;
                }

                var wall = GridGenerator.Instance.GetGridView((Vector3)node.position)?.Wall;
                return !wall || wall.FactionId == Id || !wall.FactionId.HasValue;
            }

            public uint GetTraversalCost(Path path, GraphNode node)
            {
                unchecked { return path.GetTagPenalty((int)node.Tag) + node.Penalty; }
            }
        }

So to recap the custom implementation, just the basic check + wall check.
I would say, that kind of works, but sometimes the AI is still moving through it, especially if the wall was recently built (I guess that could be fixed by reducing the path recalculation timeframe?)

My second problem is:
I try, especially for AI, to find suitable nearest nodes for operations, which basically rely on NavGraph.GetNearest

So I thought, well for that I can also just easily add a new NNConstraint :slight_smile:

        public class FactionNNConstraint : PathNNConstraint
        {
            public uint? Id { get; private set; }

            public FactionNNConstraint(uint? id)
            {
                Id = id;
                constrainArea = true;
            }

            public override bool Suitable(GraphNode node)
            {
                if (!base.Suitable(node))
                    return false;

                var wall = GridGenerator.Instance.GetGridView((Vector3)node.position)?.Wall;
                return !wall || wall.FactionId == Id || !wall.FactionId.HasValue;
            }
        }

But once I start using that constraint on paths of the RichAI/Seeker component it gets really weird, as my characters just randomly start to teleport into a point, which wasn’t even reachable before (because separated by water and the nodes were not even connected, even so on the same graph).

So my question is:
a) is my approach even the right one or do I even miss a simpler thing?
b) if my approach is right, what is going on with my teleports? :slight_smile:

Cheers and appreciate any help!

Hi

constrainArea = true

You have this in your constructor, but you never set which area to constrain to. This will lead to weird behavior. I’d recommend removing it.

It’s hard to tell, but yes, that would be my guess.

a) is my approach even the right one or do I even miss a simpler thing?

I think it’s probably the best approach if you cannot use built-in tags (Working with tags - A* Pathfinding Project).

Also. Your game seems to be very grid-based, but yet you are using a recast graph. Wouldn’t a grid graph be more appropriate here?

Hey Aron,

thanks for your reply!

You have this in your constructor, but you never set which area to constrain to. This will lead to weird behavior. I’d recommend removing it.

I derived from the PathNNConstraint, which sets the area inside SetStart, while this only works of course when using the Constraint with Paths, it should still work otherwise too, because of base.Suitable (inside NNConstraint) checks for area >= 0, which is by default -1 if not set by the SetStart method, so it shouldn’t have any negative impact or not?

I think it’s probably the best approach if you cannot use built-in tags (Working with tags - A* Pathfinding Project).

Yeah, I was also thinking about the tags, but (surely not an issue for my game as I don’t have more than 31 players), but basically, the tags system seems “limited”, as I only have a limited amount of them, so I thought a custom Constraint/TraversalProvider are the flexible way to go here.

Also. Your game seems to be very grid-based, but yet you are using a recast graph. Wouldn’t a grid graph be more appropriate here?

Good point, for now, I made it like that to support easier my multiple grid types (triangles, squares, hex) without having to check for the correct grid graph settings :slight_smile: But guess I will check that out later again :wink:

Ah, true. You will have to make sure you create a new FactionNNConnstraint for each path, though. Since it contains state.

Ah, true. You will have to make sure you create a new FactionNNConnstraint for each path, though. Since it contains state.

Oh, snap! I completely oversaw the fact that the PathNNConstraint.Default property is creating a new constraint each time, yeah makes totally sense! After changing my code to always get a new constraint, it is working :slight_smile: Thanks Aron!

An unrelated question regards the topic of that thread so, whenever I try to scan my recast graph, I get the following error:

System.InvalidOperationException: Attempted to operate on {size} bytes of memory: nonsensical
This Exception was thrown from a job compiled with Burst, which has limited exception support.
0x00007ff8d3822ff9 (3453c51d2462365c16da388e27f5e67) [AllocatorManager.cs:37] Unity.Collections.AllocatorManager.AllocateBlock<Unity.Collections.AllocatorManager.AllocatorHandle> 
0x00007ff8d382dffe (3453c51d2462365c16da388e27f5e67) [UnsafeList.cs:410] Unity.Collections.LowLevel.Unsafe.UnsafeList`1<Pathfinding.Voxels.Burst.LinkedVoxelSpan>::Unity.Collections.LowLevel.Unsafe.UnsafeList`1<Pathfinding.Voxels.Burst.LinkedVoxelSpan>.SetCapacity<Unity.Collections.AllocatorManager.AllocatorHandle> 
0x00007ff8d382f74e (3453c51d2462365c16da388e27f5e67) [LinkedVoxelFieldBurst.cs:223] Pathfinding.Voxels.Burst.LinkedVoxelField::Pathfinding.Voxels.Burst.LinkedVoxelField.AddLinkedSpan 
0x00007ff8d383a057 (3453c51d2462365c16da388e27f5e67) [unknown:0] Unity.Jobs.IJobExtensions.JobStruct`1<Pathfinding.RecastGraph.JobBuildTileMesh>.Execute 
0x00007ff8d3837ab1 (3453c51d2462365c16da388e27f5e67) 47c4e6c4f91b68d606af7267c3233e7e
0x00007ff7499e33b0 (Unity) ExecuteJob
0x00007ff7499e45bf (Unity) ForwardJobToManaged
0x00007ff7499df890 (Unity) JobQueue::Exec
0x00007ff7499e17e1 (Unity) JobQueue::Steal
0x00007ff7499dfc20 (Unity) JobQueue::ExecuteJobFromQueue
0x00007ff7499e00eb (Unity) JobQueue::ProcessJobs
0x00007ff7499e213f (Unity) JobQueue::WorkLoop
0x00007ff749bdc8b7 (Unity) Thread::RunThreadWrapper
0x00007ff8f3d47034 (KERNEL32) BaseThreadInitThunk
0x00007ff8f55026a1 (ntdll) RtlUserThreadStart

It seems non-critical as the graph gets updated correctly, but nonetheless weird to see :slight_smile:

1 Like

Hmm, that sounds pretty bad! Can you try to run it without burst compilation enabled and see what you get?

It took quite a few seconds to generate the graph without burst, but here is the error:

InvalidOperationException: Attempted to operate on {size} bytes of memory: nonsensical
Unity.Collections.Memory.CheckByteCountIsReasonable (System.Int64 size) (at Library/PackageCache/com.unity.collections@1.2.4/Unity.Collections/Memory.cs:150)
Unity.Collections.Memory+Unmanaged+Array.Resize (System.Void* oldPointer, System.Int64 oldCount, System.Int64 newCount, Unity.Collections.AllocatorManager+AllocatorHandle allocator, System.Int64 size, System.Int32 align) (at Library/PackageCache/com.unity.collections@1.2.4/Unity.Collections/Memory.cs:78)
Unity.Collections.Memory+Unmanaged.Allocate (System.Int64 size, System.Int32 align, Unity.Collections.AllocatorManager+AllocatorHandle allocator) (at Library/PackageCache/com.unity.collections@1.2.4/Unity.Collections/Memory.cs:20)
Unity.Collections.AllocatorManager.TryLegacy (Unity.Collections.AllocatorManager+Block& block) (at Library/PackageCache/com.unity.collections@1.2.4/Unity.Collections/AllocatorManager.cs:851)
Unity.Collections.AllocatorManager.Try (Unity.Collections.AllocatorManager+Block& block) (at Library/PackageCache/com.unity.collections@1.2.4/Unity.Collections/AllocatorManager.cs:883)
Unity.Collections.AllocatorManager+AllocatorHandle.Try (Unity.Collections.AllocatorManager+Block& block) (at Library/PackageCache/com.unity.collections@1.2.4/Unity.Collections/AllocatorManager.cs:511)
Unity.Collections.AllocatorManager.AllocateBlock[T] (T& t, System.Int32 sizeOf, System.Int32 alignOf, System.Int32 items) (at Library/PackageCache/com.unity.collections@1.2.4/Unity.Collections/AllocatorManager.cs:34)
Unity.Collections.AllocatorManager.Allocate[T] (T& t, System.Int32 sizeOf, System.Int32 alignOf, System.Int32 items) (at Library/PackageCache/com.unity.collections@1.2.4/Unity.Collections/AllocatorManager.cs:46)
Unity.Collections.LowLevel.Unsafe.UnsafeList`1[T].Realloc[U] (U& allocator, System.Int32 newCapacity) (at Library/PackageCache/com.unity.collections@1.2.4/Unity.Collections/UnsafeList.cs:375)
Unity.Collections.LowLevel.Unsafe.UnsafeList`1[T].SetCapacity[U] (U& allocator, System.Int32 capacity) (at Library/PackageCache/com.unity.collections@1.2.4/Unity.Collections/UnsafeList.cs:410)
Unity.Collections.LowLevel.Unsafe.UnsafeList`1[T].SetCapacity (System.Int32 capacity) (at Library/PackageCache/com.unity.collections@1.2.4/Unity.Collections/UnsafeList.cs:419)
Unity.Collections.LowLevel.Unsafe.UnsafeList`1[T].Resize (System.Int32 length, Unity.Collections.NativeArrayOptions options) (at Library/PackageCache/com.unity.collections@1.2.4/Unity.Collections/UnsafeList.cs:351)
Unity.Collections.NativeList`1[T].Resize (System.Int32 length, Unity.Collections.NativeArrayOptions options) (at Library/PackageCache/com.unity.collections@1.2.4/Unity.Collections/NativeList.cs:800)
Pathfinding.Voxels.Burst.LinkedVoxelField.AddLinkedSpan (System.Int32 index, System.UInt32 bottom, System.UInt32 top, System.Int32 area, System.Int32 voxelWalkableClimb, System.Int32 objectID) (at ExternalPackages/com.arongranberg.astar4.3.51/Generators/Utilities/Voxels/LinkedVoxelFieldBurst.cs:223)
Pathfinding.Voxels.Burst.JobVoxelize.Execute () (at ExternalPackages/com.arongranberg.astar4.3.51/Generators/Utilities/Voxels/VoxelRasterizationBurst.cs:243)
Pathfinding.RecastGraph+JobBuildTileMesh.Execute () (at ExternalPackages/com.arongranberg.astar4.3.51/Generators/RecastGenerator.cs:1643)
Unity.Jobs.IJobExtensions+JobStruct`1[T].Execute (T& data, System.IntPtr additionalPtr, System.IntPtr bufferRangePatchData, Unity.Jobs.LowLevel.Unsafe.JobRanges& ranges, System.Int32 jobIndex) (at <24d45e813e524a99bfb7a145158a7980>:0)

Hey Aron,

my creatures are still not walking correctly along the graph (like walking on nodes which even the suitable method returns false… )
Nonetheless I found a piece of code inside your StartEndModifier.cs which is curious for me:

Vector3 Snap (ABPath path, Exactness mode, bool start, out bool forceAddPoint, out int closestConnectionIndex) {
			var index = start ? 0 : path.path.Count - 1;
			var node = path.path[index];
			var nodePos = (Vector3)node.position;

			closestConnectionIndex = 0;

			forceAddPoint = false;

			switch (mode) {
			case Exactness.ClosestOnNode:
				return start ? path.startPoint : path.endPoint;
			case Exactness.SnapToNode:
				return nodePos;
			case Exactness.Original:
			case Exactness.Interpolate:
			case Exactness.NodeConnection:
				Vector3 relevantPoint;
				if (start) {
					relevantPoint = adjustStartPoint != null? adjustStartPoint() : path.originalStartPoint;
				} else {
					relevantPoint = path.originalEndPoint;
				}

				switch (mode) {
				case Exactness.Original:
					return GetClampedPoint(nodePos, relevantPoint, node);
				case Exactness.Interpolate:
					// Adjacent node to either the start node or the end node in the path
					var adjacentNode = path.path[Mathf.Clamp(index + (start ? 1 : -1), 0, path.path.Count-1)];
					return VectorMath.ClosestPointOnSegment(nodePos, (Vector3)adjacentNode.position, relevantPoint);
				case Exactness.NodeConnection:
					// This code uses some tricks to avoid allocations
					// even though it uses delegates heavily
					// The connectionBufferAddDelegate delegate simply adds whatever node
					// it is called with to the connectionBuffer
					connectionBuffer = connectionBuffer ?? new List<GraphNode>();
					connectionBufferAddDelegate = connectionBufferAddDelegate ?? (System.Action<GraphNode>)connectionBuffer.Add;

					// Adjacent node to either the start node or the end node in the path
					adjacentNode = path.path[Mathf.Clamp(index + (start ? 1 : -1), 0, path.path.Count-1)];

					// Add all neighbours of #node to the connectionBuffer
					node.GetConnections(connectionBufferAddDelegate);
					var bestPos = nodePos;
					var bestDist = float.PositiveInfinity;

					// Loop through all neighbours
					// Do it in reverse order because the length of the connectionBuffer
					// will change during iteration
					for (int i = connectionBuffer.Count - 1; i >= 0; i--) {
						var neighbour = connectionBuffer[i];
						if (!path.CanTraverse(neighbour)) continue;

						// Find the closest point on the connection between the nodes
						// and check if the distance to that point is lower than the previous best
						var closest = VectorMath.ClosestPointOnSegment(nodePos, (Vector3)neighbour.position, relevantPoint);

						var dist = (closest - relevantPoint).sqrMagnitude;
						if (dist < bestDist) {
							bestPos = closest;
							bestDist = dist;
							closestConnectionIndex = i;

							// If this node is not the adjacent node
							// then the path should go through the start node as well
							forceAddPoint = neighbour != adjacentNode;
						}
					}

					connectionBuffer.Clear();
					return bestPos;
				default:
					throw new System.ArgumentException("Cannot reach this point, but the compiler is not smart enough to realize that.");
				}
			default:
				throw new System.ArgumentException("Invalid mode");
			}
		}

You have a nested ‘switch(mode)’ inside ‘case Exactness.NodeConnection’, which basically renders all the options inside that nested switch except for ‘case Exactness.NodeConnection’ useless. Do I miss something?

Cheers

Note that Original and Interpolate fall through in the outer switch statement. So inside the inner switch statement we have to check for Original, Interpolate and NodeConnection, but not the other ones.

Gotcha!

I found also the reason why my pathfinding was still not working…
The RichAI had recalculate path enabled, which is of course nice, but unfortunately, the triggered SearchPath() is just constructing a path without any constraints and traversalproviders :slight_smile:

1 Like