The pathfinding in my XNA based RTS game finally works as desired. The following screenshot shows a few units and their paths (yellow lines). The blue squares are the grid cells which they would move to next.

Base Conflict Pathfinding

For the sake of reusability I tried to keep my code relatively general. The Pathfinder class, which calculates the path relies on the following two interfaces which offer all the neccessary information describing a 2d grid map.

    /// <summary>
    /// A grid cell of a 2D grid map.
    /// </summary>
    public interface IGridCell
    {
        /// <summary>
        /// X coordinate in 2d grid space (cell index)
        /// </summary>
        int X { get; }

        /// <summary>
        /// Y coordinate in 2d grid space (cell index)
        /// </summary>
        int Y { get; }

        /// <summary>
        /// Weight of this cell. Standard value should be 0.
        /// Can be higher to account for difficult terrain or
        /// occupied cells. To make sure the cell won't be 
        /// part of a path the weight should be very high
        /// compared to the standard or usual weights used.
        /// </summary>
        int Weight { get; }

        /// <summary>
        /// Determines whether this cell can be walked and therefore
        /// should be considered for path calculations.
        /// </summary>
        bool IsWalkable { get; }

        /// <summary>
        /// Determines whether the point p corresponds to
        /// this cell, that is its X and Y coordinates are equal
        /// to the cell coordinates X and Y.
        /// </summary>
        /// <param name="p">A point of grid coordinates</param>
        /// <returns>True if the cell matches the given coordinates</returns>
        bool Matches(Point p);

        /// <summary>
        /// The 3D position of this grid cell. This should be the point
        /// right in the middle of the cell at the height of the grid.
        /// </summary>
        /// <remarks>Is not used by Pathfinder itself. This is just a convenience
        /// property for other users of the interface. If you don't need the
        /// 3D position of the cell (because your game is 2D only), you don't
        /// have to return a defined value. Just return Vector3.Zero or anything 
        /// else, it doesn't matter.</remarks>
        Vector3 Position3D { get; }
    }

    /// <summary>
    /// A 2D grid map offering key information about the grid.    
    /// </summary>
    public interface IGridMap
    {
        /// <summary>
        /// Calculates the 2D grid position (cell indices) from
        /// a 3D position.
        /// </summary>
        /// <param name="pos">position in 3D world space</param>
        /// <returns>position in 2D grid space</returns>
        Point PosToGrid(Vector3 pos);

        /// <summary>
        /// Returns the grid cell with the grid coordinates (cell indices)
        /// p.X and p.Y.
        /// </summary>
        /// <param name="p">A point of grid coordinates</param>
        /// <returns>Corresponding grid cell</returns>
        IGridCell GetCell(Point p);

        /// <summary>
        /// Returns a collection of neighbour cells. In a simple 2D grid that
        /// should be 8 cells surrounding the current cell. This method must
        /// not return invalid cells, that means it should not include non
        /// existing or invalid cells to begin with.
        /// </summary>
        /// <param name="cell">A grid cell of the strategic map</param>
        /// <returns>Collection of neighbour cells</returns>
        ICollection<IGridCell> GetNeighbourCells(IGridCell cell);
    }

This offers the advantage of not having to create a new grid representation every time the path is calculated, since you can incorporate the grid you are probably using already anyway (I have seen quite a few examples where there was created a byte array or something similar to represent the grid cells).

For my current game I just needed to implement these interfaces in my StrategicMap class to use the Pathfinder. Each cell in the StrategicMap contains a list of units that occupy it. Consequently the weight of the cells is calculated depending on whether they contain units. The property “IsWalkable” is a shortcut for discarding cells that never can be part of the path anyway. In my specific implementation it returns true in case a unit occupies the cell. The weight on the other hand can be used to account for difficult terrain or similar situations where you want to penalise certain grid cells.

My Pathfinder implementation is a simple one, I guess. It uses the manhattan distance as a heuristic which is quick and easy to calculate but not optimal. In case I needed something better I could easily swap it, however. Here is the code:

    /// <summary>
    /// Description of a path request. The path request
    /// can differ from the path itself, because the exact
    /// path might not exist. The path request stores
    /// what path was requested. The actual found path
    /// is stored in a separate Path instance.
    /// </summary>
    public struct PathRequest
    {
        public Point start;
        public Point end;

        public PathRequest(Point start, Point end)
        {
            this.start = start;
            this.end = end;
        }

        public override bool Equals(object obj)
        {
            PathRequest other = (PathRequest)obj; 	        
            return start.Equals(other.start) && end.Equals(other.end);            
        }
    }

    /// <summary>
    /// Representation of a path.
    /// Contains a implicitly linked list of PathNodes.
    /// </summary>
    public class Path
    {
        /// <summary>
        /// Current node
        /// </summary>
        PathNode current;

        /// <summary>
        /// Original start node
        /// </summary>
        PathNode start;    

        /// <summary>
        /// Creates a new path beginning at the specified start
        /// </summary>
        /// <param name="start">start path node</param>
        public Path(PathNode start)
        {
            current = start;
            this.start = start;
        }

        /// <summary>
        /// Returns true, if the path should be at its end
        /// </summary>
        public bool Finished { get { return current == null; } }

        /// <summary>
        /// Peeks at the next path node without removing it from the path
        /// </summary>
        public PathNode Next { get { return current; } }

        /// <summary>
        /// Delivers the next waypoint and moves on in the path,
        /// discarding the returned node.
        /// </summary>
        /// <returns></returns>
        public IGridCell GetNextWaypoint()
        {            
            PathNode next = current;                        
            current = current.Predecessor;            
            return next.Cell;
        }

        /// <summary>
        /// Just for debugging: Renders the complete path from beginning.
        /// </summary>
        [Conditional("DEBUG")]
        public void DrawPath()
        {
            DrawPath(start, start.Predecessor);
        }

        /// <summary>
        /// Recursive function for rendering a path segment as a yellow line.
        /// </summary>
        /// <param name="from">Start node</param>
        /// <param name="to">End node</param>
        [Conditional("DEBUG")]
        private void DrawPath(PathNode from, PathNode to)
        {            
            if (to == null) return;            
            DebugDisplay.Instance.DrawLine(from.Cell.Position3D, to.Cell.Position3D, from == start ? Color.Red : Color.Yellow);
            DrawPath(to, to.Predecessor);
        }

        /// <summary>
        /// Copies this instance of the path.
        /// </summary>
        /// <returns></returns>
        public Path Copy()
        {
            Path copy = new Path(start);
            return copy;
        }
    }

    /// <summary>
    /// A node in an A* calculated path. 
    /// </summary>
    public class PathNode : IComparable, IComparable<PathNode>, IEquatable<PathNode>
    {        
        /// <summary>
        /// The preceding node which lead to this node
        /// </summary>
        PathNode predecessor;

        /// <summary>
        /// The corresponding grid cell on the 2d map
        /// </summary>
        IGridCell cell;

        /// <summary>
        /// Destination coordinates in 2d map space
        /// </summary>
        Point goal;

        /// <summary>
        /// base cost summed up for every already visited node
        /// </summary>
        float g;

        /// <summary>
        /// cost regarding to the heuristic, estimating the left distance
        /// to the goal.
        /// </summary>
        float h;

        /// <summary>
        /// total cost of this node (g + h)
        /// </summary>
        float f;

        /// <summary>
        /// base cost summed up for every already visited node
        /// </summary>
        public float G { get { return g; } }

        /// <summary>
        /// cost regarding to the heuristic, estimating the left distance
        /// to the goal.
        /// </summary>
        public float H { get { return h; } }

        /// <summary>
        /// total cost of this node (g + h)
        /// </summary>        
        public float F { get { return f; } }

        /// <summary>
        /// The grid cell on the 2d map represented by this node
        /// </summary>
        public IGridCell Cell { get { return cell; } }

        /// <summary>
        /// The preceding node which lead to this node
        /// </summary>
        public PathNode Predecessor
        {
            get { return predecessor; }
            set { predecessor = value; }
        }

        /// <summary>
        /// Creates a new path node. The cost (or weight) of this node is automatically
        /// calculated according to the predecessor, cell and goal.
        /// </summary>
        /// <param name="predecessor">preceding node</param>
        /// <param name="cell">grid cell represented by the node</param>
        /// <param name="goal">goal coordinate in 2d map space</param>
        public PathNode(PathNode predecessor, IGridCell cell, Point goal)
        {            
            this.cell = cell;            
            this.predecessor = predecessor;
            this.goal = goal;

            Update();            
        }

        /// <summary>
        /// Recalculates the costs. This is neccessary when the predecessor has changed.
        /// </summary>
        public void Update()
        {
            if (cell.Matches(goal))
            {
                // The path ends here
                g = 1;
                h = 1;
                f = 1;
            }
            else
            {
                // cost for moving from start to this node
                g = (predecessor != null ? predecessor.G : 0) + cell.Weight;                

                // heuristic estimating the cost for moving from this node to the goal by Manhattan distance
                h = 10 * (Math.Abs(cell.X - goal.X) + Math.Abs(cell.Y - goal.Y));

                // the combined cost is later used to compare nodes
                f = g + h;
            }
        }

        #region IComparable Member

        /// <summary>
        /// Path nodes are soley compared by comparing their costs (F).
        /// </summary>
        /// <param name="obj">An other PathNode</param>
        /// <returns>Returns -1 when the the other path node is more expensive, 1 if it is less expensive and 0 otherwise</returns>
        public int CompareTo(object obj)
        {
            PathNode node = obj as PathNode;
            if (node.F < f) return 1;
            else if (node.F > f) return -1;
            else return 0;
        }

        #endregion

        #region IEquatable<PathNode> Member

        /// <summary>
        /// Two path nodes are equal when they represent the same grid cell.
        /// </summary>
        /// <param name="other">Another path node</param>
        /// <returns>True if both nodes represent the same grid cell</returns>
        public bool Equals(PathNode other)
        {
            return cell == other.cell;
        }

        #endregion

        #region IComparable<PathNode> Member

        /// <summary>
        /// Path nodes are soley compared by comparing their costs (F).
        /// </summary>
        /// <param name="other">An other PathNode</param>
        /// <returns>Returns -1 when the the other path node is more expensive, 1 if it is less expensive and 0 otherwise</returns>       
        public int CompareTo(PathNode other)
        {
            if (other.F < f) return 1;
            else if (other.F > f) return -1;
            else return 0;
        }

        #endregion
    }

    /// <summary>
    /// An A* implementation for finding paths on a 2D map.
    /// </summary>
    public class Pathfinder
    {
        /// <summary>
        /// Maximum number of steps allowed to find a path.
        /// The more steps allowed the longer the process 
        /// can take. When the step limit is reached the
        /// search is aborted.
        /// </summary>
        int stepLimit;

        /// <summary>
        /// Debug Mode settings. If true paths may be visualized.
        /// </summary>
        public static bool DebugMode { get; set; }        
        
        /// <summary>
        /// The grid map giving information about the 2D grid.
        /// </summary>
        IGridMap map;

        /// <summary>
        /// Debug Mode is enabled by default
        /// </summary>
        static Pathfinder()
        {
            DebugMode = true;
        }

        /// <summary>
        /// List containing known paths
        /// </summary>
        Dictionary<PathRequest, Path> knownPaths = new Dictionary<PathRequest, Path>();

        /// <summary>
        /// Creates a new Path finder for the specified stragic map.
        /// </summary>
        /// <param name="map">A strategic map</param>
        /// <param name="stepLimit">Maximum number of steps to find a path</param>
        public Pathfinder(IGridMap map, int stepLimit)
        {
            this.map = map;
            this.stepLimit = stepLimit;
        }

        /// <summary>
        /// Creates a new Path finder for the specified stragic map.
        /// Sets the step limit to 140 steps by default, which is only suitable for
        /// relatively short paths (depending on the grid size).
        /// </summary>
        /// <param name="map">A strategic map</param>
        public Pathfinder(IGridMap map)
            : this(map, 140)
        {
        }

        /// <summary>
        /// Calculates a path from start to end. When no path can be found in
        /// reasonable time the search is aborted and an incomplete path is returned.
        /// When refresh is not set to true a cached path is returned where possible.
        /// </summary>
        /// <param name="start">start position in 3d world space</param>
        /// <param name="end">end position in 3d world space</param>
        /// <param name="refresh">force to recalculate the path</param>
        /// <returns></returns>
        public Path CalculatePath(Vector3 start, Vector3 end, bool refresh)
        {
            return CalculatePath(map.PosToGrid(start), map.PosToGrid(end), refresh);
        }

        /// <summary>
        /// Calculates a path from start to end. When no path can be found in
        /// reasonable time the search is aborted and an incomplete path is returned. 
        /// When refresh is not set to true a cached path is returned where possible.
        /// </summary>
        /// <param name="start">start position in 2d map space</param>
        /// <param name="end">end position in 2d map space</param>
        /// <param name="refresh">force to recalculate the path</param>
        /// <returns></returns>
        public Path CalculatePath(Point start, Point end, bool refresh)
        {
            // swap points to calculate the path backwards (from end to start)
            Point temp = end;
            end = start;
            start = temp;

            // Check whether the requested path is already known
            PathRequest request = new PathRequest(start, end);
            if (!refresh && knownPaths.ContainsKey(request))
            {                
                return knownPaths[request].Copy();
            }

            // priority queue of nodes that yet have to be explored sorted in 
            // ascending order by node costs (F)
            PriorityQueue<PathNode> open = new PriorityQueue<PathNode>();

            // list of nodes that have already been explored
            LinkedList<IGridCell> closed = new LinkedList<IGridCell>();

            // start is to be explored first
            PathNode startNode = new PathNode(null, map.GetCell(start), end);
            open.Enqueue(startNode);            

            int steps = 0;            
            PathNode current;

            do 
            {
                // abort if calculation is too expensive
                if (++steps > stepLimit) return null;

                // examine the cheapest node among the yet to be explored
                current = open.Dequeue();
                
                // Finish?
                if (current.Cell.Matches(end))
                {
                    // paths which lead to the requested goal are cached for reuse
                    Path path = new Path(current);
                    
                    if (knownPaths.ContainsKey(request))
                    {
                        knownPaths[request] = path.Copy();
                    }
                    else
                    {
                        knownPaths.Add(request, path.Copy());
                    }

                    return path; 
                }                

                // Explore all neighbours of the current cell
                ICollection<IGridCell> neighbours = map.GetNeighbourCells(current.Cell);

                foreach (IGridCell cell in neighbours)
                {
                    // discard nodes that are not of interest
                    if (closed.Contains(cell) || (cell.Matches(end) == false && !cell.IsWalkable))
                    {
                        continue;
                    }

                    // successor is one of current's neighbours
                    PathNode successor = new PathNode(current, cell, end);                    
                    PathNode contained = open.Find(successor);
                    
                    if (contained != null && successor.F >= contained.F)
                    {
                        // This cell is already in the open list represented by
                        // another node that is cheaper
                        continue;
                    }                    
                    else if (contained != null && successor.F < contained.F)
                    {
                        // This cell is already in the open list but on a more expensive
                        // path -> "integrate" the node into the current path
                        contained.Predecessor = current;
                        contained.Update();
                        open.Update(contained);
                    }
                    else
                    {
                        // The cell is not in the open list and therefore still has to
                        // be explored
                        open.Enqueue(successor);
                    }
                }

                // add current to the list of the already explored nodes
                closed.AddLast(current.Cell);                

            } while (open.Peek() != null);

            return null;
        }
    }

Of course this algorithm also works for other purposes than XNA games. There is not even XNA specific code there, other than the DebugDisplay.DrawLine()-call which is one of my own classes.

The C# sourcecode can be downloaded here and contains the PriorityQueue implementation I used, as well.