How to Implementing Morten Nobel-Jorgensen's A* Pathfinding

Hi,
Could someone help implement the code.
The code is here : GitHub - mortennobel/UnityUtils: A library of C# utility classes for Unity

The Problem :
I have a grid in Unity3D. It is 20x50. No I want to find out the shortest path from [1,1] (StartNode) to [20,50] (EndNode). I trying implementing the code but I’m really missing something. Could someone with more expertise help me out ?

What I did :

  1. Placed the UnityUtils folder in my Project.
  2. I created a Dictionary with Nodes of the grid with properties like walkable or not and so on.

How do I send the Dictionary to the script so that it can return the shortest path ? I did not quite figure out how the script works and where do I input the information it needs to calculate.

Thank you in advance.

Hey, I just stumbled across this A* implementation myself (http://blog.nobel-joergensen.com/2011/02/26/a-path-finding-algorithm-in-unity/) and I think I can explain it for you.

The algorithm is written using generics, which means it can work with whatever data type you are using to store your grid. But in order for this to work the ShortestPathGraphSearch class needs to know how to use your data.

It does this through the interface that is defined in the IShortestPath.cs. You’ll notice the interface defines 4 methods: Heuristic, Expand, ActualCost and ApplyAction.

You’ll also notice his ShortestPathTest class is defined as:

public class ShortestPathTest : UUnitTestCase, IShortestPath<Vector2i, Vector2i>

The UUnitTestCase part isn’t important, but the rest shows that this class implements the IShortestPath interface using Vector2i’s as the data type. This means this class must define the 4 methods defined in the interface.

What you have to do is basically the same thing the ShortestPathTest does, only adapt it to work with your grid data.

Hello Vatara,
I believe I understand the algorithm and the code partially, but I still can’t figure out how to input the data.
Let me explain.

As far as I saw this part is the initPart of the code :

public void TestNoObstacles () {
		ShortestPathGraphSearch<Vector2i,Vector2i> search = new ShortestPathGraphSearch<Vector2i,Vector2i>(this);
		List<Vector2i> list = search.GetShortestPath(new Vector2i(1,0), new Vector2i(3,0));
		Assert.Equals(2,list.Count);
		Debug.Log("Test No Obstacles");
		foreach (Vector2i pos in list){
			Debug.Log("Position "+pos);
		}
	}

Does it mean that in the “search.GetShortestPath(new Vector2i(1,0), new Vector2i(3,0));” Vector2i(1,0) is the StartPoint and Vector2i(3,0) is the EndPoint ?

If that is the case, than where is the input for the GridData?
I would presume that the code needs the StartPoint, the EndPoint and the GridData to process everything correctly. So, following this idea and with my grid example of 20x50 I would need :

  1. Coord(1,1) : StartPoint
  2. Coord(20,50) : EndPoint
  3. GridData (as you mentioned in the last line of your post). But this is one of the things that I do not understand. How do I create the GridData (is it suppose to be in a List or Dictionary) and then , how do I send this Data to the Script?

Do I do something like :

void Start () {
    Dictionary<string,Dictionary> NodeDictionary = new Dictionary<string,Dictionary>();
    NodeDictionary.Add("StartPoint coordonated", childNodeDictionary);

    //In the Dictionary we have only the StartingNode
    for( x=node in adjacentNodes){
        Dictionary<string,Dictionary,bool> childNodeDictionary = new Dictionary<string,Dictionary,bool>();
        myDictionary[NodeCoordonates] = childNodeDictionary;
    }
}

and after I populate the Dictionary with all childs and so on, how do I send it to the Pathfinding Script ?

There are some issues with Morten Nobel’s code. I’ve just made a Pull Request (GitHub - mortennobel/UnityUtils: A library of C# utility classes for Unity) suggesting a way to fix it, I hope he sees that soon.

His code won’t work perfectly well for a valid state as input, and will definitely not work for a invalid input (like a state that can’t be reached). Take a look at the pull request to see the changes if you want.

But it’s pretty easy to implement, just take a look at his implementations at: https://github.com/mortennobel/UnityUtils/blob/master/pathfinding/_test/ShortestPathTest.cs