Before I make the jump to the Pro version (which MultiPathTarget is a part of), I wanted to make sure that it would be the right solution for my use case!
I’m using PathUtilities.BFS() to find the nearest node with X tag from a given starting position. Once a target is acquired, it has a ring of “parking spots” around it, and I believe MultiTargetPath would be the answer to finding the closest parking spot around the target. Something like this?
(Assume that GetEntity has a signature: public Entity GetEntity(GraphNode node) and that GetNode has a signature: public GraphNode GetNode(Vector3 position):
List<GraphNode> targets = ListPool<GraphNode>.Claim();
int tagMask = (1 << Tags.Ground) | (1 << Tags.Resource);
PathUtilities.BFS(MyNode, int.MaxValue, tagMask, (GraphNode node) => {
// Only save nodes which have our desired tag
if (node.Tag == Tags.Resource) {
targets.Add(node);
}
return true;
});
foreach (GraphNode target in targets) {
// Get all the parking spots from the entity
List<Vector3> spots = GetEntity(target).ParkingSpots;
List<Vector3> validSpots = new List<Vector3();
foreach (Vector3 spot in spots) {
if (PathUtilities.IsPathPossible(MyNode, GetNode(spot), (1 << Tags.Ground)) {
validSpots.Add(spot);
}
}
if (validSpots.Count > 0) {
// The first valid node from BFS will always be the closest, so break here
Seeker.StartMultiTargetPath(transform.position, validSpots, false, OnPathFound);
break;
}
}
ListPool<GraphNode>.Release(targets);
(Please excuse the lack of error-checking )
If that looks reasonable (Use BFS to find/filter the potential target nodes by tag, use MultiTargetPath to find the closest “parking spot” around the closest target)… then consider me a Pro customer
Yes that looks like it should work.
However it would be quite slow, in particular the IsPathPossible method call with a tagmask is a very slow function. If the number of parking spots is not too large, I would recommend just passing the whole list of parking spots to the StartMultiTargetPath method (and make sure that ‘pathsForAll’ is disabled, otherwise it will try to calculate a path to every single parking spot), that will be a lot faster I think. It will also be a bit more correct. You note in your code that
// The first valid node from BFS will always be the closest, so break here
however the closest parking spot is not necessarily around the closest entity (depending on how the parking spots are distributed). So making a list of all valid parking spots and passing that to the StartMultiTargetPath method should be a bit more accurate.
You can actually simplify this even more if you mark all nodes with a parking spot using some tag (not sure if that’s reasonable in your game). The XPath class (exists in the pro version) calculates a path, but it can also be given a custom ending condition. So you can do something like this:
public class TagEndingCondition : PathEndingCondition {
public int tag;
public TagEndingCondition (int tag) {
this.tag = tag;
}
public override bool TargetFound (PathNode node) {
return node.Tag == tag;
}
}
var start = new Vector3 (2.5f, 0, -6.5f);
// We don't actually use the end point of the path for anything, so set the start point and end point to the same point
var p = XPath.Construct(start, start);
var tag = 3; // For example
p.endingCondition = new TagEndingCondition(tag);
// No heuristic makes it search radially outwards (like a dijkstra search)
// so the first valid target (i.e. satisfies the ending condition) we find will be the closest one
p.heuristic = Heuristic.None;
AstarPath.StartPath(p);
// When p is calculated, it will be the path to the closest node with the specified tag
I’m happy to contribute back to the forums! I just hope I know enough to be more helpful than harmful!
iiiiinteresting! I haven’t looked much at XPath yet. I think I could get rid of the IsPathPossible call entirely, since Seeker.StartMultiTargetPath() will automatically exclude nodes that can’t be traversed by the Seeker… (it’s only in there right now because I’m using the free version.)
Here’s a quick diagram of what I’m looking for:
The agent (purple ball) wants to find the nearest Green resource. It doesn’t care about Orange resources.
All of the blue nodes could be potential parking spots for Orange or Green resources
It’s identified T as the closest Green resource via BFS(). Others are closer, but Red nodes tagged “Obstacle” are in the way
Spot A should be excluded because it’s not a parking spot for Resource T
Spots B and C are on an inaccessible “island” blocked by other Green resources or Red obstacles
Spots D and E are equally close (no heuristics) so either can be end nodes
Spot F is farther away, so should be excluded
I think if I identify Resource T, then pass all of its potential Vector3 parking spot positions (B, C, D, E, and F) into Seeker.StartMultiTargetPath(), that should get me the results I’m looking for! The way my game is set up, I believe the closest entity found via BFS() will also logically have the closest parking spots.
I’ll definitely check out XPath to see if it can simplify my two-step process (BFS + MultiTargetPath) into one!
Thank you as always for your help and support in these forums!
Yep, parking spots form an immediate perimeter around resources and buildings. Buildings can be various sizes, so a 1x1 resource has 8 parking spots, but a 3x2 building has 14 (5 on top, 2 on each side, 5 on bottom).
When buildings/resources are adjacent to each other, their parking spots overlap:
That kept me from being able to tag certain nodes as “GreenParkingSpot” and “OrangeParkingSpot”, because certain nodes can be both (or many!)
Part of the reason for using the parking spot approach was because many many agents may be trying to harvest/access the same resource/building at the same time, and I wanted them to organize themselves in a tidy way around the target!
Okay. Then you could use this modification of the ending condition to check if there’s an adjacent node with the correct tag. So then you won’t even have to keep track of which nodes are parking spots, you can just ask it to find the closest node which is adjacent to a node with a particular tag.
public class TagEndingCondition : PathEndingCondition {
public int tag;
public TagEndingCondition (int tag) {
this.tag = tag;
}
public override bool TargetFound (PathNode node) {
bool found = false;
// note: this creates a delegate which will allocate a bit of memory, if want to avoid all allocations (for GC reasons) you could cache this delegate.
node.GetConnections(adjacentNode => found |= adjacentNode.Tag == tag);
return found;
}
}
If you have some kind of reservation system in place for parking spots you could even add a check for “find the closest node adjacent to a resource node given that the node is not reserved by another agent”.
Awesome! I do have a kind of reservation system… agents have to check their path + end node periodically along their journey, in case the graph changes en route (got cut off from their target), or in the race condition where multiple agents try to claim the same parking spot in different threads (they don’t know which parking spot they’re going to end up with until the Pathfinding callback is executed)… but yeah, those are just details
This is excellent, thank you very much once again!
)
