Unity Dijkstra's Pathfinding

Unity Engine
1

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)

GitHub | Wikipedia

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:

Path path = myGraph.GetShortestPath ( start, end );
for ( int i = 0; i < path.nodes.Count; i++ ) {
  Debug.Log ( path.nodes [i] );
}
Debug.LogFormat ( "Path Length: {0}", path.length );

Check the Follower Script for usage example.

License

MIT @ Hasan Bayat
Made with :heart: by Hasan Bayat

GitHub | Wikipedia

3292810–255094–unity-dijkstras-pathfinding.unitypackage (8.19 KB)

9 Likes
2

Thank you for this :slight_smile:

1 Like
3

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 :frowning:

4

Hi, What you mean skipping? You mean passing the Node and going to next one? Like jumping?

Thanks.

5

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

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

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

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:

IEnumerator FollowPath ()
{
    #if UNITY_EDITOR
    UnityEditor.EditorApplication.update += Update;
    #endif
    var e = m_Path.nodes.GetEnumerator ();
    while ( e.MoveNext () )
    {
        m_Current = e.Current;

        // Wait until we reach the current target node and then go to next node
        yield return new WaitUntil ( () =>
        {
            return transform.position == m_Current.transform.position;
        } );
    }
    m_Current = null;
    #if UNITY_EDITOR
    UnityEditor.EditorApplication.update -= Update;
    #endif
}

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.

1 Like
9

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

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

Since you implemented dijkstra, are you planning on implement A*?

12

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

Well, if you’re interested. Here’s my implementation of both Dijkstra and A*.

I don’t have a gui editor, it’s just the graph and resolver:
A*

Dijkstra

The graphs and what not:

14

Nice work, well done, I would definitely use them as reference.

Thanks.

15

Doesn’t unity built in navigation navesh system already do all this?

16

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

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

Ok cool thx so no need to bake a navmesh if using this node system or can they work together?

19

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

Ok would you say is is less resource intensive and any ram benefits?