A* Pathfinding Project 3.0 is Released!

Finally version 3.0 of the A* Pathfinding Project is released.
This is a rewrite of everything in the project. It's faster, more dynamic, extendable, easier to use (I hope) and better in any way! Documentation has also taken a big step forward and is now powered by Doxygen!

[EDIT] For people reading this post now. The system has been updated several times and is now (as of november 2018) at version 4.2.2. Check the package website for latest updates.

For those of you who don't know what the A* Pathfinding Project is: The project is a powerful, fast and easy to use pathfinding system (in short: what is the shortest path between A and B?). This is great in TD games where the enemies need to find their way to the goal, or in RTS games for directing units, or even in FPS games where the AIs need to find the player, or other AIs, in an area which is not just open space (which rarely is the case).
The system works in both the Free and Pro version of Unity.

The list of features is really huge, but I will try to sum it up for you:

• The system supports Point, Navmesh and Grid graphs. None of them are “hard-coded” into the system, but written as add-ons which means that it is easy to add you own
• Multithreaded - The system can optionally be run in a separate thread which means that pathfinding will have barely no effect at all on the game’s fps
• Path modifiers - Paths can be post-processed using path modifiers, for example using the funnel algorithm, raycast simplification simple smoothing using bezier curves or other smoothing algorithms
• Automatic navmesh generation - The system uses Recast translated to C# to automatically generate stable navmeshes from any level geometry
• Graph updating - Many graph types can be updated during runtime when, for example a new tower is placed in a TD game
• Blazing fast - The system can search more than a thousand nodes per millisecond. A normal path often takes less than a millisecond to calculate
• Grid Graphs - Grid graphs can be set up on any ground, they can be rotated and scaled however you want
• Navmesh Graphs - Navmesh graphs are great because they provide very high accuracy and lighting fast searches while keeping a low memory footprint
• List Graphs - Aka “Point Graphs” can be set up from a collection of Unity GameObjects, can it get easier?
• Interconnected graphs - All graphs can be mixed an matched together using Links placed in the editor
• Graphs saved to files- Graphs can be saved to files, both in the editor and during runtime and loaded later
• Low memory footprint - All graphs have been optimized for memory, and memory leaks are nowhere to be found. Compared to 2.9x version of the system, the memory usage is less than 10%, and 2.9x had huge memory leaks, so those 10% soon becomes 5% or even less after some time in gameplay
• Easy integration - A path request is a single line of code! Need to smooth the path? Add a smooth modifier component, not a single line of code needs adding, the system handles it
• Optimized and specialized search modes - Want your Resource Gatherer to find the path to the nearest resource, or do you just want your civilians find any path which takes them away from the evil enemies? You can do that in a single path request!
  Search modes available are: Normal, Multiple Target, Flee and Random. But as with graphs, all of these are written as add-ons, they are not hard coded into the system which means that you can add your own specialized search modes without modifying the pathfinding core!

The project has a Free version and a Pro version. The Pro version can be bought using PayPal on my website (linked below)

There are even more features which I haven't listed here, check them out on the A* Pathfinding Project page.
There you can also download the project for Free (without some A* Pro only features)
A* Pathfinding Project 3.0

 

One of the best free unity tools out there. Easy to install, use, and run.

 

Free but worth the purchase, and I'll be purchasing when my game deals with it. I was going to but current game doesn't need it. I tried out the earlier version and it was simply the best solution I'd ever tried in unity.

 

Just a question: Can it be placed in a 3D enviropement for planes and helicopters?

 

Yeah if you use the node based waypoints, of course. Node based waypoints are: you set up a series of gameobjects and they will connect to create an a* waypoint system, but I'm not actually at all sure how this makes even any sense for a flying game.

 

Not out of the box, however it could be extended with a custom graph. I have that written on my todo list somewhere (it is quite long though).
I have build full 3D pathfinders before, and the major problem with them is that they use a lot of memory (which limited me then to use at most 70*70*70 grids).

[Edit] Ah, of course. I didn't even think of that (and I'm supposed to have created the system, sight)

 

Cool. Being waiting for this for quite some time. Saw on your website a few days ago that it's being submitted. And now here it is.

 

Congratulations on this great release

Was missing especially the multithreading which 2.9 had cut again due to the "sideeffects". But the new modular approach naturally on its own is already a killer

 

Best in best,btw,is it free now?

 

I'm waiting for the Pro version, i would like to give it a try and see how fast it is on an iOS project.

 

Hello,

I purchased the commercial license not that long ago, is this pro version considered a separate product?

 

Everyone who has purchased a commercial license are entitled a free 3.0 Pro upgrade, I will send out the update later when the Pro version has been released.
Regarding the license, for simplicity, the project will be licensed under the Unity Asset store license. I read that I should be able to choose between three free licenses, but I have only found one, so... Anyway, it does not prohibit commercial usage of the product, so it now free to use in any commercial project (a credit would be nice though )

 

So Aron, in general, how fast it is compared to your old system? Like for example, your new waypoint system vs your 2.9x one? Or your recast implementation vs your old pathfinding system? You don't need to run a stress benchmark with exact numbers, approximate ones should be ok.

 

One thing though. does it support detection of objects, I meen if you have a moving cube on terrain or you change the position of it, will it detect it and move around it or something like simple path does ?

Oh and how do you make a nav mesh since the free version doesnt allow it ? T.T I wish I could afford unity pro, and ai like this ....

 

When you say that it currently doesn't work with JavaScript, what does that mean exactly?

 

Superb, I look forward to cracking it open. Quick question, in 2.9 you could recalculate a small part of a grid and set nodes to be unwalkable with a full physics retest. Is a similar system supported for regenerating a specified area on a NavMesh?

EDIT: just read the documentation and seen it's supported for grid and navmesh types. Will be buying the pro license in a few days.

 

what is the difference between free and pro?

 

Hmm, Unity keeps on crashing when I try to get a path.

 

Free vs Pro Comparison :
http://www.arongranberg.com/unity/a-pathfinding/free-vs-pro/

 

Are you using Mikko Mononen's Recast for this?

 

@RickyBozzy, Oops, sounds bad. Does the log say anything interesting? And is it the example scene?

@SamSam thanks for pointing that out!

@GamesFoundry, correct, but it will not create a hole or similar in the navmesh, only deactivate the nodes the box intersects.
And the Pro version will probably not be for sale in a couple of days, I'm still waiting for a response from the Unity guys.

@WarpedAxiom, for C# scripts to be accessible from Js, it must be compiled in a different pass. With the current Asset Store directory structure, I cannot have editor scripts and C# scripts accessible from Js, it seems.

@Gore23, You create your navmesh in a 3D modeling program (such as Blender, which is free). Export it so Unity can read it, and then assign it to the Navmesh field in the Navmesh Graph inspector.
It does not support automatic detection of every object (that would require too much CPU power). But you can update graphs in specific areas using the UpdateGraphs function, can be found in the docs - http://www.arongranberg.com/astar/docs/graph-updates.html


@Tatoforever, I have no exact numbers. Early tests I did indicated a 100% speed boost (it would be twice as fast, but I doubt it, I would say 5-10% or something, I am setting up a test right now).

@Metron, Yes I do, a small part of it, which I have translated to C# and changed around in other small ways.

 

That's good news and a credit is definately deserved.

 

Ok, got some data now... It seems like 2.95 is faster in some ways and slower in some.

In several tests, 2.95 was had a higher average fps. In one test it even outperformed 3.0 with 60%! But usually 2.95 was a few percent faster.
However, that was with Grid Graphs. On Navmesh graphs it was weaker, with 10 random paths per frame, 3.0 was 5% faster. However 3.0 calculated a few extra things too, like the closest point on the start and end polygons.
List graphs were almost exactly the same.
Since 2.95 was optimized for Grid Graphs it is a bit faster on Grid Graphs. And I guess that's a price you have to pay for higher extendability and a lot of virtual functions.

When many (almost all) of the paths were canceled, 3.0 outperformed 2.95 with almost 100% (that is however, a very unlikely case).

On memory however, 3.0 outperformed 2.95 with huge amounts on Grid Graphs, about 5 mb for 3.0 and 32 mb for 2.95.
List and Navmesh graphs are so small though, so both allocated 1 mb all the time.

One special thing a noticed with 2.95 was that the framerate jumped up and down a lot, it was in almost all tests down to 16 or 18 fps many times, in some cases it was even down to 5 fps. This has to do with the poor memory usage as GC get's called a lot.
While 3.0 stayed constant between 110 and 400, 2.95 was between 46 and 600. It doesn't matter much in that case because the framerate is high anyway, but I think many of you which have used the pathfinding project have experienced sudden lags in the music of your game, it just stops for a split second before continuing again, this won't occur with 3.0 (unless some other script in the game messes things up).

When turning on multithreading though, everything changes. I ran a test on a navmesh, requested a 100 paths per frame. While 2.95 slowed down to a crawl of 78 fps (comparatively speaking) and was able to calculate 67 thousand paths in 30 seconds, 3.0 didn't notice the pathfinding at all and ran steady 800 fps and managed to calculate an astonishing 1.8 million paths in 30 seconds! Outperforming 2.95 with 2680%!
I love multithreading

 

is their a way to get the player to pick a route diffrent than it was originally going if the way he was going was blocked or covered ? maybe have it use a ray to check if it is blocked or just if they covered he is forced to pick a diffrent route and goes from their ? How does simplepath do it O.O I seen they have theirs update on the go.

 

Sure there is!

On the AIFollow component there is a repath rate variable, it determines how often to search for a new path.
You can have it calculate a new path every frame if you want.
That is also how SimplePath solves it, judging by their videos

Or you can register to the OnGraphsUpdated delegate which will send a callback every time a graph is updated and recalculate the path then.
http://arongranberg.com/astar/docs/class_astar_path.html#a552cd9c67cefa9468524366e6158b7ab

Code (csharp):

1. AstarPath.OnGraphsUpdated += MyRepathFunction

I had logic for recalculating based on graph change built in to the Seeker component, but I removed it in the last minute because it was hard to know which path to recalculate. I will try to reimplement it better for the next version.

 

Alright so 3.0 list graphs is more or less equal to 2.9x running on one thread?

 

Hi,sturestone:

It's really nice work, I test on ios platform with multi-seeker and more obstacles, and it still gets high fps. Thanks for shareing such an awesome plugin for free(For me, the free version is enough to use^_^).

However, the Editor is unable to use, do I miss something?
I use unity 3.3 pro.

here's the compile error:

Code (csharp):

1. Assets/AstarPathfindingProject/Editor/GraphEditors/GridGeneratorEditor.cs(353,38): error CS0103: The name `Tool' does not exist in the current context

btw, is it ok if I use it in commercial game?
thanks!

 

@Tatoforever, yes it seems so. With the exception that 2.9x could sometimes drop to really low framerates caused by the poor memory management.

I have updated the project to 3.0.1 to fix the Unity 3.3 compatibility issue with the Tool class, I have also put the Path class in the Pathfinding namespace as that conflicted with System.IO.Path for some users.

 

yeah this is fantastic! I'm definitely gonna purchase it when I use it in a game I try to release, the features pro gives are just too good.

question though, I noticed that you ran them all with C# scripts, say if I made a simple RTS game, would you think I would have to mess with any of those C# scripts? as I use UnityScript and I don't think you can combine the two, like getting a gobal variable from the C# script with the UnityScript script.

 

@Akinon93 Unfortunately, due to a limitation in the Asset Store directory structure, I cannot get my C# scripts to be accessible from Js. I have tried asking the Unity guys about it, but they haven't answered (that was a few weeks ago... maybe they are on holiday...).
If you can, try converting to C# if you want to use the project, otherwise 2.95 is still compatible with Js.

 

alright thanks. I'm kinda leaning towards C# because learning that would open me up to easily learning C++ later down the road, it's just all so confusing lol.

 

Dynamic Obstacles Everyone!

Implemented it this afternoon!

 

Looks fast yes, dynamic obstacle avoidance is a welcome plus! Do it works with navmesh and lists?
Cheers,

 

@Tatoforever
I haven't done any tests, but it should work with navmeshes, however only by making nodes unwalkable, not creating a hole.
List graphs haven't got support for UpdateGraphs yet, however it is really easy to implement, so it should take long before I implement it.

 

Hmm, I am having a very strange issue with the interface... all the fonts are faded out.

Please see the attached image

 

I saw that too. I assumed it was because I was using the free version.

 

Very nice

 

Ahh, seems this is a bug with the Pro Skin shurestone. Guessing you don't have Unity Pro

 

Hi

Found out about the Dark Skin bug yesterday.
I had suspected that I might get bugs with pro, but I didnt have pro to test it.
Unfortunately, it does not seem to be any way to detect if the user has the dark skin active, even in the undocumented parts of the API.
I will try to find a solution to the next version, until then you can use the light (free) skin.

 

Great system. I'll give it a try in a next project.

 

Lol nice im goin to try this :]

 

One 2.9x feature I hadn't implemented before was the ability to textures as a source for penalty and walkability.
You can now also sample the height of the nodes from the texture and you can choose which channel to use.

Now I have implemented that again, it will be included in the next version.
I have also thrown in the ability to add penalty based on the angle of the surface the node is placed on and also based on the Y position of the node.

 

Fantastic work. Probably the single most useful unity package going!

I'm getting a vertexCount > 60000 an awful lot. I'm only mapping a grid 100x100 with a node size of 1... anything I'm doing wrong?

 

Nooo! Not that evil "vertexCount > 60000" error... I thought it had disappeared.
I really have no idea why that error pops up sometimes, it seems to have something to do with raycasting on a Terrain object or possible on other objects too, but I don't really know anything more than that.

 

That error is dead annoying. All other solutions suffer from it too (the navmesh preview in Rain {One} for example), anything that seems to raycast the ground to a reasonable degree

 

Ahh, sorry I didn't know it was a known thing. It's horrible, spamming away whilst I'm trying to grid my scene.

Just for the record, this is just a plane, nothing else, so I don't think it occurs just for terrains.

 

The Unity guys really should fix it, it's been known since before 2.6 I think, probably before that too.

 

In my scene, I have a terrain object with the AstarPath component attached ("source terrain") which I'm sculpting and painting as I proceed through development. Using Windows Explorer, I duplicate the source_terrain_data.asset file into a sub-folder under the resources folder and load it at runtime, applying it to a newly instantiated terrain object, enabling me to deform the terrain at run-time without permanently writing changes to the source terrain asset that still resides in the scene. As soon as the path grid scan completes on startup on the AstarPath attached to the source terrain, using Path 2.9 I copy the node data from the original astartpath component over to the instantiated terrain, then de-activate the source terrain. It worked wonderfully:

Original code:

Code (csharp):

1.  
2. AstarPath originalPath = GameObject.Find("Terrain_Map").GetComponent<AstarPath>();
3. AstarPath astarPath = newTerrain.AddComponent<AstarPath>();
4. astarPath.staticNodes = originalPath.staticNodes;
5. astarPath.grids = originalPath.grids;
6. GameObject.Find("Terrain_Map").active = false;
7.  

Today I started migrating to Path 3.x (free version until pro is available for purchase), and noted the serialization classes. I had a quick play, but it appears the following doesn't work. I'm probably doing it wrong, so this code is more an illustration of what I'm trying to accomplish.

New code under 3.x:

Code (csharp):

1. AstarPath originalPath = GameObject.Find("Terrain_Map").GetComponent<AstarPath>();
2. AstarSerializer serializer = new AstarSerializer(originalPath);
3. byte[] terrainByteData = originalPath.astarData.SerializeGraphs(serializer);
4. AstarPath astarPath = newTerrain.AddComponent<AstarPath>();
5. serializer = new AstarSerializer(astarPath);
6. astarPath.astarData.DeserializeGraphs(serializer, terrainByteData);
7. GameObject.Find("Terrain_Map").active = false;
8.  

Of course, I'll replace this whole approach with loading a navgraph from a file once I get the pro version. But as we don't know how long it will be until UnityStore activates it, I need to be able to continue dev work using the approach shown above. Is this achievable with the free version? Or is serialization really only usable with the pro version?

Much appreciation in advance.

 

Your code almost works, it does work in fact, but there is just a small problem. When you select the new path object, the editor will try to deserialize the graph from the previously saved data (though it is null in this case because no data has been saved before). So it will replace the graphs by an empty NavGraph array.
What you have to to, is to assign your data to the astarData.data field, then the editor will also find it.
Here's my code:

Code (csharp):

1. GameObject newTerrain = new GameObject ("NewPath");
2.         AstarPath originalPath = GameObject.Find("A*").GetComponent<AstarPath>();
3.        
4.         AstarSerializer serializer = new AstarSerializer(originalPath);
5.         byte[] terrainByteData = originalPath.astarData.SerializeGraphs(serializer);
6.        
7.         AstarPath astarPath = newTerrain.AddComponent<AstarPath>();
8.         serializer = new AstarSerializer(astarPath);
9.         astarPath.astarData.data = terrainByteData;
10.         astarPath.astarData.DeserializeGraphs(serializer);
11.        
12.         GameObject.Find("A*").active = false;

Also, if you haven't made any changes by script to the first AstarPath, you can just grab it's saved "data" field which would already contain the serialized graphs:

Code (csharp):

1. GameObject newTerrain = new GameObject ("NewPath");
2.         AstarPath originalPath = GameObject.Find("A*").GetComponent<AstarPath>();
3.        
4.         //Get previously saved data
5.         byte[] terrainByteData = originalPath.astarData.data;
6.        
7.         AstarPath astarPath = newTerrain.AddComponent<AstarPath>();
8.         serializer = new AstarSerializer(astarPath);
9.        
10.         //This was the line you were missing before
11.         astarPath.astarData.data = terrainByteData;
12.        
13.         astarPath.astarData.DeserializeGraphs(serializer);
14.        
15.         GameObject.Find("A*").active = false;

And also, since this is the Free version, only the settings will be serialized, so you need to scan the graphs again.

Code (csharp):

1. astarPath.Scan ();

Seems like I should write a better documentation page about serialization though.

Hope it works for you!

 

Also, it is a good idea to destroy the previous AstarPath object, or at least call OnDestroy () on it, before you create the new one, otherwise some static pathfinding data might screw up pathfinding.