Wayfarer Tools

PathFinder Manual

Version 1.0.0

PathFinder is a complete pathfinding solution for Unity: several graph types, a multithreaded A* core, path post-processing, ready to use movement components and ORCA based local avoidance for crowds.

1. Installation and requirements

The package is split into assembly definitions: PathFinder.Runtime, PathFinder.Editor, PathFinder.Samples and PathFinder.Tests.EditMode. Reference PathFinder.Runtime from your own asmdef if you use them.

2. Core concepts

Graph — a set of nodes and connections that describes where agents can walk. A scene can have up to 32 graphs.

Node — one walkable location (a grid cell, a triangle or a waypoint). Nodes have a position, a walkable flag, a penalty (extra cost) and a tag (0..31).

Area — a connected component. After every scan and graph update PathFinder flood fills the graphs and stores an area id on each node. Two nodes with the same area are guaranteed to be reachable from each other; this is used to answer "is a path possible?" instantly and to make unreachable targets cheap to handle.

Path — a request from A to B. Paths are calculated on worker threads and returned on the main thread through a callback. The result is a list of nodes and a list of world space points (VectorPath).

Seeker — the component that requests paths for one agent and applies modifiers.

Modifier — a component that post-processes the point list (funnel, raycast simplification, smoothing).

Graph update — a runtime change to nodes inside a bounding box: walkability, penalty, tag or a physics rescan.

3. The Pathfinder Manager

Create it with GameObject > PathFinder > Pathfinder Manager. There must be exactly one in the scene.

Inspector sections:

Runtime API highlights (PathfinderManager.Active):

manager.Scan();                              // rescan everything (blocks, pauses threads)
manager.ScanGraph(graph);                    // rescan one graph
manager.StartPath(path);                     // queue a path
manager.GetNearest(position, NNConstraint.Default);
manager.UpdateGraphs(new GraphUpdateObject(bounds));
manager.FlushGraphUpdates();                 // apply queued updates now
manager.OnGraphsScanned += () => { ... };
manager.OnGraphsUpdated += () => { ... };

4. Graph types

Grid Graph

A regular grid of square nodes. Best for open terrain, RTS/tower defence maps and anything that changes at runtime.

Extra features: Linecast(from, to, out hit) walks the cells between two points and reports the first blocked boundary. Graph updates support physics rescans (UpdatePhysics = true), used by DynamicObstacle.

Layered Grid Graph

A grid graph where every cell column can hold several nodes (floors of a building, bridges). Extra settings: Max Layers, Character Height (minimum head room; nodes with a ceiling closer than this are unwalkable) and Merge Distance. Everything else works like the grid graph, including updates and linecasts. Each cell column is scanned with a RaycastAll, so layered grids scan slower than plain grids; keep them as small as the level allows.

Point Graph

Hand placed waypoints. Assign a Root transform whose children (recursively) become nodes, or a Search Tag. Nodes within Max Distance are connected, optionally only when a Raycast (with Thickness) finds no obstacle. From code you can AddNode, Connect and Disconnect at runtime. Nearest node queries are brute force, which is fine for a few thousand nodes.

A graph of triangles. Two sources:

Vertices closer than Weld Threshold are merged so adjacent triangles become neighbours. Nearest node queries use a bucket grid (Lookup Cell Size, 0 = automatic). The graph supports linecasts (walking across triangle edges). Always add a Funnel Modifier to seekers using navmesh graphs; the raw path goes through triangle centres.

You can also build a navmesh graph from code with graph.Build(vertices, triangles) followed by manager.RebuildNodeLookup() and manager.RecalculateAreas() under the write lock, or simply manager.ScanGraph(graph) after assigning SourceMesh.

Recast Graph (automatic navmesh)

Generates a navmesh from the scene automatically. Set Bounds Center / Bounds Size (scene handles are available), pick what to voxelize (Rasterize Colliders, Meshes, Terrains), a layer Mask and optionally an Exclude Tag for your agents, then scan.

Recast settings:

The pipeline is: rasterize triangles into a heightfield, filter ledges and low ceilings, build a compact heightfield, erode by the agent radius, partition into regions, trace and simplify contours, triangulate and weld. The result is a normal navmesh graph, so everything from the NavMesh Graph section applies (use a Funnel Modifier). Build times: a 60 x 60 m level at 0.3 m cells takes a few tens of milliseconds.

Give agents no colliders, or put them on a layer excluded from Mask / give them the Exclude Tag, otherwise they are baked into the mesh.

5. Requesting paths from code

The simplest way is through a Seeker:

using PathFinder;

public class Example : MonoBehaviour
{
    Seeker seeker;

    void Start()
    {
        seeker = GetComponent<Seeker>();
        seeker.StartPath(transform.position, target.position, OnPathComplete);
    }

    void OnPathComplete(Path path)
    {
        if (path.Error) { Debug.Log(path.ErrorLog); return; }
        // path.VectorPath is a List<Vector3> of waypoints, path.Nodes the nodes
        Debug.Log("Path with " + path.VectorPath.Count + " points, state " + path.CompleteState);
    }
}

Without a Seeker (no modifiers are applied):

var path = ABPath.Construct(start, end, p => Debug.Log(p.CompleteState));
PathfinderManager.Active.StartPath(path);

Path types:

Path settings (all optional): TraversableTags, TagPenalties, NNConstraint (which graphs / tags / area may be used for the start and end node, XZ distance, max distance), HeuristicOverride, CalculatePartial, MaxSearchedNodesOverride, StartSnapping / EndSnapping.

CompleteState is Complete, Partial (target unreachable; the path leads to the closest reachable node) or Error (see ErrorLog). SearchedNodes and DurationMs are filled for profiling.

In edit mode (no worker threads) StartPath calculates synchronously, which is handy for editor tools and tests. manager.CalculateImmediately(path) does the same at runtime when you need a result right now.

6. Seeker and modifiers

Seeker settings: Traversable Tags (bit mask), Tag Penalties, Graph Mask, start/end snapping, Allow Partial Paths, gizmo colour. Requesting a new path cancels the previous pending one. Subscribe to seeker.PathCallback to receive every path, or pass a callback to StartPath.

Modifiers live on the same GameObject and run in ascending Order:

Write your own by deriving from PathModifier and implementing Apply(Path path).

7. Moving agents (AIPath)

Add AIPath (it requires a Seeker). Set Destination from code or add AIDestinationSetter with a target transform. The agent repaths every Repath Rate seconds and follows the path.

Movement settings: Max Speed, Max Acceleration, Rotation Speed, Slowdown Distance, Pick Next Waypoint Distance, End Reached Distance. Mode is Auto (CharacterController or Rigidbody when present, otherwise the transform), and gravity is applied in CharacterController mode. In Transform mode the agent follows the path height, so it walks up ramps on layered grids without physics.

Off-mesh links: when a path crosses a Node Link the agent switches to Link Traversal mode: Jump (parabolic arc with Jump Height), Straight or Teleport, at Link Speed Multiplier times the max speed. Local avoidance and gravity are suspended while crossing; IsTraversingLink is true and OnLinkStarted / OnLinkFinished fire with the link segment, which is where you trigger a jump animation.

Useful members: ReachedEndOfPath, ReachedDestination, RemainingDistance, Velocity, IsStopped, CanMove, CanSearch, SearchPath(), SetPath(path), Teleport(position), events OnTargetReached and OnPathCalculated. AIPath.All lists every enabled agent.

Patrol cycles an agent through a list of transforms with an optional delay, sequentially or randomly.

8. Local avoidance (RVO)

Add GameObject > PathFinder > RVO Simulator once per scene and an RVOController to each agent. AIPath detects the controller and routes its desired velocity through the simulation automatically. Objects without AIPath can set DesiredVelocity themselves and read CalculatedVelocity, or tick Move Self.

The simulation is an original implementation of ORCA (optimal reciprocal collision avoidance): every neighbour contributes a half-plane of allowed velocities and a small linear program finds the allowed velocity closest to the desired one. Settings: simulation FPS, Agent Time Horizon (how early agents react to each other), Obstacle Time Horizon, Max Neighbours, Neighbour Distance, Symmetry Breaking and multithreading.

Per agent: Radius, Height (agents on different floors ignore each other), Priority (higher priority agents are avoided more by others), Locked (does not move but is avoided), RVO Layer and Collides With masks.

RVOObstacle adds static obstacles: a box from the transform (or BoxCollider) or a custom polyline. Tick Dynamic for moving obstacles. Obstacles are handled by treating the closest point on each edge as a static agent, which is robust for walls and boxes but does not model long concave shapes perfectly.

9. Tags and penalties

Every node has a tag (0..31) and a penalty in world units (a penalty of 5 costs the same as walking five extra units). Seekers choose which tags they may traverse (Traversable Tags) and how expensive each tag is (Tag Penalties). Typical uses: "road" tag with negative penalty preference for vehicles, "water" only for amphibious units, "door" tag that some factions cannot pass.

Set tags and penalties with graph updates, with GraphUpdateScene components placed in the level, with erosion tags, or from code by iterating graph.GetNodes(...) under manager.GraphLock write lock.

10. Graph updates at runtime

var guo = new GraphUpdateObject(collider.bounds)
{
    UpdatePhysics = true,      // rescan height and collision for the nodes (grid graphs)
    ModifyWalkability = false, // or set SetWalkability
    AddPenalty = 10f,
    ModifyTag = true, SetTag = 2
};
PathfinderManager.Active.UpdateGraphs(guo);

Updates are queued and applied on the main thread during the next Update (or the next batch flush) while pathfinding threads are paused. Areas are recomputed afterwards. NodeFilter and CustomAction let you apply arbitrary changes.

Components:

Graph cache

Scanning needs physics queries and can take a while on big levels. Press Save Cache To File... on the manager to store the node data of all graphs in a .bytes asset, assign it to Cache File and tick Load Cache On Awake. At startup the nodes are restored in a few milliseconds without touching physics. The cache stores nodes only; the graph settings stay in the scene, and the graph list must match the one used when saving (same count and types), otherwise loading fails and the manager falls back to scanning. Grid, layered grid, point, navmesh and recast graphs support caching. From code: manager.SaveCache() returns the bytes, manager.LoadCache(bytes) restores them. Remember to save the cache again after changing the level.

10b. 2D games (XY plane)

Set Movement Plane on the manager to XY. Then:

The 07 2D Grid Graph demo scene shows a complete 2D setup with sprites and 2D colliders.

11. Utilities

PathUtilities.IsPathPossible(a, b) (nodes or positions), GetReachableNodes(seed, tagMask, maxDepth), GetNodesWithinCost(seed, maxCost), GetPointsAroundPoint(center, count, spacing) for group formations, GetRandomNode(list).

manager.GetNearest(position, constraint) returns the closest node and the position clamped to it. NNConstraint lets you restrict graphs, walkability, tags, area and distance.

12. Performance guide

13. Troubleshooting

13b. Tests and demo captures

Tests/EditMode contains unit tests for the core (heap, grid, navmesh, funnel, tags, cache, node links, recast builder, ORCA). Tests/PlayMode runs the generated demo scenes for real: agents are sent to targets and the tests assert they arrive, climb the ramp, cross the RVO circle and that dynamic obstacles update the grid. Run them in Window > General > Test Runner or from the command line:

Unity.exe -batchmode -projectPath <project> -runTests -testPlatform PlayMode -testCategory Agents

The Marketing category records PNG frame sequences of scripted scenarios into <project>/Marketing/frames (rendered from the scene camera at 1280 x 720, 30 fps). Encode them with ffmpeg using Marketing/encode_videos.py in the project root (creates one MP4 per scene, a combined showreel and a GIF preview).

14. API overview

Namespace PathFinder

Namespace PathFinder.Graphs

Namespace PathFinder.Graphs.Recast

Namespace PathFinder.Modifiers

Namespace PathFinder.RVO

Namespace PathFinder.Editor

Writing a custom graph

Derive from NavGraph, add [Serializable] and [GraphType("My Graph")], create nodes deriving from GraphNode (implement GetConnections and GetPortal), implement Scan, GetNearest, GetNodes and NodeCount. Optionally override UpdateArea, Linecast, GetBounds and OnDrawGizmos. The graph appears in the Add Graph... menu automatically. Add a GraphEditor with [CustomGraphEditor(typeof(MyGraph))] for custom inspector or scene handles.