- Home /
How to Implementing Morten Nobel-Jorgensen's A* Pathfinding
Hi, Could someone help implement the code. The code is here : https://github.com/mortennobel/UnityUtils
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.
Answer by vatara · Jan 12, 2012 at 02:18 AM
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.
Answer by dotSnipe · Jan 12, 2012 at 11:35 AM
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 :
Coord(1,1) : StartPoint
Coord(20,50) : EndPoint
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 ?
"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 ?"
Correct. But you don't need to worry about creating the Dictionary or nodes. The algorithm builds that using the interface. Think of the interface as questions the algorithm needs to ask about your data. The Heuristic is asking how far from one node to another (estimated). Expand returns a list of all possible moves from the given node. ActualCost returns the distance given a node and a movement(action) from that node. ApplyAction adds the node and the action(movement direction) to return the new node. The test class is working with the same type of simple grid you're using. You could do: List list = search.GetShortestPath(new Vector2i(1,1), new Vector2i(20,50)); The only change you would have to make, is modifying the Expand method. The line: "if (newState.magnitude==0) continue; // location 0,0 is blocked" means the node (0,0) will never be returned as a valid move, aka it's blocked. If you have no obstacles in your grid you can get rid of that line and the method will return a list every direction as valid moves(4 if !moveDiagonal, 8 if it's true). If you do have obstacles you need to change Expand to not add the blocked node to the list of moves, given the current state.
So you are saying that in this method of the ShortestPathTest.cs class :
public List Expand(Vector2i state){ List res = new List(); for (int x=-1;x<=1;x++) for (int y=-1;y<=1;y++){ if (x==0 && y==0) continue; Vector2i action = new Vector2i(x,y); Vector2i newState = ApplyAction(state, action); if (newState.magnitude==0) continue; // location 0,0 is blocked if (!moveDiagonal && x*y!=0) continue; // res.Add(action); } return res; }
and I want to mark let's say Node (2,5) as unwalkable I just do :
if (x!=2 && y!=5) continue;
and so for every unwalkable Node on my grid ?
Almost. See how the x and y go from -1 to 1? They represent the direction you're trying to go from the current state (up, up-right, right, down-right, down, down-left, left, up-left). The vector newState adds the action to the current state, which gives the new state. You'd want to do:
if (newState.x==2 && newState.y==5) continue;
Thanks for clearing that out. Will post back in the next few days with feedback.
Answer by MouseCaneta · Dec 14, 2013 at 07:15 PM
There are some issues with Morten Nobel's code. I've just made a Pull Request (https://github.com/mortennobel/UnityUtils) 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