Critique my generic A* pathfinding algorithm
April 01, 2010 09:43 AM
I've optimized it accordingly and Woot!, it does work. Now, I just have to get SlimTune connected...
Now open: MouseProduced Games
April 01, 2010 09:49 AM
There's only one problem, now: It doesn't return a "close enough" path if it can't find a complete path. How do I fix it so it will do that?
Current code:
Current code:
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. AStarNode S = graph.Start; // Make a list of open nodes. List<AStarNode> open = new List<AStarNode>(); // SortedSet<AStarNode> open = new SortedSet<AStarNode>( // Make a list of closed nodes. // List<AStarNode> closed = new List<AStarNode>(); HashSet<AStarNode> closed = new HashSet<AStarNode>(); // Add the Start node to the Open list. open.Add(item: S); // A temporary slot for the Best node. AStarNode 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; }); // Get the best node in the open list and remove it from // that list. do { // 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) { // Get the best path, anyway. closed.OrderBy<AStarNode, Double>(a => { return a.F + a.H; }); path = closed.ElementAt(0).Path(); return false; } B = open[0]; open.RemoveAt(0); } while (closed.Contains(B)); // 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 (AStarNode C in B.Links) { // 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); // Get the best path, anyway. closed.OrderBy<AStarNode, Double>(a => { return a.F + a.H; }); path = closed.ElementAt(0).Path(); // If the While loop ends, we have no more Open nodes to check, so failure. return false; } }
Now open: MouseProduced Games
128
April 01, 2010 10:18 AM
There isn't really any direct way of doing this. You can't just use the last closed node or anything since the last closed node may as well be the furthest node from the target.
One possibility is to search the closed set for the node with the lowest heuristic value ("closest" to the target), and return the path to that.
One possibility is to search the closed set for the node with the lowest heuristic value ("closest" to the target), and return the path to that.
128
April 01, 2010 10:22 AM
Also, your loop is needlessly complicated. Instead of nesting a do {} while () loop inside the "main" loop, just do something like:
Also, no need for a do {} while () loop for your main loop. Your open set will always start with the starting node, so you can just do:
Another thing is, I suggest closing the open node right after you pop it off the open set and verify that it isn't closed. Like this:
Instead of doing it at the end. Personally, this makes the logic flow better: "Get the best node off the open set, and if it's not already closed, then close it and process it." Though this is just a personal preference, if you don't like it then it's up to you.
...B = open[0];open.RemoveAt(0);if (closed.Contains(B)) continue; // already closed, go for next one...Also, no need for a do {} while () loop for your main loop. Your open set will always start with the starting node, so you can just do:
while (open.Count > 0) // guaranteed to execute at least once due to starting node{ ...}Another thing is, I suggest closing the open node right after you pop it off the open set and verify that it isn't closed. Like this:
B = open[0];open.RemoveAt(0);if (closed.Contains(B)) continue;closed.Add(B); // immediately close itInstead of doing it at the end. Personally, this makes the logic flow better: "Get the best node off the open set, and if it's not already closed, then close it and process it." Though this is just a personal preference, if you don't like it then it's up to you.
April 01, 2010 10:45 AM
I think what I have (Which is pretty much what you said, only going by F + H (Which seems to work better than F alone) will work, if I filer out everything that has a Null parent. Possibly, everything that doesn't have a path back to the start.
Going by just Heuristic doesn't work.
Ok, I'm going to need a bit of explanation here.
That would work, but it would also sort them again, which isn't needed. The do-loop contains only what is needed.
That makes sense. Done.
Also and done. :)
Thanks. :)
Going by just Heuristic doesn't work.
Ok, I'm going to need a bit of explanation here.
Quote: Original post by nullsquared
Also, your loop is needlessly complicated. Instead of nesting a do {} while () loop inside the "main" loop, just do something like:...B = open[0];open.RemoveAt(0);if (closed.Contains(B)) continue; // already closed, go for next one...
That would work, but it would also sort them again, which isn't needed. The do-loop contains only what is needed.
Quote:
Also, no need for a do {} while () loop for your main loop. Your open set will always start with the starting node, so you can just do:while (open.Count > 0) // guaranteed to execute at least once due to starting node{ ...}
That makes sense. Done.
Quote:
Another thing is, I suggest closing the open node right after you pop it off the open set and verify that it isn't closed. Like this:B = open[0];open.RemoveAt(0);if (closed.Contains(B)) continue;closed.Add(B); // immediately close it
Instead of doing it at the end. Personally, this makes the logic flow better: "Get the best node off the open set, and if it's not already closed, then close it and process it." Though this is just a personal preference, if you don't like it then it's up to you.
Also and done. :)
Thanks. :)
Now open: MouseProduced Games
April 01, 2010 11:31 AM
It will now return the best path it can get, even if it doesn't find a complete path.
Source code:
Source code:
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, out List<GraphNode> path) { // Make a path of data. path = new List<GraphNode>(); // Get the graph's Start node. AStarNode S = graph.Start; // Make a list of open nodes. List<AStarNode> open = new List<AStarNode>(); // SortedSet<AStarNode> open = new SortedSet<AStarNode>( // Make a list of closed nodes. // List<AStarNode> closed = new List<AStarNode>(); HashSet<AStarNode> closed = new HashSet<AStarNode>(); // Add the Start node to the Open list. open.Add(item: S); // A temporary slot for the Best node. AStarNode 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>(); while (open.Count > 0) { // 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; }); // Get the best node in the open list and remove it from // that list. do { // 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) { // Get the best path, anyway. closed.RemoveWhere(a => { return Object.Equals(a.Parent, null); }); // closed = (HashSet<AStarNode>)closed.OrderBy<AStarNode, Double>(a => { return a.F; }).AsEnumerable(); if (closed.Count > 0) path = closed.OrderBy<AStarNode, Double>(a => { return a.F + a.H; }).ElementAt(0).Path(); return false; } B = open[0]; open.RemoveAt(0); } while (closed.Contains(B)); closed.Add(B); // 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 (AStarNode C in B.Links) { // Make it's parent B, C.Parent = B; // Calculate it's values C.Recalculate(); // and add it to the Open list. open.Add(C); } // Continue until we have no more Open nodes. } // Get the best path, anyway. closed.RemoveWhere(a => { return Object.Equals(a.Parent, null); }); // closed = ; if (closed.Count > 0) path = closed.OrderBy<AStarNode, Double>(a => { return a.F + a.H; }).ElementAt(0).Path(); // If the While loop ends, we have no more Open nodes to check, so failure. return false; } }
Now open: MouseProduced Games
128
April 01, 2010 12:25 PM
Quote: Original post by Narf the Mouse
I think what I have (Which is pretty much what you said, only going by F + H (Which seems to work better than F alone) will work, if I filer out everything that has a Null parent. Possibly, everything that doesn't have a path back to the start.
Going by just Heuristic doesn't work.
Hm. Well, it depends on what you mean by "best" path when there is no full path to the target. By using the node with the smallest F score, you get the "best node so far" path. Of course, unless you know that there will be an opening near this node that will allow you to get to the target, then this may or may not be the actual best path. By using the node with the smallest H score, you get the "closest node so far" path. This path will get you physically close to the target, but once again, depending on where an opening comes up in the future, it may or may not be the actual best path.
Quote:
That would work, but it would also sort them again, which isn't needed. The do-loop contains only what is needed.
Oh yeah, missed that part. Why are you sorting the list anyway, that's incredibly slow compared to just using a sorted container (a tree-based set, a heap, a priority queue, etc.)?
April 01, 2010 01:33 PM
True; but the full version will optionally output all its data, so if they don't like the default...
Nope - I've researched it in Reflector. At greater than, I think, 50 items, List uses a very, very fast Quick Sort.
Quote: Original post by nullsquared
Oh yeah, missed that part. Why are you sorting the list anyway, that's incredibly slow compared to just using a sorted container (a tree-based set, a heap, a priority queue, etc.)?
Nope - I've researched it in Reflector. At greater than, I think, 50 items, List uses a very, very fast Quick Sort.
Now open: MouseProduced Games
128
April 01, 2010 02:24 PM
Quote: Original post by Narf the Mouse
Nope - I've researched it in Reflector. At greater than, I think, 50 items, List uses a very, very fast Quick Sort.
Quicksort is O(nlogn) on random data. On data that is mostly sorted (such as your open list, since you only add one node at a time), quicksort is O(n^2). This is incredibly slow compared to the possible alternatives.
One alternative is to do a binary search in O(logn) time to find the insertion point for the new node, and then insert it into the already-ordered list. The problem here is that inserting into an array-based list is slow. You can insert into a linked-list in O(1), but then you can't binary-search it efficiently.
The better alternative is to simply use a sorted contained, such as a priority queue, a heap, or a tree-based set (of which some may be internally implemented as a heap anyways). These containers are inherently sorted, and are hands-down the fastest way to retrieve the best node from the open set. Of these three, using the heap based approach is the fastest, as both insertion and deletion are O(logn) or better.
April 01, 2010 03:12 PM
Unfortunately, the only one I found in .Net 4.0 is SortedSet, which does almost what I need. The problem is, it doesn't allow multiple inserts of the same data - Or rather, it simply doesn't insert them and returns false on an add.
I've thought it before and I'll think it again - .Net is a leetle too light on self-sorting collections.
Looks like it's time to build one...Unless someone's found one I missed?
I've thought it before and I'll think it again - .Net is a leetle too light on self-sorting collections.
Looks like it's time to build one...Unless someone's found one I missed?
Now open: MouseProduced Games
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
