Path Finding Using A* in C# 3.0, Part Three

Path Finding Using A* in C# 3.0, Part Three

Rate This
  • Comments 14

In order to make the A* algorithm work we need to get the lowest-estimated-cost-path-discovered-so-far out of the list of paths under consideration. The standard data structure for doing so is called a “priority queue”. Priority queues are so-called because they are typically used to store a list of jobs where each job has an associated priority.

Now, there’s a bit of a semantic problem with priority queues in that we typically think of “priority 1” as being higher priority than “priority 2”, even though 1 is a smaller number than 2. Fortunately for us, that is exactly what we want in this case; the “highest priority” path is the one with the least estimated cost.

There are lots of ways to implement priority queues – I have a nice example of an immutable priority queue that I’ll probably blog about at some point, but for now, let’s go with an old-fashioned mutable priority queue.

A priority queue can be implemented as list of sub-queues with the list sorted in priority order. The implementation is pretty straightforward:

class PriorityQueue<P, V>
{
    private SortedDictionary<P, Queue<V>> list = new SortedDictionary<P, Queue<V>>();
    public void Enqueue(P priority, V value)
    {
        Queue<V> q;
        if (!list.TryGetValue(priority, out q))
        {
            q = new Queue<V>();
            list.Add(priority, q);
        }
        q.Enqueue(value);
    }
    public V Dequeue()
    {
        // will throw if there isn’t any first element!
        var pair = list.First();
        var v = pair.Value.Dequeue();
        if (pair.Value.Count == 0) // nothing left of the top priority.
            list.Remove(pair.Key);
        return v;
    }
    public bool IsEmpty
    {
        get { return !list.Any(); }
    }
}

We could implement IEnumerable<V>, a Peek operation, etc, but this is all we need for A*, so let’s not go crazy here.

Next time: now we have all the parts we need to implement A*, so let's do it already.

  • PingBack from http://www.artofbam.com/wordpress/?p=6131

  • Noting the ugly "private SortedDictionary<P, Queue<V>> list = new SortedDictionary<P, Queue<V>>();" led me to wonder - has there been any discussion of supporting 'var' for fields with an initializer like that?  At first blush I can't see any risk or breaking change.

  • There is a serious problem with doing so, unfortunately. Namely, what happens when you say

    public class Foo {

     public var bar = new { Blah = 123 };

    ? Now you have a public member of a public type which is of an anonymous type. We have carefully designed anonymous types so that they never escape from methods, and this would break that property.

    If we allowed that then before you know it, people would want an anonymous type defined in a VB assembly to interoperate with one structurally identical exposed by a C# assembly, and we just don't want to go there.

    Until we have a CLR-wide, version-safe strategy for dealing with anonymous types we'll avoid that situation.

  • You've been kicked (a good thing) - Trackback from DotNetKicks.com

  • Why not just define public var field definations as illegal? and allow the useful private var bar  = ... ?

    A private field, which is how fields are most of the time, does not have the 'possible escaped anonymous type' issue you raise.

  • Heaps are a nice data structure to use in A* search priority queues. You get an amoratized constant time complexity for insertion and don't have to pay the logn cost until you remove items. Since A* often ends up with a bunch of unexplored nodes on the queue after you find the goal, it saves a bit of time.

  • Welcome to the thirty-third edition of Community Convergence. This week we have a new video called Programming

  • SortedDictionary.First(); defined? you're using it like: var pair = list.First(); and also with .Any();

    i can not get it running since this method is not declared. what am i doing wrong?

    filip

  • Are you using C# 3?  

    Have you got a "using System.Linq;" directive?

  • hm sorry, i'm still using c# 2. thanks.

  • switched to c#3.0 now...

    the results increased from 300ms to 15ms for my pathfinder :) great!

  • The first thing I want to be able to do in MicroQuest is move my &quot;unit&quot; around the &quot;game

  • Performance of the SortedDictionary is reportedly very slow. It might be worthwhile to write your own implementation.

    http://dotnetperls.com/Content/SortedDictionary.aspx

  • Can we store multiple same priority items for e.g.

    (1,  objA)

    (1,  objB)

    (2, objeCJ)

    (2, objK)

Page 1 of 1 (14 items)