www.pudn.com > PersonModel-1.1.rar > Astar.cs, change:2012-04-05,size:15535b


using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Drawing; 
using System.Windows.Forms; 
 
namespace PersonModel 
{ 
    class Astar 
    { 
        private static int row = 750; 
        private static int col = 510; 
        private static int hangkuan = 30; 
        private Model[,] tumian = new Model[(row + hangkuan) / hangkuan, (col + hangkuan) / hangkuan]; 
        public enum CompassDirections 
        { 
            NotSet = 0, 
            North = 1, //UP 
            NorthEast = 2, //UP Right 
            East = 3, 
            SouthEast = 4, 
            South = 5, 
            SouthWest = 6, 
            West = 7, 
            NorthWest = 8 
        } 
 
 
        #region ClosedList 
        private IList<Model> closedList = new List<Model>(); 
        /// <summary> 
        /// ClosedList 关闭列表,即存放已经遍历处理过的节点。 
        /// </summary> 
        public IList<Model> ClosedList 
        { 
            get { return closedList; } 
        } 
        #endregion 
 
        #region OpenedList 
        private IList<Model> openedList = new List<Model>(); 
        /// <summary> 
        /// OpenedList 开放列表,即存放已经开发但是还未处理的节点。 
        /// </summary> 
        public IList<Model> OpenedList 
        { 
            get { return openedList; } 
        } 
        #endregion 
 
        #region Destination 
        private Point destination = new Point(); 
        /// <summary> 
        /// Destination 目的节点的位置。 
        /// </summary> 
        public Point Destination 
        { 
            get { return destination; } 
        } 
        #endregion 
 
 
        #region Start 
        /// <summary> 
        /// 开始节点的位置. 
        /// </summary> 
        private Point start = new Point(); 
        public Point Start 
        { 
            get { return Start; } 
        } 
        #endregion 
 
        #region GetAllCompassDirections 
        /// <summary> 
        /// GetAllCompassDirections 方位列表 
        /// </summary> 
 
        private static IList<CompassDirections> AllCompassDirections = new List<CompassDirections>(); 
 
        public IList<CompassDirections> GetAllCompassDirections() 
        { 
            return AllCompassDirections; 
        } 
        #endregion 
 
        #region Plan 
 
        public IList<Point> Plan(Point start, Point destination,Model [,] tumian) 
        { 
            this.start = start; 
            this.destination = destination; 
           // this.tumian = tumian; 
 
            for (int i = 0; i <= row; i += hangkuan) 
                for (int j = 0; j <= col; j += hangkuan) 
                { 
                    Model temp = new Model(); 
                    temp.X = i; 
                    temp.CostG = 0; 
                    temp.CostH = 0; 
                    temp.PreviousNode = null; 
                    temp.Y = j; 
                    temp.Intergral = 0; 
                    temp.Isbiaoji = false; 
                     
                    temp.Counter = 0; 
                    temp.Tyle = "space"; 
                    i /= hangkuan; 
                    j /= hangkuan; 
                    temp.Tonggguo = tumian[i,j].Tonggguo; 
                   this.tumian[i, j] = new Model(); 
                   this.tumian[i, j] = temp; 
                    i *= hangkuan; 
                    j *= hangkuan; 
                } 
 
            AllCompassDirections.Add(CompassDirections.East); 
            AllCompassDirections.Add(CompassDirections.West); 
            AllCompassDirections.Add(CompassDirections.South); 
            AllCompassDirections.Add(CompassDirections.North); 
 
            AllCompassDirections.Add(CompassDirections.SouthEast); 
            AllCompassDirections.Add(CompassDirections.SouthWest); 
            AllCompassDirections.Add(CompassDirections.NorthEast); 
            AllCompassDirections.Add(CompassDirections.NorthWest); 
 
            Model startNode = new Model(); 
 
            startNode.X = start.X; 
            startNode.Y = start.Y; 
            startNode.PreviousNode = null; 
            startNode.CostG = 0; 
            startNode.CostH = 0; 
 
            OpenedList.Add(startNode); 
 
            Model currenNode = startNode; 
 
            //从起始节点开始进行递归调用 
            return DoPlan(currenNode); 
        } 
        #endregion 
 
        #region DoPlan 
        /// <summary> 
        /// 递归函数求解最短路线 
        /// </summary> 
        /// <param name="currenNode"></param> 
        /// <returns></returns> 
        private IList<Point> DoPlan(Model currenNode) 
        { 
            IList<CompassDirections> allCompassDirections = GetAllCompassDirections(); 
 
            //MessageBox.Show(currenNode.X+":"+currenNode.Y); 
            foreach (CompassDirections direction in allCompassDirections) 
            { 
                Point currentPoint = new Point(currenNode.X, currenNode.Y); 
                Point nextCell = GetAdjacentPoint(currentPoint, direction); 
 
                if (this.tumian[nextCell.X / hangkuan, nextCell.Y / hangkuan].Tonggguo == false) //下一个Cell为障碍物 
                { 
                    continue; 
                } 
 
                if (direction == CompassDirections.SouthWest) 
                { 
                    Point shapeCell = GetAdjacentPoint(currentPoint, CompassDirections.South); 
 
                    if (this.tumian[shapeCell.X / hangkuan, shapeCell.Y / hangkuan].Tonggguo == false) //下一个Cell为障碍物 
                    { 
                        continue; 
                    } 
 
                    shapeCell = GetAdjacentPoint(currentPoint, CompassDirections.West); 
 
                    if (this.tumian[shapeCell.X / hangkuan, shapeCell.Y / hangkuan].Tonggguo == false) //下一个Cell为障碍物 
                    { 
                        continue; 
                    } 
 
                } 
                else if (direction == CompassDirections.SouthEast) 
                { 
                    Point shapeCell = GetAdjacentPoint(currentPoint, CompassDirections.South); 
 
                    if (this.tumian[shapeCell.X / hangkuan, shapeCell.Y / hangkuan].Tonggguo == false) //下一个Cell为障碍物 
                    { 
                        continue; 
                    } 
 
                    shapeCell = GetAdjacentPoint(currentPoint, CompassDirections.East); 
 
                    if (this.tumian[shapeCell.X / hangkuan, shapeCell.Y / hangkuan].Tonggguo == false) //下一个Cell为障碍物 
                    { 
                        continue; 
                    } 
                } 
                else if (direction == CompassDirections.NorthEast) 
                { 
                    Point shapeCell = GetAdjacentPoint(currentPoint, CompassDirections.North); 
 
                    if (this.tumian[shapeCell.X / hangkuan, shapeCell.Y / hangkuan].Tonggguo == false) //下一个Cell为障碍物 
                    { 
                        continue; 
                    } 
 
                    shapeCell = GetAdjacentPoint(currentPoint, CompassDirections.East); 
 
                    if (this.tumian[shapeCell.X / hangkuan, shapeCell.Y / hangkuan].Tonggguo == false) //下一个Cell为障碍物 
                    { 
                        continue; 
                    } 
                } 
                else if (direction == CompassDirections.NorthWest) 
                { 
                    Point shapeCell = GetAdjacentPoint(currentPoint, CompassDirections.North); 
 
                    if (this.tumian[shapeCell.X / hangkuan, shapeCell.Y / hangkuan].Tonggguo == false) //下一个Cell为障碍物 
                    { 
                        continue; 
                    } 
 
                    shapeCell = GetAdjacentPoint(currentPoint, CompassDirections.West); 
 
                    if (this.tumian[shapeCell.X / hangkuan, shapeCell.Y / hangkuan].Tonggguo == false) //下一个Cell为障碍物 
                    { 
                        continue; 
                    } 
                } 
                else 
                { 
                } 
 
                if (GetNodeOnClose(nextCell) != null) 
                { 
                    continue; 
                } 
 
                int costG = currenNode.CostG + this.GetCost(currentPoint, direction); 
 
                int costH = (Math.Abs(nextCell.X - this.Destination.X) + Math.Abs(nextCell.Y - this.Destination.Y)); 
                if (costH == 0) //costH为0,表示相邻点就是目的点,规划完成,构造结果路径 
                { 
                    IList<Point> route = new List<Point>(); 
                    route.Add(this.Destination); 
                    route.Insert(0, currentPoint); 
                    Model tempNode = currenNode; 
                    while (tempNode.PreviousNode != null) 
                    { 
                        Point previousPoint = new Point(); 
                        previousPoint.X = tempNode.PreviousNode.X; 
                        previousPoint.Y = tempNode.PreviousNode.Y; 
                        route.Insert(0, previousPoint); 
                        tempNode = tempNode.PreviousNode; 
                    } 
                    //string ss = null; 
                    //foreach(Point ro in route) 
                    //{ 
                    //    ss += ro.ToString(); 
                    //} 
                   // MessageBox.Show(ss); 
                    return route; 
                } 
 
                Model existNode = this.GetNodeOnOpen(nextCell); 
                if (existNode != null) 
                { 
                    if (existNode.CostG > costG) 
                    { 
                        //如果新的路径代价更小,则更新该位置上的节点的原始路径 
                        existNode.ResetPreviousNode(currenNode, costG); 
                    } 
                } 
                else 
                { 
                    Model newNode = new Model(); 
                    newNode.X = nextCell.X; 
                    newNode.Y = nextCell.Y; 
                    newNode.PreviousNode = currenNode; 
                    newNode.CostG = costG; 
                    newNode.CostH = costH; 
                    this.OpenedList.Add(newNode); 
                } 
            } 
 
            //将已遍历过的节点从开放列表转移到关闭列表 
            this.OpenedList.Remove(currenNode); 
            this.ClosedList.Add(currenNode); 
 
            Model minCostNode = this.GetMinCostNode(this.OpenedList); 
            if (minCostNode == null) //表明从起点到终点之间没有任何通路。 
            { 
                return null; 
            } 
 
            //对开放列表中的下一个代价最小的节点作递归调用 
            return this.DoPlan(minCostNode); 
        } 
        #endregion 
 
        #region getCost 
        /// <summary> 
        /// getcost 取得g的值 
        /// </summary> 
        /// <param name="currentNodeLoaction"></param> 
        /// <param name="moveDirection"></param> 
        /// <returns></returns> 
 
        public int GetCost(Point currentNodeLoaction, CompassDirections moveDirection) 
        { 
            if (moveDirection == CompassDirections.NotSet) 
            { 
                return 0; 
            } 
 
            if (moveDirection == CompassDirections.East || moveDirection == CompassDirections.West || 
                moveDirection == CompassDirections.South || moveDirection == CompassDirections.North) 
            { 
                return 10; 
            } 
            else 
                return 14; 
        } 
        #endregion 
 
 
        #region GetAdjacentPoint 
        /// <summary> 
        /// 获得相邻方向的网格坐标 
        /// </summary> 
        /// <param name="current"></param> 
        /// <param name="direction"></param> 
        /// <returns></returns> 
 
        private static Point GetAdjacentPoint(Point current, CompassDirections direction) 
        { 
            switch (direction) 
            { 
                case CompassDirections.North: 
                    { 
                        return new Point(current.X, current.Y - hangkuan); 
                    } 
                case CompassDirections.South: 
                    { 
                        return new Point(current.X, current.Y + hangkuan); 
                    } 
                case CompassDirections.East: 
                    { 
                        return new Point(current.X + hangkuan, current.Y); 
                    } 
                case CompassDirections.West: 
                    { 
                        return new Point(current.X - hangkuan, current.Y); 
                    } 
                case CompassDirections.NorthEast: 
                    { 
                        return new Point(current.X + hangkuan, current.Y - hangkuan); 
                    } 
                case CompassDirections.NorthWest: 
                    { 
                        return new Point(current.X - hangkuan, current.Y - hangkuan); 
                    } 
                case CompassDirections.SouthEast: 
                    { 
                        return new Point(current.X + hangkuan, current.Y + hangkuan); 
                    } 
                case CompassDirections.SouthWest: 
                    { 
                        return new Point(current.X - hangkuan, current.Y + hangkuan); 
                    } 
                default: 
                    { 
                        return current; 
                    } 
            } 
        } 
 
        #endregion 
 
 
        #region GetNodeOnOpen 
        /// <summary> 
        /// GetNodeOnLocation 目标位置location是否已存在于开放列表中 
        /// </summary>        
        private Model GetNodeOnOpen(Point location) 
        { 
            foreach (Model temp in OpenedList) 
            { 
                if (temp.X == location.X && temp.Y == location.Y) 
                { 
                    return temp; 
                } 
            } 
 
            return null; 
        } 
        #endregion 
 
 
        #region GetNodeOnClose 
        /// <summary> 
        /// GetNodeOnLocation 目标位置是否已存在于关闭列表中 
        /// </summary>        
        private Model GetNodeOnClose(Point location) 
        { 
            foreach (Model temp in ClosedList) 
            { 
                if (temp.X == location.X && temp.Y == location.Y) 
                { 
                    return temp; 
                } 
            } 
 
            return null; 
        } 
        #endregion 
 
        #region GetMinCostNode 
        /// <summary> 
        /// GetMinCostNode 从开放列表中获取代价F最小的节点,以启动下一次递归 
        /// </summary>       
        private Model GetMinCostNode(IList<Model> openedList) 
        { 
            if (openedList.Count == 0) 
            { 
                return null; 
            } 
 
            Model target = openedList[0]; 
            foreach (Model temp in openedList) 
            { 
                if (temp.CostF < target.CostF) 
                { 
                    target = temp; 
                } 
            } 
 
            return target; 
        } 
        #endregion 
    } 
}