I'm trying to determine if this is an optimization I should pursue or if this is way to complicated to be worth my time. I've successfully implemented the A Star Algorithm for my video game. I used this awesome reference. Here's a video of the algorithm working in my mobile game. In game, the screen size is a programatic coordinate system of (135, 185). Those aren't actual pixels, just think of them as coordinates. And my pathfinding nodes are every 5 coordinates, so that means 135/5 = 27 nodes horizontally and 37 nodes vertically.
Because of all the stuff going on in my game I want to optimize the A Star algorithm so that I don't have to use that many nodes unless it's necessary. Let's say you're in a building and you have lots of narrow hallways, you'll need nodes that close together. But if you're in a wide open field or something you won't need nodes that are so close together simply because there aren't many obstacles in your way.
So I'm thinking of implementing two different node coordinate systems, one that's a node every 5 coordinates as calculated above and then another that's a node every 8 coordinates. The idea is that if I have fewer nodes the calculations will be much faster. I'll need some sort of detection that determines which node system to use or possibly to combine both.
Example: Let's say the soldier wants to walk from coordinate (10, 10) to (100, 100), I'll need to determine whether the pathfinding algorithm use the nodes every 5 coordinates grid or the nodes every 8 coordinates grid or does it use the 5 for the first half and the 8 for the second half...
Thoughts?
-----EDIT-----
Here's a video of the pathfinding's calculation duration in game. With a grid of 135x185, I had 3 soldiers move from one end of the screen to the other through various obstacles. The quickest path was calculated in 46 ms, the next 99 ms, and the longest in 127 ms. I ran my game through XCode Instruments time profiler but didn't notice any pathfinding functions hogging CPU time. The biggest chunks of time was being spent on animations of the soldier's body parts....
Here's the code for my A Star Implementation in C# with Xamarin Studio. I've also noticed that there are some other A Star Implementation posts on this site, I'm reviewing them now to see if some of the optimization suggestions for other people apply to me.
-----EDIT-----
I still am not able to get any good information from XCode Instruments regarding the CPU usage of my pathfinding function, but I did some manual time measuring myself using DateTime and discovered this: The foreach loop where I "Calculate the F G H for all nodes on openList" is using about 50% of the path CPU time for long paths. My "GetAdjacentNodesToThisNode" function that is called many many times ends up using about 33% of the CPU time for long paths. So clearly optimizing those two sections of code would help. I'll see what I can do.
-----EDIT-----
I was able to reduce the pathfinding CPU usage dramatically (but about 60% on long paths) by simply replacing my static function calls with the code itself. It results in code duplication which I hate, but the performance boost is noticeable!!
public static List<AStar_Node> AStarAlgorithm ( long startNode, long endNode, bool forceMove_regardlessOfIsWalkable )
{
// The UIApplicationDelegate for the application.
AppDelegate appDel = (AppDelegate)UIApplication.SharedApplication.Delegate;
DateTime before = DateTime.Now;
List<AStar_Node> openList = new List<AStar_Node>();
AStar_Node CurrentNode;
AStar_Node StartNode;
AStar_Node EndNode;
long diagonalMoveCost = 14;
long vertOrHorzMoveCost = 10;
long startNodeX = (((startNode-1)%appDel.globals.NumOfNodesX));
long startNodeY = (((startNode-1)/appDel.globals.NumOfNodesX));
// Console.WriteLine("startNodeX = " + startNodeX + " startNodeY = " +startNodeY);
long endNodeX = (((endNode-1)%appDel.globals.NumOfNodesX));
long endNodeY = (((endNode-1)/appDel.globals.NumOfNodesX));
// Console.WriteLine("endNodeX = " + endNodeX + " endNodeY = " +endNodeY);
StartNode = appDel.globals.BattlefieldGraph[startNodeX, startNodeY];
// subtract the vertOrHorzMoveCost value from the StartNode's G so that it's initialized correctly
StartNode.G -= vertOrHorzMoveCost;
// Make the CurrentNode the start node and make the start node's parent node itself...
CurrentNode = StartNode;
appDel.globals.BattlefieldGraph[startNodeX, startNodeY].parentNode = CurrentNode;
openList.Add (CurrentNode);
EndNode = appDel.globals.BattlefieldGraph[endNodeX, endNodeY];
// Clean up the closed nodes from the previous pathfinding calculation
for ( int rows = 0; rows < appDel.globals.NumOfNodesY; rows++ )
{
for ( int cols = 0; cols < appDel.globals.NumOfNodesX; cols++ )
{
appDel.globals.BattlefieldGraph[cols,rows].isClosed = false;
}
}
bool Loop = true;
bool PathFound = false;
while ( Loop )
{
// Calculate F G H for all nodes on openList
foreach ( AStar_Node node in openList )
{
// Calculate G
if ( Library_AstarAlgorithm.ThisNodeIsHorizontalOrVerticalToThatNode(node, node.parentNode) )
{
node.G = node.parentNode.G + vertOrHorzMoveCost;
}
else
{
node.G = node.parentNode.G + diagonalMoveCost;
}
// Calculate H using Diagonal Method
long xDistance2 = Math.Abs(node.X - EndNode.X);
long yDistance2 = Math.Abs(node.Y - EndNode.Y);
if ( xDistance2 > yDistance2 )
node.H = diagonalMoveCost*yDistance2 + vertOrHorzMoveCost*(xDistance2 - yDistance2);
else
node.H = diagonalMoveCost*xDistance2 + vertOrHorzMoveCost*(yDistance2 - xDistance2);
// Calculate H using Manhattan Method
// node.H = (Math.Abs(node.X - EndNode.X))*10 + (Math.Abs(node.Y - EndNode.Y)*10);
// Calculate F by adding G and H
node.F = node.G + node.H;
}
// Find lowest cost. Because I've been sorting the list by F
CurrentNode = openList[0];
// Remove CurrentNode form openList
openList.Remove (CurrentNode);
// Move CurrentNode to closedList
// closedList.Add (CurrentNode);
CurrentNode.isClosed = true;
// Console.Write("Moving to Node ");
// Library_AstarAlgorithm.PrintNode(CurrentNode);
// Stop when you add the target node to the closed list, in which case the path has been found
if ( CurrentNode == EndNode )
{
// Console.WriteLine("Path Found!");
Loop = false;
PathFound = true;
}
List<AStar_Node> adjacentNodesList = Library_AstarAlgorithm.GetAdjacentNodesToThisNode(CurrentNode);
// Console.WriteLine("New List of adjacentNodes.count() = " + adjacentNodesList.Count());
foreach ( AStar_Node node in adjacentNodesList )
{
// If it is in the closed list, ignore it
if ( node.isClosed )
{
// Ignore the node
}
// If it is not walkable and we're not on force move, ignore it
else if ( !node.isWalkable && !forceMove_regardlessOfIsWalkable )
{
// Ignore the node
}
// Otherwise do the following
else
{
// If it isn’t on the open list, add it to the open list. Make the current node the parent of this node. Record the F, G, and H costs of the node.
if ( ! openList.Contains(node) )
{
// Set the parentNode
node.parentNode = CurrentNode;
// Calculate G
if ( Library_AstarAlgorithm.ThisNodeIsHorizontalOrVerticalToThatNode(node, node.parentNode) )
{
node.G = node.parentNode.G + vertOrHorzMoveCost;
}
else
{
node.G = node.parentNode.G + diagonalMoveCost;
}
// Calculate H using Diagonal Method
long xDistance = Math.Abs(node.X - EndNode.X);
long yDistance = Math.Abs(node.Y - EndNode.Y);
if ( xDistance > yDistance )
node.H = diagonalMoveCost*yDistance + vertOrHorzMoveCost*(xDistance - yDistance);
else
node.H = diagonalMoveCost*xDistance + vertOrHorzMoveCost*(yDistance - xDistance);
// Calculate H using Manhattan Method
// node.H = (Math.Abs(node.X - EndNode.X))*10 + (Math.Abs(node.Y - EndNode.Y)*10);
// Calculate F by adding G and H
node.F = node.G + node.H;
// Console.Write("Added to openList: ");
// Library_AstarAlgorithm.PrintNode(node);
// openList.Add (node);
// Console.WriteLine("Adding node with F value " + node.F);
// Add node to the openList in such a way that it's sorted by F. Smallest first, largest last.
long openListCount = openList.Count();
bool didInsert = false;
for ( int i = 0; i < openListCount; i++ )
{
// Insert node at the correct place based on the F values...
if ( openList[i].F >= node.F )
{
// Console.WriteLine("inserting " + node.F + " infront of " + openList[i].F);
openList.Insert(i, node);
didInsert = true;
break;
}
// if ( didInsert )
// Console.WriteLine("You shouldu never see this");
}
if ( !didInsert )
openList.Add (node);
}
// If it is on the open list already, check to see if this path to that node is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the node to the current node, and recalculate the G and F scores of the node. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.
else
{
// Determine the cost of going from node to CurrentNode
long tempCost;
if ( Library_AstarAlgorithm.ThisNodeIsHorizontalOrVerticalToThatNode(node, node.parentNode) )
{
tempCost = vertOrHorzMoveCost;
}
else
{
tempCost = diagonalMoveCost;
}
if ( (tempCost+CurrentNode.G) < node.G )
{
// Update node's parentNode and recalculate FGH scores
node.parentNode = CurrentNode;
// Calculate G
if ( Library_AstarAlgorithm.ThisNodeIsHorizontalOrVerticalToThatNode(node, node.parentNode) )
{
node.G = node.parentNode.G + vertOrHorzMoveCost;
}
else
{
node.G = node.parentNode.G + diagonalMoveCost;
}
// H does NOT need calculated here
// Calculate F by adding G and H
node.F = node.G + node.H;
// Console.WriteLine("F has been recalculated, now we need to resort for this value. It's index is " + openList.IndexOf(node));
int thisIndex = openList.IndexOf(node);
int indexToCheck = thisIndex - 1;
bool switchNeedsPerformed = false;
int indexToSwitch = -99999;
// Resort if need be...
while ( indexToCheck >= 0 )
{
if ( openList[indexToCheck].F > openList[thisIndex].F )
{
switchNeedsPerformed = true;
indexToSwitch = indexToCheck;
}
else
{
if ( switchNeedsPerformed )
{
// Console.WriteLine("making a swap. Putting " + openList[thisIndex].F + " before " + openList[indexToSwitch].F);
AStar_Node tempNode = openList[thisIndex];
openList.Remove(tempNode);
openList.Insert(indexToSwitch, tempNode);
break;
}
}
indexToCheck--;
}
// Console.WriteLine("thisIndex-2 = " + openList[thisIndex-2].F + " thisIndex-1 = " + openList[thisIndex-1].F + " thisIndex = " + openList[thisIndex].F);
// Console.WriteLine("thisIndex = " + openList[thisIndex].F + " thisIndex+1 = " + openList[thisIndex+1].F + " thisIndex+2 = " + openList[thisIndex+2].F);
}
// Console.Write("Already exists in openList: ");
// Library_AstarAlgorithm.PrintNode(node);
}
}
}
// Stop when you fail to find the target node, and the open list is empty. In this case, there is no path
if ( openList.Count() <= 0 )
{
Console.WriteLine("Path Not Possible. OpenList is empty!");
// There is not path, exit loop
// Loop = false;
return null;
}
// Console.WriteLine("Looping through with openlist.coutn = " + openList.Count());
}
// **** OPTIMIZATION **** //
// Here is where I optimize the path that we're returning.
// If I make up the path based on a smaller number of nodes, there will be less animations that have to start and stop. Doing so will reduce the CPU usage
List<AStar_Node> Path = new List<AStar_Node>();
if ( PathFound )
{
CurrentNode = EndNode;
try
{
while ( CurrentNode != StartNode )
{
Path.Add(CurrentNode);
// Reset the isClosed variable to false;
CurrentNode = CurrentNode.parentNode;
}
Path.Reverse();
}
catch(Exception e)
{
Console.WriteLine("Warning Inside AStarAlgorithm");
Console.WriteLine(e.Message);
Console.WriteLine(e.StackTrace);
return null;
}
}
else
{
Console.WriteLine("No Path possible. Reached Blockade!");
return null;
}
Console.WriteLine("AStarAlrogirthm Duration in ms = " + DateTime.Now.Subtract(before).TotalMilliseconds);
return Path;
}
