Welcome to AnyPath
AnyPath is a completely generic, lightning fast A* pathfinding solution for Unity. View in the Unity Asset Store.
Create your own data structure from scratch or use any of the included graphs as a starting point.
AnyPath uses Unity's job system and the Burst compiler. All of the heavy lifting is done on multiple threads and by highly optimized burst compiled code. Because all of the customizability is done via generic type parameters, all of the code is generated at compile time. This means there is zero overhead in defining custom functionality. On top of that, there's an efficient managed layer that hides the complexity of managing the native jobs, making it extremely easy to use.
Click here for a basic walkthrough or check out the API reference for a complete overview.
Features
Version 1.0
- Completely customizable graph data structures using generic types
- Grids or any number of dimensions are supported
- Leverages Unity's Job system and the Burst compiler, so performance and multithreading by default
- Works in jobs and with Unity ECS by utilizing the core building blocks in the AnyPath.Native namespace.
- A managed layer on top of the native code that is extremely easy to use
- Fully automated memory management (Non-ECS only). No need to worry about multi threading or race conditions, even when rebuilding your graph structure live.
- "Evaluate Only" requests that skip reconstructing a path in cases where it is sufficient to only check if a path exists, saving resources!
- Native support for adding extra stops in between the start and the goal of a request.
- Planning by giving a request a set of target objects
- Target picking by evaluating a set of target objects. Automatically generating a path to it.
- Target picking by evaluating which target is closest on the graph.
- Validating and reserving targets (Non ECS) without race conditions.
- "Edge Modifiers" that allow for applying small changes to a graph without the need to rebuild the entire graph. A door being open or closed for instance.
- Batch pathfinding operations. Evaluate multiple paths in a single job.
- ALT heuristics for any type of graph, which can significantly speed up pathfinding on very large and complex graphs.
- Object pooling is used where possible, so very low GC pressure
- Zero memory allocation requests (v1.4)
- 2D square grid
- Hexagonal grid
- 3D navigation mesh with support for curved surfaces
- A specialized platformer 'waypoint' graph
- A versatile 3D waypoint graph (v1.2)
- A simple 3D node graph
- Full source code included
The built in graphs also come with some utility classes that are neccessary for them to work properly, which you can use for your own custom graphs or any other kind of use you see fit:
- Burst compatible quadtree and octree implementations optimized for raycast queries.
- A 3D mesh welder utility, which welds together very close vertices on meshes.
- Burst compatible priority queue
- String pulling algorithms for straightening paths on a navigation mesh
- String pulling algorithm for usage with realtime steering behaviour
- Various geometry and math related utility functions
Updates
Version 1.5 (5/8/2024)
- New graph type: VoxelGrid. A 3D voxel grid that's easily extendable with out of the box support for various movement types.
- Edge modifiers now have an additional method "ModifyEdgeBuffer" that allows for dynamic addition of extra edges.
- New included edge modifier: AdditionalEdges. Allows for added edges per pathfinding query without the need for rebuilding the graph. Can be used for portals for instance.
- New included edge modifier: ExcludeEdges. Can be used to exclude certain edges per pathfinding query.
- New included edge modifier: ExcludeLocations. Can be used to exclude certain locations/nodes per pathfinding query.
- CodeGenerator utility now also includes the correct namespaces.
- Dedicated SquareGrid heuristic providers without branching for better performance
Version 1.4.4 (4/5/2024)
- Updated readme with some known issues
- Fixed a bug where you would get an ObjectDisposedException if you have Domain Reload turned off in the editor player settings
- Fixed a bug where a NullReferenceException occurs with PriorityFinders combined with ReuseResult
Version 1.4.3 (3/2/2024)
- Fixed a bug in the NavMesh where the triangle flags weren't passed on correctly.
- Fixed a mistake in the documentation regarding the FlagBitMask.
Version 1.4.2 (28/1/2024)
- Fixed a bug where the MaxExpand value on a finder was not actually used in the A* algorithm.
Version 1.4.1 (8/1/2024)
- Several bounds checks on code that runs in jobs that throw exceptions have been surrounded by ENABLE_UNITY_COLLECTIONS_CHECKS, this fixes numerous warnings when building the player.
- CodeGen editor folder has its own assembly definition file so that it is excluded on player builds.
- The ALT heuristic generation code has been changed such that the burst compiled jobs actually compile in a build.
Version 1.4 (21/8/2023)
- Zero allocation finders! Managed path finding queries now have the option to reduce managed allocations, allowing them to be used without creating any garbage at all.
- Dijkstra algorithm supports edge modifiers.
- The NavMesh can now generate more straight paths for grid like meshes.
- Upgrade note: The path result Segments property has been removed to allow for zero allocation results. Path segments access by index should now be done via the indexer on the Path class itself.
Version 1.3.1 (29/4/2023)
- Fixed Triangle.ClosestPoint returning NaN's for some degenerate triangles
- Added editor checks to avoid infinite running jobs when the cost of an edge is NaN
Version 1.3 (6/3/2023)
- Native Dijkstra's algorithm, which you can use to find all shortest paths from a starting location to all reachable locations, optionally within a maximum cost budget
- Added a managed finder to perform Dijkstra's algorithm without needing to worry about job scheduling
- Added an example that demonstrates Dijkstra's algorithm
- NavMesh now has nearest location query
- Nearest location queries for all graphs that support it have a more performant overload for when it's called many times in a row
- Better default values for navmesh, linegraph and platformergraph construction
- Square grid example improved
- Fixed a bug in the navmesh example
- Extra flexibility for path straightening (SSFA), allowing it to be used on other types of paths as well (not included)
- Documentation improved
Version 1.2 Updates:
- LineGraph added. A versatile 3D waypoint graph with support for queries from and to anywhere along the graph lines/edges.
- NodeGraph added. A simple node to node 3D graph.
- Overall pathfinding performance boosted by using ref comparisons where possible
- Closest location query for PlatformerGraph, useful in a top down context
- Simplified PlatformerGraphBuilder
- PlatformerGraph now has optional Id's per edge, allowing for easy mapping back to MonoBehaviour script via GetInstanceId.
- PlatformerGraph's closest edge query now accepts a delegate to check for obstructions in the line of sight.
- Internal trees of NavMesh and PlatformerGraph are public now, useful for advanced location queries
- New octree and quadtree implementation (https://github.com/bartofzo/NativeTrees), significantly boosting raycast performance for the NavMesh and PlatformerGraph
- Bugfix: fixed incorrect traversing of platformergraph edge with a cost of infinity (which should be unwalkable)
Version 1.1 Updates:
NavMeshGraph: Fast welding of vertices together using Unity's Job system, useful for large graphs and frequent updates
NavMeshGraph: Can be populated and calculated inside of a burst compiled job now, useful for frequent updates
NavMeshGraph: AABB triangle overlap queries, useful for cutting out triangles in a given area
Breaking change: The NavMeshGraph constructor using NativeArrays now makes an internal copy of the data. Which prevents memory safety issues and allows the graph to be generated on another thread.
PlatformerGraph: Fast welding of vertices together using Unity's Job system, useful for frequent updates
PlatformerGraph: Can be populated and calculated inside of a burst compiled job now, useful for frequent updates
PlatformerGraph: Graph can be drawn using the PlatformerGraphDrawer with automatic joining of vertices, making it extremely easy to generate a graph on the fly
Fast copying of NavMesh, Platformer Graph, Quad- and Octree
Tested with Unity 2021.3
Who's this for?
AnyPath was designed for intermediate to advanced programmers with customizability in mind. If you just need a drop in solution for AI, then this framework is not for you. If you need total control over your data layout and fast pathfinding, then AnyPath is for you.
What's not included?
- No agent code, you write the movement code yourself. AnyPath only provides a (processed) path to follow
- No dynamic obstacle avoidance, as this is beyond the scope of A* and very game dependant
- Graph serialization (except for the platformer graph), as usually the graph can be easiliy generated at runtime. You can write your own serialization though.
- The platformer graph is the only graph which has a built in edit tool, other data structures need to be generated at runtime.
- No bi-directional A* search, search is always from start to goal
Requirements
- Unity 2020.3 or higher
- Burst package
- Unity.Collections package Look at the installation instructions here.
Contact
If you have any questions or encounter any bugs, feel free to contact me at anypath@bartvandesande.nl.