/// <summary>
/// Pathfinds on any mappable graph.
/// </summary>
/// <typeparam name="T">The type of data the graph contains.</typeparam>
/// <param name="graph">An abstract Graph class.</param>
/// <param name="start">The start data.</param>
/// <param name="destination">The end data.</param>
/// <param name="path">The output path.</param>
/// <returns>Returns true if a path is found.</returns>
public static Boolean Pathfind<T>(Graph graph, T start, T destination, out List<T> path)
{
// Make a path of data.
path = new List<T>();
// Set the destination.
graph.SetDestination(destination);
// Get the Start graph node. It will be the one with
// the same data as the start position data.
GraphNode S = graph.Nodes.Find(match: a => { if (a.Data == start) return true; else return false; });
// Make a list of open nodes.
List<GraphNode> open = new List<GraphNode>();
// Make a list of closed nodes.
List<GraphNode> closed = new List<GraphNode>();
// Add the Start node to the Open list.
open.Add(item: S);
// A temporary slot for the Best node.
GraphNode B;
// I prefer my own Tuple class, as the items are not read-only and
// it'll fill using Default(T) if there's no creation data.
// This is for temporary G-, H- and F-values (Distance to here,
// Estimated (Heurustic) Distance to there and Total Estimated Distance).
NetExtensions.VariablesNS.Tuple2<Double, Double, Double> tempValues =
new NetExtensions.VariablesNS.Tuple2<Double, Double, Double>();
do
{
// Sort from lowest F-value (Estimated distance to solution)
// to highest F-value.
open.Sort((a, b) => { if (a.F < b.F) return -1; else if (a.F > b.F)return 1; else return 0; });
// If there's nothing left in the open list, we've checked
// everywhere and there's no solution. Exit, returning false.
if (open.Count == 0)
return false;
// Get the best node in the open list and remove it from
// that list.
B = open[0];
open.RemoveAt(0);
// If it's the destination,
if (B.Data == destination)
{
// Get the path to this node and return true.
path = B.Path<T>();
return true;
}
// Parse through all of the graph nodes linked to B.
foreach (GraphNode C in B.Links)
{
// If the Open or Closed lists contain the Current node,
if (open.Contains(C) || closed.Contains(C))
{
// we may have found a new, better path to that node.
// So, we recalculate and use tempValues to store the resulting
// G, H and F values.
C.Recalculate(withParent: B, tempValues: ref tempValues);
// If this is a better path,
if (tempValues.Item3 < C.F)
{
// C's new parent is B,
C.Parent = B;
// and it should recalculate it's values.
C.Recalculate();
}
}
// If it's a totally new graph node,
else
{
// Make it's parent B,
C.Parent = B;
// Calculate it's values
C.Recalculate();
// and add it to the Open list.
open.Add(C);
}
}
// Add B to the Closed list. Remember, we removed it from the
// Open list.
closed.Add(B);
// Continue until we have no more Open nodes.
} while (open.Count > 0);
// If the While loop ends, we have no more Open nodes to check, so failure.
return false;
}
Critique my generic A* pathfinding algorithm
Author
Seeing as I'm working on a library, I've decided to make a robust A* pathfinding section. Right now, I have a generic A* Pathfind that, without a single clue that the graph it's traversing is a 2D Passable/Impassable randomized map, correctly finds the end result.
I've got a graphical display that shows the F, G and H values for every square, colours it green or red based on passability and shows both the correct path in yellow (If any) and all paths it tried in blue.
The current version works perfectly in all the tests I've tried; there's no problem there. However, it could possibly be more robust, efficient and maybe sane. So I'm looking for a check on that, rather than a correctness check (Although, of course, if you see something wrong, feel free to point it out)
Thanks and feel free to research it for your own needs.
[Edited by - Narf the Mouse on April 1, 2010 8:16:42 AM]
Author
I've changed it so that the graph stores the start and goal nodes; among other things, this will result in greater flexibility - And, as you don't have to designate a <T> value, it's more generic, as well.
A facade function ensures that you may still designate the start and goal data in the Pathfind function.
No loss of functionality was noticed in the tests.
A facade function ensures that you may still designate the start and goal data in the Pathfind function.
No loss of functionality was noticed in the tests.
public static class AStar { /// <summary> /// Pathfinds on any mappable graph. /// </summary> /// <typeparam name="T">The type of data the graph contains.</typeparam> /// <param name="graph">An abstract Graph class.</param> /// <param name="start">The start data.</param> /// <param name="goal">The end data.</param> /// <param name="path">The output path.</param> /// <returns>Returns true if a path is found.</returns> public static Boolean Pathfind(Graph graph, dynamic start, dynamic goal, out List<GraphNode> path) { graph.SetStart(start); graph.SetGoal(goal); return Pathfind(graph, out path); } /// <summary> /// Pathfinds on any mappable graph. /// </summary> /// <typeparam name="T">The type of data the graph contains.</typeparam> /// <param name="graph">An abstract Graph class.</param> /// <param name="path">The output path.</param> /// <returns>Returns true if a path is found.</returns> public static Boolean Pathfind(Graph graph, /* T start, T destination, */ out List<GraphNode> path) { // Make a path of data. path = new List<GraphNode>(); // Get the graph's Start node. GraphNode S = graph.Start; // Make a list of open nodes. List<GraphNode> open = new List<GraphNode>(); // Make a list of closed nodes. List<GraphNode> closed = new List<GraphNode>(); // Add the Start node to the Open list. open.Add(item: S); // A temporary slot for the Best node. GraphNode B; // I prefer my own Tuple class, as the items are not read-only and // it'll fill using Default(T) if there's no creation data. // This is for temporary G-, H- and F-values (Distance to here, // Estimated (Heurustic) Distance to there and Total Estimated Distance). NetExtensions.VariablesNS.Tuple2<Double, Double, Double> tempValues = new NetExtensions.VariablesNS.Tuple2<Double, Double, Double>(); do { // Sort from lowest F-value (Estimated distance to solution) // to highest F-value. open.Sort((a, b) => { if (a.F < b.F) return -1; else if (a.F > b.F)return 1; else return 0; }); // If there's nothing left in the open list, we've checked // everywhere and there's no solution. Exit, returning false. if (open.Count == 0) return false; // Get the best node in the open list and remove it from // that list. B = open[0]; open.RemoveAt(0); // If it's the destination, if (B.Data == graph.Goal.Data) { // Get the path to this node and return true. path = B.Path(); return true; } // Parse through all of the graph nodes linked to B. foreach (GraphNode C in B.Links) { // If the Open or Closed lists contain the Current node, if (open.Contains(C) || closed.Contains(C)) { // we may have found a new, better path to that node. // So, we recalculate and use tempValues to store the resulting // G, H and F values. C.Recalculate(withParent: B, tempValues: ref tempValues); // If this is a better path, if (tempValues.Item3 < C.F) { // C's new parent is B, C.Parent = B; // and it should recalculate it's values. C.Recalculate(); } } // If it's a totally new graph node, else { // Make it's parent B, C.Parent = B; // Calculate it's values C.Recalculate(); // and add it to the Open list. open.Add(C); } } // Add B to the Closed list. Remember, we removed it from the // Open list. closed.Add(B); // Continue until we have no more Open nodes. } while (open.Count > 0); // If the While loop ends, we have no more Open nodes to check, so failure. return false; } }
I'd personally change your implementation to use a Step() method which you can use for single-stepping the pathfinder and getting better control over the amount of time spent on large pathfinds. This will also help break up your code a bit, as the function length is a bit longer than it should be IMHO.
Author
Quote:Original post by alexjc
I'd personally change your implementation to use a Step() method which you can use for single-stepping the pathfinder and getting better control over the amount of time spent on large pathfinds. This will also help break up your code a bit, as the function length is a bit longer than it should be IMHO.
...I was thinking of implementing it Anytime when I started, but I forgot - You jogged my memory on that, thanks.
Plus, I could watch it search, which, while not strictly necessary while it's working, would be kinda neat.
As an addition, if it can't find a path, it'll return the best path, so your units can march back and forth along the shoreline, waiting for a ship. :D
I added the following to both failure condition checks.
// Get the best path, anyway. closed.Sort( (a, b) => { // Sort first by F-value, if (a.F < b.F) return -1; else if (a.F > b.F) return 1; else // then, if that fails, by H-value. if (a.H < b.H) return -1; else if (a.H > b.H) return 1; else return 0; } ); path = closed[0].Path();
Several things to note:
1) Don't use lists. Use a hash map for the closed set for O(1) time closing nodes and check if they are closed; use a (multi)set, priority queue, heap, or some other type of sorted container for the open set so that you don't have to manually sort it every iteration
2)
You only want to check the open set here, not the closed set. The closed set is closed because all of the best paths have been exhausted, therefore there cannot be a better path.
3) An optimization to #2 is to check every node if it is closed right after you pop it off the open set. If it's closed, just continue onto the next best node, and if it's not closed, then close it, and continue to use it as the best candidate. This way, you don't have to check if the open set already has the current node; you can simply add the current node to the open set every time, and if there's a better-scored candidate, then it will be processed & closed before this one.
1) Don't use lists. Use a hash map for the closed set for O(1) time closing nodes and check if they are closed; use a (multi)set, priority queue, heap, or some other type of sorted container for the open set so that you don't have to manually sort it every iteration
2)
Quote:// If the Open or Closed lists contain the Current node,if (open.Contains(C) || closed.Contains(C))
You only want to check the open set here, not the closed set. The closed set is closed because all of the best paths have been exhausted, therefore there cannot be a better path.
3) An optimization to #2 is to check every node if it is closed right after you pop it off the open set. If it's closed, just continue onto the next best node, and if it's not closed, then close it, and continue to use it as the best candidate. This way, you don't have to check if the open set already has the current node; you can simply add the current node to the open set every time, and if there's a better-scored candidate, then it will be processed & closed before this one.
Author
Quote:Original post by nullsquared
Several things to note:
1) Don't use lists. Use a hash map for the closed set for O(1) time closing nodes and check if they are closed; use a (multi)set, priority queue, heap, or some other type of sorted container for the open set so that you don't have to manually sort it every iteration
Good advice there; I'll check it out.
Quote:
2)Quote:// If the Open or Closed lists contain the Current node,if (open.Contains(C) || closed.Contains(C))
You only want to check the open set here, not the closed set. The closed set is closed because all of the best paths have been exhausted, therefore there cannot be a better path.
I would strongly disagree; the Closed list doesn't designate which paths ended in failure, but which nodes have already been parsed. Without checking both, the path doesn't optimize or doesn't optimize as well.
Quote:
3) An optimization to #2 is to check every node if it is closed right after you pop it off the open set. If it's closed, just continue onto the next best node, and if it's not closed, then close it, and continue to use it as the best candidate. This way, you don't have to check if the open set already has the current node; you can simply add the current node to the open set every time, and if there's a better-scored candidate, then it will be processed & closed before this one.
That, also, doesn't make sense.
Quote:Original post by Narf the Mouse
I would strongly disagree; the Closed list doesn't designate which paths ended in failure, but which nodes have already been parsed. Without checking both, the path doesn't optimize or doesn't optimize as well.
The closed list is the set of all nodes so far that you have the best path to. Every time you pop the best candidate off of the open set, you have the best path to that node. Therefore, by closing it, you are saying "I have found the best path to this node, and there is no better way of getting to it."
If you don't believe me, feel free to check any source on A* or Dijkstra path finding.
Quote:
That, also, doesn't make sense.
When you grab a new candidate, you're supposed to check if the candidate is already in the open list. If it is, and it has a worse score than the new version, then you replace it with the new version. If it has a better score, the you disregard the new version.
Instead of doing this expensive search & replace, you simply add the new candidate to the open set either way. If it has a worse score, it will come after the previous candidate, and by the time you get to it, it will be closed. If it has a better score, it will come before the previous candidate and then be closed, therefore invalidating the previous candidate. This is much quicker than a search & replace in the middle of the loop.
Author
...Ok, that does make sense, thanks. Except, wouldn't you be adding nodes multiple times?
Quote:Original post by Narf the Mouse
...Ok, that does make sense, thanks. Except, wouldn't you be adding nodes multiple times?
Yeah, you would. That may or may not be a problem based on your node setup; for example, my path finding nodes are completely separate from the actual graph nodes, so two nodes may differ by only their score, not necessarily by their corresponding graph node. Other than that, as long as you keep your open set sorted (priority queue/(multi)set/heap/etc.), things will Just Work if you check if a node is already closed right after popping it off the open set.
Author
Quote:Original post by nullsquaredQuote:Original post by Narf the Mouse
...Ok, that does make sense, thanks. Except, wouldn't you be adding nodes multiple times?
Yeah, you would. That may or may not be a problem based on your node setup; for example, my path finding nodes are completely separate from the actual graph nodes, so two nodes may differ by only their score, not necessarily by their corresponding graph node. Other than that, as long as you keep your open set sorted (priority queue/(multi)set/heap/etc.), things will Just Work if you check if a node is already closed right after popping it off the open set.
...Guess I'll have to resurrect AStarNode.cs from the exclusion bin.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
