Namespace AnyPath.Graphs.NavMesh

Classes

NavMeshPopulator

Utility to populate a NavMesh using Unity's Job system. This can be useful if you have frequent updates and want this process to be as fast as possible and/or on another thread.

NavMeshWelder

Utility to weld close vertices in a mesh together.

SSFA

Simple Stupid Funnel Algorithm implementations, used for 'straightening' a path on the NavMesh as much as possible. See http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html

Structs

CornerAndNormal

Output of the NavMeshGraphCorners3D path processor. This gives you a list of points and their up vector your agent can follow.

NavMeshGraph

Navigation Mesh implementation with support for raycasting, area cost, flags and arbitrarily curved surfaces.

v1.1 adds features to populate the graph from within jobs. See Populate(NativeArray<Vector3>, NativeArray<int>) as well as some variations on this, including one that copies the contents from another NavMehsGraph, which can be efficient if you need to make slight adjustments to the graph as fast as possible.

SetUnwalkable(int), which can be used to essentialy cut some areas from the NavMesh. Depending on your use case, this may be a very efficient way to dynamically alter the graph without a lot of overhead. Using GetOverlappingTriangles(AABB, NativeList<int>), an area can be scanned and then these triangles can be excluded from pathfinding queries.

Paths can be processed using: NavMeshGraphCorners - creates a nice corner array from a starting position to the goal for flat worlds with slopes NavMeshGraphCorners3D - creates a nice corner array for arbitrarily curved worlds NavMeshGraphUnroller - processes the path so that it can be used for realtime steering behaviour

NavMeshGraph.EnterCostAndFlags

A struct per triangle that holds information about extra cost and flags.

NavMeshGraph.Enumerator

Enumerator that enumerates all triangles/locations contained in this navigation mesh. This can be used to construct ALT heuristics.

NavMeshGraphCorners

Converts a NavMeshGraph path into a list of corner points. Use this processor if your world is mostly flat (in the XZ plane). Slopes are allowed but they should not exceed 90 degrees. If you have a curved world, use NavMeshGraphCorners3D.

NavMeshGraphCorners3D

Converts a NavMeshGraph path into a list of corner points. Use this processor if your world has arbitrary curvature.

NavMeshGraphHeuristic

Basic heuristic provider for usage with the NavMeshGraph

NavMeshGraphLocation

A location on the NavMeshGraph represents a triangle and a position within that triangle. Furthermore, when part of a path, the Left and Right properties point to the shared edge with the next triangle in the path.

NavMeshGraphUnroller

Processes a NavMeshGraph path for use with realtime steering using GetSteerTargetPosition<T>(T, float3, ref int)

NavMeshLineBitmaskMod

Combines NavMeshLineMod and FlagBitmask<TNode> into one modifier. Locations that don't pass the bitmask will not be considered walkable.

NavMeshLineMod

Encourages A* on a navmesh to follow a straight line from start to goal.

Depending on the structure of your navmesh, this may be useful to get better looking straight paths. This is especially true for meshes that resemble a grid like structure. Because A* can only operate on the triangles itself, there may be many optimal paths to the destination that share the same cost (at the triangle level). If you use SSFA, then it may become apparent that the path that was chosen was not the most optimal after SSFA was performed. See this article for an in depth explanation: https://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#breaking-ties

This edge modifier mitigates this by dynamically adding a cost penalty to triangles that lie further away from a straight line between the start and the goal location. Causing A* to always prefer paths that are as close to a straight line as possible at the triangle level.

Note that when using this modifier, you must assign your pathfinding start and end locations manually before making the request! If you forget to do this, it will not work and produce unexpected paths. For this reason, this modifier is not suitable for pathfinding requests that have multiple stops in between.

finder.Stops.Add(from); // pathfinding start location
        finder.Stops.Add(to); // pathfinding end location
        finder.EdgeMod = new NavMeshStraightLineMod(from, to); // assign the straight line mod with our start+goal, obtained via a raycast
        finder.Run(); // run the query

You should test if this modifier is actually necessary for your use case, as in many cases and navmesh types, this offers no significant benefit and decreases performance slightly.

NavMeshPlaneBitmaskMod

Combines NavMeshPlaneMod and FlagBitmask<TNode> into one modifier. Locations that don't pass the bitmask will not be considered walkable.

NavMeshPlaneMod

Similar to NavMeshLineMod, but instead measures the distance to a plane.

Using this modifier makes A* prefer paths that are close to a plane.

A use case for this is to obtain more geodesic paths on a spherical navmesh. Or more straight looking paths on navmeshes that contain a lot of hills or more complicated 3D shapes.

UnrolledNavMeshGraphPortal

Intermediate struct used by the SSFA algorithm. It keeps track of the original 3D sides of the portals and the 2D projected ones. This information can then be used to reconstruct the intersection points of the straightened path in 3D.

Interfaces

IUnrolledNavMeshGraphPortal

Data needed for SSFA to work in curved worlds

If the path is already in a flat plane, you can feed it directly to AppendCorners<TProj>(NativeSlice<TProj>, NativeList<float3>). If the path is curved however, you must first pass it to Unroll<T>(NativeSlice<T>, NativeSlice<UnrolledNavMeshGraphPortal>), which will 'unroll' it into a flat plane. The output of which can then be fed into GetSteerTargetPosition<T>(T, float3, ref int) or AppendCornersUnrolled<T>(NativeSlice<T>, NativeList<CornerAndNormal>, float) for path smoothing in 3D.

Delegates

ClosestNavMeshLocationPredicate

Describes a function that validates if a location on a triangle is valid as a return value for the Closest queries. This can be used for instance to check if there are objects obstructing the line of sight between the origin and the location.