Looking for speedups for A* search

Question

I've got the following working A* code in C#:

static bool AStar(
    IGraphNode start,
    Func<IGraphNode, bool> check,
    out List<IGraphNode> path)
{
    // Closed list. Hashset because O(1).
    var closed =
        new HashSet<IGraphNode>();
    // Binary heap which accepts multiple equivalent items.
    var frontier =
        new MultiHeap<IGraphNode>(
            (a, b) =>
            { return Math.Sign(a.TotalDistance - b.TotalDistance); }
            );
    // Some way to know how many multiple equivalent items there are.
    var references =
        new Dictionary<IGraphNode, int>();
    // Some way to know which parent a graph node has.
    var parents =
        new Dictionary<IGraphNode, IGraphNode>();

    // One new graph node in the frontier,
    frontier.Insert(start);
    // Count the reference.
    references[start] = 1;

    IGraphNode current = start;

    do
    {

        do
        {
            frontier.Get(out current);
            // If it's in the closed list or
            // there's other instances of it in the frontier,
            // and there's still nodes left in the frontier,
            // then that's not the best node.
        } while (
            (closed.Contains(current) ||
            (--references[current]) > 0) &&
            frontier.Count > 0
            );

        // If we have run out of options,
        if (closed.Contains(current) && frontier.Count == 0)
        {
            // then there's no path.
            path = null;
            return false;
        }


        closed.Add(current);
        foreach (var edge in current.Edges)
        {
            // If there's a chance of a better path
            // to this node,
            if (!closed.Contains(edge.End))
            {
                int count;
                // If the frontier doesn't contain this node,
                if (!references.TryGetValue(edge.End, out count) ||
                    count == 0)
                {
                    // Initialize it and insert it.
                    edge.End.PathDistance =
                        current.PathDistance + edge.Distance;
                    edge.End.EstimatedDistance = CalcDistance(edge.End);
                    parents[edge.End] = current;
                    frontier.Insert(edge.End);
                    references[edge.End] = 1;
                }
                else
                {
                    // If this path is better than the existing path,
                    if (current.PathDistance + edge.Distance <
                        edge.End.PathDistance)
                    {
                        // Use this path.
                        edge.End.PathDistance = current.PathDistance +
                            edge.Distance;
                        parents[edge.End] = current;
                        frontier.Insert(edge.End);
                        // Keeping track of multiples equivalent items.
                        ++references[edge.End];
                    }
                }
            }
        }
    } while (!check(current) && frontier.Count > 0);

    if (check(current))
    {
        path = new List<IGraphNode>();
        path.Add(current);
        while (current.PathDistance != 0)
        {
            current = parents[current];
            path.Add(current);
        }
        path.Reverse();
        return true;
    }

    // Yep, no path.
    path = null;
    return false;
}

How do I make it faster? No code samples, please; that's a challenge I've set myself.

Edit: To clarify, I'm looking for any advice, suggestions, links, etc. that apply to A* in general. The code is just an example. I asked for no code samples because they make it too easy to implement the technique(s) being described.

Thanks.

Answer 1

Have you looked at this page or this page yet? They have plenty of helpful optimization tips as well as some great information on A* in general.