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
Anonymous
October 04, 2007
PingBack from http://www.artofbam.com/wordpress/?p=5173Anonymous
October 04, 2007
Is this the same thing as consing up a list? Sounds like everything old is new again.Anonymous
October 04, 2007
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?Anonymous
October 04, 2007
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.Anonymous
October 04, 2007
> 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.Anonymous
October 04, 2007
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):
- 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.
- [S]uddenly undo-redo implementations become trivial. Only #2 has anything to do with threading...
Anonymous
October 05, 2007
"Those who do not understand lisp are doomed to reinvent it." I'm glad to see C# going down this path! :)Anonymous
October 05, 2007
The comment has been removedAnonymous
October 05, 2007
Looking forward to your sharing your thoughts on immutable structures. One imagines you might mention how nicely they play with ParallelFX? ;-)Anonymous
October 05, 2007
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.Anonymous
October 08, 2007
So when will we see wholistic suport for immutable data in C# and the CLR?Anonymous
October 08, 2007
The comment has been removedAnonymous
October 09, 2007
The comment has been removedAnonymous
October 09, 2007
> 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".Anonymous
October 09, 2007
We like functional languages. They are... functional.Anonymous
October 10, 2007
The comment has been removedAnonymous
October 10, 2007
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.Anonymous
October 14, 2007
Welcome to the thirty-third edition of Community Convergence. This week we have a new video called ProgrammingAnonymous
November 13, 2007
I said in an earlier post that I believe that immutable objects are the way of the future in C#. I standAnonymous
November 13, 2007
I said in an earlier post that I believe that immutable objects are the way of the future in C#. I standAnonymous
November 19, 2007
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?Anonymous
December 18, 2007
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.Anonymous
April 28, 2008
During ALT.NET Open Spaces, Seattle, I spent a bit of time with Rustan Leino and Mike Barnett from theAnonymous
April 28, 2008
During ALT.NET Open Spaces, Seattle, I spent a bit of time with Rustan Leino and Mike Barnett from theAnonymous
June 25, 2008
The first thing I want to be able to do in MicroQuest is move my "unit" around the "game