Search Unity

2D NavMesh PathFinding......

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

  1. Vinnie711

    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.  
    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....
     
  2. r3tNull

    r3tNull

    Joined:
    Apr 29, 2015
    Posts:
    51
  3. Vinnie711

    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

    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:

    https://noobtuts.com/unity/navigation2d
     
  5. r3tNull

    r3tNull

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

    GameDevCouple_I

    Joined:
    Oct 5, 2013
    Posts:
    1,889
  7. r3tNull

    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

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

    upload.jpg
     
    orchard800 and Yousef_Hadhrami like this.
  9. Vinnie711

    Vinnie711

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

    Vinnie711

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

    GameDevCouple_I

    Joined:
    Oct 5, 2013
    Posts:
    1,889
    Works fine for me?

    What did you do to set it up?
     
  12. tetramess

    tetramess

    Joined:
    Feb 10, 2018
    Posts:
    2
    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

    DanielThomas

    Joined:
    Mar 30, 2013
    Posts:
    64
    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
    wlwlz and YBtheS like this.
  14. vhman

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    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"
     
    Last edited: Oct 17, 2018
  15. vhman

    vhman

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

    It will generate NavMesh from first TileMap with TilemapColider2d.
     

    Attached Files:

  16. mvinc006

    mvinc006

    Joined:
    Jan 1, 2018
    Posts:
    89
    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

    SXtheOne

    Joined:
    Sep 5, 2018
    Posts:
    2
    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

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    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

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    Ahahaha

    after couple of updates it does not work)
     
  20. vhman

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    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:

  21. SXtheOne

    SXtheOne

    Joined:
    Sep 5, 2018
    Posts:
    2
    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.
     
  22. vhman

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    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
     
    clang2 and laurentlavigne like this.
  23. clang2

    clang2

    Joined:
    Jan 27, 2018
    Posts:
    6
    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

    clang2

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

    vhman

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

    clang2

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

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    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.     }
     
  28. vhman

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    Last edited: Dec 21, 2018
  29. riverleo

    riverleo

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

    MaDDoX

    Joined:
    Nov 10, 2009
    Posts:
    754
    Looks great! Any chance this also works with hex grids?
     
  31. arsjac

    arsjac

    Joined:
    Apr 28, 2017
    Posts:
    16
    Wait, does that mean your github project is obsolete, and all you need are those two lines of code?
     
  32. mdookie4

    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

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    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

    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
     
    MaDDoX likes this.
  35. vhman

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
  36. Sharlatan

    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.
     
  37. Devastadus

    Devastadus

    Joined:
    Jan 27, 2015
    Posts:
    35
    @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

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    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
     
  39. vhman

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    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

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    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.
     
    Yousef_Hadhrami likes this.
  41. Devastadus

    Devastadus

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

    bikmoped

    Joined:
    Sep 30, 2018
    Posts:
    3
    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 ?
     
  43. vhman

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    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

    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.
    upload_2019-2-18_19-32-38.png
    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 !
     

    Attached Files:

  45. vhman

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    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

    Ennaxor

    Joined:
    Sep 2, 2013
    Posts:
    5
    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!
     
  47. vhman

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    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.
     
  48. vhman

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    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

    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

    vhman

    Joined:
    Aug 13, 2018
    Posts:
    80
    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/)