Poly|Nav: Pathfinding for Unity2D

hi, I've got around 15 AI monsters in my scene all with an avoid radius of 0.5 and the move between script with 5 points to move between. occasionally if most of the AI have chosen the same point they will all stop then nothing happens because they cant reach the chosen point
(I thaught this would be when the OnDestinationInvalid would kick in but it doesn't) . i was wondering if this happens is there a way for the script/AI to choose a different point/path.

 

Hello,
Send me a PM with your invoice ID and I will forward the request to the asset store team.
Don't worry about it.

Hello,

Indeed, If there is agent avoidance on, and many agents try to reach the same goal together at the same time, they can't reach it because they still try to avoid each other. Right now there is no way to handle this, but I should add so that OnDestinationInvalid is raised when this situation happens, like you would expect in the first place

Thanks

 

In my project I have fairly complex boundary polygons that are going to change a bunch during level design, so I'm trying to find a way to automate creating the PolyNav boundary since it will take forever to make it over and over manually. I tried letting Unity auto-generate a PolygonCollider2D around a sprite of the level. Then I copy/pasted the component values into PolyNav's boundary PolygonCollider2D. Unfortunately, this makes PolyNav's pathfinding stop working. It seems as though PolyNav does not recognize the boundary polygon's nodes and can only pathfind using line of sight or using obstacle nodes - pathfinding respects the boundary in that it won't allow an agent to move outside of it, but pathfinding sends the agents only to obstacle nodes and direct line of sight. Here's an example of what I mean, you can see that pathfinding ignores the boundary poly and sends the agent towards obstacles rather than taking the shorter path:



Bigger link: https://gfycat.com/MajorSharpArawana

I also tried copying the PolygonCollider2D's path into PolyNav's boundary poly in code, but that has the same problem. Is there any reason that Unity's auto-generated collider does not work as a PolyNav boundary? Something to do with the "inverse" setting maybe? Is there anything I can do to fix the poly in code so that it does work? Thanks for any help.

Update: Haha, problem possibly solved a few minutes after I wrote that - I took a look at the code and inverting the polygon is just one line of code: System.Array.Reverse(points). I tried that on the boundary poly's points and it does seem to work now! Sorry for the trouble, I should have looked at that first.

 

It seems that the Playmaker Actions for PolyNav has been mistaken with NodeCanvas Actions in the latest update.

By the way, does PolyNav have a 'LookAt' feature? I'm trying to make my enemies to 'look at' the player after they reached their destination like they should know where the player is, not losing the player whenever the player is in close proximity. I tried coding it with PolyNav's API but weird and funny results ensured.

Cheers

 

Just wanted to check in real quick and see how this was going. Does it look like this feature will be possible?

 

Right now, if my destination is a point inside the obstacle polygon, it cannot move at all.
Can you change it to move to the closest valid point to the destination?

 

Hey Nuverian!, Love your asset! <3.

(and correct me if I'm wrong)
Quick thing when generating procedurally for everyone else who might find it useful

When generating the initial navigation mesh you need to set the outer path to be clock wise, and the inner paths (holes) (CYAN, BLUE, PURPLE) they have to be counter clock wise so you can get the edges placed correctly.

ALSO (but not sure if this matters or not): the outer path (RED) has to be the first path in the path arrays in the polygon.

You could just quickly know if a polygon follows a clockwise or counter clockwise direction
in case anyone is wondering

http://stackoverflow.com/questions/...list-of-polygon-points-are-in-clockwise-order

Checkout the screenshot attached . hope it helps everyone!

 

Also @nuverian I would like to ask, why do my agents get through the edges? :S I have set the raidus for both the agents and the edges to 0.13 as you can see in the screenshot attached., and also they get slow when going through the corridors, am I missing something? :S

Thanks a lot!

UPDATE: Set the avoid radius to 0 and they overlap which is totally fine, but still they somehow cut trough edges :/

 

Hello,
I am realy sorry. I somehow missed your post and only noticed now that more posts have been made. Sorry :/
You are correct about this mistake. I will push an updated version soon. Meanwhile you can download the Playmaker actions here.

Regarding the look at thing you are after, if you have enabled "Rotate Transform" for the PolyNavAgent, it wont let you rotate the transform while the agent has a path, but when it hasn't there shouldnt be a problem. What issue did you encounter?

Thanks.

Hello,
To be honest, I didn't really had the chance to work on updating PolyNav yet. I will have the time to do so after some closure with other "hanging" projects firsts.
Thanks for understanding in advance
Cheers.

Hello,

There is an option on the PolyNavAgent inspector to move to "Closer Point On Invalid". Is that what you mean?
Thanks.

Hey. Thanks a lot!

Great information shared here and you are correct about this information as well.
Indeed the outer path (red) has to be the first path in the array

To correct the "cut corner" thing, can you please enable "Repath" and let me know if it works correctly?
The slowing down in tight corridors can be eliminated or decreased by lowering the "Look Ahead Distance" if you dont like that behaviour

Cheers and thanks again.

 

Solved the slowing down issue!, but still they cut trough corners (with repath enabled) any other idea?

 

Hello,
Is there the possibility to send me a project so that I can take a closer look at what might be wrong. Even just a simple reproduction one?

Thanks a lot

 

Hey Nuverian,

I checked better and seems the problem is happening when I create the points for the nav path. I'll organize this and if still have issues will let you know (but I think this is the problem)

STILL: Quick thing. Even if the problem got solved with the "Repath" checkbox. I want to ask how bad is this performance wise?

I checked on the docs and it says:
Repath: if enabled the agent will revaluate and repath its current path for occasions where the map has changed. Disable for performance.

But my map never changes.

Again thanks a lot!

 

Hey,

Dont mention it. Thats what I am here for
Please let me know how it turns out and if the issue persists.
Regarding performance on Repath option enabled, after version 1.5 (current) where the pathfinder has been rewriten, the difference is minimal.
Now, since your map is not changing it should work with Repath disabled as well, but it seems that in your case there is a problem with it either being on or off, so maybe there is something else going on. I will make a recheck tomorrow to see if I have missed something, but please let me know as well if it turns out to be something relevant to the points of the polygon paths.

Cheers and Thanks!

 

Will do! thanks!

 

Hi Nuverian,

Im loving the ease of using your asset, very straight forward and easy to implement.

Unfortunately I have run into a performance problem where if i open a door it creates a spike in performance. Its very small (around 0.5 seconds or so) but its very jarring. Is there a certain way i should be handling NavObstacles other than just turning them off? The spike occurs even with no NavAgents in the scene

My scene isn't overly large and it seems like a large hit for what is going on. Hope you can help!

 

Hey @nuverian ,

Do you know what might be causing that the white lines arent parallel with the green lines (the edges) ?

I havent been able to figure out why is this happening and my AI is navigating across the walls because of this :/

Thanks.

 

Hello and thanks a lot

Unfortunately the performance drop is due to the number of PolyNavObstacles, because it's treated like a grid based solution, while its not

The drop when enabling/disabling an obstacle would be minimal if instead of many obstacles, the map would be less and outlinining the walkable and obstacle areas.
(Blue being the walkable and red the obstacle areas)


Now, I know this might not always be an option, especialy in procedural generated maps, thus I am looking at possible ways to automate this prosses by creating a polygon out of tiles like this, by merging to less polygons.

Meanwhile, I could PM you a way to decrease the spike when regenerating the map by making the process a coroutine.

Thanks!

Hey,

There seems to be an extra vertex there. It must be due to how you generate the map I think.
Can you please confirm an extra vertex there by entering edit mode of the polygon?

Thanks

 

Hello.

Is there a method of controlling the acceleration for an agent? If not, is there any chance of it being added in the future? This would make PolyNav completely perfect!!

Thank you!

 

Hey @nuverian , there is just 1 vertex, not two overlapped, any idea?, checkout the screenshot I attached.

 

Hi @jmunozar, are you by any chance converting from edge colliders to polygon colliders? I ran into the same issues here. I have some working code, they missing pieces are:
1. Remove duplicate points
2. Remove points on the same line

I just made this work a few hours ago, went for a quick and easy approach, I didn't notice any performance issues since I don't swap out tilemaps that often. I'm sure it can be faster, but it's not a bottleneck for me right now.

Here's the method I'm using:

Code (CSharp):

1. private static Vector2[] MassageEdgeColliderPoints(EdgeCollider2D x)
2.         {
3.             const float identicalPointDelta = .1f;
4.             var resultPoints = new List<Vector2>();
5.             for (int i = x.points.Length-1; i >=0; i--)
6.             {
7.                 var nextPointToAdd = x.points[i];
8.                 if (!resultPoints.Any() || !PointsAreIdentical(nextPointToAdd, resultPoints.Last(), identicalPointDelta))
9.                     resultPoints.Add(nextPointToAdd);
10.                 if (resultPoints.Count >= 2)
11.                 {
12.                     var lastPoint = resultPoints[resultPoints.Count - 1];
13.                     var oneBeforeLastPoint = resultPoints[resultPoints.Count - 2];
14.                     if (OnSameLine(oneBeforeLastPoint, lastPoint, nextPointToAdd))
15.                         resultPoints[resultPoints.Count - 1] = nextPointToAdd;
16.                 }
17.             }
18.             while (resultPoints.Count >= 2 && PointsAreIdentical(resultPoints.First(), resultPoints.Last(), identicalPointDelta))
19.                 resultPoints.RemoveAt(resultPoints.Count - 1);
20.  
21.             while (resultPoints.Count >= 3 && OnSameLine(resultPoints[resultPoints.Count - 2], resultPoints[resultPoints.Count - 1], resultPoints[0]))
22.                 resultPoints.RemoveAt(resultPoints.Count - 1);
23.  
24.             while (resultPoints.Count >= 3 && OnSameLine(resultPoints[resultPoints.Count - 1], resultPoints[0], resultPoints[1]))
25.                 resultPoints.RemoveAt(0);
26.  
27.             return resultPoints.ToArray();
28.         }
29.  
30.    private static bool OnSameLine(Vector2 oneBeforeLastPoint, Vector2 lastPoint, Vector2 nextPointToAdd)
31.         {
32.             var line1 = lastPoint-oneBeforeLastPoint;
33.             var line2 = nextPointToAdd-lastPoint;
34.             var angle = Vector2.Angle(line1, line2);
35.             return angle < .1f;
36.         }
37.  
38.         private static bool PointsAreIdentical(Vector2 point1, Vector2 point2, float identicalPointDelta)
39.         {
40.             var pointsAreIdentical = Vector2.Distance(point1, point2) < identicalPointDelta;
41.             return pointsAreIdentical;
42.         }

Yes, the method is named "Massage"

 

One more thing, you'll notice this is doing reversal of points as well, it goes well with this:

Code (CSharp):

1.  private static void BuildColliderForObstacle(GameObject child, EdgeCollider2D x, PolyNavObstacle polyNavObstacle)
2.         {
3.             var polygonCollider = child.AddComponent<PolygonCollider2D>();
4.             polygonCollider.isTrigger = x.isTrigger;
5.             polygonCollider.points = MassageEdgeColliderPoints(x);
6.             polyNavObstacle.invertPolygon = false;
7.             polyNavObstacle.shapeType = PolyNavObstacle.ShapeType.Polygon;
8.         }

Notice invertPolygon is false.

 

Hello,
Currently there is no such setting. I will see adding this though
Thanks!

Such a corner can exist if there are 2 points nearly overlaping each other. Can you confirm there is only a single vertex there? Maybe @vividhelix helped in determining what's wrong?

@vividhelix Thanks for sharing those for everyone!

 

Thanks for the reply @nuverian,

Are you saying i could get the performance up dramatically if I did some calculations to place larger NavObstacles instead of several smaller ones? Is it possible i would be able to get it to a point where i would be able to create and remove some obstacles in real time without any performance hiccups? Its simply a fast paced game so the lag spikes wont do.

I would appreciate a coroutine solution if you dont mind as well. I tried to do this myself but a lack of understanding of your code meant that i dont think i had it right, it didnt fix my problem anyhow.

Thanks again!

 

Oh wow!, thanks! I will try it out and let you know! thanks a lot for chipping in!

 

hey @nuverian, problem solved! indeed it was overlapping vertices!, thanks a lot @vividhelix for guiding me in the right direction!

 

Hey,
Glad it's solved and thanks for letting me know

Cheers!

 

Hello !
First of all, thx for great asset.
I have one question, is there any way to setup some Agents to move through some obstacle ?


------ Boring details -----
I'm trying to create door object and i need to cover following scenario:
Character does not know if door is open or closed, but he assumes it to be open by default, so when you click him he trying to go through door and get stopped. My idea was do disable obstacle initially and enable it, once character "check" the door. So once obstacle enabled character will avoid it during path building.

Works fine, but not with guards. They can pass every door(or more complicated some doors by access level) so i want them to move through doors anyway.
-----------------

Thanks in advance !

 

Hello,

Unfortunately there is no such feature right now, where you can selectively allow some agents to ignore specific obstacles, but it's a nice feature idea to have . I will take a look at that.
Thanks

 

Have you considered moving PolyNav2D.FindPath() into a background thread? I'm struggling with poor performance on iPad because of PolyNav's need to repeatedly iterate over the all of the map's polygons, which really destroys the framerate for even fairly basic maps (100-200 nodes).

Today, I decided to try using a separate thread, and to my amazement it worked right away. The only code inside of FindPath() that needed to happen on the main Unity thread was the callback, and AStar.CalculatePath because it's a Coroutine. I immediately noticed a huge improvement in performance.

I'm not really familiar with all the guts of PolyNav, so I don't know what sorts of issues might arise from making use of a separate thread. But if the Physics2D approach that you've mentioned previously doesn't work out, perhaps this could be an alternative way to optimize performance.

 

Hey Zelek,

I haven't really fiddled with multilpe threads, but sounds like a very sinsible suggestion. I will take a look at that and see what comes up
The Physics2D I was talking about some time ago, is obsolete and not needed after version 1.5 in which the pathfinding had been rewriten. I means, there nothing that using Physics2D would improve now on that part.

Thanks and cheers!

 

The improvements in 1.5 are much appreciated, though I still find the repeated iteration of all the polygon obstacles by these two functions to be overwhelmingly expensive. If there's some way to only iterate over only the nearby nodes, that would be ideal. But if not, then maybe the background thread will help. Allowing multiple PolyNav2D objects in the scene will also give us some options for optimizing node count.

 

Is there a way an agent to an exact point in 2d space. Now it goes near that point but not exact. I need this because I make custom animation for my adventure game and I want them to start from exact points. Thanks

 

Hey,
The way I am trying to solve the issue is by merging the obstacle polygons (probably using clipper or similar), so that in the end there is only one polygon to care for, and thus there be no need for iterating. Using another thread on top of that is certainly a nice suggestions to look for.
Taking into acount only the closest nodes, would not really result in correct paths in circuimstances where the destination or the means to get there, is very far away.

Thanks

Hello,
There is a "stopping distance" variable you can change on the PolyNavAgent inspector. By default it's set to 0.1, but that might not be correct in your case, depending on the scale of the scene and the sprites. Feel free to decrease this value.
Let me know if that solves your issue, or maybe I misunderstood the problem here.

 

I would like a way an agent to stop at an exact point in space eg at x=1.1235 and y=0.5863

 

Is it possible to set the navigation to the xz axis instead of the xy axis? I didn't find a way to rotate it..

 

Hi Nuverian,
I was going to buy this asset as it looks simple yet awesome. My only question is whether the upgrade to 5.0 has any issues. When I go to download it , I get a message box saying that the upgrade might not be without issues.
Thanks
Da Voodoochief

 

Hello,
It works fine with Unity 5.

Thanks!

 

Wowza! Now THAT is a responsive post!! Thanks so much for the info I look forward to working with your asset.

Da Voodoochief

 

Hi, first let me say that this is a great asset, easy to use and implement. However I'm having some issues with it. For some reason a few of the agents in particular places of my map are not able to find a path. The strange thing is that others created at the same spot actually manage to find one.

This is my setup:

Here is the problematic spot:


And I'm using ferr2d (asset store) to create the terrain(Islands) and this is the resulting collider:



I then add a polyNavObstacle to each of the Islands. It seems to work fine in most places but in others the agent don't move at all (even when Closer Point On Invalid is checked). There is also some strange behavior when I set the Radios in the @polyNav2D. The pink lines form small triangles in every corner:


I'm not sure if my setup is right. I really need to work with this ferr2d tool, and to create each of the island polygons collider manually would be very hard, specially because I'm trying to include some random generation. Please if you think on a solution to my problem let me know.

Thanks!!

 

Hello and thanks.

As it seems the polygons are inverted for the Fer2D islands. There is an option in the PolyNavObstacle inspector to "Invert Polygon". Can you please try toggling that option and confirm that the island outlines show correct? If they do the pathfinding should also work correctly.

Please let me know.
Thanks.

 

How can I place waypoints on map?

 

Hello,
PolyNav is not a waypoint based system, thus you don't have to place waypoints for it to work. You just need to call SetDestination(Vector2 position) on the PolyNavAgent.

Did I misunderstood your question?

Thanks

 

I want to make enemies follow a path, so maybe the proper question will be how do I do that? Custom way, by calling setDestination when it reaches position/waypoint designed by me, or is there a build in way to do it?

By the way congratz for making it all, its really usefull and will save me months of work! And price is great aswell.

 

Thank you. I'm glad it helps you.
There is no built in way for that, but here is an example to get you started

Code (CSharp):

1. using UnityEngine;
2. using System.Collections;
3. using System.Collections.Generic;
4.  
5. [RequireComponent(typeof(PolyNavAgent))]
6. public class PatrolPath : MonoBehaviour {
7.  
8.     public List<Vector2> WPoints = new List<Vector2>();
9.     private int currentIndex = -1;
10.  
11.     private PolyNavAgent _agent;
12.     public PolyNavAgent agent{
13.         get
14.         {
15.             if (_agent == null)
16.                 _agent = GetComponent<PolyNavAgent>();
17.             return _agent;        
18.         }
19.     }
20.  
21.     void OnEnable(){
22.         agent.OnDestinationReached += MoveNext;
23.         agent.OnDestinationInvalid += MoveNext;
24.     }
25.  
26.     void OnDisable(){
27.         agent.OnDestinationReached -= MoveNext;
28.         agent.OnDestinationInvalid -= MoveNext;
29.     }
30.  
31.     void Start(){
32.         if (WPoints.Count > 0)
33.             MoveNext();
34.     }
35.  
36.     void MoveNext(){
37.         currentIndex = (int)Mathf.Repeat(currentIndex + 1, WPoints.Count);
38.         agent.SetDestination(WPoints[currentIndex]);
39.     }
40.  
41.     void OnDrawGizmosSelected(){
42.         for ( int i = 0; i < WPoints.Count; i++)
43.             Gizmos.DrawSphere(WPoints[i], 0.1f);        
44.     }
45. }

Cheers!

 

Thanks alot!

 

HI Nuverlan, i'm making a 2d bookgame with some sprite animation, and i've choosed Poly|Nav for path finding.
It works very well, but i've got a little problem.
I've checked Rotate Trasform to true on my sprite instance, and when i put in play the sprite follow the path and rotate itself, my problem is that the sprite rotates immediatly when i click play, and i don't understand why.

here is the sprite on the editor:

https://dl.dropboxusercontent.com/u/225838/before.png

here just after press play:

https://dl.dropboxusercontent.com/u/225838/after.png

can you help me?

thanks

 

Hello,

I can't realy reproduce this behaviour here. Are you sure there is no SetDestination call happening, or maybe you have added the MoveBetween example script on the creature?
It looks like the character get it's path set somehow, else it would not rotate.

Let me know.
Thanks.

 

Hey again, I'm using your asset together with Destructible2D.
Is it possibile to update Poly Nav Obstacle mesh to the one Destructible2D uses?

I would like the enemies to have ability to see/walk through the holes created in walls with Destructible2D

 

Yes, i modified the script:

Code (CSharp):

1.  
2. using UnityEngine;
3. using System.Collections;
4. using System.Collections.Generic;
5.  
6.  
7. //example. moving between some points at random
8. [RequireComponent(typeof(PolyNavAgent))]
9. public class MoveBetween : MonoBehaviour{
10.     private int currentWaypoint = 0;
11.  
12.     public List<Vector2> WPoints = new List<Vector2>();
13.  
14.     private PolyNavAgent _agent;
15.     public PolyNavAgent agent{
16.         get
17.         {
18.             if (!_agent)
19.                 _agent = GetComponent<PolyNavAgent>();
20.             return _agent;          
21.         }
22.     }
23.  
24.     IEnumerator Start(){
25.         yield return new WaitForSeconds(1);
26.         if (WPoints.Count > 0)
27.             MoveToWaypoint();
28.     }
29.  
30.     void MoveToWaypoint(){          
31.         agent.SetDestination(WPoints[currentWaypoint]);      
32.  
33.         //Move to next waypoint:
34.         currentWaypoint++;
35.         if(currentWaypoint > WPoints.Count){
36.             //currentWaypoint=0;
37.             return;
38.         }
39.     }
40. }
41.  

 

Hello,
I don't have Destructible2D to tell for sure, but there would probably be a way to get the polygon from the "D2D_DestructibleSprite" component as well as some kind of event when the collider changes.
You could then use this data to set the regular PolygonCollider2D polgon paths using SetPath. It depends on what the D2D_DestructibleSprite offers, but it will certainly require some coding.

Let me know if you need more help.

Please do not publicly post links that contain commercial assets!
(link removed by moderator)

The sprite is rotating at start of game because on Start, the agent is set a new destination and as such it is rotated. Whenever the agent has a path it's also rotated (if Rotate Transform is checked). If you don't want the agent to be rotated on Start, then you should not set a destination on Start.
You could disable the MoveBetween behaviour in editor and enable it when you need to, through scripting.