# A Star pathfinding algorithm, multiple node set optimization

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;
}

• even if you use all those coordinates as A* nodes there won't be a noticeable performance cost... 135*185 < 150*200 = 30000 ~ 0.002s computation time. Compare that to 0.0167s that you have to render each frame. Also note that Usually it won't even take 0.1ms, I've computed the worst case time. – Ali1S232 Sep 19 '14 at 21:17
• I've added a video showing the duration in ms during game play. I've also posted my C# code. My calculation times are drastically longer than what you're describing(46ms up to 127ms). But do note that I'm using a mobile device, an iOS iPad 2. – LampShade Sep 21 '14 at 13:25

## 2 Answers

What you're really looking for are navigation meshes:

These meshes will conform to the walkable areas in your game. You can make the nodes as small as you like. In this way, you can have far fewer nodes for your A* algorithm to work on. You can still have smaller nodes if you like for fine detail pathing, or you can use something like steering to get between nodes.

If you'd still like to do your idea of a larger grid and a smaller grid, that's fine too. The larger nodes would just be made up of multiple smaller walkable nodes. There's no reason to make the larger nodes include non-walkable areas. I think what you'd eventually end up with is something like the navigation mesh above.

• Well I'll add a piece of information that I left out. My entire environment is destructible. So anything, a wall, car, barrel, etc could be destroyed changing several non-walkable nodes to walkable nodes. That's why I have the entire screen filled with nodes. With that being said, does a mesh apply here? – LampShade Sep 19 '14 at 15:30
• @LampShade Yes. You can rebuild the navigation mesh whenever needed. – MichaelHouse Sep 19 '14 at 16:00
• I have to say, this is pretty awesome. After reading this I'm thinking about path finding a lot differently. Thanks for the insite and references. – LampShade Sep 19 '14 at 16:13
• Yep, they're pretty neat. You have a lot of work ahead of you for generating these navigation meshes though. Make sure you're putting your time into something that's needed. Profile your pathfinding to ensure it's actually slow enough to warrant putting a lot of time into optimizing it. Have fun! – MichaelHouse Sep 19 '14 at 16:31
• I'm sure after my fascination with this stuff wares off I'll come to the realization that "If it ain't broke, don't fix it" especially since this is a mobile 2D game and not some big AAA studio game. But I'm going to keep it in mind going forward for sure. I made this game engine myself and probably won't do that my all other future games... – LampShade Sep 21 '14 at 13:28

This article: http://www.ai-blog.net/archives/000152.html gives a good overview of Navigation meshes and discusses dealing with realtime modification of the mesh due to environmental changes at least a little bit...

The basic idea is that you mesh out all the potentially walkable spaces by default, then either mod a section of the mesh, or deal with moving around obstacles using a little ray casting to find the clear path...

• Great article. So many awesome examples. I'm going to spend some time thinking about programmatically laying down the mesh on my battlefields. – LampShade Sep 19 '14 at 16:16
• Destructable walls are easy enough if you create nodes that match the base of the wall sections, and have them marked as "blocked" until the wall is destroyed... if your destruction of the wall is not quite so deterministic, its still easy to split one long quad marked as blocked in to 3 quads with one marked as passable based on the edges of the opening created during destruction. – Ascendion Sep 19 '14 at 18:48
• And with meshes you can create nodes wherever you want rather than being locked to a grid, right? So the node placement will be dependent on the objects on the map. – LampShade Sep 21 '14 at 13:30
• Exactly -- and you can attach properties to nodes that tell things about what can and cannot traverse a node, or if an entity will suffer a motion penalty of some sort for crossing the node, all sorts of possibilities. For instance -- tanks don't do well in swamps, If the slope is too steep, a player may slide down rather than being able to walk across the slope, etc etc... there are literally 1000s of special cases you could created if desired to make the game play more interesting/realistic. – Ascendion Sep 21 '14 at 20:51