- Home /
dijkstra's algorithm optimization
Hey,
I did an implementation of dijkstra's algorithm and it was too slow, so I did some research and rewrote the entire thing. Well it is still too slow. I am new to programming, so I may be making some huge errors as far as efficiency. Anyway, what can I do to make this more efficient? Right now it takes about a second on a 16x16 grid. Half a second would be better, but instantaneous would be ideal.
@Graham: I thought maybe there could be something I am not understanding as far as using ArrayList in a unity scripting environment. I will look into finding an algorithm message board.
@Mortennobel: I thought A* used dijkstra's? Also, I am trying to find all the possible moves for one piece, not that route from one point to one point. Or am I confusing what A* does? Thanks for the example. I will take a look at it.
enter code here
function GetMoves (startNode: Vector3)//the coordinates of the piece we are moving aka the start node
{
openNodes.Clear(); //removes data from last move
closedNodes.Clear();
for (x = 0; x<Nodes.Count; x++) //Nodes is an arrayList of all the squares in the map in the form of Node which is my custom class for storing information about each square
{
openNodes.Add(new Node (Nodes[x])); //this is done using a custom overloaded constructor to make a deep 'copy' of node x. openNodes is now a deep copy of Nodes
}
var tempNode: Node; //Node is my custom class with information about a given square or space. tempNode is used once below to set up the openNodes array list
var currentNode: Node; //Used to store the Node we are currently working with in the core of the algorithm
var testNode:Node; //Used to store the child node of the current node so that we don't have to look it up in the openNodes array list multiple times
var testDistance:int; //Used to store a possible distance for an adjacent node to see if it is lower than the current theoretical distance
for (x=0; x<openNodes.Count; x++)//now that openNodes is populated, we need to set it up so that the open Node with the smallest .totalDistance (that is, the smallest theoretical distance from the start node) is always at position 0 in the arrayList this loop gets things started by finding the start node, setting the start node totalDistance to zero and putting that node at position 0 in the openNodes arrayList.
{
if (openNodes[x].coordinates == startNode)//Node.coordinates is a vector3 that is the location of the space on the board. This looks for the one that is our start node
{
tempNode = openNodes[x];
openNodes.Remove(openNodes[x]);
openNodes.Insert(0, tempNode);
openNodes[0].totalDistance = 0;
break;
}
}
while (openNodes.Count > 0) //This checks to see if any of the neighbors of the current node have a shorter path through the current node than any path discovered before. if so, we set the totalDistance of that node to reflect the new shortest known path to that node. We close each node (remove it from openNodes) after we visit it. This is the heart of the algorithm, so anything that will make a major impact on the efficiency will probably happen here
{
currentNode = openNodes[0]; //we sort by distance at the end so 0 is always the shortest distance unvisited (open) node
openNodes.RemoveAt(0);//we still have to do the calculations, but the current node has been/is being visited so we remove it from openNodes. We will put it into closedNodes (visited nodes) at the end
for (i = 0; i < currentNode.Children.Count; i++) //each Node has a precalculated array of the coordinates of that nodes neighbors. These for loops search through openNodes to find any children (neighbors) of the current node and then tests to see if the distance from the start node through the current node to the child is smaller than the child's current theoretical distance from the start node. If so, the child gets a new lower distance.
{
for (j=0;j < openNodes.Count; j++)
{
if (openNodes[j].coordinates == currentNode.Children[i]) //is the openNodes[j] a child of the current node?
{
testNode = openNodes[j];//we store this in testNode so that we can avoid looking up this Node in the arrayList multiple times.
testDistance = testNode.moveCost + currentNode.totalDistance; //move cost is the the move cost of a single square (eg clear terrain = 1 and rough = 3 etc) testDistance is the total distance from the start node to the current node + the move cost of the child node (adjacent node to the current node)
if (testNode.totalDistance > testDistance) // if the child Node (here testNode) totalDistance (theoretical distance) is greater than the distance to the current node from the start node + the move cost of the child, then we have found a shorter route to the child node and we set the total distance to the new shorter route
{
openNodes[j].totalDistance = testDistance;
}
}
}
}
closedNodes.Add(currentNode);//not a deep copy, but does not have to be.
openNodes.Sort(new MyComparer()); //this uses a simple custom comparer to make it sort by totalDistance. Someone said that Sort would be faster than anything I could cook up, but I really only need the smallest of the children to be organized as only their values will have changed. Should this be changed?
}
print ("done" + currentNode);
}
There is nothing here particularly Unity related. You might get more assistance from a specialist algorithm site.
A second? On what hardware? That's an inordinately huge amount of time, there may be something actually wrong with your implementation (sorry, I didn't notice that point when I answered).
@SmooveB please stop posting comments and questions as answers. Ins$$anonymous$$d use this space here or edit your question to include clarifications as necessary.
Sorry. I swear I did not see the add new comment button even thought I thought there should be one. Never used the Answers form before... Or the internet really.
No worries, you're far from the first to miss that ; )
As for the stuff you've already posted as answers, it will be easier to understand (for people joining the conversation) if you consolidate the additional details you've given into your original post and delete the answers; that way all the relevant data is in one spot and it won't look (as it does now) like you've received 6 possible solutions already.
Answer by Waz · Jul 26, 2011 at 11:09 AM
Issues I see are:
Using Sort (which is O(n Log n)) rather than a linear search for smallest (O(n)).
The openNodes and closedNodes appear to be ArrayList. That's not fast enough. Use a List..
You should use an iterator, not indexing (if they are List.)
Finally, how often are you calling all this? Once every frame? Every frame for every enemy? Or only when the nodes change? It should be the latter.
I am calling it when you click on a piece to move (This is a turn based strategy game. Ultimately I display highlighted squares that the piece has enough movement to get to). I also call it right after a piece moves to show an updated highlight if the piece has any movement left.
For number 1: I guess just make my own simple for loop search?
For number 2: Got it, this is just the kind of thing that I needed to know.
For number 3: Not sure I totally know what this means. Indexing is what an arrayList does. What is an iterator in this context?
I am going to implement number 2 and number 1 as I understand it. I will let you know what kind of an impact that makes. Thanks!
Generally, this pattern:
for (var i=0; i<list.Count; ++i) {
var item = list[i];
...
}
is only most efficient for true array-based containers. I'm not an expert, but IIRC, LinkedList<T>
is not array-based, but List<T>
might be. For Dijkstra's algorithm works best with link lists, since the primary operations are iterating, adding, and removing elements, not random access (which is what array-based containers are good at).
As an aside, the Profiler that comes with Unity Pro is made for exactly this sort of thing. Turn on Deep Profiling and it pretty-well answers this question for you.
Ok, getting rid of Sort did it. Thanks a ton.
Simply replaced Sort with iterating through openNodes. Is that the only change you were referring to with #3, or did that refer to another change as well?
For anyone running across this thread, switching from arrayList to List would have helped, but when I went to do that, I found out that the change had already been made. I don't know how this happened and I am a little freaked out.
Welcome to the Twilight Zone....
You might get slightly better performance if you switch to LinkedList and an iterator:
for (var e=list.GetEnumerator(); e.$$anonymous$$oveNext();) {
var item = e.Current;
...
}
$$anonymous$$ay be negligible though.
Your answer
Follow this Question
Related Questions
How can I get my pathfinding algorithm to know that it cant go through certain sides of tiles 1 Answer
Is there an algorithm to find the path that should be taken in this scenario? 2 Answers
3D Grid Based Movement (X-Com 2012 etc) – How to implement vertical movement? 0 Answers
How does A* pathfinding algorithm work in unity 3d? 1 Answer