AnyPath is a completely generic, lightning fast A* pathfinding solution for Unity. 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.
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
2D square grid
Hexagonal grid
3D navigation mesh with support for curved surfaces
A specialized platformer ‘waypoint’ 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
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
The algorithm is fairly simple and uses ‘buckets’ with a dictionary of a list. It is not burst compatible (yet) though but I’ll write it down for a future update. I think for a very large mesh as it stands now it will be too slow for real time usage but fine for pre processing.
Just updated the package to v1.1. It now supports burst accelerated vertex welding as well as some other features making graph updating much faster. For full details please refer to https://anypath.bartvandesande.nl/
I don’t get the impression that this asset has half the features of ASTAR, but it’s promising a generic and fast version of astar. Does this asset generate navmeshes?
It does everything better than ASTAR, but only if you’re willing to program the heuristics. Read the reviews, they’ll give you an idea of what you’d get into.
This asset does not generate navmeshes by itself, but it can perform fast pathfinding on them. You can use Unity’s navmesh generation, or any custom mesh data.
That is why I’m asking though.
Astar Project’s navmesh generation as far as I understand is vastly more robust than anything Unity offers.
It sounds like I need to bridge that gap myself?
We have a huge map with user-driven runtime changes that affect navigation. What we’re looking for is a way to get more control over pathing without rewriting the entirety of Astar’s backend (it’s all managed).
My current plan is to chuck astar project’s triangles into anypath, and then add our custom pathing behaviour into our anypath implementation. Then we would get burst pathfinding with the custom logic we need + Astar Project’s robust navmesh generation at runtime.
That should be possible. The built in NavMesh accepts a mesh in the form of vertices and indices.
Here are some relevant parts of the docs to get a better idea of how it works:
AnyPath has been updated to v1.5 and a lot of new features were added since I’ve last posted here.
Some highlights include:
A built VoxelGrid that’s easily adjustable to suit your pathfinding needs
Zero memory allocations for managed pathfinding queries
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
NavMesh now has nearest location query
Pathfinding queries can carry with them modifications to the graph you’re searching on. Allowing for portals, doors or expansions without rebuilding the entire graph.
If you’re looking for an affordable, fast and highly customizable pathfinding solution for Unity, make sure to give this a try!
It uses an older version to remain compatibility with older Unity versions.
The readme file gives a solution to this:
If you’re getting a compilation error along the lines of:
“The type or namespace name ‘NativeMultiHashMap<,>’ could not be found.”
This package was made with Unity 2020.3.16f1, so that it remains compatible with older Unity versions.
The error occurs because Unity renamed these collections. NativeMultiHashMap became NativeParallelMultiHashMap in later versions.
This should be resolved automatically, but if it doesn’t, you can fix it by running the API updater by launching
Unity with the -accept-apiupdate option.
Thanks! For some reason I couldn’t get the API updater to run even with that command line option, or re-importing etc. So just manually fixed all the code
