PathfindingLib

A library for Lethal Company mods (and probably mods for any other game using Unity's AI Navigation package) to run pathfinding off the main thread.

A high-level API is provided to allow convenient calculation of single paths off the main thread.

Synchronization functions are provided to prevent modifications to the navmesh while searching for a path on a non-main thread. If such a thread reads from the navmesh without synchronizing first, the engine may access invalid memory and crash. See the Threading Safety section.

This readme is a work in progress!

Feel free to submit suggestions for clarifications or improvements as issues or pull requests.

Usage

In order to run pathfinding off the main thread, the library provides a pre-built job called FindPathJob that can be used to calculate a path that the provided NavMeshAgent can traverse from a starting position to an ending position.

To do so, you will need to request a job from the pool of jobs:

var pooledJob = JobPools.GetFindPathJob();

Then you will need to initialize the job with the data it needs to run off the main thread:

pooledJob.Job.Initialize(origin, destination, agent);

If you are simply finding a path from the agent to a destination, it is recommended to use the GetPathOrigin() extension method to determine where such a path should begin, ensuring that the path succeeds even if the agent is on a navmesh link:

var origin = agent.GetPathOrigin();
pooledJob.Job.Initialize(origin, destination, agent);

After the job is initialized, you should schedule your job via ScheduleByRef() to run whenever there are job threads available, then store the job to check the status later. When scheduling, it is preferred to ensure that your job runs after any previous jobs you have scheduled for the agent:

var previousJobHandle = default(JobHandle);
for (var i = 0; i < destinations.Length; i++) {
    var pooledJob = JobPools.GetFindPathJob();
    var origin = agent.GetPathOrigin();
    pooledJob.Job.Initialize(origin, destinations[i], agent);
    previousJobHandle = pooledJob.Job.ScheduleByRef(previousJobHandle);
    pathJobs[i] = pooledJob;    // Store the job to query status later
}

Then, you can check the status using GetStatus(), and check the path length using GetPathLength():

var result = pooledJob.Job.GetStatus().GetResult(); // GetResult() removes detail flags from the status
if (result != PathQueryStatus.InProgress) {
    var pathReachedDestination = result == PathQueryStatus.Success;
    if (pathReachedDestination) {
        var pathLength = pooledJob.Job.GetPathLength();
        // Use the result of the job here
    }
}

In order to not leak jobs, ensure that you release the job back to the pool when you don't need it anymore:

JobPools.ReleaseFindPathJob(pooledJob);

If you are checking a large number of paths, it may be preferable for you to implement your own job to run through an array of destinations, rather than scheduling multiple individual FindPathJob instances. The code in FindPathJob can be adapted to implement IJobFor instead of IJob, and only grow arrays as necessary to fit the input data. However, you will need to ensure that you use the safeties outlined in the section on Threading Safety.

Threading Safety

If you choose to implement your own Unity Job to calculate a path off the main thread instead of using the provided FindPathJob, any calls to NavMeshQuery methods should be preceded by a call to NavMeshLock.BeginRead(), which will block the thread until the navmesh is safe to read without causing crashes. Then, on all code branches following the start of the read, NavMeshLock.EndRead() must be called, or the main thread will be deadlocked when it reaches the next AI update.

Here is a simple excerpt of how this can be handled:

// Block until the navmesh is safely readable.
NavMeshLock.BeginRead();

var status = query.BeginFindPath(origin, destination, areaMask);
if (status.GetStatus() == PathQueryStatus.Failure)
{
    // We are returning early. Release our read lock on the navmesh to unblock
    // the main thread.
    NavMeshLock.EndRead();
    return status;
}

while (status.GetStatus() == PathQueryStatus.InProgress)
{
    // Limit on the number of iterations per read lock to free up the main thread quickly
    // when it is waiting for a write lock.
    status = query.UpdateFindPath(NavMeshLock.RecommendedUpdateFindPathIterationCount, out int _);
    NavMeshLock.YieldRead();
}

status = query.EndFindPath(out var pathNodesSize);

if (status.GetStatus() != PathQueryStatus.Success)
{
    // Another early return, release the lock.
    NavMeshLock.EndRead();
    return status;
}

var pathNodes = new NativeArray<PolygonId>(pathNodesSize, Allocator.Temp);
query.GetPathResult(pathNodes);

// Release the lock once we are done with all code that needs access to our
// NavMeshQuery.
NavMeshLock.EndRead();

Version 0.0.11

• Reverted unreliable NavMeshLock safeties that were causing exceptions when apparently taking read locks on the main thread.

Version 0.0.10

• Fixed pathfinding jobs not functioning properly in release builds.

Version 0.0.9

• Added some extra checks to help ensure NavMeshLock that is used safely.
• Made TogglableProfilerAuto methods public.

Version 0.0.8

• Fixed an issue where FindPathJob was not taking the read lock at the start of the job, but would later take the lock without releasing it, which could result in deadlocks.

Version 0.0.7

• Reduced blocking of the main thread by hooking into the Unity runtime to detect when carving obstacles will make changes to the navmesh.
• Changed documentation to recommend using NavMeshQuery.UpdateFindPath() with an iteration limit, and unlocking the navmesh read between calls.

Version 0.0.6

• Prevented API users releasing null PooledFindPathJob back to the pool to avoid null error spam.

Version 0.0.5

• Reverted an unintentional change to the plugin's GUID string.

Version 0.0.4

• Made the plugin GUID public for convenient hard dependency setup.

Version 0.0.3

• Renamed the Plugin class to PathfindingLibPlugin.

Version 0.0.2

• Replaced the icon with a new placeholder that will totally not stay indefinitely...

Version 0.0.1

Initial version. Public-facing API includes:

• FindPathJob: A simple job to find a valid path for an agent to traverse between a start and end position.
• JobPools: A static class providing pooled FindPathJob instances that can be reused by any API users.
• NavMeshLock: Provides methods to prevent crashes when running pathfinding off the main thread.
• PathfindingJobSharedResources: A static class that provides a NativeArray<NavMeshQuery> that can be passed to a job to access a thread-specific instance of NavMeshQuery.
• AgentExtensions.GetAgentPathOrigin(this NavMeshAgent): Gets the position that paths originating from an agent should start from. This avoids pathing failure when crossing links.
• Pathfinding.FindStraightPath(...): Gets a straight path from the result of a NavMeshQuery.