Poly|Nav: Pathfinding for Unity2D

Hey,

The next version will include the way to find a path of 'start' and 'end' positions in out of limits. It's basicaly based on what I've posted above before.

I'll go ahead and take another look for possible optimizations. There are always more to do

Regarding using the CircleCollider for obstacles, even it that is done, in the end it will translate into a polygon and of course, if that polygon has a lot of vertices, it will mean that a lot of path nodes will be created and as a result, the more there are, the slower it will be.
Still, I could add support for a CircleCollider with a resolution slider to determine the number of points of the resulting polygon used.

Cheers!

 

So, I've submited the next version. Here are the changes:

• Support for BoxCollider2D as an obstacle shape.
• Support for BoxCollider2D as a walkable area shape.
• Added SetMessageReceiver(GameObject) in PolyNavAgent to define where the messages are send to if at all.
• Added per-obstacle extra 'offset from edges'.
• Out of limits start position for when requesting a path in PolyNav is now handled.

The circle collider shape support is not added in this version. Sorry

Cheers!

 

Thanks!

Yeah, that's sort of an issue.

Good idea! That'll allow squares, equilateral triangles, and all regular polygons.

 

The new version is now live on the asset store
Enjoy.

@Shifty Geezer
I will add the circle shape in the next version

Cheers

 

thanks man great asset. i was having trouble with my previous pathfinding solution, and it was just too resource intensive, this one seems like its going to work nicely.

 

Hey thanks a lot!
I'm glad you like PolyNav

If you have any questions feel free to ask.
Cheers!

 

Right now I'm trying to do destructible objects in a 2D twin stick shooter. The problem I'm getting right now is that whenever I destroy a GameObject with the PolyNavObstacle script on it, I get massive slowdown. I'm sure this is because of the Regenerate on Change. So my question is, is it possible for me to do destructible objects and still use this poly nav system? If not, then it's no huge deal

 

Hello,
Yes, this is because of the map regenerating automaticaly. If you are destroying a lot of objects at the same time, it would be best to disable 'Regenerate On Update' and manually call PolyNav.current.RegenerateMap() after all game objects have been destroyed.

Let me know.
Thanks

 

I tried the manual call but i still get a massive stutter (which is the navmesh regenerating). Are the obstacles not dynamic?

 

Hello,
They are not dynamic in the sense that the Unity's build in navigation system has dynamic obstacles, but generaly they should not hikup the game in most cases. I will take a look for possible optimizations and let you know. I am sure there are some that can be made.
By the way, for about how many Obstacles and node count (shown in the PolyNav inspector in runtime) are we talking about?

Thanks

 

Just bought PolyNav, really cool asset.

When I try to get an agent to move towards a moving object, the agent remains essentially still (with some little movements), yet the path is continually updated. When the target object comes to a halt, or if the agent has direct line of sight of the target, the agent will path to it as normal.

Is there any way to make the agent move more normally towards a moving target? If not, is this something that could occur in the future?

I'm using the PlayMaker action to Move to a Game Object, with Every Frame checked.

Thanks!

 

Hello, I have one question before I purchase this. Although this is 2D Astar, does it support a way to set rules for platforming AI? In the examples, the AI floats to the target point, but I want to know if there is a way to make it so it can only reach the target point based on its jump strength or some other defined rule.

For example,
http://i.imgur.com/8FI3gOZ.jpg

Thanks

 

Can this be used for Turn-based grid style 2D games ?
I am looking for a solution for this:
http://gamedev.stackexchange.com/questions/89963/unity-grid-movement-turn-based-2d/

 

Hello and thanks!

Indeed there is a bug introduced in last version. Please open up PolyNav2D.cs and comment out line #118 and it should work fine. I will fix it the next version as well.

Thanks!

Hello,

Unfortunately no This is quite beyond the scope of PolyNav. Sorry about that!
With that said, I had some thougts for platforming pathfinding like this, but even then it will not be able to do such calculations, like for example just strength, but instead provide a set of linked nodes to place around the scene and ways to "transition" between them. Again, this feature is not there now, but will possibly (no promise) be in the future

Cheers!

Hello,

PolyNav is not a grid based pathfinding solution and as such the included steering agent, does not move grid-like, but instead moving straight on the most direct path available.
With that said, you can of course use PolyNav to find a path in such a game with square obstacles and units in between. It's just that the included agent will not move from square to square, but instead freely

Let me know if you have any questions on the matter.
Cheers!

 

1. Okay so basically instead of checking a path grid by grid, it checks it in a line like X-Y position from a point ?
2. If you check the link I posted and the screenshot it, can it be used in something like this ? I can create the grid movement logic/method but what I mean is whether I can detect if there is a GO in front of me (x-1), below me (y-1) or such, with squares and chara GO both having colliders

Are there anymore videos available which I can use to better understand the asset and its working to make sure if it will work for my use ?

 

Hello,

Yes, the path result is not grid by grid like you describe.
Sorry but no you can't check for a character/obstacle to see if it's in front, back, etc. since that requires a grid logic behind and there is really no grid logic in PolyNav. You can use some exceptional grid solutions found on the asset store for those checks. eg http://u3d.as/content/hi-phish/grid-framework/3bR

What you can do with PolyNav though is to check if a specific location is free/valid or is blocked, meaning that there is an obstacle there, or is simply out of the navigation map.

There are no further videos than those, but feel free to let me know if you have any questions that you feel are missing

Cheers!

 

I've been optimizing the scene, removing all unneeded vertices and using as little colliders as possible. I am getting around 418 node counts. Is there no way to make the polynav work dynamically and have moving polynav obstacles as well?

 

Hello,
Working dynamicaly in PolyNav means that the navigation map is regenerated when a change in obstacles takes place.
I will take a deep look for possible optimizations first thing after holidays

 

I'm doing some prototyping, and perhaps I missed something in the documentation about PolyNav2D and large worlds.

I am prototyping a large game world, which is entirely walkable. However, once I make it big enough, it locks up Unity as well as locks up the game after I try Build/Run. I imagine this is because there are too many objects or the walkable area is too large.

It works absolutely fine if I keep it within a few screens. However, the game map is quite big so I am curious if I am missing an option or a way to do it. Obviously I do not need to have the game know the entire map to play- I just need to to figure out pathfinding for the immediate area / nearby obstacles.

The world map im testing is about 7x7 screens of 1080p. So 13440x7560 size map.

If I try a 3x3 area instead, it takes a bit to load but eventually loads fine.

Is PolyNav2D only suppose to be for games which have very small scenes, like a Point & Click game?


edit: The size of the walkable area doesn't matter. It was the number of obstacles in the walkable area. Still an issue though. Will I have to enable/disable objects based on the player's proximity, and then refresh the @polynav2D constantly? Was hoping for a simpler solution.

 

alendro I too am using this with some destructible terrain a solution i have found was mixing this http://quantumyeti.com/blog/destructible-terrain-in-ferr2d and then using a trigger to disable the obstacle once either a certain amount of damage is done, or the player moves into space previously occupied by the terrain. not sure if it will help you, but so far its been working for me.

 

hey so im having this issue where i get a massive frame rate drop when i use obstacles, like from ~100 to 15. if i get rid of the obstacles and just adjust the walkable area to be the same thing then frames stay ~100. which i did for most of my levels but for a few its just not possible. This is one of the levels

 

@CarterG81 @angelsin and everyone else

The performance bane of PolyNav right now are 2 particular functions, 'CheckLOS' and 'PointIsValid', which respectively determine if 2 points in the navigation map can see each other and whether or not a specific point is a valid navigation point. Both of them iterate the polygon obstacles to determine the outcome bool and that is why the more obstacles there are the slower it becomes.

The good news
In the next version PolyNav will once again use Physics2D to determine the above. The performance difference of using Physics2D versus how it's done now, is simply tremendus. The very first versions of PolyNav were using Physics2D for that, but it was later removed to remove the need of using custom Layers and any coupling with the physics system. As it seems the payoff wasn't worth it.
Once the new version is done (about 3 days more or less) I will post it here and you will be able to get it directly by email if you dont wish to wait for it to go live on the asset store.

There are also some optimizations done regarding the speed at which the navigation map is regenerated and some other things as well.

@CarterG81 Most than probably the issue you got will be resolved with the new version and there will be no reason to enable/disable obstacles

@angelsin Even on how PolyNav works right now, this seems a very simple map for that kind of drop. Seems very weird. Rest be asured though that everything will be resolved in the next version

Thanks for using PolyNav and happy holidays!

 

Awesome, I can't wait
I'll just leave the levels out of the rotation until it's ready.

 

Just purchased PolyNav and it's awesome. So simple to use. I'm also making a large scrolling world game (like CarterG81), so I'm very excited to hear about the switch to Physics2D. I'm thinking I may end up with 1,000+ NavObstacles in the scene, so this change is my only hope for making it usable in this type of game.

It would be very interesting to see an option in PolyNav for it to only track the NavObstacles that are currently visible in the scene, so that it's not iterating through all the obstacles off camera. At least for my game I don't give the player any way to move the camera independent of the character, so the target location for the pathfinding can never be further away than the edges of the screen.

 

well I released my game that uses this. I had been having issues with the obstacles so I took them out for the most part. I plan to go back and change some things once the update is live and I download it.

 

Hello,
I've downloaded PolyNav but have some issue.
I've created snippet simialr to ClickToMove:

Code (CSharp):

1. this.Character.State = this.Agent.SetDestination(clickedPoint,
2.                                                   b =>
3.                                                   {
4.                                                       this.Character.State =
5.                                                           States.Idle;
6.                                                   })
7.                                       ? States.Moving
8.                                       : States.Idle;

Is you can see, when point is clicked I change state to "Moving". The problem is callback passed to SetDestination. I've noticed that sometimes callback is not called despite path is completed. I have tried to debug code, but when I attach debugger, the velocity vector is calculated properly and callback is called.
Very strange. What could be a problem?

 

Sorry everyone for not bringing the promised update yet. I was veery busy with some other matters :/
I will try and hurry the update up this time.

@theredace I will investigate into your suggestions if the performance is not as expected after the update

@pwas The problem could reside in the anonymus method, but I can't tell for sure without the rest of the nearby code. Does it work correctly by not using an anonymus method?

Thanks

 

@nuverian do you mean replacing anonymous method with concrete method? If yes, it doesn't help.
Here is whole snippet:

Code (CSharp):

1. public override void Update()
2. {
3.     if (!Input.GetMouseButton(LeftMouseNo))
4.     {
5.         return;
6.     }
7.  
8.     var clickedWorldPoint = Camera.main.ScreenToWorldPoint(Input.mousePosition);
9.     this.lastClickedPoint = clickedWorldPoint;
10.  
11.     this.Character.State = this.Agent.SetDestination(clickedWorldPoint,
12.                                                                 b =>
13.                                                                 this.Character.State =
14.                                                                 CharacterState.Idle)
15.                                           ? CharacterState.Moving
16.                                           : CharacterState.Idle;
17.  
18.     base.Update();
19. }

There is only code that uses Agent.

Why GetMouseButton instead of GetMouseButtonDown? I want to make character "follow" moue when button is pressed (like in Diablo)

 

fixed warning "The referenced script on this Behaviour is missing!"?
it appeare when use as behaivore.
There is any problem using it with this warning?
thanks

 

Hello again. Sorry for the late reply.
I just realized that the callback is not called when you manualy call Stop() on the PolyNavAgent. Otherwise I can't reproduce a case where it doesn't. Could it be that you are calling Stop() on the PolyNavAgent and thus the reason why you don't get the callback provided in the SetDestination?

Please Let me know.
Thanks.

Hello,
This warning means that you have a script on some game object that though that script is deleted. To resolve the warning you will need to remove the component on the game object which has the deleted script. Probably you did something like that by accident?

 

Unfortunately - not. The Update method is the only one that uses PolyNav. No Stop method is called. May it be that this.Agent.SetDestination is called multiple times when mous button is pressed?

 

Hello,

When SetDestination is called multiple times, only the last SetDestination's callback provided will be called, which is not really a problem though. I can't seem to reproduce a case where the callback is not called at all :/
Is it at all possible that you send me a project showcasing this issue?
Sorry

 

Hello,
I've found issue. It turned out that decelration rate was... to high. When I decreased it couple times, everything started working property.

 

If the destination is (0,0), SetDestination() does not work. Is there a work around for this?

 

This is very exciting! Do you have a recommended number of polygons / vertices that it's optimized for? Trying to get a sense of how complicated I can get before things get overloaded.

Was also wondering how difficult it is to set the vertices/polygon procedurally. If I created a procedurally generated level, how much work is it to feed PolyNav a bunch of vertices/polygons/edges through a script?

 

hi ive just brought polynav and its absoulutly amazing. I was just woundering if you could give me a quick example on how to use "remainingDistance:float" for instance I have a agent following the player but if the player is within a certain distance I want the agent to do something but then if the players leaves that distance I want the agent to do something else like follow again.

 

Hello there! Great work on this, working great so far. I do have one question about something I might be misunderstanding.

I am using FindPath but it is only returning one node that is the same as the start node. I am not sure if this is intended or if the path is supposed to still return a correct path from the out of limits position. My use case is an several objects that pathfind but are obstacles for eachother.

At the moment I can just disable the obstacle when it moves. This would cause problems if two obstacles need to find paths at the same time however, as they would not see each other as obstacles at that time.

Edit: Strange, it seems to work sometimes.. but the paths are way off, they tend towards corners of other obstacles.

Edit2: The box collider functionality also seems a little broken. Half the time it doesn't generate correct paths (or anything past the start position). Inverting polygon doesn't do anything.

 

How do you check to see if the path is blocked?

My best attempt (of many) was this:
bool targetIsBlocked = !myAgent.polyNav.PointIsValid(destination); //always false
but it is always false.

 

Hello everyone and sorry for the late replies.

Indeed that is true only when the first SetDestination is Vector2.zero because I am checking for whether or not the new destination is almost the same as the last destination goal and the last destination goal initializes at Vector2.zero.
So a quick fix would be to open up PolyNavAgent and at line #38 change the _primeGoal to something crazy
I will fix this properly though.

Thanks
I can't realy recomend a specific number, but currently the more the obstacles the more the performance hit, which also depends on the number of path agents of course. Something that will change in the future (it should have already, but I was very busy with some other matter unfortunately)

Regarding setting the vertices proceduraly, you can definetely do so. In practise all you have to do is set the vertices of the PolygonCollider2D as normal and then call PolyNav2D.current.GenerateMap()
The PolygonCollider2D used for the main navigation polygon (the one attached on the same game object as PolyNav2D, not the obstacles), also supports multiple polygon paths. So you can use the API shown here to do that
Just remember to call GenerateMap() afterwards.

Thanks a lot! I am glad you like PolyNav
Notice that the remainingDistance is not the actual straight line distance to the goal, but the distance of the path to the goal and thus its greater than 0 only when the agent has an actual path going somewhere. Here is a simple example:

Code (CSharp):

1.  
2.     void Update() {
3.  
4.         if (Input.GetMouseButton(0))
5.             agent.SetDestination(Camera.main.ScreenToWorldPoint(Input.mousePosition));
6.  
7.         if (agent.hasPath){
8.             if (agent.remainingDistance < 3){
9.                 Debug.Log("Im close enough");
10.             } else {
11.                 Debug.Log("Im far enough");
12.             }
13.         }
14.     }

Hello and thanks

I highly dont recoment using PolyNavObstacle on top of moving agents because its highly ineficient performance wise. Instead you should use the Avoidance Radious on the PolyNavAgents so that they avoid each other.
This is probably the reason why the resulting path of FindPath get quite funky.
Are the rest of your issues realtive to using PolyNavObstacle on moving agents?

Please let me know. Thanks

Hello,

PointIsValid will check if the specified Vector2 position is a valid navigation point where an agent can be on, but it doesn't acualy check if the agent can go there. To do that, you will have to actualy find a path to there.

So to recap. If PointIsValid returnts false, then it already means that the agent will not be able to go there, even without checking a path to that position. But if there are obstacles in between, then the only way is to actualy check a path.
The SetDestination function returns false if a path is not possible. So you can do this for example:

Code (CSharp):

1.     void Update() {
2.  
3.         if (Input.GetMouseButton(0)){
4.        
5.             var goal = Camera.main.ScreenToWorldPoint(Input.mousePosition);
6.             if (!PolyNav2D.current.PointIsValid(goal)){
7.                 Debug.Log("Goal is block or is outside of the navigation map");
8.                 return;
9.             }
10.  
11.             if (agent.SetDestination(goal) == false){
12.                 Debug.Log("I cant go there");
13.             } else {
14.                 Debug.Log("On my way...");
15.             }
16.         }
17.     }

As you can see the PointIsValid is not really necessary since you can do it directly with SetDestination, but it have it's uses in other places for sure.

Cheers!

 

Could we make LookAhead checking optional? For my settings the look ahead vector doesn't allow my character reach most of destinations. With LookAhead commented out everything is fine. I know I can comment it out every time I upgrade but option would be a permanent solution.

 

Hello,

The LookAhead method is used for the slowing down but as well as for the agent avoidance. I suppose that in your case the default lookAhead value of 1, is too big. So, it would be better if you decrease that value instead of commenting the whole LookAhead method in my opinion, of course unless you dont have any agent avoidance

I can definetely make the lookAhead distance public so that you can tweek it as you need and if the value is set to 0 then basicaly ignore the LookAhead method as well.

Will do for the next update

Cheers!

 

Setting _primeGoal to new Vector2(Mathf.Infinity, Mathf.Infinity); seems to do the trick. Thanks!

 

I am interested in PolyNav. It is stressed that this is a 2D pathfinding solution. How is this different from 3D pathfinding solutions?

 

Hi,

I just purchased your asset and I am having difficulty finding out how to set the size of the agent. What I mean is, I want the following to work:



But the below to not work:



As in, I want the size of my Poly Nav Agent to affect the gaps between Poly Nav Obstacles it can go through. Can you assist with this?

Kind regards,
Gary

 

Hello,

The main differences are that it works in the unity 2D plane without hack arounds, it works with Vector2 directly and with 2DColliders, which are basicaly used to set up the navigation area with ease visually.

Let me know if you have any questions.
Cheers!

Hello and thanks for the purchase.

Having different sizes in different agents is not currently supported. Instead you can set a global radious for all of the agents in the PolyNav2D inspector "Radius", similar to how you set it up in the Unity's Navigation/Bake inspector.

Let me know if you have any other questions.
Cheers!

 

Incompatibility with Aron Granberg's A* project

Hi,

I just bought this in the sale because I wanted to check out the Behaviour Designer integration. When I tried to import it into a project which includes this and Aron Granberg's A* project I got this error:

Assets/AstarPathfindingProject/Modifiers/RadiusModifier.cs(127,35): error CS0117: `Polygon' does not contain a definition for `Left'

Do you have any suggestions here?


cheers

Nalin

 

Thanks for the reply.

Do you intend on implementing this any time soon? This was a pretty core mechanic I wanted in my game.

 

Hey man, love the asset. Any news on the new version?
Also, different size agents would be real nice, if possible.

 

I see it is a static variable in a singleton

I can make this work for me, as each client will only have 1 type of agent. What I can do is just have this value change depending on what "player object" is chosen. If a bigger one is chosen, then set the variable higher, while the other clients will do their own calculations and just send me their current locations.

Thanks for your replies

 

Hi, I was wondering if anyone could tell me how to change the animation to the direction the agent is going.
I have 5 animations of; idle, left, right, up and down, and I was wondering what property of the agent would I use in order to tell what direction it was traveling.
(Using mecanim)I was wanting Boolean parameters for each animation so that if the agent was going left then the parameter for walking left would be set to true. I was wondering if this was at all possible.

thanks in advance.