A* 算法理解与实现

F=G（已花费）+H（将花费）；   G：直线花费10点。斜着走花费14点。   A* 算法的核心是，确定F花费最少的节点，并将节点记录下来。 1建立节点信息类，用以处理节点。 2确定初始节点    Node root = new Node (start); 3利用BFS思想，确定可以拓展的节点 4.在确定可拓展节点前，拓展队列中最小花费的节点，作为将要拓展节点的父节点。（父节点唯一） 5.在可扩展节点处，实例新的节点信息，确定父节点，并计算当前节点的F、G、H值。（计算与终点的预估值H）（G为已花费） 核心在于F值的大小会影响优先级。 6,当节点坐标与终点坐标重合时，即找到目标，通过循环，将此线路的父节点压入栈中。 7.通过读取栈中的值，可以确定路线。   public class Node {     //坐标     public int X, Y;     //消耗     public int F, G, H;     //父节点     public Node Parent;     //计算H值     public void CalculateH( Vector2 end) {         this .H = ( int )(10 * ( Mathf .Abs(end.x - X) + Mathf .Abs(end.y - Y)));     }     public void CalculateF() {         this .F = this .G + this .H;     }     public Node( int x, int y, Node parent= null ) {         this .X = x;         this .Y = y;         this .Parent = parent;     }     public Node( Vector2 point, Node parent = null )     {         this .X =( int )point.x;         this .Y = ( int )point.y;         this .Parent = parent;     }   }   #region Segment     public static Stack < Vector2 > path = new Stack < Vector2 >();     Vector2 start;     Vector2 end;     public const int RowCount = 7;     public const int ColCount = 9;     byte [,] mapData = new byte [RowCount, ColCount];     Transform player;     Vector3 moveDir;     Vector3 targer;     #endregion       #region Mothed     private void Start()     {         //LoadMapData();         //CreateMap();         //GetStartEnd();         //BFS();         //player = GameObject.CreatePrimitive(PrimitiveType.Sphere).transform;         //player.transform.position = GetPosition(start);         //targer = GetPosition(path.Peek());     }       public void Update()     {         moveDir = (targer - player.position).normalized;         player.Translate(moveDir* Time .deltaTime);         if ( Vector3 .Distance(player.transform.position,targer)<0.1f)         {             path.Pop();             if (path.Count==0)             {                 this .enabled = false ;             }             else             {             targer = GetPosition(path.Peek());             }         }     }       //获取游戏数据     private void LoadMapData()     {         string path = Application .dataPath + "/Map/map.txt" ;         StreamReader sr = new StreamReader (path);         string result = sr.ReadToEnd();         string [] data = result.Split( new string [] { "\r\n" }, System. StringSplitOptions .None);         for ( int i = 0; i < RowCount; i++)         {             for ( int j = 0; j < ColCount; j++)             {                 mapData[i, j] = byte .Parse(data[i][j].ToString());             }         }     }       //生成地图数据     public void CreateMap()     {         GameObject Roads = new GameObject ( "Roads" );         GameObject red = Resources .Load( "red" , typeof ( GameObject )) as GameObject ;         GameObject blue = Resources .Load( "blue" , typeof ( GameObject )) as GameObject ;         GameObject yellow = Resources .Load( "yellow" , typeof ( GameObject )) as GameObject ;         for ( int i = 0; i < RowCount; i++)         {             for ( int j = 0; j < ColCount; j++)             {                 GameObject road = null ;                 switch (mapData[i, j])                 {                     case 0:                         road = Instantiate(red) as GameObject ;                         break ;                     case 1:                         road = GameObject .CreatePrimitive( PrimitiveType .Cube);                         break ;                     case 2:                         road = Instantiate(blue) as GameObject ;                         break ;                     case 9:                         road = Instantiate(yellow) as GameObject ;                         break ;                     default :                         road = GameObject .CreatePrimitive( PrimitiveType .Cube);                         break ;                 }                 road.transform.SetParent(Roads.transform);                 road.transform.position = GetPosition(i, j);                 road.transform.localScale = Vector3 .one * 0.8f;                 road.name = i.ToString() + "_" + j.ToString();             }         }     }       Vector3 GetPosition( int x, int y)     {         int pos_x = -RowCount / 3 + y;         int pos_y = ColCount / 3 + x;         return new Vector3 (pos_x, 0, pos_y);     }     Vector3 GetPosition( Vector2 pos)     {         int pos_x = -RowCount / 3 + ( int )pos.y;         int pos_y = ColCount / 3 + ( int )pos.x;         return new Vector3 (pos_x, 1, pos_y);     }     void GetStartEnd()     {         for ( int i = 0; i < mapData.GetLength(0); i++)         {             for ( int j = 0; j < mapData.GetLength(1); j++)             {                 if (mapData[i, j] == 0)                 {                     start.x = i;                     start.y = j;                 }                 else if (mapData[i, j] == 9)                 {                     end.x = i;                     end.y = j;                     Debug .Log( new Vector2 (i, j));                 }             }         }     }       List < Node > list = new List < Node >();     List < Node > visited = new List < Node >();     private Vector2 [] dirs = new Vector2 [] { Vector2 .up, Vector2 .down, Vector2 .left, Vector2 .right, new Vector2 (1, 1), new Vector2 (-1, 1), new Vector2 (1, -1), new Vector2 (-1, -1) };       void BFS()     {         Node root = new Node (start);         list.Add(root);         while (list.Count > 0)         {             //f值排序             list.Sort(Comparer);             Node node = list[0];             list.Remove(node); //移除             visited.Add(node); //添加访问节点             for ( int i = 0; i < dirs.Length; i++)             {                 Vector2 point;                 point.x = node.X + dirs[i].x;                 point.y = node.Y + dirs[i].y;                 if (IsOk(point))                 {                     Node n = new Node (point, node);                     n.G = i > 3 ? node.G + 14 : node.G + 10;                     n.CalculateH(end);                     n.CalculateF();                     list.Add(n);                     if (point == end)                     {                         Debug .Log( "find" );                         Node p = n;                         while (p != null )                         {                             Debug .Log(p.X + "\t" + p.Y);                             path.Push( new Vector2 (p.X,p.Y));                             p = p.Parent;                         }                         return ;                     }                 }             }         }     }       private int Comparer( Node x, Node y)     {         if (x.F == y.F)         {             return 0; //表示不交互位置         }         else if (x.F > y.F)         {             return 1; //表示交互位置         }         else         {             return -1; //表示不交换位置         }     }       public bool IsOk( Vector2 point)     {         if (point.x <= 0 || point.x >= mapData.GetLength(0) || point.y <= 0 || point.y >= mapData.GetLength(1))         {             return false ;         }         if (mapData[( int )point.x, ( int )point.y] == 2)         {             return false ;         }         for ( int i = 0; i < visited.Count; i++)         {             if (visited[i].X == point.x && visited[i].Y == point.y)             {                 return false ;             }         }         for ( int i = 0; i < list.Count; i++)         {             if (list[i].X == point.x && list[i].Y == point.y)             {                 return false ;             }         }         return true ;     }     #endregion

转载于:https://www.cnblogs.com/NoXing/p/5894364.html

相关资源：A*算法A星算法