using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public enum GridType
{
    None =0,
    Road,
    Obstacle,
}
public class Grid
{
    public int X { get; set; }
    
    public  int Y { get; set; }
    
    public  Vector3 Position { get; set; }

    public Grid Parent { get; set; }
    
    public bool Visited { get; set; }
    
    public GridType GridType { get; set; }
    
    public int F { get; set; }
    
    public int G { get; set; }
    
    public int H { get; set; }
    

   
    public Grid(int x, int y)
    {
        this.X = x;
        this.Y = y;
        Position = new Vector3(x,0,y);
        
        GridType = Random.Range(0, 10) > 6 ? GridType.Obstacle : GridType.Road;
        if (x == 0 && y == 0)
        {
            GridType = GridType.Road;
        }
        if (x == 9 && y == 9)
        {
            GridType = GridType.Road;
        }
    }

    public void CalF()
    {
        F = G + H;
    }
    
    
    //计算H值（估算值）
    private void CalH(Grid target)
    {
        H = Mathf.Abs(target.X - this.X ) + Mathf.Abs(target.Y - this.Y );
        H *= 10;
        CalF();
    }
    //计算G值
    public void CalG(Grid parent, Grid target)
    {
        int dir = Mathf.Abs(parent.X - this.X ) + Mathf.Abs(parent.Y - this.Y);
        if (dir == 1)
            G = parent.G + 10;
        else
            G = parent.G + 14;
        
        this.Parent = parent;
        
        CalH(target);
    }
}

using System.Collections;
using System.Collections.Generic;
using System.Linq.Expressions;
using UnityEngine;

public class AStar 
{
   public  bool CanReach { get; private set; }

   private Grid[,] mMap;

   private Grid mStart;

   private Grid mEnd;

   private List<Grid> mOpenList;

   private List<Grid> mClosedList;
   
   int[,] dir = new int[,]{
         {1, 0},{-1, 0},
         {0, 1},{0, -1},
         {1, 1},{1, -1},
         {-1, 1},{-1, -1}
   };
   
   int[,] dir2 = new int[,]{
      {1, 0},{-1, 0},
      {0, 1},{0, -1},
   };


   public AStar(Grid[,] map, Grid start, Grid end)
   {
      this.mMap = map;
      this.mStart = start;
      this.mEnd = end;
      mOpenList = new List<Grid>();
      mClosedList = new List<Grid>();
   }


   public void FindPath()
   {
      mOpenList.Add(mStart);
      while (mOpenList.Count>0)
      {
         Grid first = mOpenList[0];
         
         for (int i = 0; i < 4; i++)
         {
            Grid tmpGrid = GetRoundGrid(first,i);
            if (CanAddOpenList(tmpGrid))
            {
               mOpenList.Add(tmpGrid);
               SetParent(first,tmpGrid);
               if (tmpGrid.X == mEnd.X && tmpGrid.Y == mEnd.Y)
               {
                  CanReach = true;
                  return;
               }
            }
         }

         mOpenList.Remove(first);
         mClosedList.Add(first);
         mOpenList.Sort(Cmp);
      }
   }

   public Vector3[] GetPath()
   {
      Stack<Vector3> stack = new Stack<Vector3>();
      while (mEnd.Parent != null)
      {
         stack.Push(mEnd.Position);
         mEnd = mEnd.Parent;
      }
 
      Vector3[]  path = new Vector3[stack.Count];
      int i = 0;
      while (stack.Count > 0)
      {
         path[i++] = stack.Pop();
      }
      return path;
   }

   private Grid GetRoundGrid(Grid grid, int index)
   {
      int x = grid.X + dir2[index, 0];
      int y = grid.Y + dir2[index, 1];
      if (x < 0 || y < 0 || x >= mMap.GetLength(0) || y >= mMap.GetLength(1))
         return null;
      if (mMap[x, y].GridType == GridType.Obstacle)
         return null;
      return mMap[x, y];
   }

   public bool CanAddOpenList(Grid grid)
   {
      if (grid == null)
      {
         return false;
      }

      if (grid.GridType == GridType.Obstacle)
      {
         return false;
      }
      for (int i = 0; i < mClosedList.Count; i++)
      {
         if (mClosedList[i].X == grid.X && mClosedList[i].Y == grid.Y)
         {
            return false;
         }

      }
      
      for (int i = 0; i < mOpenList.Count; i++)
      {
         if (mOpenList[i].X == grid.X && mOpenList[i].Y == grid.Y)
         {
            return false;
         }

      }
      return true;
   }

   public void SetParent(Grid parent, Grid son)
   {
      son.Parent = parent;
      son.CalG(parent,mEnd);
   }
   
   public int Cmp(Grid a, Grid b)
   {
      if (a.F > b.F)
         return 1;
      else if (a.F == b.F)
         return 0;
      else
         return -1;
   }
 
}

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Test : MonoBehaviour
{
    //行/列
    public int Row = 10;
    public int Col = 10;
    public GameObject mapQuad;
    
    public GameObject target;
    Grid[,] map;
 
    void Start()
    {
        InitMap();
    }
 
    void InitMap()
    {
        map = new Grid[Row, Col];
        for (int i = 0; i < map.GetLength(0); i++)
        {
            for (int j = 0; j < map.GetLength(1); j++)
            {
                map[i, j] = new Grid(i, j);
                GameObject item = (GameObject)Instantiate(mapQuad);
                item.transform.position = map[i, j].Position;
                if (map[i, j].GridType == GridType.Obstacle)
                {
                    item.GetComponent<Renderer>().material.color = Color.red;
                }
            }
        }
      
        target.transform.position = map[0, 0].Position;
        
        AStar aStar = new AStar(map, map[0, 0], map[9, 9]);
        aStar.FindPath();
        if (!aStar.CanReach)
        {
            Debug.LogError("无法到达目标点");
            return;
        }
           
        Hashtable ht = iTween.Hash("path", aStar.GetPath(), "time", 10f
            , "easeType", iTween.EaseType.linear);
        iTween.MoveTo(target, ht);
    }
}