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


In order to implement the A* algorithm in C# 3.0 I am going to need to implement some custom data structures. Today we’ll consider how to implement the “path”.

You’ll notice in my description of the algorithm that the only operations we perform on paths are:

  • Make a new path consisting of a single node.
  • Make a new path by adding a new node onto the end of an existing path.
  • Fetch the last element on the path.
  • Get the total cost of a path.

This cries out to me “Eric! A path is an immutable stack!”

A mutable stack like System.Collections.Generic.Stack<T> is clearly not suitable. We want to be able to take an existing path and create new paths from it for all of the neighbours of its last element, but pushing a new node onto the standard stack modifies the stack. We’d have to make copies of the stack before pushing it, which is silly because then we’d be duplicating all of its contents unnecessarily.

Immutable stacks do not have this problem. Pushing onto an immutable stack merely creates a brand-new stack which links to the old one as its tail. Since the stack is immutable, there is no danger of some other code coming along and messing with the tail contents. You can keep on using the old stack to your heart’s content.

ASIDE: Immutable data structures are the way of the future in C#. It is much easier to reason about a data structure if you know that it will never change. Since they cannot be modified, they are automatically threadsafe. Since they cannot be modified, you can maintain a stack of past “snapshots” of the structure, and suddenly undo-redo implementations become trivial. On the down side, they do tend to chew up memory, but hey, that’s what garbage collection was invented for, so don’t sweat it. I’ll be talking more about programming using immutable data structures in this space over the next few months.

Let’s make an immutable stack of nodes which tracks the total cost of the whole path. Later on, we’ll see that we need to enumerate the nodes of this thing, so we’ll do a trivial implementation of IEnumerable while we’re at it. And since we don’t know exactly what a node will look like, let’s make the thing generic:

class Path<Node> : IEnumerable<Node>
{
    public Node LastStep { get; private set; }
    public Path<Node> PreviousSteps { get; private set; }
    public double TotalCost { get; private set; }
    private Path(Node lastStep, Path<Node> previousSteps, double totalCost)
    {
        LastStep = lastStep;
        PreviousSteps = previousSteps;
        TotalCost = totalCost;
    }
    public Path(Node start) : this(start, null, 0) {}
    public Path<Node> AddStep(Node step, double stepCost)
    {
        return new Path<Node>(step, this, TotalCost + stepCost);
    }
    public IEnumerator<Node> GetEnumerator()
    {
        for (Path<Node> p = this; p != null; p = p.PreviousSteps)
            yield return p.LastStep;
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

Well, that was painless. Next time: implementing the priority queue.

Comments (25)

  1. Phil says:

    Is this the same thing as consing up a list? Sounds like everything old is new again.

  2. she says:

    Hmm i am having a little problem trying to understand this… or rather the use case for a non-threaded standalone app for example, and why to pick this route instead over others?

  3. EricLippert says:

    Re: threading: I do not understand the question.

    Re: why this route?  Because this algorithm efficiently discovers the _optimal_ path if the heuristic algorithm has certain properties. We’ll get into that more later.

  4. Wesner Moise says:

    > Immutable data structures are the way of the future in C#.

    Music to my ears. Immutable data structures are pretty much what I use nowadays.

  5. Dean Harding says:

    I think she is asking "why would you use an immutable stack instead of a mutable one in a non-threaded application?"

    But it was already explained the reasoning for using immutable data structures in general (from the blog post):

    1. It is much easier to reason about a data structure if you know that it will never change.

    2. Since they cannot be modified, they are automatically threadsafe.

    3. [S]uddenly undo-redo implementations become trivial.

    Only #2 has anything to do with threading…

  6. Richard says:

    "Those who do not understand lisp are doomed to reinvent it." I’m glad to see C# going down this path! 🙂

  7. KristofU says:

    At my previous job, basically all objects were immutable.

    Some even logically immutable, but physically mutable ( caching ! ).

    It’s one hell of a tool for most jobs, but certainly not all.

    It can make some data structures very tough to deal with optimally, especially those were peformance is key, for example large matrices or vectors for data acquisition and processing.

    Of course you always have to use common sense, but when "always use immutability" is posed as a dogmatic rule you can run into huge problems when your app is scaling up.

  8. Tom Kirby-Green says:

    Looking forward to your sharing your thoughts on immutable structures. One imagines you might mention how nicely they play with ParallelFX? 😉

  9. foxyshadis says:

    Is this just going to be a keyword that can be applied to any class definition? (Or an anti-keyword if it’s the new default.) Or will it be part of the declaration/instantiation? I’m suddenly very interested in where this is heading, especially if you can easily ask for old copies.

  10. damien morton says:

    So when will we see wholistic suport for immutable data in C# and the CLR?

  11. EricLippert says:

    It’s already possible to have fully immutable data structures in C# and the CLR enforced by the runtime and the type system.  That’s what the "readonly" keyword is for.

    What I would like to see in hypothetical future versions of the language is more syntactic sugar to make this feature which already exists easier to use.  Doing stuff like

    class Foo {

     private readonly int blah;

     public int Blah { get { return blah; } }

     public Foo(int blah) { this.blah = blah; }

    is a pain in the rear.  Wouldn’t it be nice if you could do something like:

    class Foo {

     public readonly int Blah { get; set; }

     public Foo() { }

    Foo f = new Foo() { Blah = 123 };

    ?

  12. damien morton says:

    Yep – that would be nice.

    Also nice would be something that let you say:

    Foo a = new Foo() { Blah=123 };

    Foo b = new Foo(a) { Blah=124 };

    So that you can copy-and-modify in one operation.

  13. WaterBreath says:

    > Immutable data structures are the way of the future in C#.

    Hmmm….

    First there were delegates.  Then lambdas and a smattering of type inference.  And now immutable data structures as "the future".  Sounds to me like you guys are slowly trying to turn C# into a full-fledged "functional language".

  14. EricLippert says:

    We like functional languages. They are… functional.

  15. damien morton says:

    Hmm. Interesting question: do you want to declare that classes/structs are immutable, or merely that their individual properties are immutable.

    For example,

    class Bar

    {

       public readonly int Blah { get; set; }

       public int Bleh {get; set; }

    }

    class Foo

    {

       public readonly Bar Baz { get; set; }

    }

    var f = new Foo() { Baz = new Bar() { Blah=123, Bleh=124}};

    f.Baz.Bleh=145;

    Baz is a readonly property, and yet its value can be modified; or rather, a part of its value can be modified.

    I think it would be more usefull to declare classes/structs as immutable, and these classes could only contain properties whose classes were in turn immutable.

  16. EricLippert says:

    Right, what you are describing is deep vs shallow immutability.  Both have their uses. It would be nice if there were an easier way to describe and enforce what kind of immutability you want.

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

  18. I said in an earlier post that I believe that immutable objects are the way of the future in C#. I stand

  19. I said in an earlier post that I believe that immutable objects are the way of the future in C#. I stand

  20. Songphon says:

    I’m concerning about two things.

    One is overhead of creation of immutable object.

    Whatif objects are created masively which that the way in real-life usage.right?

    The other is GC.

    if all things go immutable, Is GC will does the collecting up oftenly which is led to performance problem?

    How can we handle this issues?

  21. Murph says:

    I’m glad that immutable data structures are making there way to the forefront.  In response to "she," one of the nice uses for them that I’ve found that doesn’t have anything to do with threading and whatnot is for specifying return types for methods and properties that have more functionality than arrays, but clearly cannot be modified.  For example, sometimes I would like to have a property whose value was similar in functionality to Dictionary<TKey, TVal> but whose contents would be generated by the getter.  With a mutable Dictionary, one might think that the value returned by the property could be modified and expect the modifications to be reflected on the object that contains the property.  However, this would not be the case and an immutable Dictionary would make it more clear that the returned value provides read-access only.

  22. During ALT.NET Open Spaces, Seattle, I spent a bit of time with Rustan Leino and Mike Barnett from the

  23. During ALT.NET Open Spaces, Seattle, I spent a bit of time with Rustan Leino and Mike Barnett from the

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