求C# 写的A*算法，最好有示例源码。

Question

如题，谢谢。

Answer 1

共3个文件//AStarNode.cs using System; 
using System.Collections; 
 
namespace AStar 
{ 
    public class AStarNode 
    { 
        private float     _g = 0.0f; 
        private float     _h = 0.0f; 
        private AStarNode _parent; 
 
        public AStarNode() {} 
 
        public AStarNode Parent 
        { 
            get { return _parent; } 
            set { _parent = value; } 
        } 
 
        /**//// <summary> 
        /// F = G + H 
        /// </summary> 
        public float F 
        { 
            get { return G + H; } 
        } 
 
        /**//// <summary> 
        /// 从开始节点到当前节点的实际花费 
        /// </summary> 
        public float G 
        { 
            get { return _g; } 
            set { _g = value; } 
        } 
 
        /**//// <summary> 
        /// 从当前节点到目标节点的估计花费 
        /// </summary> 
        public float H 
        { 
            get { return _h; } 
            set { _h = value; } 
        } 
 
        /**//// <summary> 
        /// 判断两个节点是否相同 
        /// </summary> 
        /// <param name="node"></param> 
        /// <returns></returns> 
        public virtual bool EqualTo(AStarNode node) 
        { 
            throw new Exception("Not Implemented"); 
        } 
 
        public virtual void Propagate(ArrayList successors) 
        { 
            throw new Exception("Not Implemented"); 
        } 
 
        public virtual float GoalDistEstimate(AStarNode node) 
        { 
            throw new Exception("Not Implemented"); 
        } 
 
        public virtual float Cost(AStarNode node) 
        { 
            throw new Exception("Not Implemented"); 
        } 
    } 
} 

Answer 2

//AStarEngine.cs 
using System; 
using System.Collections; 
 
namespace AStar 
{ 
    public class AStarEngine 
    { 
        private ArrayList _openList = new ArrayList(); 
        private ArrayList _closedList = new ArrayList(); 
        private AStarNode _resultNode = null; 
 
        public AStarEngine() { } 
 
        public AStarNode ResultNode 
        { 
            get { return _resultNode;} 
        } 
 
        public bool Found 
        { 
            get { return _resultNode != null; } 
        } 
 
        public bool Execute(AStarNode start, AStarNode goal) 
        { 
            _openList.Clear(); _closedList.Clear(); 
 
            start.G = 0; 
            start.H = start.GoalDistEstimate(goal); 
            _openList.Add(start); 
            while (_openList.Count > 0) 
            { 
                AStarNode node = getBestNode(); 
                if (node.EqualTo(goal)) 
                { 
                    _resultNode = node; 
                    return true; 
                } 
 
                ArrayList successors = new ArrayList(); 
                node.Propagate(successors); 
                foreach(AStarNode sn in successors) 
                { 
                    int no = findNodeIndex(_openList, sn); 
                    int nc = findNodeIndex(_closedList, sn); 
                    float newg = node.G + node.Cost(sn); 
 
                    if (no >= 0 && ((AStarNode)_openList[no]).G <= newg) 
                        continue; 
                    if (nc >= 0 && ((AStarNode)_closedList[nc]).G <= newg) 
                        continue; 
 
                    if (nc >= 0) _closedList.RemoveAt(nc); 
                    if (no >= 0) 
                    { 
                        AStarNode nt = (AStarNode)_openList[no]; 
                        nt.G = newg; 
                        nt.H = nt.GoalDistEstimate(goal); 
                        nt.Parent = node; 
                    } 
                    else 
                    { 
                        sn.G = newg; 
                        sn.H = sn.GoalDistEstimate(goal); 
                        sn.Parent = node; 
                        _openList.Add(sn); 
                    } 
                } 
 
                _closedList.Add(node); 
            } 
 
            return false; 
        } 
 
        private AStarNode getBestNode() 
        { 
            AStarNode node = null; 
 
            for (int i = 0; i < _openList.Count; i ++) 
            { 
                if ((node != null) && node.F > ((AStarNode)_openList[i]).F) 
                    node = (AStarNode)_openList[i]; 
 
                if (i == 0) node = (AStarNode)_openList[0]; 
            } 
 
            if (node != null) _openList.Remove(node); 
 
            return node; 
        } 
 
        private int findNodeIndex(ArrayList list, AStarNode node) 
        { 
            for (int i = 0; i < list.Count; i ++) 
            { 
                if (((AStarNode)list[i]).EqualTo(node)) 
                    return i; 
            } 
 
            return -1; 
        } 
    } 
} 

Answer 3

//Main.cs 
using System; 
using System.Collections; 
 
namespace AStar 
{ 
    class Map 
    { 
        public const int MapSize = 10; 
 
        static int[,] MapData =  
        { 
            { 0,-1, 0, 0, 0, 0, 0, 0, 0, 0 }, 
            { 0,-1, 0, 0,-1,-1,-1,-1, 0, 0 }, 
            { 0,-1, 1, 0,-1, 0, 2,-1, 0, 0 }, 
            { 0,-1, 0, 0,-1, 0, 0, 0, 0, 0 }, 
            { 0,-1, 0, 0,-1, 0, 0, 0, 0, 0 }, 
            { 0,-1,-1,-1,-1, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } 
        }; 
 
        public int GetMapData(int x, int y) 
        { 
            if (x < 0 || x > 9 || y < 0 || y > 9) 
                return -1; 
            else 
                return MapData[y, x]; 
        } 
    } 
 
    class AStarNode2D : AStarNode 
    { 
        private int _x, _y; 
        private Map _map; 
 
        public AStarNode2D(int x, int y, Map map) 
        { 
            this._x = x; 
            this._y = y; 
            this._map = map; 
        } 
 
        public int X 
        { 
            get { return _x; } 
        } 
 
        public int Y 
        { 
            get { return _y; } 
        } 
 
        public override bool EqualTo(AStarNode node) 
        { 
            AStarNode2D n = (AStarNode2D)node; 
            return (n.X == this.X) && (n.Y == this.Y); 
        } 
 
        public override void Propagate(ArrayList successors) 
        { 
            AddSuccessor(    _x, _y - 1, successors); 
            AddSuccessor(_x + 1, _y - 1, successors); 
            AddSuccessor(_x + 1,     _y, successors); 
            AddSuccessor(_x + 1, _y + 1, successors); 
            AddSuccessor(    _x, _y + 1, successors); 
            AddSuccessor(_x - 1, _y + 1, successors); 
            AddSuccessor(_x - 1,     _y, successors); 
            AddSuccessor(_x - 1, _y - 1, successors); 
        } 
 
        private void AddSuccessor(int x, int y, ArrayList successors) 
        { 
            int cost = _map.GetMapData(x, y); 
            if (cost == -1) return; 
             
            AStarNode2D node = new AStarNode2D(x, y, _map); 
            AStarNode2D p = (AStarNode2D)this.Parent; 
            while (p != null) 
            { 
                if (node.EqualTo(p)) return; 
                p = (AStarNode2D)p.Parent; 
            } 
 
            successors.Add(node); 
        } 
        public override float GoalDistEstimate(AStarNode node) 
        { 
            return Cost(node); 
        } 
 
        public override float Cost(AStarNode node) 
        { 
            AStarNode2D n = (AStarNode2D)node; 
            int xd = n.X - this.X; 
            int yd = n.Y - this.Y; 
            return (float)Math.Sqrt(xd * xd + yd * yd); 
        } 
    } 
 
    class MainEntryPoint 
    { 
        static void Main(string[] args) 
        { 
            Map map = new Map(); 
            AStarNode2D start = new AStarNode2D(2, 2, map); 
            AStarNode2D goal = new AStarNode2D(6, 2, map); 
            AStarEngine engine = new AStarEngine(); 
            ArrayList solution = new ArrayList(); 
 
            if (engine.Execute(start, goal)) 
            { 
                AStarNode2D node = (AStarNode2D)engine.ResultNode; 
                while (node != null) 
                { 
                    solution.Insert(0, node); 
                    node = (AStarNode2D)node.Parent; 
                } 
 
                Console.WriteLine("Path found:"); 
                for (int i = 0; i < 10; i ++) 
                { 
                    for (int j = 0; j < 10; j ++) 
                    { 
                        if (map.GetMapData(j, i) == -1) 
                            Console.Write("X"); 
                        else 
                        { 
                            AStarNode2D nt = new AStarNode2D(j, i, map); 
                            bool inSolution = false; 
 
                            foreach(AStarNode2D n in solution) 
                            { 
                                if (n.EqualTo(nt)) 
                                { 
                                    inSolution = true; 
                                    break; 
                                } 
                            } 
 
                            if (inSolution) Console.Write("S"); 
                            else Console.Write("."); 
                        } 
                    } 
 
                    Console.WriteLine(); 
                } 
            } 
            else 
            { 
                Console.WriteLine("Unable to find a path."); 
            } 
 
            Console.ReadLine(); 
        } 
    } 
}