# 2D NavMesh PathFinding......

Discussion in '2D' started by Vinnie711, Nov 8, 2017.

Not open for further replies.
1. ### Vinnie711

Joined:
Sep 6, 2017
Posts:
5
I am working on 2D game, My 2D project need use pathfinding. I search manual from official, and I found the NavMesh Pathfinding of unity support 3D game only... there must be mesh renderer. It cant work on 2D because there is no mesh renderer, unless you add MeshRenderer component add to GameObject,But it conflict with 2D SpriteRenderer...

So... I use the vertex coordinates of Collider2D attached to gameobject to create mesh, eg:
Code (CSharp):
1. private MeshTransform CreateEdge2dMesh (EdgeCollider2D e2d)
2.     {
3.         if (e2d == null) {
4.             return null;
5.         }
6.         Vector2[] points = e2d.points;
7.         Vector2 offset = e2d.offset;
8.         Bounds bounds = e2d.bounds;
9.         Vector3 cv = new Vector3 (bounds.center.x, bounds.center.y, 0);
10.
11.         Vector3[] vertices = new Vector3[points.Length + 1];
12.         Vector2[] uvs = new Vector2[vertices.Length];
13.         int[] triangles = new int[(points.Length - 1) * TRIANGLES_COUNT];
14.         vertices [points.Length] = cv;
15.         uvs [points.Length] = Vector2.zero;
16.         for (int i = 0; i < points.Length; i++) {
17.             Vector2 pt = e2d.transform.TransformPoint (points [i]);
18.             vertices [i] = new Vector3 (pt.x + offset.x, pt.y + offset.y, 0);
19.             uvs [i] = Vector2.zero;
20.             if (i < points.Length - 1) {
21.                 triangles [i * TRIANGLES_COUNT] = i;
22.                 triangles [(i * TRIANGLES_COUNT) + 1] = i + 1;
23.                 triangles [(i * TRIANGLES_COUNT) + 2] = points.Length;
24.             }
25.         }
26.
27.         Mesh mesh = new Mesh ();
28.         mesh.vertices = vertices;
29.         mesh.triangles = triangles;
30.         mesh.uv = uvs;
31.         mesh.RecalculateNormals ();
32.         MeshTransform mt = new MeshTransform ();
33.         mt.mesh = mesh;
34.         mt.transform = e2d.transform;
35.
36.         return mt;
37.     }
Then I call the function eg:
Code (CSharp):
1. public void AddMesh (MeshTransform mt)
2.     {
3.         if (mt == null) {
4.             return;
5.         }
6.
7.         NavMeshBuildSource nmbs = new NavMeshBuildSource ();
8.         nmbs.shape = NavMeshBuildSourceShape.Mesh;
9.         nmbs.transform = mt.transform.localToWorldMatrix;
10.         nmbs.area = 0;
11.         nmbs.sourceObject = mt.mesh;
12.
14.     }
and call NavMeshBuilder.UpdateNavMeshData....
I add the NavMeshAgent to my player, but it doesn't work.
Console print:
Failed to create agent because it is not close enough to the NavMesh

I think the NavMesh PathFinding system need the mesh vertex information to create or bake the walkable/diswalkable area, I create mesh which sharp is exactly match the collider, and use this to create/bake walkable area.....

Do I went about it in the wrong way?...

thx....

AntonioModer likes this.
2. ### r3tNull

Joined:
Apr 29, 2015
Posts:
51
AntonioModer likes this.
3. ### Vinnie711

Joined:
Sep 6, 2017
Posts:
5
Thank you, I think the navmesh need the mesh vertex information to bake walkable area, so I create mesh and send the mesh information to navmesh system of unity, no matter what unity pathfinding algorithm is It need something like mesh to generate nodemap or orther else assist struct, the algorithm just calculate out the walk path data and return base on the mesh information we provided.... But I found it cant work... Is there something wrong, or the thread go to a wrong way?

4. ### r3tNull

Joined:
Apr 29, 2015
Posts:
51
Apparently the problem with navmesh in 2d is the coordinates. 2d uses x,y and navmesh uses x,z. People with a lot of time on their hands have figured out how to switch the coordinates around. Check this out:

AntonioModer likes this.
5. ### r3tNull

Joined:
Apr 29, 2015
Posts:
51
orchard800 likes this.

Joined:
Oct 5, 2013
Posts:
4,002
7. ### r3tNull

Joined:
Apr 29, 2015
Posts:
51
Have you gotten this to work? I don't think it works with sprites due to coordinate mismatch

orchard800 likes this.
8. ### r3tNull

Joined:
Apr 29, 2015
Posts:
51
Apparently, it's theoretically possible for this to work, however, it's not feasible. You will need to rebuild your scene in 3d and rotate all game objects to face xz instead of xy. You will also need 3d colliders instead of 2d. I've ran some tests and with some tinkering it maybe is possible, but, I strongly recommend using A*!!

9. ### Vinnie711

Joined:
Sep 6, 2017
Posts:
5
thx you so mush, you best! I will try A*.

10. ### Vinnie711

Joined:
Sep 6, 2017
Posts:
5
I dont think it work... I have tried....

Joined:
Oct 5, 2013
Posts:
4,002
Works fine for me?

What did you do to set it up?

### Guest

Just to confirm before sinking in hours upon hours trying to do the impossible.
You made navmesh pathfinding work just on sprites in a 2D unity project (started as a 2D project)?

orchard800 likes this.
13. ### DanielThomas

Joined:
Mar 30, 2013
Posts:
114
Not without some workarounds. From my experience I had to do this:

* As mentioned, you need to get the navmeshplane component from unity's git. This will make it possible to bake on any plane, no matter the orientation. So we can use XY plane.

* 2D Colliders doesn't bake by default. I found a script from a blog that made it possible on runtime. If you want to bake in editor I would need to use a 3D collider.

* The navmesh agent would rotate itself to ground to the plane, this would be a problem because it would rotate the sprite/image as well with it. Work around for this was to just put the agent component on an child object and use it with script. So you set it to not move or rotate, but still give it a path - you can then use the desiredVelocity and use those values to move the 2D object.

I think that solved all the problems. But it's a lot of workaround, so you would need to get used to setting your objects up in this way.

Hope that helped. Just saying it's possible.
If anyone has an easier way I would love to hear about it!

Last edited: Oct 12, 2018
wlwl2 and YBtheS like this.
14. ### vhman

Joined:
Aug 13, 2018
Posts:
373
Hi.

I here to confirm that NavMesh totally works in 2D. I implemented NavMeshSurface2d for tilemap in top down shooter as proof of concept.

You need:
1. https://docs.unity3d.com/Manual/class-NavMeshSurface.html just because it has base implementation
2. Empty object rotated respectively to Tilemap (90;0;0) with NavMeshSurface
3. Implement source collector for tiles, because NavMeshBuilder.CollectSources will not work
4. Use X and Z axis for NavMeshBuildSource()

so with something like this

Code (CSharp):
1.     var src = new NavMeshBuildSource();
2.     src.transform = Matrix4x4.Translate(tilemap.GetCellCenterWorld(vec3int));
3.     src.shape = NavMeshBuildSourceShape.Box;
4.     src.size = Vector3.one;
You will able to bake tilemap. With NavMesh API you can implement any complex shapes you want.

Also totally check this "Runtime NavMesh Generation"

Last edited: Oct 17, 2018
EKafer and Ledesma099 like this.
15. ### vhman

Joined:
Aug 13, 2018
Posts:
373
here some POC code, if somebody interested.

It will generate NavMesh from first TileMap with TilemapColider2d.

#### Attached Files:

File size:
19.2 KB
Views:
1,757
• ###### NavMeshSurfaceEditor2d.cs
File size:
19.8 KB
Views:
1,515
Arkade, EKafer and Ledesma099 like this.
16. ### mvinc006

Joined:
Jan 1, 2018
Posts:
91
Wish I found this before I implemented my own A* pathing into my 2D game, though I guess now I have something more efficient and optimisable.

17. ### SXtheOne

Joined:
Sep 5, 2018
Posts:
21
Hi,

Could you please help me out with a basic Unity project where you set up these? I'm stuck with it. I have a simple project but I'm generating the Tilemap in runtime. To be honest I don't know where to put the 90,0,0 rotated empty game object, but I've set a navmeshsurface2d component to the Tilemap and the 'Collect Objects' is set to Grid. 'Use Geometry' is set to Render Meshes but I tried also with Physics Collider doesn't change a thing.
Sorry I'm completely lost. I'm a bit new to Unity but otherwise an experienced programmer.

18. ### vhman

Joined:
Aug 13, 2018
Posts:
373
Hi,

This kind a proof of concept for Top Down games, so it is not a production code. So in any way you need to learn it by yourself.
But here some hints:
1. If you generating Tilemap at runtime, so NavMeshSurface2d.BuildNavMesh() should be called after it is done (check the videos I linked).
2. Empty Gameobject should be placed in Scene root, with NavMeshSurface2d component added and configured. Press right click on its transform, and input rotation x:90 y:0 z:0
3. In NavMeshSurface2d select Collection Object to Grid.

So the points of code you are interested are "CollectObjects2d.Grid" (enum that I added)

First - word bounds calculation:
L:351 Bounds CalculateWorldBounds(List<NavMeshBuildSource> sources)
Second - collect source objects, that are tiles:
L:241 List<NavMeshBuildSource> CollectSources()

My implementation looks for TilemapCollider2D component, by iteration through its tiles as unwalkable. That's all folks.

You can proxy with navmeshAgent, or use static methods CalculatePath. Just be sure that agent touches navmesh, or it will throw exception that agent is too far.

Last edited: Oct 30, 2018
19. ### vhman

Joined:
Aug 13, 2018
Posts:
373
Ahahaha

after couple of updates it does not work)

20. ### vhman

Joined:
Aug 13, 2018
Posts:
373
After couple of updates code above does not work)

So here is an update, it has better production value, but still its just a POC. Maybe I will put in on GitHub

I updated bounds calculation
Code (CSharp):
1. if (m_CollectObjects == CollectObjects2d.Grid)
2.
3.             {
4.
5.                 var grid = FindObjectOfType<Grid>();
6.
7.                 var colider = grid.GetComponentInChildren<CompositeCollider2D>();
8.
9.                 var bounds = GetWorldBounds(worldToLocal , colider.bounds);
10.
11.                 bounds.Expand(0.1f);
12.
13.                 return bounds;
14.
15.             }
And Source Collection, that will substract unwalkable areas
It is mandatory to have CompositCollider2d, as it used to get bounds.
Create root object, rotate x 90, in navmesh2d select "Grid" and "Unwalkable".

#### Attached Files:

File size:
19.8 KB
Views:
1,049
• ###### NavMeshSurface2d.cs
File size:
19.8 KB
Views:
1,143
Ledesma099 likes this.
21. ### SXtheOne

Joined:
Sep 5, 2018
Posts:
21
That's what I was afraid of but thanks for the effort!
I just finished my own A* implementation so I think I can live without navmesh although it would have made my life easier.

Ledesma099 likes this.
22. ### vhman

Joined:
Aug 13, 2018
Posts:
373
I don't know how A* is efficient in your case, but navmesh was about bake.
And my tiles are 8px size. So I have no option not to use some kind of bake)

I updated code and will maintain it on GitHub
https://github.com/h8man/NavMeshPlus

Ledesma099, clang2 and laurentlavigne like this.
23. ### clang2

Joined:
Jan 27, 2018
Posts:
9
Thanks vhman for maintaining the NavMeshPlus repo. I just set it up in a 2D project I'm working on and can verify it works well. I''m currently on Unity 2018.2.16f1. You saved me a bit of trouble. Appreciate the effort!

24. ### clang2

Joined:
Jan 27, 2018
Posts:
9
Ugh... it broke after upgrading to 2018.3. See issue report in repo.

25. ### vhman

Joined:
Aug 13, 2018
Posts:
373
Fixed, check it out.
I'm planning to add Agent wrappers 2d, as I found handling the cornering if not so trivial

26. ### clang2

Joined:
Jan 27, 2018
Posts:
9
Looks good. Thanks!

27. ### vhman

Joined:
Aug 13, 2018
Posts:
373
I thought I need to tweak NavMeshAgent, but as I found, the only thing you need to do is to disable up axis alignment

Code (CSharp):
1.     void Start()
2.     {
3.         agent = GetComponent<NavMeshAgent>();
4.         agent.updateUpAxis = false;
5.     }

Ledesma099 likes this.
28. ### vhman

Joined:
Aug 13, 2018
Posts:
373
Last edited: Dec 21, 2018
aihodge and Ledesma099 like this.
29. ### riverleo

Joined:
Nov 15, 2018
Posts:
1
Thanks vhman, You save my life.

Joined:
Nov 10, 2009
Posts:
764
Looks great! Any chance this also works with hex grids?

### Guest

Wait, does that mean your github project is obsolete, and all you need are those two lines of code?

32. ### mdookie4

Joined:
Jun 15, 2017
Posts:
8
Hi, when i copied over NavMeshComponents, Unity prompted "UnityEditor.PrefabUtility" does not contain a definition for 'GetCorrespondingObjectFromSource'.. does that mean I need to update Unity to 2018ver? I am on 2017.2 and when I perform Unity check for update, it states that Unity editor is up to date.
Pls help ,thank you!

33. ### vhman

Joined:
Aug 13, 2018
Posts:
373
Tnx.
No, it uses only boxes. You can implement hexagonal mesh if you want. I can give you some hints where to start
No, it is still valid, the project is about nav mesh baking. I just never tried NavMeshAgents on it, and good news, they just works with all the rotations))
Emmm.. Yes you need to update to unity 2018.3. I'm not able to manage multiple versions.

34. ### Sharlatan

Joined:
Jul 23, 2013
Posts:
111
@MaDDoX I've just developed a solution that works with hex grids. You just have to make the TilemapCollider part of a CompositeCollider2D. If that's no problem for you, you should be good to go: https://github.com/SharlatanY/NavMeshSurface2DBaker

Joined:
Aug 13, 2018
Posts:
373
36. ### Sharlatan

Joined:
Jul 23, 2013
Posts:
111
@vhman

Thanks!
It's probably not the most efficient nor sophisticated approach. Basically, before calling the Unity bake function, I just create 3D objects from the 2D colliders and delete them again after baking.

But it's (hopefully) easy to use and should cover most use cases.

There are some more features that could be implemented, e.g. support for run time baking. But since that might take some time I'd rather spend on other projects, I'll for now stick to bug fixes, better warning messages and other polish stuff, unless someone explicitly asks for a new feature.

Joined:
Jan 27, 2015
Posts:
80
@vhman thanks for all your hard work. Really appreciate it. But question though, how would you support your sprites rotating towards the object they are facing. I notice in your demo you disable rotation. and by default they *standup* on the plane and you can no longer see the sprites.

38. ### vhman

Joined:
Aug 13, 2018
Posts:
373
First, I have nothing to do with navmesh or agents, its unity core features)
But, here are some hints how to override:
Code (CSharp):
1.
2.     private NavMeshAgent agent;
3.     // Start is called before the first frame update
4.     void Start()
5.     {
6.         agent = GetComponent<NavMeshAgent>();
7.         agent.updateRotation = false;
8.         agent.updateUpAxis = false;
9.     }
So updateUpAxis is preventing from *standup*, while updateRotation should prevent automatic object rotation. Nice.

The simplest solution is to allow all the "positioning", and rotate renderer child object -90 degree on x.
Pros: all is done automatic; Cons: you will see sprites only in "play"; Workaround: re-rotate in editor by scripting

Next, disable updateUpAxis, and make custom update of renderer child object, so Y rotation will corresponds to sprites Z rotation
Pros: all is done automatic; Cons: inconvenient rotations update;

The last solution, disable all updates, and do them by yourself
Pros: customizable; Cons: its now your work to do)

39. ### vhman

Joined:
Aug 13, 2018
Posts:
373
Hi,

I here with new update.

Now redHotSweetPapper has two scenes, one with square and one with hex tiles!
You can use grids with any tile, just create a mesh of that tile and feed to NavMeshSurface2d.
Its easy and done with two clicks.

Latter I will push changed to NavMeshPlus.

40. ### vhman

Joined:
Aug 13, 2018
Posts:
373
Hello again.

NavMeshPlus now supports NavMeshBuildSourceShape.Mesh as a tile, this mean than you can use any tile you want.
It can be hex or isometric tile map as well. All you need is a Mesh that corresponds to a tile shape. See documentation and demo update.

In future I planning to simplify the process by incorporating triangulation to build meshes for 2d objects right in unity editor. So we will able to generate mesh for 2d object or tile and put them on NavMesh as modifiers.

Joined:
Jan 27, 2015
Posts:
80
Hey vhman thanks for the help i got my project working with the rotations.

42. ### bikmoped

Joined:
Sep 30, 2018
Posts:
3
Btw I am trying to exclude some layers from the NavMeshSurface and doesn't seem to work. After baking the corresponding NavMeshModifiers are still modifying the surface.
Is it a feature you have not implemented yet ?

43. ### vhman

Joined:
Aug 13, 2018
Posts:
373
Hi,
Thanks for feedback. What do you mean "exclude layers"? I tested NavMeshModifier.ignoreFromBuild is working for tilemap.
Reference code:
Code (CSharp):
1.                 if (modifier != null && !modifier.ignoreFromBuild)
2.                 {
3.                     CollectTileSources(sources, tilemap, area);
4.                 }
5.                 else
6.                 {
7.                     var collider = tilemap.GetComponent<TilemapCollider2D>();
8.                     if (collider != null &&
9.                         (modifier == null || (modifier != null && !modifier.ignoreFromBuild)))
10.                     {
11.                         CollectTileSources(sources, tilemap, area);
12.                     }
13.                 }
Can you give more details? Maybe steps to reproduce with screens?)

44. ### bikmoped

Joined:
Sep 30, 2018
Posts:
3
Thank you for your answer ! My problem was very simple, I have 2 different layers of obstacles in my map and I wanted to remove one from the "include layers" list of the NavMesh Surface, as you can see below.

But after hiting bake, the Bushes were still active in the NavMesh Surface.
However as you said NavMeshModifier.ignoreFromBuild is working perfectly and is totally doing what I wanted.
Thanks buddy !

File size:
51.2 KB
Views:
1,126
File size:
33.3 KB
Views:
1,012
45. ### vhman

Joined:
Aug 13, 2018
Posts:
373
Now I get it. I will check layers and Ill try to implement proper source collection

UPDATE. Done.

Code (CSharp):
1.     if ( ((0x1 << tilemap.gameObject.layer) & m_LayerMask) == 0)
2.     {
3.         continue;
4.     }

Last edited: Feb 19, 2019
46. ### Ennaxor

Joined:
Sep 2, 2013
Posts:
5
Hi vhman!

I'm trying to implement this in a small prototype I'm working on, testing with some random sprites through Unity's tilemap system. The thing is: I have a small problem that I'm not sure how to resolve:

The objects on my terrain have their own colliders and everything seems fine with this. The problem comes when I bake the navmesh:

The collision areas become a lot larger and I think that due to this, when I navigate through the terrain with my player, the pathfinding does strange things:

https://gyazo.com/32f207879b02425d5f6e20a9fe26679a

I've used the same values as in your github project. I've also tried to change the obstacle avoidance radius but it doesn't seem to affect, so I'm not sure what can be causing this (maybe the sprites I use? 16x16 tiles?)

47. ### vhman

Joined:
Aug 13, 2018
Posts:
373
Hi @Ennaxor,

As usual, keep in mind, I'm not capable to do anything with NavMesh or Agents, its unity core features)

As you can see, in my sample, sprites has tile size and shape of a grid, while colliders can use "sprite shape" or "grid cell shape" or "none". It can explain large holes in NavMesh , as well as Agents Radius. A log has 1 tile thick, and nice +0.3 units bounds, while pond is 3x3 units +0.3 bound, that's the reason. Wait for a day, I'm releasing NavMeshSurface that using "sprite shape".

As for agent navigation.. it seems fine. It has it angle momentum, acceleration and braking. Explain what undesired behavior you are getting.

48. ### vhman

Joined:
Aug 13, 2018
Posts:
373
Hi,

New update. Now https://github.com/h8man/NavMeshPlus supports baking mesh directly form sprites.
This mean it supports tiles of any shape as long as palette collider type is Tile.ColliderType.Sprite
I will appreciate testing and performance testing feedbacks.

Documentation update will be soon. Keep in mind, you should use NavMeshModifier to targeted tilemaps (sample: https://github.com/h8man/RedHotSweetPepper)

Next feature is tile Tile.ColliderType.Grid support.

djDavidj likes this.
49. ### Ennaxor

Joined:
Sep 2, 2013
Posts:
5
Thanks @vhman,

I'll wait for the NavMeshSurface update. As for the agent navigation, I'm trying to avoid the kind of elliptical movement it does when approaching object colliders, like in this gif:
https://gyazo.com/f9b4044b1de86e17e5a0127f1b24cbaf
I'm not sure what causes the agent to do that extra movement.
Also, do you now if NavMesh supports a grid system or if there's a way to base de agent's movement as if it was grid based, constraining movement to 8 directions?

50. ### vhman

Joined:
Aug 13, 2018
Posts:
373
Update "Tile.ColliderType.Sprite" is ready, take a try.

If you want instant turning and acceleration, just pump it up, make values big. Agent doesn't follow path strictly. Use Debug.Line to draw the path.

and nope, navmesh or agents do not have grid behavior, nor does camera. You need to implement it.
I'm not using agents at all, NavMesh has static methods for path finding, it gives you route and then do what you want.
I think this question is better to ask in this forum (https://forum.unity.com/forums/navigation.79/)