A* Pathfinding Project
4.2.7
The A* Pathfinding Project for Unity 3D
|
Namespaces | |
namespace | Examples |
namespace | Legacy |
namespace | Recast |
namespace | RVO |
Local avoidance related classes. | |
namespace | Serialization |
namespace | Util |
namespace | Voxels |
namespace | WindowsStore |
Classes | |
class | ABPath |
Basic path, finds the shortest path from A to B. More... | |
class | ABPathEndingCondition |
Ending condition which emulates the default one for the ABPath. More... | |
class | AdvancedSmooth |
Smoothing by dividing path into turns and straight segments. More... | |
class | AIBase |
Base class for AIPath and RichAI. More... | |
class | AIDestinationSetter |
Sets the destination of an AI to the position of a specified object. More... | |
class | AILerp |
Linearly interpolating movement script. More... | |
class | AILerpEditor |
class | AIPath |
AI for following paths. More... | |
class | AlternativePath |
Applies penalty to the paths it processes telling other units to avoid choosing the same path. More... | |
class | AnimationLink |
class | AnimationLinkEditor |
class | AstarColor |
Stores editor colors. More... | |
class | AstarData |
Stores the navigation graphs for the A* Pathfinding System. More... | |
class | AstarDebugger |
Debugger for the A* Pathfinding Project. More... | |
class | AstarMath |
Utility functions for working with numbers and strings. More... | |
class | AstarPathEditor |
class | AstarProfiler |
class | AstarSplines |
Contains various spline functions. More... | |
class | AstarUpdateChecker |
Handles update checking for the A* Pathfinding Project. More... | |
class | AstarUpdateWindow |
struct | AstarWorkItem |
An item of work that can be executed when graphs are safe to update. More... | |
class | BaseAIEditor |
class | BBTree |
Axis Aligned Bounding Box Tree. More... | |
class | BinaryHeap |
Binary heap implementation. More... | |
class | BlockManager |
Manager for blocker scripts such as SingleNodeBlocker. More... | |
struct | Connection |
Represents a connection to another node. More... | |
class | ConstantPath |
Finds all nodes within a specified distance from the start. More... | |
class | CustomGraphEditorAttribute |
Added to editors of custom graph types. More... | |
class | CustomPath |
class | DebugUtility |
Helper for drawing debug information for the recast graph. More... | |
class | DefaultITraversalProvider |
Convenience class to access the default implementation of the ITraversalProvider. More... | |
class | DynamicGridObstacle |
Attach this script to any obstacle with a collider to enable dynamic updates of the graphs around it. More... | |
class | EditorBase |
Helper for creating editors. More... | |
class | EditorGUILayoutx |
Handles fading effects and also some custom GUI functions such as LayerMaskField. More... | |
class | EndingConditionDistance |
Target is found when the path is longer than a specified value. More... | |
class | EndingConditionProximity |
Ending condition which stops a fixed distance from the target point. More... | |
class | EnumFlagAttribute |
class | EnumFlagDrawer |
class | EuclideanEmbedding |
Implements heuristic optimizations. More... | |
class | FadeArea |
Editor helper for hiding and showing a group of GUI elements. More... | |
class | FleePath |
Returns a path heading away from a specified point to avoid. More... | |
class | FloodPath |
Floods the area completely for easy computation of any path to a single point. More... | |
class | FloodPathConstraint |
Restrict suitable nodes by if they have been searched by a FloodPath. More... | |
class | FloodPathTracer |
Traces a path created with the Pathfinding.FloodPath. More... | |
class | Funnel |
Implements the funnel algorithm as well as various related methods. More... | |
class | FunnelModifier |
Simplifies paths on navmesh graphs using the funnel algorithm. More... | |
class | GraphCollision |
Handles collision checking for graphs. More... | |
class | GraphEditor |
class | GraphEditorBase |
Defined here only so non-editor classes can use the target field. More... | |
struct | GraphHitInfo |
Returned by graph ray- or linecasts containing info about the hit. More... | |
struct | GraphMask |
Holds a bitmask of graphs. More... | |
class | GraphModifier |
GraphModifier is used for modifying graphs or processing graph data based on events. More... | |
class | GraphNode |
Base class for all nodes. More... | |
class | GraphUpdateObject |
Represents a collection of settings used to update nodes in a specific region of a graph. More... | |
class | GraphUpdateProcessor |
class | GraphUpdateScene |
Helper class for easily updating graphs. More... | |
class | GraphUpdateSceneEditor |
Editor for GraphUpdateScene. More... | |
class | GraphUpdateShape |
Defines a shape for a Pathfinding.GraphUpdateObject. More... | |
class | GraphUpdateUtilities |
Contains useful functions for updating graphs. More... | |
class | GraphUtilities |
Contains utility methods for getting useful information out of graph. More... | |
class | GridGraph |
Generates a grid of nodes. More... | |
class | GridGraphEditor |
class | GridNode |
Node used for the GridGraph. More... | |
class | GridNodeBase |
Base class for GridNode and LevelGridNode. More... | |
class | GUIUtilityx |
Simple GUI utility functions. More... | |
class | HierarchicalGraph |
Holds a hierarchical graph to speed up certain pathfinding queries. More... | |
interface | IAstarAI |
Common interface for all movement scripts in the A* Pathfinding Project. More... | |
interface | IGraphInternals |
Exposes internal methods for graphs. More... | |
interface | INavmesh |
interface | INavmeshHolder |
Interface for something that holds a triangle based navmesh. More... | |
struct | Int2 |
Two Dimensional Integer Coordinate Pair. More... | |
struct | Int3 |
Holds a coordinate in integers. More... | |
struct | IntRect |
Integer Rectangle. More... | |
interface | IPathInternals |
Used for hiding internal methods of the Path class. More... | |
interface | IPathModifier |
Base for all path modifiers. More... | |
interface | IRaycastableGraph |
Graph which supports the Linecast method. More... | |
interface | ITransformedGraph |
Graph which has a well defined transformation from graph space to world space. More... | |
interface | ITraversalProvider |
Provides additional traversal information to a path request. More... | |
interface | IUpdatableGraph |
Graphs which can be updated during runtime. More... | |
interface | IVersionedMonoBehaviourInternal |
Exposes internal methods from Pathfinding.VersionedMonoBehaviour. More... | |
interface | IWorkItemContext |
Interface to expose a subset of the WorkItemProcessor functionality. More... | |
class | LayerGridGraph |
Grid Graph, supports layered worlds. More... | |
class | LayerGridGraphEditor |
class | LayerGridGraphUpdate |
GraphUpdateObject with more settings for the LayerGridGraph. More... | |
class | LevelGridNode |
Describes a single node for the LayerGridGraph. More... | |
class | LocalSpaceGraph |
Helper for Pathfinding.Examples.LocalSpaceRichAI. More... | |
class | MeshNode |
class | MonoModifier |
Base class for path modifiers which can be attached to GameObjects. More... | |
class | MultiTargetPath |
A path which searches from one point to a number of different targets in one search or from a number of different start points to a single target. More... | |
class | NavGraph |
Base class for all graphs. More... | |
class | NavmeshAdd |
Adds new geometry to a recast graph. More... | |
class | NavmeshBase |
Base class for RecastGraph and NavMeshGraph. More... | |
class | NavmeshClamp |
Attach to any GameObject and the object will be clamped to the navmesh. More... | |
class | NavmeshClipper |
Base class for the NavmeshCut and NavmeshAdd components. More... | |
class | NavmeshCut |
Navmesh cutting is used for fast recast/navmesh graph updates. More... | |
class | NavmeshCutEditor |
class | NavMeshGraph |
Generates graphs based on navmeshes. More... | |
class | NavMeshGraphEditor |
class | NavmeshTile |
class | NavmeshUpdates |
Helper for navmesh cut objects. More... | |
class | NNConstraint |
Nearest node constraint. More... | |
struct | NNInfo |
Result of a nearest node query. More... | |
struct | NNInfoInternal |
Internal result of a nearest node query. More... | |
class | NodeLink |
Connects two nodes with a direct connection. More... | |
class | NodeLink2 |
Connects two nodes via two intermediate point nodes. More... | |
class | NodeLink3 |
Connects two TriangleMeshNodes (recast/navmesh graphs) as if they had shared an edge. More... | |
class | NodeLink3Node |
class | ObjImporter |
class | OptimizationHandler |
Helper for enabling or disabling compiler directives. More... | |
class | Path |
Base class for all path types. More... | |
class | PathEndingCondition |
Customized ending condition for a path. More... | |
class | PathHandler |
Handles thread specific path data. More... | |
class | PathModifier |
Base class for path modifiers which are not attached to GameObjects. More... | |
class | PathNNConstraint |
A special NNConstraint which can use different logic for the start node and end node in a path. More... | |
class | PathNode |
Stores temporary node data for a single pathfinding request. More... | |
class | PathPool |
Pools path objects to reduce load on the garbage collector. More... | |
class | PathProcessor |
class | PathReturnQueue |
class | PathUtilities |
Contains useful functions for working with paths and nodes. More... | |
class | Patrol |
Simple patrol behavior. More... | |
class | PointGraph |
Basic point graph. More... | |
class | PointGraphEditor |
class | PointKDTree |
Represents a collection of GraphNodes. More... | |
class | PointNode |
Node used for the PointGraph. More... | |
class | Polygon |
Utility functions for working with polygons, lines, and other vector math. More... | |
class | ProceduralGridMover |
Moves a grid graph to follow a target. More... | |
class | Profile |
struct | Progress |
Progress info for e.g a progressbar. More... | |
class | RadiusModifier |
Radius path modifier for offsetting paths. More... | |
class | RandomPath |
Finds a path in a random direction from the start node. More... | |
class | RaycastModifier |
Simplifies a path using raycasting. More... | |
class | RaycastModifierEditor |
class | RecastBBTree |
Axis Aligned Bounding Box Tree. More... | |
class | RecastBBTreeBox |
class | RecastGraph |
Automatically generates navmesh graphs based on world geometry. More... | |
class | RecastGraphEditor |
Editor for the RecastGraph. More... | |
class | RecastMeshObj |
Explicit mesh object for recast graphs. More... | |
class | RecastMeshObjEditor |
class | RecastTileUpdate |
Updates the recast tile(s) it is in at start, needs RecastTileUpdateHandler. More... | |
class | RecastTileUpdateHandler |
Helper for easier fast updates to recast graphs. More... | |
class | RelevantGraphSurface |
Pruning of recast navmesh regions. More... | |
class | RichAI |
Advanced AI for navmesh based graphs. More... | |
class | RichFunnel |
class | RichPath |
class | RichPathPart |
class | RichSpecial |
class | RVONavmeshEditor |
class | RVOSimulatorEditor |
class | RVOSquareObstacleEditor |
class | Seeker |
Handles path calls for a single unit. More... | |
class | SeekerEditor |
class | SimpleSmoothModifier |
Modifier which smooths the path. More... | |
class | SingleNodeBlocker |
Blocks single nodes in a graph. More... | |
class | SmoothModifierEditor |
class | StartEndModifier |
Adjusts start and end points of a path. More... | |
class | TargetMover |
Moves the target in example scenes. More... | |
class | ThreadControlQueue |
Queue of paths to be processed by the system. More... | |
class | TileHandlerHelper |
Helper for navmesh cut objects. More... | |
class | TriangleMeshNode |
Node represented by a triangle. More... | |
class | UniqueComponentAttribute |
class | UnityReferenceHelper |
Helper class to keep track of references to GameObjects. More... | |
class | VectorMath |
Various vector math utility functions. More... | |
class | VersionedMonoBehaviour |
Base class for all components in the package. More... | |
class | WorkItemProcessor |
class | XPath |
Extended Path. More... | |
Typedefs | |
using | Math = System.Math |
using | Thread = System.Threading.Thread |
Enumerations | |
enum | CloseToDestinationMode { Stop, ContinueToExactDestination } |
What to do when the character is close to the destination. More... | |
enum | ColliderType { Sphere, Capsule, Ray } |
Determines collision check shape. More... | |
enum | GraphDebugMode { SolidColor, G, H, F, Penalty, Areas, Tags, HierarchicalNode } |
How to visualize the graphs in the editor. More... | |
enum | GraphUpdateThreading { UnityThread = 0, SeparateThread = 1 << 0, UnityInit = 1 << 1, UnityPost = 1 << 2, SeparateAndUnityInit = SeparateThread | UnityInit } |
enum | Heuristic { Manhattan, DiagonalManhattan, Euclidean, None } |
How to estimate the cost of moving to the destination during pathfinding. More... | |
enum | HeuristicOptimizationMode { None, Random, RandomSpreadOut, Custom } |
enum | InspectorGridHexagonNodeSize { Width, Diameter, NodeSize } |
enum | InspectorGridMode { Grid, IsometricGrid, Hexagonal, Advanced } |
enum | NumNeighbours { Four, Eight, Six } |
Number of neighbours for a single grid node. More... | |
enum | OrientationMode { ZAxisForward, YAxisForward } |
Determines which direction the agent moves in. More... | |
enum | PathCompleteState { NotCalculated = 0, Error = 1, Complete = 2, Partial = 3 } |
State of a path request. More... | |
enum | PathLog { None, Normal, Heavy, InGame, OnlyErrors } |
How path results are logged by the system. More... | |
enum | PathState { Created = 0, PathQueue = 1, Processing = 2, ReturnQueue = 3, Returned = 4 } |
Internal state of a path in the pipeline. More... | |
enum | RayDirection { Up, Down, Both } |
Determines collision check ray direction. More... | |
enum | Side : byte { Colinear = 0, Left = 1, Right = 2 } |
Indicates the side of a line that a point lies on. More... | |
enum | ThreadCount { AutomaticLowLoad = -1, AutomaticHighLoad = -2, None = 0, One = 1, Two, Three, Four, Five, Six, Seven, Eight } |
Number of threads to use. More... | |
Functions | |
delegate void | OnGraphDelegate (NavGraph graph) |
delegate void | OnPathDelegate (Path p) |
delegate void | OnScanDelegate (AstarPath script) |
delegate void | OnScanStatus (Progress progress) |
using Math = System.Math |
|
strong |
What to do when the character is close to the destination.
|
strong |
Determines collision check shape.
|
strong |
How to visualize the graphs in the editor.
Enumerator | |
---|---|
SolidColor | Draw the graphs with a single solid color. |
G | Use the G score of the last calculated paths to color the graph. The G score is the cost from the start node to the given node.
|
H | Use the H score (heuristic) of the last calculated paths to color the graph. The H score is the estimated cost from the current node to the target.
|
F | Use the F score of the last calculated paths to color the graph. The F score is the G score + the H score, or in other words the estimated cost total cost of the path.
|
Penalty | Use the penalty of each node to color the graph. This does not show penalties added by tags. |
Areas | Visualize the connected components of the graph. A node with a given color can reach any other node with the same color. |
Tags | Use the tag of each node to color the graph. |
HierarchicalNode | Visualize the hierarchical graph structure of the graph. This is mostly for internal use.
|
|
strong |
|
strong |
How to estimate the cost of moving to the destination during pathfinding.
The heuristic is the estimated cost from the current node to the target. The different heuristics have roughly the same performance except not using any heuristic at all (#None) which is usually significantly slower.
In the image below you can see a comparison of the different heuristic options for an 8-connected grid and for a 4-connected grid. Note that all paths within the green area will all have the same length. The only difference between the heuristics is which of those paths of the same length that will be chosen. Note that while the Diagonal Manhattan and Manhattan options seem to behave very differently on an 8-connected grid they only do it in this case because of very small rounding errors. Usually they behave almost identically on 8-connected grids.
Generally for a 4-connected grid graph the Manhattan option should be used as it is the true distance on a 4-connected grid. For an 8-connected grid graph the Diagonal Manhattan option is the mathematically most correct option, however the Euclidean option is often preferred, especially if you are simplifying the path afterwards using modifiers.
For any graph that is not grid based the Euclidean option is the best one to use.
Enumerator | |
---|---|
Manhattan | Manhattan distance. |
DiagonalManhattan | Manhattan distance, but allowing diagonal movement as well.
|
Euclidean | Ordinary distance. |
None | Use no heuristic at all. This reduces the pathfinding algorithm to Dijkstra's algorithm. This is usually significantly slower compared to using a heuristic, which is why the A* algorithm is usually preferred over Dijkstra's algorithm. You may have to use this if you have a very non-standard graph. For example a world with a wraparound playfield (think Civilization or Asteroids) and you have custom links with a zero cost from one end of the map to the other end. Usually the A* algorithm wouldn't find the wraparound links because it wouldn't think to look in that direction. |
|
strong |
|
strong |
|
strong |
|
strong |
|
strong |
|
strong |
State of a path request.
Enumerator | |
---|---|
NotCalculated | The path has not been calculated yet.
|
Error | The path calculation is done, but it failed.
|
Complete | The path has been successfully calculated. |
Partial | The path has been calculated, but only a partial path could be found. |
|
strong |
How path results are logged by the system.
|
strong |
|
strong |
|
strong |
|
strong |
delegate void Pathfinding.OnGraphDelegate | ( | NavGraph | graph | ) |
delegate void Pathfinding.OnPathDelegate | ( | Path | p | ) |
delegate void Pathfinding.OnScanDelegate | ( | AstarPath | script | ) |
delegate void Pathfinding.OnScanStatus | ( | Progress | progress | ) |