Finders
The Finder class and it's derivations manage creating and scheduling a path finding request and hold the result when the request is finished. Similar to how a UnityWebRequest is made.
Behind the scenes, the request is passed on to Unity's Job system, which runs it on a different thread and with the massive speedup the Burst compiler gives, so your game code can keep on running. Once your request is in flight, the finder object may not be modified until the result is back.
Awaiting a request can be done with a callback, or with a yield return statement inside of a coroutine. When the job has completed, all of the data is converted back into the managed domain, so you don't have to worry about the memory management that the Job system imposes.
The base PathFinder class has the following definition:
public class PathFinder<TGraph, TNode, TSeg, TProc>
You'll notice there are 4 (!) different generic type parameters:
- TGraph: The type of graph the finder operates on
- TNode: The type of location/node that the graph contains
- TSeg: The type of path segments the path will be made up of
- TProc: The type of (post) processing to apply to the path
Luckily, you don't need to fill these in yourself. AnyPath's built in graphs all come with predefined finders that fill in these parameters. If you've created your custom graph type, AnyPath comes with a tool to automatically generate the concrete types suitable for your graph. See Custom Graphs for more information.
Building the request
Setting data on a finder can be done directly via it's properties, or with extension methods allowing fluid style method chaining. See FinderExtensions in the API documentation for a detailed description on the extension methods.
Before making a request, a few properties need to be set:
- Graph: Set the graph the request should be evaluated on.
- Stops: The stops contain the start and goal location for the request. If you add more than two stops, AnyPath will try to find a path that visits all stops in the order in which they were added.
You can then either use the Run() method to directly run the request on the main thread, or the Schedule() method to use Unity's Job system to execute it on another thread. The Schedule method returns an IEnumerator which can be used to suspend a coroutine until the request is finished. Additionaly, you can bind to the Completed event to receive a callback.
After the request has completed, the Result property of the finder will contain the result of the request. Depending on the type of finder, this can be a Path<TSeg> object or an Eval struct.
Warning
When a finder's request is in flight, you can not modify it's properties. This is to ensure the result that comes back always matches the request's settings. If you want to reuse the same finder for a new request, you should always call Clear(ClearFinderFlags) before making a new request.
Zero allocations
Since version 1.4, finders have the ReuseResult option. When set to true, this reduces heap allocations to the absolute minimum (zero if the container doesn't have to be resized). If you perform a lot of queries over time, this will not generate any garbage at all, which is great for performance.
Warning
Be careful with using this option (especially in async mode), as the result is re-populated when the query is finished. If other objects have a seperate reference to the result class, it's content may have changed causing unexpected results.
Finder Types
Below is an overview of the different type of finders AnyPath has built in. Each of these finder types has a corresponding Evaluator, which does not reconstruct a path and is cheaper to use when all you need to know is if a path exists.
PathFinder
Just finds a path from a start to a goal, with the possibility of adding stops in between.
MultiPathFinder
A batch operation that finds multiple paths in one job.
OptionFinder
The option finder can assist in planning which target to choose from a set of options. Each option can be defined as a start and goal location with the possibility of adding stops in between. An option is associated with a user defined object of any type.
When the request is made, the options are evaluated in the order in which they were added. Then on the first option that results in a valid path, the evaluation stops and that option is returned.
PriorityOptionFinder
Similar to the OptionFinder, but prioritizes options using an IComparer that must be provided. This can be done with the SetComparer extension method or by directly assigning the Comparer property with your custom IComparer.
CheapestOptionFinder
Similar to the OptionFinder but results in the option that is the cheapest to reach from the starting location. The process is optimized in such a way that options that have a heuristic value larger than the currently found cheapest option are discarded right away.
Validating and Reserving
Consider the situation where multiple agents are given the same set of target objects to visit but you need every agent to pick a unique target. Every OptionFinder can be extended with a custom validation and reserval function on your target objects, which can help to ensure no agents will plan a path to the same object. This is shown in the included HexGrid example.
public class HexGridGoalValidator : IOptionValidator<HexGridGoal>, IOptionReserver<HexGridGoal>
{
public static HexGridGoalValidator Instance { get; } = new HexGridGoalValidator();
// A seeker may only consider goals that aren't already seeked
// This function is called before any attempt at finding a path to this target is made. When a path is found
// this is called again to ensure no other seeker reserved the goal in the time it took to run the algorithm on another thread.
// If the target was reserved in that time, the request is restarted and other options will be considered.
public bool Validate(HexGridGoal target)
{
return !target.IsSeeked;
}
// Reserves a goal so that no other seekers may target it
public void Reserve(HexGridGoal option)
{
option.IsSeeked = true;
}
}
Options are validated twice. Once before the actual A* starts, and once when the result is back. The second validation occurs because the object may have been invalidated in the time it took for the request to complete. If the validator returns false on the second call, the option is discarded and the request is retried without the options that were already marked as invalid.
Note
Be careful with clearing an option finder that's in flight in conjunction with a reserver. This may leave a dangling reservation that will never get cleared, depending on your implementation.
Note
Altough rarely the case, you can use the MaxRetries property to specify how many retries may be attempted. Keep in mind that a retry will only occur if the validation fails on the second call (which has a small chance since the change must have happened within a few ms), also, there must still be any valid options left for a retry to occur.
DijkstraFinder
Performs Dijkstra's algorithm on a graph. This can be used to obtain the shortest paths from a starting location to every other reachable location in the graph, optionally withing a maximum cost budget.
DebugFinder
Finally, there exists the debug finder. The debug finder returns the path in original node format, so you can debug it against what your path processor is doing. Also, an array containing all of the nodes A* visited, which can be helpful in determining the quality of your heuristic function, since for optimal performance, this array should be as small as possible.