2D NavMesh PathFinding......

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.  
13.         m_NavMeshSourceList.Add (nmbs);
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....

 

You can't use navmesh in 2d right now. If you absolutely cannot use a grid for A*, check this out:

http://www.jgallant.com/nodal-pathfinding-in-unity-2d-with-a-in-non-grid-based-games/

 

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?

 

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:

https://noobtuts.com/unity/navigation2d

 

PolyNav is another asset with strong reviews:

https://www.assetstore.unity3d.com/en/#!/content/14718

 

I am sorry but this is completely incorrect. Navmesh can be used in 2D since 2017. Use a navmesh surface component, and youll be able to create a navmesh on anything.

https://docs.unity3d.com/Manual/class-NavMeshSurface.html

 

Have you gotten this to work? I don't think it works with sprites due to coordinate mismatch

 

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*!!

 

thx you so mush, you best! I will try A*.

 

I dont think it work... I have tried....

 

Works fine for me?

What did you do to set it up?

 

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)?

 

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!

 

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;
5.     sources.Add(src);

You will able to bake tilemap. With NavMesh API you can implement any complex shapes you want.

Also totally check this "Runtime NavMesh Generation"

 

here some POC code, if somebody interested.

It will generate NavMesh from first TileMap with TilemapColider2d.

 

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.

 

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.

 

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.

 

Ahahaha

after couple of updates it does not work)

 

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". ​

 

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.

 

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

 

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!

 

Ugh... it broke after upgrading to 2018.3. See issue report in repo.

 

Fixed, check it out.
I'm planning to add Agent wrappers 2d, as I found handling the cornering if not so trivial

 

Looks good. Thanks!

 

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.     }

 

Uploaded demo with NavMeshAgents chasing around https://github.com/h8man/RedHotSweetPepper

Also added windows binaries to try it out https://github.com/h8man/RedHotSweetPepper/releases

 

Thanks vhman, You save my life.

 

Looks great! Any chance this also works with hex grids?

 

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

 

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!

 

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.

 

@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

 

@Sharlatan

Proj looks awesome!

 

@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.

 

@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.

 

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)

Fell free to ask questions

 

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.

 

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.

 

Hey vhman thanks for the help i got my project working with the rotations.

 

Thanks a lot for your work vhman, it's very helpful !
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 ?

 

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?)

 

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 !

 

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.     }

 

Hi vhman!
Thanks a lot for your examples and for your work!

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?)


Thanks in advance!

 

Hi @Ennaxor,

As usual, keep in mind, I'm not capable to do anything with NavMesh or Agents, its unity core features)
Thank you for your feedback.

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.

 

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.

 

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?

 

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/)