A* Pathfinding 2.9 Is Released (Unity 3 Compatible)

Hi Everyone

The A* Pathfinding Project version 2.9 has just been released, this is mostly a bug-fix update which addresses many known bugs.

First of all Unity 3 Compatibility.
Secondly, a bug which could cause units to stop getting path requests computed when a large number of units requested paths at the same time is now solved. The pathfinding query functions has been completely rewritten to use path queues which ensures all paths get computed in order.

For those of you who don't know what the A* Pathfinding Project is:
The A* Pathfinding Project is an easy to set up system for making pathfinding possible in your game.
With it's blazing fast speed and high customisability it's a great choice for integrating pathfinding into your games.
Read more here - http://arongranberg.com/unity/a-pathfinding/

Download the new version at the project homepage - http://arongranberg.com/unity/a-pathfinding/

Some features has been removed due to high crash-rate, multithreading and the beta version of navmesh saving.


Cheers,
Aron

 

I'm excited! I'm currently using this (an older version, I believe) in a non-commercial project and I am beyond impressed.

I personally wish Unity would buy this from you and incorporate it into their game engine. It's sad that such a great game engine lacks such a fundamental (and very hard to code) part of a game, such as pathfinding.

Again, thanks so much for this hard work, and as soon as I need this in a commercial project, I'll fork over the money you want (and deserve) in a heart beat!

 

Congrats on the great release

 

Wheee, thanks for this. I recently mentioned a problem I was having with your (very, very impressive) navmesh generation in this thread, as we're currently trialing a number of engines and pathfinding is an important part of our project. I was amazed to see you'd included a quadtree optimizer, so have been experimenting with your system all day.

Can you suggest any improvements to our workflow for generating a navmesh for something like a multi-floored building on a relatively large terrain? I haven't looked through the code yet, but would it be (relatively) simple to extend raycasts through walkable surfaces, for example to generate a mesh for a building with several stories and stairs, etc, in one pass/grid?

Happy to see an update, and sorry to flood it with questions. Consider this a free thread-bump!

 

Nice.

Are there any plans to reintroduce multithreading in a later version?

 

thanks for the great work,all the time.

 

Would I be right in saying that this should work for the iPhone version of unity also?

Btw, it looks awesome

 

I'm using mesh path and some links added manually and..

Same problem liket the 2.8:


if (Polygon.ContainsPoint (node.GetArea (),pos2D)) {
minNode = node;
minYDist = dist;
}


NullReferenceException: Object reference not set to an instance of an object
AstarMath.Polygon.ContainsPoint (UnityEngine.Vector2[] polyPoints, Vector2 p)
AstarPath.ToLocalTest2 (Vector3 pos, Boolean forceNodesUnder) (at Assets/Pathfinding/AstarPath.cs:709)
AstarPath.ToLocal (Vector3 Vpos, Boolean forceNodesUnder) (at Assets/Pathfinding/AstarPath.cs:780)
AstarPath.ToLocal (Vector3 Vpos) (at Assets/Pathfinding/AstarPath.cs:771)
AstarPath.OnDrawGizmos () (at Assets/Pathfinding/AstarPath.cs:404)
UnityEditor.DockArea:OnGUI()


It happens when i connect 2 areas with a manual link creation. It seams that node.GetArea () return null.

In the 2.5 t worked well. I connected 2 areas and more areas with a manual link. Since 2.8 it doesn't seem to work.

Can you have a look please?

Thank you

 

Awesome work !!! I'll download it and try it out with Unity 3.1. Cheers mate !!!

 

Hi

Oops, nasty bug. Sorry for re-updating the project again so soon, but well... it's better than having a known bug in the system.
2.91 can be downloaded now!

If anyone finds other bugs, please post them.

-Aron

 

Oh wow - thanks for this. I'll download and have a play with it over the weekend

 

oh, finally i am so happy, thank you, Aron!

Edit: played around a little
imports nicely on 3.1, all scenes works perfectly. Few duplicate scripts if copied over new default unity project, easy to trace, using console and delete. Deleted duplicate assets that came with this project and it was still working perfect. Yet to test something manual made, will report if any bugs here

 

Well done at a first look it seems to work now, thank you
I'll post yo other bugs if i'll find them

 

Sturestone, i can't get a correct path with the navmesh (with the same object and links and areas with 2.5 it worked). I connected all the disconnected areas so now it's a full area but the points it gives me to reach the target are not correct and too far away. It doesn't give me the near one first. Do you want the mesh to test it?

thank you

 

i've looked a bit but i'm not seeing anything. is there a function to calculate the distance from the seeker to the target along the path, as opposed to in a straight line?

 

I don't remember right now how did i figured out, i haven't used Aron's A* since a while but i remember doing this before.
You must find out the list of walkable nodes (of the returned path) to the target, then:

Code (csharp):

1. float dist = o;//distance
2. foreach (node in WalkablesNodesToTarget)
3. {
4.     //sum of distances between each node to the target within the calculated (computed) path.
5.     dist  += Vector3.Distance(node.position, target.position);
6. }

Take this as a pseudo-code and not as an exact answer by any means.

 

thanks, i'll give that a shot.

 

Yeah, that would be appreciated,
thanks.

Yup, that's about the right way to do it.
First calculate the path, then calculate the length of it by adding the distances between the points.

 

"AstarData settings disabled due to not functioning correctly"
....................
would u fixed it in next version?
i think it is very important,because the layer maybe used for rendering information setting or other logic,so it could not be "scan map on startup"

 

Don't know, working with serializing is not easy. I will see how it goes.
In the meantime you can duplicate your models used for raycasting, put them in a different layer and destroy them on Start ()

 

hey, I think your pathfinding library seems amazing so far!
But I have some issues with dynamic obstacles.

I saw that you have this setup in your clicker.cs script, and it adds an obstacle in the way, but it doesnt seem to recalculate the grid.
And I get "Flood Filled 343 Nodes, The Grid now contains 4 Areas"

And the number of areas just increase as I add more obstacles. However, the grid is not updated.

The only thing that seems to work is this:
astar.SetNodes(false,new Vector3(10,0,10),0,false);

Then it sets the false at a certain point. When I use the other methods, like bounds and Rect then it seems to just create a new "Area".

Some input would be fantastic

Kjetil

 

that not possible to our big MMO project,if will not work it out recently so maybe i would fixed it myself.
as all my layer is more important for rendering and other logic

 

Hi, sturestone, I'm so glad to see the system upgraded a lot!
I have just upgraded my project from Unity iPhone1.7 to Unity3 successfully, the AstarPathfinding system is ok.

So I decided to upgrade your pathfinding system from 2.5.2 to 2.9.
I imported the allRequiredAssets2_9.unitypackage to my project.

But I found the system changed after the upgrade, The unwalkable nodes moved from the edge to the center.
See the pics I attached which is captured from the left-top corner of the grid, the pic with gray background is 2.5.2, and the one with black background is 2.9, the system changed.

this leads great changes in my game, how can I reset the unwalkable nodes to the edge??

btw, I'm using a 32*32 texture to generate the grid.

Thanks!

 

@DavidiaMagic

The nodes being placed at corners was actually a bug, it is more correct to place them like 2.9 does.
If you want to have them at the previous positions you could use the Offset variable

@Kjetil

I have also found a couple of bugs in the SetNodes functions, I will look into it.

@Mingo

I would have implemented that long ago if it wasn't storage problems, I am not sure how to go about finding the nearest node from an arbitrary position without using huge amounts of memory (remember each byte I use for a 256*256 grid uses 65 kb, an int uses four bytes).

-Aron

 

this is the mesh, can you have a full test of it?
it should be a full connected area, so i connect the different automatic areas manually with node linker. But when i try to get the node path it gives only 1 node even if the target it's far away.

attached the mesh..

 

Hi, thanks for making this pathing library for us. So far, except for this one issue, it has been working great!

I have an issue with your library where is causes Unity 3 to hiccup every few seconds for about 100 milliseconds while playing. It happens even if no path is ever generated. This is very problematic, as it also causes the music and graphics to hiccup. It is calling the garbage collector for each one (viewed with the profiler). Oh, and it also keeps hiccuping after moving to a scene with no A* object in it.

I am creating a single raycasting grid where width=400, depth=400, nodeSize=2.5, height=200. Don't Cut Corners is enabled, quad tree is not, cache paths is not, simplification is off, straight line testing is on, etc etc.

Everything else is working perfectly. I am using version 2.92, but it also happened in the last build I have, which was 2.6 I think.

Please advise.

I also sent this via PM just in case you are not subscribed to this thread. Thank you for your help.

 

@Ayrik

Answered your PM

@Goldrake

Haven't forgot, but I haven't tested it yet.

 

K
try it becasue i think you'll find some bugs

waiting

 

Hi Goldrake

I tried your mesh, it seems like you have a bunch of polygons with more than three connections. This isn't supported by the system as you can see by the error message.

On the screenshot attached, you can see some polys highlighted in red, those are the ones which are connected to more than three other polys.

A triangle should logically only be connected to at most three other polys, if you are not dealing with jumping and such stuff, which the system doesn't support anyway.

Watch out for polys with zero size too, because the system compares the positions of the vertices, not the index values (to prevent areas being disconnected due to not using smooth tangents).

 

Aron,

Using latest version of the code (2.9) however I was noticing issues with my framerate, basically every couple of second the game freezes (drops from 100+ fps to about 4) for half a second. Using the profiler I narrowed the issue down to your code, specifically your OnGUI routines (not sure which one). The GUIUtility.EndGUI() is spending over 250ms there (on a very fast computer).

I played around a bit more before posting this and I can get rid of it by making the size of the grid smaller. I am using a node size of 0.5 (for accuracy) and was using a grid size of 512x512x20, I changed this to 64x64x5 and still at node size of 0.5 and I do not see the issue. However I will need to make it larger over time. For reference I am using Raycasting down to create the Grid.

Any suggestions? Any other info you need?

EDIT: I just realized that Ayrik is complaining of same thing in above post....

 

Huh, GUI?

I am just investigating an issue were the game freezes for a split second when the garbage collector is called, for a 512*512 grid that would be quite often. It is related to that the A* grid uses huge amounts of memory right now. A 512*512 grid would a couple of hundred megabytes in memory ( = not good).

But the GUI...

Do you think you could do me the favor of trying to figure out which gui call (simply by putting a return; statement on functions you want to skip and see if the lag is still there)?

 

Yes, what I am seeing is also b/c of GCCollect calls, but they are coming from GUIUtility.EndGUI(). I bet if you ask Ayrik we will see the GCCollect calls are from the EndGUI function.

I will try and track down the issue as you requested.

 

It appears (still testing) that it might be related to the "Show Debug" checkbox in the static settings. I wonder if you and Ayrik can test this as well. Make sure you make a huge grid and enable that checkbox. Also make sure you use the 0.5 node size as if I use 256x256 with node size of 1 (same overall area grid) I do not see the issue.

 

Nevermind was not that option. I just increased the grid size to 1024x1024x100 and wow what a crash in the editor. Dozens of window error windows popped up stating "Fatal error in GC - Too many GC heaps". So I am thinking somehow your code is causing all these GC calls..

 

After doing more testing it appears that it occurs when two independent situations exist. 1) you use a very large grid such as 512x512x20 with a small node size (0.5) AND 2) You have many OnGUI routines running in your code. For me if I disable all my own GUI code, it runs fine even with a large grid, OR if I make the grid smaller (or just change the node size to 1) and leave my OnGUI running, it is fine. Somehow the combination of these two things has the GC Collection run way too often and take way too long (250+ ms). Since my GUI code is as optimized as it can be - I cache as many of the vars as I can, is there any way you can optimize your code when large grids are used? For instance, is there no way to remove/ignore all nodes that are not used (outside the area). For my dungeon scene I used very little of the actual grid. Or would it be better to create many small grids and combine them with a node? Would this not be slower (having many grids), or recommended?

 

OnGUI is a serious cpu and gc hogg unhappily. Thats very well known and a reason why GUIX or EZGUI are highly recommend out of my view (which one you favor depend on what you want to achieve)

But yea ah 512x512 grid is definitely too large as well, a grid should reasonably be as small as possible and then you should link the different grids accordingly for example

 

Hmm... actually, after more thought, I don't think it is important where the GC calls come from. You see, GC get's called at the moment there isn't enough memory to allocate an object, so it could get called from anywhere.

Or... are they always coming from GUI?

 

Again I think its a combo - however I only have three or maybe four OnGUI's so it should not be an issue. And it does not occur until I increase the size of the grid as I mentioned above,

 

Also the issue is quite a bit less pronounced in a build (FPS drops by about half as much in a build).

 

Hey Aron, another issue I am having. I am trying to get monsters to path through doorways. If I walk straight through I can get the monster to follow, but if I come through at an angle and then cut back a bit the monster gets stuck on the wall next to the door even though I have no nodes there. I think these screenshots will show more:
View attachment 15947

Image 1 shows the path the monster should take and this looks right. However the monster is actually stuck behind the wall directly to the right of the doorway (basically straight ahead).

Image 2 shows my grid from the same point of view
Image 3 shows what the dungeon looks like without the grid
Image 4 shows that area from the top, where the red mark is where the player was and the blue is where the monster is stuck.

Any ideas?

 

Hi there!
I'm really very impressed with the quality of your solution, it's very well done and powerful!
Is there any additional documentation concerning multiple multiresolution grids?

Thanks a lot!

 

Fernando, what exactly do you mean? You can create grids with different node sizes (and number of nodes) and then connect them using node links. It is very easy to do.

 

@KrankyBoyGames
Thank you, that's what I've meant.
I've seen a example about it, but was considering if there's more documentation.


--
Another question
When I'm testing the system in iPhone and iPad, when I close the game an open again, sometimes it crashes, And I'm considering it can possibly be because o multitask is trying to save and load all the data of the pathfind, is that possible?
there's something related with the "cache" ? I didn't got very well how it works.

Thanks a lot : )))

 

Hi, i was just wondering, is it possible to place your own nodes to create your own grid for a more optimized pathfinding ?

 

Thats the easier way,
create an emtpy gameObject, add few gameobjets on it (they could have materials so you can see were they are), then set the A editor to list,
and give the nodes parent to that list. Tada, done

 

Hey, thanks a bunch for this!

 

@FernandoRibeiro

Basically what KrankyBoyGames said, there is no more documentation, I am a bit lazy on adding that.

Regarding the crash:
Hmm, that might be possible, is it working when you are not using pathfinding?
If you have problems you might have to consider using a smaller grid size, the iPhone doesn't have much memory.

The Cache stuff just saves the latest paths and if a unit wants to pathfind from the same start node to the same target node, the pathfinding can use the cached path and doesn't need to bother about recalculating it.

 

If you want something more complicated (more controlled), you can take a look at the custom grid generators in the example project.
I don't remember their names right now, but I think you can find them under the scripts folder somewhere.

 

@KrankyBoyGames

Try using the Don't Cut Corners option (there might be a bug when using it in the latest build though).
Or you can try using a lower Next waypoint distance (there is a variable called something like that on the AIFollow script if you are using it).

 

I modified the code AIFollow.cs and i add the functions code. And this functions are GetEnemies() and FindClosest() .
I want to try Real Time Strategy game and i also use it for A* pathfinding.
There are not working. GetEnemies() create an array which includes "Target" tag of GameObjects. But it is not working.

Any help i will appriciate.

Here is the Code:

Code (csharp):

1.  
2. using UnityEngine;
3. using System.Collections;
4.  
5.  
6. public class AIFollow : MonoBehaviour {
7.     //[RequireComponent (typeof(CharacterController))]
8.     public float speed = 3.0F;
9.     public float rotationSpeed = 5.0F;
10.     public float pickNextWaypointDistance = 3.0F;
11.     public float SearchWaypointFrequency = 0.2F;
12.     public float maxStop = 3;
13.    
14.     public bool continousTargetSearch = false;
15.     public float targetSearchFrequency = 1.0F;
16.     private bool canSearchAgain = true;
17.     public Command command = Command.Stay;
18.    
19.     public Transform target;
20.     private CharacterController controller;
21.     private AIAnimation animator;
22.     private Seeker seeker;
23.    
24.     public Vector3 myPosition;
25.     public Transform[] enemies;
26.     public float distance;
27.                    
28.    
29.     // Make sure there is always a character controller
30.    
31.     public enum Command {
32.         Stay,
33.         Walk
34.     }
35.    
36.    
37.    
38.     public IEnumerator Start () { //public IEnumerator Start ()
39.        
40.         waypointPosition = transform.position;
41.         command = Command.Stay;
42.         controller = GetComponent (typeof(CharacterController)) as CharacterController;
43.         Object anim = GetComponent (typeof(AIAnimation));
44.         animator = anim != null ? anim as AIAnimation : null;
45.         seeker = GetComponent (typeof(Seeker)) as Seeker;
46.        
47.         StartCoroutine (Patrol());
48.         yield return new WaitForSeconds (Random.value*0.5F);
49.        
50.         if (continousTargetSearch) {
51.             StartCoroutine (SearchPlayer());
52.         }
53.        
54.         [COLOR="red"]//here is the start array operations[/COLOR]
55.         GetEnemies();    
56.         myPosition = transform.position;    
57.         target = FindClosest(enemies);
58.         distance=Vector3.Distance(target.position,transform.position);
59.        
60.         while (true) {
61.             FindPoint (curpoint);
62.             yield return new WaitForSeconds (SearchWaypointFrequency);
63.         }
64.     }
65.    
66.     private Vector3 waypointPosition;
67.     //private bool continuous = false;
68.     private Vector3[] points;
69.     private int curpoint = 0;
70.    
71.     public void Update () {
72.         //Debug.color = Color.blue;
73.         Debug.DrawLine (transform.position, waypointPosition, Color.blue);
74.        
75.         //Stop();
76.         Start();
77.         /*GetEnemies();    
78.         myPosition = transform.position;    
79.         target = FindClosest(enemies);
80.         distance=Vector3.Distance(target.position,transform.position);*/
81.     }
82.    
83.     public IEnumerator SearchPlayer () {
84.         yield return 0;
85.         while (true) {
86.             yield return 0;
87.             while (!canSearchAgain) {
88.                 yield return 0;
89.             }
90.             if (continousTargetSearch) {
91.                 canSearchAgain = false;
92.                 seeker.StartPath (transform.position,target.position);
93.             }
94.             yield return new WaitForSeconds (targetSearchFrequency);
95.         }
96.        
97.     }
98.    
99.     public void PathComplete (Vector3[] newPoints) {
100.         canSearchAgain = true;
101.         points = newPoints;
102.         FindPoint (0);
103.         command = Command.Walk;
104.     }
105.    
106.     public void PathError () {
107.         canSearchAgain = true;
108.     }
109.    
110.     public bool HasReachedTarget () {
111.         return curpoint >= points.Length;
112.     }
113.    
114.     public void FindPoint (int cpoint) {
115.         curpoint = cpoint;
116.         if (points == null || points.Length == 0 || curpoint >= points.Length) {   
117.             waypointPosition = transform.position;
118.             Stop ();
119.             return;
120.         }
121.        
122.         if (points.Length == 1) {
123.             waypointPosition = points[0];
124.             command = Command.Walk;
125.             return;
126.         }
127.        
128.         command = Command.Walk;
129.        
130.         waypointPosition = points[curpoint];
131.         Vector3 p = waypointPosition;
132.         p.y = transform.position.y;
133.        
134.         if (curpoint < points.Length - 1) {
135.             if ((transform.position-p).sqrMagnitude < pickNextWaypointDistance*pickNextWaypointDistance) {
136.                 curpoint++;
137.                 FindPoint (curpoint);
138.             }
139.            
140.         } else {
141.             if ((transform.position-p).sqrMagnitude < maxStop*maxStop) {
142.                 curpoint++;
143.                 FindPoint (curpoint);
144.             }
145.         }
146.     }
147.    
148.     public IEnumerator Patrol () {
149.         while (true) {
150.             if (command == Command.Walk) {
151.                 MoveTowards(waypointPosition);
152.             }
153.            
154.             yield return 0;
155.         }
156.     }
157.    
158.     public void Stop () {
159.         command = Command.Stay;
160.         if (animator != null) {
161.             animator.SetSpeed (0.0F);
162.         }
163.     }
164.    
165.     public void RotateTowards (Vector3 position) {
166.         if (animator != null) {
167.             animator.SetSpeed (0.0F);
168.         }
169.        
170.         Vector3 direction = position - transform.position;
171.         direction.y = 0;
172.        
173.         if (curpoint == points.Length - 1  direction.sqrMagnitude < maxStop*maxStop) {
174.             FindPoint (curpoint);
175.             return;
176.         }
177.        
178.         if (direction.sqrMagnitude < 0.1F*0.1F) {
179.             return;
180.         }
181.        
182.         // Rotate towards the target
183.         transform.rotation = Quaternion.Slerp (transform.rotation, Quaternion.LookRotation(direction), rotationSpeed * Time.deltaTime);
184.         transform.eulerAngles = new Vector3(0, transform.eulerAngles.y, 0);
185.     }
186.    
187.     public void MoveTowards (Vector3 position) {
188.         Vector3 direction = position - transform.position;
189.         direction.y = 0;
190.        
191.         if (direction.sqrMagnitude < 0.2F*0.2F) {
192.             Stop ();
193.             return;
194.         }
195.        
196.         // Rotate towards the target
197.         transform.rotation = Quaternion.Slerp (transform.rotation, Quaternion.LookRotation(direction), rotationSpeed * Time.deltaTime);
198.         transform.eulerAngles = new Vector3(0, transform.eulerAngles.y, 0);
199.    
200.         // Modify speed so we slow down when we are not facing the target
201.         Vector3 forward = transform.TransformDirection(Vector3.forward);
202.         float speedModifier = Vector3.Dot(forward, direction.normalized);
203.         speedModifier = Mathf.Clamp01(speedModifier);
204.        
205.         // Move the character
206.         if (controller) {
207.             direction = forward * speed * speedModifier*speedModifier;
208.             controller.SimpleMove(direction);
209.         } else {
210.             direction = forward * speed * speedModifier*speedModifier;
211.             transform.Translate (direction*Time.deltaTime,Space.World);
212.         }
213.        
214.         if (animator != null) {
215.             animator.SetSpeed (speed * speedModifier);
216.         }
217.     }
218.    
219.     public void GetEnemies(){ [COLOR="red"]// Get enemies from the Scene [/COLOR]
220.        
221.         GameObject[] enemyObjects = GameObject.FindGameObjectsWithTag("Target");
222.        
223.         Transform[]  enemies = new Transform[enemyObjects.Length];  
224.        
225.         for (int i = 0; i < enemyObjects.Length; i++)
226.         {          
227.                 enemies[i] = enemyObjects[i].transform;
228.             Debug.Log("GetEnemies() : count = " + i );
229.         }
230.        
231.         Debug.Log("GetEnemies() : enemy count = " + enemies.Length);
232.        
233.     }  
234.    
235.     public Transform FindClosest(Transform[] targets) [COLOR="red"]// Find Closest enemy[/COLOR]
236.         {
237.             Debug.Log("FindClosest() : ---------------> " +targets.Length);
238.            
239.             GameObject[] enemyObjects = GameObject.FindGameObjectsWithTag("Target");
240.        
241.             float closestDistance = (enemies[0].position-myPosition).sqrMagnitude;  
242.            
243.             int targetNumber=0;
244.            
245.             for(int i=1; i<targets.Length ;i++)
246.             {
247.                
248.                 float thisDisatance = (enemies[i].position-myPosition).sqrMagnitude;
249.                
250.                     if(thisDisatance<closestDistance)
251.                     {
252.                        
253.                         closestDistance=thisDisatance;
254.                         targetNumber=i;
255.                        
256.                     }  
257.             }      
258.                    
259.             return enemies[targetNumber];
260.            
261.         }      
262.    
263.     }
264.  
265.  

enemy must detect the target from an array and goes through it. Then Fire() and Destroy "target". After getting another target from an array and goes to the next target....

i am good at javascript but how can i modified it? can it possible to write javascript to array operations? Also how the .js and .cs work together efficiently?