A Fast, General A* in C# (Part 1)

As I work more on moving things into the Vapor .NET Client Library, sometimes I add functionality that I feel needs to be covered in a place which is more expressive than the XML comment system. For that, I turn here. I will be talking about Vapor.Graph.Searcher.AStar (snapshot as I write this).

Before I present the algorithm itself, I would like to mention two of the data structures that I use from the library which are not specific to A*. The first is the HashedSet<T>, which is almost identical in behavior to .NET's HashSet<T>, except that it is available on the .NET Compact Framework and does not allow for removing individual items, just clearing the whole set. I also use a structure called an OrderedQueue<T>, which is similar to a priority queue, except that the items themselves provide the ordering (through an IComparer<T>). It is backed by a min-heap, which means it is quite ideally suited for use in this algorithm.

Well, I have delayed quite long enough. Without further ado:

public static Path<TNode, TTransition> AStar<TNode, TTransition, TScore, TAdder>
   (
    TNode startNode,
    TNode goalNode,
    [NotNull] CostFunction<TNode, TScore> travelCost,
    [NotNull] HeuristicFunction<TNode, TScore> estimateCost,
    [NotNull] GenerateFunction<TNode, TTransition> nextGenerator,
    [NotNull] TAdder scoreAdder,
    [NotNull] IEqualityComparer<TNode> nodeEqualityComparer,
    [NotNull] IComparer<TScore> scoreComparer
   )
   where TAdder : IAdder<TScore>
  {
   var searched = new HashedSet<TNode>(nodeEqualityComparer);
   var toSearch = new OrderedQueue<AStarSearchNode<TNode, TTransition, TScore>>
                      (
                          new AStarSearchNodeComparer<TNode, TTransition, TScore, TScoreComparer>(scoreComparer)
                      );
   {
    var initCost = estimateCost(startNode, goalNode);
    toSearch.Enqueue(AStarSearchNode.Create
     (
      Step.Create(startNode, default(TTransition)),
      default(TScore),
      initCost,
      initCost,
      null
     ));
   }

   while (!toSearch.IsEmpty)
   {
    var current = toSearch.Dequeue();

    // skip if we've already searched this
    if (searched.Contains(current.Node))
     continue;

    // check if this is the solution
    if (nodeEqualityComparer.Equals(current.Node, goalNode))
     return BuildPath(current);

    searched.Add(current.Node);

    foreach (var next in nextGenerator(current.Node))
    {
     var costForNext = scoreAdder.Add(current.CostToHere, travelCost(current.Node, next.Result));
     var heuristic = estimateCost(next.Result, goalNode);
     var estimated = scoreAdder.Add(costForNext, heuristic);

     var nextNode = AStarSearchNode.Create
      (
       next,
       costForNext,
       estimated,
       heuristic,
       current
      );

     toSearch.Enqueue(nextNode);
    }
   }

   return null;
  }

What is with this insane amount of generality?

In general, this is a pretty good demonstration of just how general the type system of C#/.NET will allow you to go. Although that does not address the underlying question of: WHY? This started as a quick way to search for best paths on a 2D grid and worked quite nicely. Soon after, I needed to use a graph search algorithm for image unification. Instead of writing another implementation of A* (or any other graph-search algorithm), I decided to generalize the one I currently had. The ultimate reason why I want this to be as general as possible is because it is way easy to specialize a function for ease-of-use with wrapper functions, but almost impossible to generalize.

I do have a reason for every single type parameter!

TNode and TTransition
These are unavoidable type parameters. TNode is the type of nodes we are searching on and over, while TTransition is some transition which takes us from one TNode to another. There is no way to know what domain-specific types a user would want here.

TScore
This is the type of score value used in all cost calculations: it is the return type of a CostFunction<TNode, TScore> and HeuristicFunction<TNode, TScore>. Here's where my judgement gets questionable. Why would one need to do this? Aren't all scores just ints? Somebody might have ready that last statement an thought: What about float/double/long/MyOwnScoreType? The difference in effort of implementing one type of score and all types of scores (including those not yet made) was minimal. I do not care what type of score that you use, just that I can add it to another and tell if one is smaller than another (like concepts in C++).

TAdder
This is an IAdder<T> which takes two scores and adds them together. Why have the type parameter and not just pass an IAdder<T>? This allows the compiler to do some crazy optimizations for us. The contents of a IAdder<T>.Add probably look something like this:

public int Add(int x, int y)
  {
    return x + y;
  }

This is an ideal candidate for inlining. However, if the compiler only knows that scoreAdder is an IAdder<int>, it must make a virtual call and, thus, cannot inline. Even if the compiler cannot inline the calls, we save one boxing conversion per call (which is good, because A* is something that is probably called a whole bunch of times).

Why aren't nodeEqualityComparer and scoreComparer done like this? In 99% of cases, people are going to be using EqualityComparer<T>.Default and Comparer<T>.Default for these parameters, which will force the system to fall back to the worst-case of making the virtual calls. Perhaps I will change it in the future, but right now the advantages are very few.

Wow, all this talk and I've only managed to justify the function signature!