Sign in to follow this  
Narf the Mouse

Critique my generic A* pathfinding algorithm

Recommended Posts

Narf the Mouse    322
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.
        /// <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;
        }


[Edited by - Narf the Mouse on April 1, 2010 8:16:42 AM]

Share this post


Link to post
Share on other sites
Narf the Mouse    322
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.

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

Share this post


Link to post
Share on other sites
alexjc    457
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.

Share this post


Link to post
Share on other sites
Narf the Mouse    322
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();

Share this post


Link to post
Share on other sites
nullsquared    126
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)
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.

Share this post


Link to post
Share on other sites
Narf the Mouse    322
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.

Share this post


Link to post
Share on other sites
nullsquared    126
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.

Share this post


Link to post
Share on other sites
nullsquared    126
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.

Share this post


Link to post
Share on other sites
Narf the Mouse    322
Quote:
Original post by nullsquared
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.

...Guess I'll have to resurrect AStarNode.cs from the exclusion bin.

Share this post


Link to post
Share on other sites
Narf the Mouse    322
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:

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

Share this post


Link to post
Share on other sites
nullsquared    126
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.

Share this post


Link to post
Share on other sites
nullsquared    126
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

...


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 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.

Share this post


Link to post
Share on other sites
Narf the Mouse    322
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.
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. :)

Share this post


Link to post
Share on other sites
Narf the Mouse    322
It will now return the best path it can get, even if it doesn't find a complete path.

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


Share this post


Link to post
Share on other sites
nullsquared    126
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.)?

Share this post


Link to post
Share on other sites
Narf the Mouse    322
True; but the full version will optionally output all its data, so if they don't like the default...
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.

Share this post


Link to post
Share on other sites
nullsquared    126
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.

Share this post


Link to post
Share on other sites
Narf the Mouse    322
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?

Share this post


Link to post
Share on other sites
nullsquared    126
Quote:
Original post by Narf the Mouse
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?


Hm, yeah, I can't find such a container either. I'm coming from C++ (multiset) and Java (PriorityQueue) so I didn't know C# didn't have a good equivalent.

This looks like a good piece of code for a C# multiset: http://www.ikriv.com/en/prog/code/Set/Set.html

Share this post


Link to post
Share on other sites
Narf the Mouse    322
Thanks - Yeah, my brain is exhausted, but I can't sleep, so...

In any case, I ran it in the following testbed and got this result:
Loops: 1000, Seconds: 86.5001775, Loops per Second: 11.5606699188565

Seems kinda slow to me.

Testbed code:

static System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
static Random random = new Random();
static void Main(string[] args)
{
stopwatch.Start();

Int32 t = 0,
count = 1000;



Int32 x, y,
sizeX = 20, sizeY = 20;
Boolean[,] pathabilityMap = new Boolean[sizeX, sizeY];
Double seconds = 0.0;

for (t = 0; t < count; ++t)
{
for (y = 0; y < sizeY; ++y)
{
for (x = 0; x < sizeX; ++x)
{
pathabilityMap[x, y] = random.NextDouble() >= 0.4;
}
}

AIExtensions.AStarNS.GraphMap2D graph = new AIExtensions.AStarNS.GraphMap2D(passabilityMap: pathabilityMap);
graph.SetStart(new NetExtensions.VariablesNS.Point(0, 0));
graph.SetGoal(new NetExtensions.VariablesNS.Point(19, 19));
AIExtensions.AStarNS.AStar.AStarData data = new AIExtensions.AStarNS.AStar.AStarData(graph: graph);


Double startTime = stopwatch.Elapsed.TotalSeconds;
AIExtensions.AStarNS.AStar.Pathfind(data: ref data);
seconds += stopwatch.Elapsed.TotalSeconds - startTime;
}


Console.WriteLine(Handy.LoopString(count, seconds));


Console.ReadKey(true);
}

Share this post


Link to post
Share on other sites
Narf the Mouse    322
Quote:
Original post by nullsquared
Don't time the whole thing, just time how long the path-find call takes.

Compare it to your original path-find call.

Yeah...That's exactly what I'm doing.

Will do that.

[Edited by - Narf the Mouse on April 1, 2010 10:25:57 PM]

Share this post


Link to post
Share on other sites
nullsquared    126
Quote:
Original post by Narf the Mouse
Quote:
Original post by nullsquared
Don't time the whole thing, just time how long the path-find call takes.

Compare it to your original path-find call.

Yeah...That's exactly what I'm doing.

Woops, sorry, didn't notice you explicitly subtract the start time.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this