public sealed class NavPathQueueSearches, run a slice at a time against a fixed budget, so that a crowd changing its mind all at once costs a frame what one search costs rather than what all of them do.
No guide page documents this yet — the page shows what the code says about itself.
Remarks
The problem is measured rather than imagined: a search across an eighty-metre level is about thirteen microseconds, so two hundred and fifty-six agents given a new destination in the same update is three and a half milliseconds of pathfinding — more than the whole rest of the crowd, and all of it in one frame. Spread over ten frames nobody notices; taken at once it is a visible hitch, and it happens exactly when something interesting has happened in the game.
It is a budget first and threads second. Every Update runs at most iterations polygon expansions in total, shared between however many searches are in flight, and that alone is enough to fix the spike. Setting Scheduler then runs each search's slice on a job instead of on the caller's thread — the searches are already independent, one query object each.
The two run the same rounds and give the same answers in the same updates. An update is a sequence of rounds: assign every free query from the waiting list, advance every assigned query by its share, collect whatever finished. Nothing in that depends on which thread ran what or how fast, so a scheduler changes where the work happens and nothing else — a test asserts it, the same way the sliced search is asserted to agree with the whole one.
A request whose result is never taken holds its slot until the queue runs out and starts refusing new ones. Cancel is how an agent that changed its mind again gives the slot back.
Fields and properties (4)
public NavMesh MeshThe mesh being searched.
public JobScheduler? SchedulerWhere to run the searches, or to run them on the caller's thread.
public int PendingCountHow many requests are waiting or being worked on.
public int LastIterationsHow many polygons the last Update expanded, across every search.
Methods (6)
public NavPathQueue(NavMesh mesh, int capacity = 64, int maximumPathLength = 256, int parallelSearches = 4)Creates a queue over a mesh.
public NavPathRequest Submit(NavPolyRef start, NavPolyRef end, Vector3 startPosition, Vector3 endPosition, NavQueryFilter filter)Asks for a path.
public bool Cancel(NavPathRequest request)Gives a request's slot back, whether or not it has finished.
public NavPathRequestState GetState(NavPathRequest request)How a request is getting on.
public void Update(int iterations = 128)Runs the searches for a while.
public bool TryTakeResult(NavPathRequest request, Span<NavPolyRef> path, out int count, out NavPathStatus status)Takes a finished path, and gives the slot back.
Used by (5)
- PathQueueBenchmarksVixen.Benchmarks.Navigation
- CrowdVixen.Navigation
- NavPathQueueJobTestsVixen.Navigation.Tests
- NavPathQueueTestsVixen.Navigation.Tests
- SliceJobVixen.Navigation