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

Techy News Blog » Path Finding Using A* in C# 3.0, Part Two

Techy News Blog » Path Finding Using A* in C# 3.0, Part Two — Thu, 04 Oct 2007 17:39:04 GMT

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

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

Phil — Fri, 05 Oct 2007 00:40:53 GMT

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

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

she — Fri, 05 Oct 2007 01:47:14 GMT

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: Path Finding Using A* in C# 3.0, Part Two

Eric Lippert — Fri, 05 Oct 2007 01:54:56 GMT

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.

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

Wesner Moise — Fri, 05 Oct 2007 02:28:32 GMT

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

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

Dean Harding — Fri, 05 Oct 2007 02:42:41 GMT

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

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

Richard — Fri, 05 Oct 2007 15:45:30 GMT

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

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

KristofU — Fri, 05 Oct 2007 16:17:10 GMT

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.

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

Tom Kirby-Green — Sat, 06 Oct 2007 08:30:33 GMT

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

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

foxyshadis — Sat, 06 Oct 2007 10:04:19 GMT

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.

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

damien morton — Tue, 09 Oct 2007 00:22:35 GMT

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

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

Eric Lippert — Tue, 09 Oct 2007 01:16:30 GMT

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

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

damien morton — Tue, 09 Oct 2007 19:07:44 GMT

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.

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

WaterBreath — Tue, 09 Oct 2007 22:37:52 GMT

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

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

Eric Lippert — Tue, 09 Oct 2007 22:45:56 GMT

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

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

damien morton — Thu, 11 Oct 2007 03:03:16 GMT

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.

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

Eric Lippert — Thu, 11 Oct 2007 08:40:00 GMT

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.

Community Convergence XXXIII

Charlie Calvert's Community Blog — Mon, 15 Oct 2007 04:17:50 GMT

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

Immutability in C# Part One: Kinds of Immutability

Fabulous Adventures In Coding — Tue, 13 Nov 2007 21:14:38 GMT

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

Immutability in C# Part One: Kinds of Immutability

Noticias externas — Tue, 13 Nov 2007 21:35:20 GMT

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

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

Songphon — Tue, 20 Nov 2007 07:05:29 GMT

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?

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

Murph — Tue, 18 Dec 2007 20:26:13 GMT

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.

Making Spec# a Priority

Matthew Podwysocki — Tue, 29 Apr 2008 02:21:11 GMT

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

Making Spec# a Priority

Matthew Podwysocki's Blog — Tue, 29 Apr 2008 02:24:24 GMT

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

MicroQuest – AStar Pathfinding

Marc: My Words — Wed, 25 Jun 2008 17:22:31 GMT

The first thing I want to be able to do in MicroQuest is move my "unit" around the "game