Search Unity

  1. Unity 6 Preview is now available. To find out what's new, have a look at our Unity 6 Preview blog post.
    Dismiss Notice
  2. Unity is excited to announce that we will be collaborating with TheXPlace for a summer game jam from June 13 - June 19. Learn more.
    Dismiss Notice

Unity Dijkstra's Pathfinding

Discussion in 'Scripting' started by hasanbayat, Nov 19, 2017.

  1. hasanbayat

    hasanbayat

    Joined:
    Oct 18, 2016
    Posts:
    630
    Hi.
    Note: Not being maintained by me, it was just an experiment for learning unity and c# concepts. (I may publish a complete package for this manner in future)


    It is the implementation of Dijkstra's Pathfinding Algorithm in Unity (Game Engine) that let's you find the shortest path between two Nodes in a Graph.


    In this example we are going to find the shortest path from Node A to Node F:


    In this example we will try to follow the path using a simple Cube object:


    Usage

    Editor Usage

    Click on Graph object to use the Editor Integration.

    Runtime Usage

    You can use the Graph GetShortestPath method to get the shortest path and follow it:
    Code (CSharp):
    1. Path path = myGraph.GetShortestPath ( start, end );
    2. for ( int i = 0; i < path.nodes.Count; i++ ) {
    3.   Debug.Log ( path.nodes [i] );
    4. }
    5. Debug.LogFormat ( "Path Length: {0}", path.length );
    Check the Follower Script for usage example.

    License

    MIT @ Hasan Bayat
    Made with ❤️ by Hasan Bayat

     

    Attached Files:

    Last edited: May 30, 2019
  2. imaginationrabbit

    imaginationrabbit

    Joined:
    Sep 23, 2013
    Posts:
    349
    Thank you for this :)
     
    hasanbayat likes this.
  3. neokit

    neokit

    Joined:
    May 28, 2016
    Posts:
    6
    Thank you! Hope you explain how to tell the follower to ignore specific nodes by tag (not all the followers) only specific one, I tried but no luck :(
     
  4. hasanbayat

    hasanbayat

    Joined:
    Oct 18, 2016
    Posts:
    630
    Hi, What you mean skipping? You mean passing the Node and going to next one? Like jumping?

    Thanks.
     
  5. neokit

    neokit

    Joined:
    May 28, 2016
    Posts:
    6

    What i exactly mean is each follower has a list contains all the tags that he is allowed to walk through if the E is locked he will go to B instead
     
  6. hasanbayat

    hasanbayat

    Joined:
    Oct 18, 2016
    Posts:
    630
    For example, if the follower has the path of A, B, C and D, and is starting at A and the target is C, When the user is at A, he can pass the B and go to C instead, so simply pass the Node you don't want to move through.

    Thanks.
     
  7. neokit

    neokit

    Joined:
    May 28, 2016
    Posts:
    6
    Good is it possible to tell the follower to read the nodes tag? like giving the Follower a string list called ( enabled tags ) if the node's tag is not added in this list the Follower will not pass through it, he should make the shortest path only through the nodes that is added in the enabled tags list
     
  8. hasanbayat

    hasanbayat

    Joined:
    Oct 18, 2016
    Posts:
    630
    Yes, it is possible, you have full access to the whole game object properties, components and etc.
    Open the Follower.cs file and take a look at FollowPath coroutine:
    Code (CSharp):
    1. IEnumerator FollowPath ()
    2. {
    3.     #if UNITY_EDITOR
    4.     UnityEditor.EditorApplication.update += Update;
    5.     #endif
    6.     var e = m_Path.nodes.GetEnumerator ();
    7.     while ( e.MoveNext () )
    8.     {
    9.         m_Current = e.Current;
    10.  
    11.         // Wait until we reach the current target node and then go to next node
    12.         yield return new WaitUntil ( () =>
    13.         {
    14.             return transform.position == m_Current.transform.position;
    15.         } );
    16.     }
    17.     m_Current = null;
    18.     #if UNITY_EDITOR
    19.     UnityEditor.EditorApplication.update -= Update;
    20.     #endif
    21. }
    The m_Current is the current Node, and you can access the GameObject via m_Current.gameObject like other component associations.

    This feature seems to be a good addition, I have plan to make this pathfinding more familiar with unity and add extra components and features.

    Thanks.
     
    neokit likes this.
  9. TheGameChainJS

    TheGameChainJS

    Joined:
    Feb 1, 2018
    Posts:
    2
    Hi I'm trying to change the size of the connections from 1 to 3 in the nodes, but it keeps going back to 1 element. I would like to have three different nodes being connected to the one node, but it won't let me. What should I do? Thanks in advanced.
     
  10. hasanbayat

    hasanbayat

    Joined:
    Oct 18, 2016
    Posts:
    630
    Hi.
    For example, for connecting node A to node B you need to add node B to node A connections list and do the same thing in node B side to make an two-way connection.
    Also, as you can see in the Image above, three different nodes are connected to node E.
    Anyway, if you provide more information I can do more to help you.

    Hope this helps.
    If you have any further questions or help request, just let me know.
    Thanks.
     
  11. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,560
    Since you implemented dijkstra, are you planning on implement A*?
     
  12. hasanbayat

    hasanbayat

    Joined:
    Oct 18, 2016
    Posts:
    630
    Yes, I am planning to implement A* too, but there are some implementations already available for Unity, anyway, I will create an implementation by myself, but I can't provide any specified time or any time soon.

    Thanks.
     
  13. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,560
  14. hasanbayat

    hasanbayat

    Joined:
    Oct 18, 2016
    Posts:
    630
    Nice work, well done, I would definitely use them as reference.

    Thanks.
     
  15. tawdry

    tawdry

    Joined:
    Sep 3, 2014
    Posts:
    1,357
    Doesn't unity built in navigation navesh system already do all this?
     
  16. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,560
    Sort of yes, and sort of no.

    First off unity's navmesh is pre-baked. You can't recalculate the graph at runtime.

    Also, Unity's system is mesh based instead of node based. This is fine for open 3d worlds. But can be very limiting for 2d games, if even useful at all. And it also can make for some odd shaped graph paths without averaging.
     
  17. Kiwasi

    Kiwasi

    Joined:
    Dec 5, 2013
    Posts:
    16,860
    Sort of. But the built in system has some severe limitations. It's not really practical for anything other then straight forward navigation on a Navmesh.

    With a more generic system, you can do anything.
     
  18. tawdry

    tawdry

    Joined:
    Sep 3, 2014
    Posts:
    1,357
    Ok cool thx so no need to bake a navmesh if using this node system or can they work together?
     
  19. hasanbayat

    hasanbayat

    Joined:
    Oct 18, 2016
    Posts:
    630
    These two different system don't have any relation to each other and there is no need they work together, because their purpose is different from each other.

    Thanks.
     
  20. tawdry

    tawdry

    Joined:
    Sep 3, 2014
    Posts:
    1,357
    Ok would you say is is less resource intensive and any ram benefits?
     
  21. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,560
    Dijkstra as an algorithm is more naive than A* (if I recall correctly, unity's navmesh uses A*.. the documentation says it does). Which means it technically is less efficient since it'll do a more broad search of the graph... checking nodes that A* would otherwise ignore.

    But that's only part of the equation of "resource intensity".

    RAM wise, I'd suspect this would take up more memory since it appears they use GameObjects for the nodes, and stores neighbours in a List. Where as unity has a navmesh that is probably more compact and resolves neighbours through the vertex neighbours. But there's no way for me to really say without running tests. I just suspect it's less RAM on the unity navmesh end of things.

    Again though... these aren't the benefits to using a 3rd party option to the unity navmesh. The reasons to use them are for things like runtime recalculation, or because a navmesh is less flexible for your design.
     
    Kiwasi likes this.
  22. TheGameChainJS

    TheGameChainJS

    Joined:
    Feb 1, 2018
    Posts:
    2
    Hi again, I managed to connect all of the nodes in the graph, thanks for the help. Is it possible to show the shortest path on screen whilst playing the game? I am trying to implement a way-point system for a car game, thanks.
     
  23. hasanbayat

    hasanbayat

    Joined:
    Oct 18, 2016
    Posts:
    630
    Yes, you can, it depends on your own implementation, for example you can use Line Renderer component for displaying connections.

    Thanks.
     
  24. Gradofan

    Gradofan

    Joined:
    Jun 21, 2017
    Posts:
    1
    Hi Hasan. I've tried to add new node, and make 2 Connections. But I cannot set Connections more than 1. Why does this happen?
     
  25. hasanbayat

    hasanbayat

    Joined:
    Oct 18, 2016
    Posts:
    630
    Hi.
    Did you have tried to increase the size of connections array?
    We have done it in the demo scene, without any issues, should it maybe is a local issue.

    Thanks.
    Best Regards.
     
  26. MarcoMassa

    MarcoMassa

    Joined:
    Oct 2, 2018
    Posts:
    1
    Same problem here! The number displayed in array come back to normal 1.
    Any suggestion for this issue?
     
  27. ZackrulNizam

    ZackrulNizam

    Joined:
    Jan 20, 2018
    Posts:
    1
    Hi Hassan. Thanks for sharing this. But I have a question, is it possible to add a new node and it automatically connected to the nearest node?
    node.png
     
  28. Shfr

    Shfr

    Joined:
    Jul 30, 2018
    Posts:
    1
    Hi Hassan
    why i cant add more than 1 conection in node ? no matter how i add is always revert back to 1
    you said early try increase size connection array, but where i do that ?
     
    Last edited: May 19, 2019
  29. bgebitekin

    bgebitekin

    Joined:
    Dec 22, 2020
    Posts:
    11
    If anyone is looking for a fix on this, remove the code line that checks for the duplicates in the node code.
     
    YggdrasilGames likes this.