dijkstra's algorithm optimization

Questions & Answers
1

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*) //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);
    }

2

Issues I see are:

  1. Using Sort (which is O(n Log n)) rather than a linear search for smallest (O(n)).
  2. The openNodes and closedNodes appear to be ArrayList. That’s not fast enough. Use a List..
  3. 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.