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

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

Rate This
  • Comments 25

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.

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

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

  • 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?

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

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

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

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

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

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

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

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

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

    ?

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

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

  • We like functional languages. They are... functional.

Page 1 of 2 (25 items) 12