I was amused to read this post about an arithmetic bug which accidentally turned into an AI feature (found via Raymond’s recent link clearance .) It reminded me of a story that my friend Lars told me about working on a certain well-known first-person shooter back in the day. The developers of this game...

Finally we are ready to translate our pseudocode into C# 3.0. What do we need to make the algorithm run? We need a start node, a destination node, a function which tells us the exact distance between two neighbours, and a function which tells us the estimated distance between the last node on a proposed...

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

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

As we get into the home stretch for the Orcas release I’ve been spending a little time lately just playing around implementing some “classic” algorithms and data structures in C#. The one I implemented today is the famous A* algorithm. Surely you’ve played games like Age of Empires. You know the kind...