那些游戏中的寻路算法

大家好，欢迎来到IT知识分享网。

在游戏中，AI人物的移动往往有许多种实现方法，本文主要列出其中的几种常见的2D寻路方法并附上完整源代码，供读者参考，批评以及指正。
所有的代码均在Unity下完成，并通过测试可以使用。

Depth-First-Search 深度优先搜索

深度优先（DFS）算法，正如他的名字，每次先往深度走，如果此路走到底都没找到，退回到原点，换另一条路找，如果走到底还是没找到，继续换一条路，直到全部路走完。
DFS由于每次向深处搜索然后返回，很容易就让人想到用栈实现，而系统本来就有提供栈，即用递归实现。
由于深度优先算法有可能出现搜索不到目标点的情况，在这里就没有实现，仅仅做简单介绍。

Breadth First Search 广度优先搜索

广度优先搜索算法（BFS），在寻路中广度搜索算法是一种彻彻底底的盲目搜索，也就是以自己为单位，搜索地图中的每一个格子并且和目标比对，如果找到，则返回路径。
BFS的实现需要用队列，大体步骤如下：

• 首先将根节点放入队列中。

• 从队列中取出第一个节点，并检验它是否为目标。

• 如果找到目标，则结束搜寻并回传结果。

• 否则将它所有尚未检验过的直接子节点（邻节点）加入队列中。

• 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”

简单地说，就是从自身出发，像横竖斜向共八个方向进行搜索，询问自己的邻居们是不是目标点，如果不是，则将他们加入队列中。将自己的邻居遍历完了，发现没有要找的点，那么就从队列中取出之前的邻居，以邻居为起点，进行横竖斜向共八个方向的搜索，再看能不能找到目标，如此反复。

以下是部分代码，完整代码会放在文末，下同。

    public const int XLength = MapManager.XLength;
    public const int YLength = MapManager.YLength;

    public Point[,] Grid = MapManager.Grid;
    public bool[,] Book = new bool[XLength, YLength];//用于确定该点是否来过

    public Stack<Point> PathPosStack = new Stack<Point>(); //存放最终寻路结果的栈

    public int[] StepX = new int[] { 
    1, -1, 0, 0, 1,-1, 1, -1 };//向横竖以及斜方向八个方向走
    public int[] StepY = new int[] { 
    0, 0, 1, -1,1, 1, -1, -1 };
    public Stack<Point> FindPath(Point StartPoint,Point EndPoint)
    { 
   
        //清除上一次算法留下的节点与节点之间的父子关系
        ClearPoint();

        Queue<Point> Queue = new Queue<Point>();

        Book[StartPoint.PosX, StartPoint.PosY] = true;
        Queue.Enqueue(StartPoint);

        while(Queue.Count>0)
        { 
   
            Point CurrentPoint = Queue.Dequeue();
            int X = CurrentPoint.PosX;
            int Y = CurrentPoint.PosY;

            //八个方向都尝试走一下，如果可以走则加入Queue中，否则不加入
            for(int i=0;i<8;i++)
            { 
   
                int NextX = X + StepX[i];
                int NextY = Y + StepY[i];

                if(NextX<0 || NextX>=XLength || NextY<0 || NextY>=YLength || 
                    Grid[NextX,NextY].IsObstacle==true || Book[NextX,NextY]==true)
                { 
   
                    continue;
                }

                Queue.Enqueue(Grid[NextX, NextY]);
                Grid[NextX, NextY].ParentPoint = CurrentPoint;
                Book[NextX, NextY] = true;
            }
            //到达终点，返回
            if (CurrentPoint == EndPoint)
            { 
   
                PathPosStack.Clear();
                while (CurrentPoint!=StartPoint)
                { 
   
                    PathPosStack.Push(CurrentPoint);
                    CurrentPoint = CurrentPoint.ParentPoint;
                }
                PathPosStack.Push(StartPoint);
                return PathPosStack;
            }
        }
        return null;
    }

BFS没有办法计算代价。这句话是什么意思呢？举个例子，目前我们的地图中只有墙。墙是不可能越过的。但是如果地图中加入了可以走过但是花费时间会比较久的沼泽地，广度搜索就没有办法衡量这个代价了，它只会直接走过去（如下图）。这明显不是我们想要的结果。

Dijkstra 算法

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。
我们不管这玩意叫什么，只要知道，这玩意能解决刚才说的沼泽地难题。
Dijkstra算法就是通过在每一个地图格子中加入一个权值G，这个G值表示的是上一个格子到当前格子所需要花费的代价。Dijkstra在每次搜索的时候都会计算周围格子的G值，然后每次都选择G值最小的格子作为下一个拓展格子。搜索到最后，Dijkstra能返回代价最小的路径，也就是最优路径。
这比BFS智能多了，BFS会将每一个周围的格子都拓展搜索一遍，相当盲目。
部分代码如下：

public const int XLength = MapManager.XLength;
    public const int YLength = MapManager.YLength;

    public Point[,] Grid = MapManager.Grid;

    public Stack<Point> PathPosStack = new Stack<Point>();
public Stack<Point> FindPath(Point StartPoint, Point EndPoint)
    { 
   
        //清除上一次算法留下的节点与节点之间的父子关系
        ClearPoint();

        //初始化Open表和Close表
        List<Point> OpenList = new List<Point>();
        List<Point> CloseList = new List<Point>();

        //开始时将起点加入Open表
        OpenList.Add(StartPoint);

        while (OpenList.Count > 0)
        { 
   
            //寻找Open表中G值最小的节点
            Point MinPoint = FindMinPoint(OpenList);

            OpenList.Remove(MinPoint);

            CloseList.Add(MinPoint);

            //寻找MinPoint周围的点（边界和障碍物不会算在内）
            List<Point> SurroundPoints = FindSurroundPoints(MinPoint);

            //如果SurroundPoints中的点在Close表中出现过，则移除这些点
            foreach (Point ClosePoint in CloseList)
            { 
   
                if (SurroundPoints.Contains(ClosePoint))
                { 
   
                    SurroundPoints.Remove(ClosePoint);
                }
            }

            //遍历SurroundPoints中的点
            foreach (Point Son in SurroundPoints)
            { 
   
                //若该点在Open表中出现过，则检查这条路径是否更优，
                //也就是说经由当前方格(我们选中的方格) 到达那个方格是否具有更小的 G 值。
                if (OpenList.Contains(Son))
                { 
   
                    float NewPathG = CalcG(Son, MinPoint);
                    //如果 G 值更小，则把那个方格的父亲设为当前方格 ( 我们选中的方格 ) ，
                    //然后重新计算那个方格的G 值
                    if (NewPathG < Son.G)
                    { 
   
                        Son.ParentPoint = MinPoint;
                        Son.G = NewPathG;
                    }
                    //如果没有，不做任何操作。
                }
                else
                { 
   
                    //若该点没有在Open表中出现过，则直接计算G值存入点内，且将该点的父亲设置为minPoint
                    Son.G=CalcG(Son, MinPoint);
                    Son.ParentPoint = MinPoint;
                    OpenList.Add(Son);
                }
            }

            //若已经到达终点，则退出循环
            if (OpenList.IndexOf(EndPoint) > -1)
            { 
   
                break;
            }
        }
        //返回寻路结果
        return GetPathWay(StartPoint, EndPoint);
    }

Dijkstra算法虽然可以计算出最优的路径，但是它也存在盲目搜索的问题。因为虽然Dijkstra每次选择的格子都是代价最小的那一个，但不会考虑这个格子是否离终点更近一步。有可能出现终点在右边，但Dijkstra选择的下一个格子往左边走的情况。

Best-Frist-Search贪婪最佳优先搜索

贪婪最佳优先搜索就可以解决这个问题。
贪婪最佳优先搜索（BestFrist）是一种启发式算法，其也会在地图格子中添加权值，但这次添加的权值H表示的是离终点的代价。也就是采用每个格子到目标格子的距离进行排序。每次搜索都选择离终点最近的那一个格子。

 public const int XLength = MapManager.XLength;
    public const int YLength = MapManager.YLength;

    public Point[,] Grid = MapManager.Grid;

    public Stack<Point> PathPosStack = new Stack<Point>();public Stack<Point> FindPath(Point StartPoint, Point EndPoint)
    { 
   
        //清除上一次算法留下的节点与节点之间的父子关系
        ClearPoint();

        //初始化Open表和Close表
        List<Point> OpenList = new List<Point>();
        List<Point> CloseList = new List<Point>();

        //开始时将起点加入Open表
        OpenList.Add(StartPoint);

        while (OpenList.Count > 0)
        { 
   
            //寻找Open表中H值最小的节点
            Point MinPoint = FindMinPoint(OpenList);

            OpenList.Remove(MinPoint);

            CloseList.Add(MinPoint);

            //寻找MinPoint周围的点（边界和障碍物不会算在内）
            List<Point> SurroundPoints = FindSurroundPoints(MinPoint);

            //如果SurroundPoints中的点在Close表中出现过，则移除这些点
            foreach (Point ClosePoint in CloseList)
            { 
   
                if (SurroundPoints.Contains(ClosePoint))
                { 
   
                    SurroundPoints.Remove(ClosePoint);
                }
            }

            //遍历SurroundPoints中的点
            foreach (Point Son in SurroundPoints)
            { 
               
                //若该点没有在Open表中出现过，则直接计算G值存入点内，且将该点的父亲设置为minPoint
                Son.H = CalcH(Son, EndPoint);
                Son.ParentPoint = MinPoint;
                OpenList.Add(Son);
                
            }

            //若已经到达终点，则退出循环
            if (OpenList.IndexOf(EndPoint) > -1)
            { 
   
                break;
            }
        }
        //返回寻路结果
        return GetPathWay(StartPoint, EndPoint);
    }

这么一来就很明显了，BestFirst算法理论上是最快的，毕竟你每次都在向终点靠近。但是这样也牺牲了准确性，BestFirst没有办法计算出最优路径，只能给出一个相对最优的路径，最终的搜索路径就会显得有点怪怪的。

那么有没有折中的方法，既可以保证搜索的最优性，又可以保证搜索的快速性呢？

A*算法

终于到A算法了。A（念做：A Star）算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度。其于1968年，由Stanford研究院的Peter Hart, Nils Nilsson和Bertram Raphael发表。它可以被认为是Dijkstra算法的扩展。
A* 算法是一种启发式算法，它利用启发信息寻找最优路径。A* 算法需要在地图中搜索节点，并设定适合的启发函数进行指导。通过评价各个节点的代价值，获取下一需要拓展的最佳节点，直至到达最终目标点位置。A* 算法优点在于对环境反应迅速，搜索路径直接，是一种直接的搜索算法，因 此被广泛应用于路径规划问题。其缺点是实时性差，每一节点计算量大、运算时间长，而且随着节点数的增多，算法搜索效率降低，而且A* 算法并没有完全遍历所有可行解，所得到的结果不一定是最优解。
A算法结合了Dijkstra和Best-First算法的优点，在每个格子中赋予的权值F=G+H，也就是结合了前两个算法的权值进行判断。
A算法可以参考我转载的这篇文章，非常浅显易懂
AStar算法的超详细介绍
部分代码：

public const int XLength = MapManager.XLength;
    public const int YLength = MapManager.YLength;

    public Point[,] Grid = MapManager.Grid;

    public Stack<Point> PathPosStack = new Stack<Point>();
    public Stack<Point> FindPath(Point StartPoint, Point EndPoint)
    { 
   
        //清除上一次算法留下的节点与节点之间的父子关系
        ClearPoint();

        //初始化Open表和Close表
        List<Point> OpenList = new List<Point>();
        List<Point> CloseList = new List<Point>();

        //开始时将起点加入Open表
        OpenList.Add(StartPoint);

        while (OpenList.Count > 0)
        { 
   
            //寻找Open表中F值最小的节点
            Point MinPoint = FindMinPoint(OpenList);

            OpenList.Remove(MinPoint);

            CloseList.Add(MinPoint);

            //寻找MinPoint周围的点（边界和障碍物不会算在内）
            List<Point> SurroundPoints = FindSurroundPoints(MinPoint);

            //如果SurroundPoints中的点在Close表中出现过，则移除这些点
            foreach (Point ClosePoint in CloseList)
            { 
   
                if (SurroundPoints.Contains(ClosePoint))
                { 
   
                    SurroundPoints.Remove(ClosePoint);
                }
            }

            //遍历SurroundPoints中的点
            foreach (Point Son in SurroundPoints)
            { 
   
                //若该点在Open表中出现过，则检查这条路径是否更优，
                //也就是说经由当前方格(我们选中的方格) 到达那个方格是否具有更小的 G 值。
                if (OpenList.Contains(Son))
                { 
   
                    float newPathG = CalcG(Son, MinPoint);
                    //如果 G 值更小，则把那个方格的父亲设为当前方格 ( 我们选中的方格 ) ，
                    //然后重新计算那个方格的 F 值和 G 值
                    if (newPathG < Son.G)
                    { 
   
                        Son.ParentPoint = MinPoint;
                        Son.G = newPathG;
                        Son.F = Son.G + Son.H;
                    }
                    //如果没有，不做任何操作。
                }
                else
                { 
   
                    //若该点没有在Open表中出现过，则直接计算F值存入点内，且将该点的父亲设置为minPoint
                    CalcF(Son, EndPoint);
                    Son.ParentPoint = MinPoint;
                    OpenList.Add(Son);
                }
            }

            //若已经到达终点，则退出循环
            if (OpenList.IndexOf(EndPoint) > -1)
            { 
   
                break;
            }
        }
        //返回寻路结果
        return GetPathWay(StartPoint, EndPoint);
    }

A*算法的优化方法：
1.动态修改权值的方法。在之前的A算法中我们说F=G+H，实际上在H的位置还有一个权重系数W，也就是F=G+WH (W>=1)。 W是可以影响评估值的系数。在搜索过程中，我们可以通过动态修改W来影响搜索过程 H 对A星算法的影响。可以推理出，W 越大，越趋近于Best-First算法，而 W 相对越小，则相对于趋近于Dijkstra算法。
2.分级寻径：把搜索过程拆分开了，如查找空间A中的p1点到空间B中的p2点最短路径，那么可以分为两部分，先查找p1点到空间B的路径，再搜索到p2的路径，整个过程分为了两步，甚至是将计算一次的消耗，拆分成了两次，计算压力也变小了
到这里，游戏中常见的算法就算是介绍完了（其实还有B*，WayPoint，NavMesh之类的算法，我之后再继续补充），下边开始上代码

完整代码

如图所示，其中黑色的是墙壁，绿色的为寻路的物体（这里命名为Enemy），红色的为寻路的终点。
地图由80×45的正方形格子组成，统一由MapMamager类动态生成，可添加障碍物。

Scene视图，其中以算法名字+Enemy的物体都是绿色的方块，是用来寻路的物体。

类视图，其中Point为地图格子的数据结构。
先从基础的类开始：
Point类，这个类是每一个地图格子都保存的数据结构，里边主要用于存储权值，父亲节点，对应的游戏格子GameObject等数据。

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

public class Point
{ 
   
    public Point ParentPoint { 
    get; set; }//父节点
    public GameObject GameObject { 
    get; set; }//节点的游戏物体
    public Renderer PointRenderer { 
    get; set; }
    //F，G，H值
    public float F { 
    get; set; }
    public float G { 
    get; set; }
    public float H { 
    get; set; }

    public Vector2 Position { 
    get; set; }//当前节点所处于的位置
    public int PosX { 
    get; set; }
    public int PosY { 
    get; set; }

    public bool IsObstacle { 
    get; set; }//是否是障碍物

    /// <summary>
    /// 构造函数
    /// </summary>
    /// <param name="X">该节点的X坐标</param>
    /// <param name="Y">该节点的Y坐标</param>
    public Point(int X, int Y)
    { 
   
        PosX = X;
        PosY = Y;
        Position = new Vector2(PosX, PosY);
        ParentPoint = null;
        GameObject = GameObject.Find(X + "," + Y);//根据坐标绑定到场景中的游戏物体
        PointRenderer = GameObject.GetComponent<Renderer>();
    }
}

MapManager类，主要负责管理整个地图的生成以及设置障碍物。

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

public class MapManager : MonoBehaviour
{ 
   

    //生成地图
    public GameObject MapPoint;
    public const int XLength=80;
    public const int YLength=45;

    public static Point[,] Grid = new Point[XLength, YLength];
    
    public static void InitPoint()
    { 
   
        for (int i = 0; i < XLength; i++)
        { 
   
            for (int j = 0; j < YLength; j++)
            { 
   
                Grid[i, j] = new Point(i, j);
            }
        }
    }
   
    public void SetObstacle(int x, int y)
    { 
   
        Grid[x, y].IsObstacle = true;
        Grid[x, y].PointRenderer.material.color = Color.black;
    }

    void Awake()
    { 
   
        for (int i = 0; i < XLength; i++)
        { 
   
            for (int j = 0; j < YLength; j++)
            { 
   
                GameObject go = GameObject.Instantiate(MapPoint);
                go.transform.SetParent(gameObject.transform);
                go.transform.position = new Vector3(0 - XLength / 2 + i, 0, 0 - YLength / 2 + j);
                go.name = i + "," + j;
            }
        }


        InitPoint();

        for (int i=30;i<=60;i++)
        { 
   
            for(int j=29;j<=30;j++)
            { 
   
                SetObstacle(i, j);
            }
        }
        for (int i = 60; i <= 61; i++)
        { 
   
            for (int j = 15; j <= 30; j++)
            { 
   
                SetObstacle(i, j);
            }
        }
        for (int i = 30; i <= 60; i++)
        { 
   
            for (int j = 15; j <= 16; j++)
            { 
   
                SetObstacle(i, j);
            }
        }
    }
}

下边是各个寻路算法以及需要挂在在游戏物体上的类。算法类主要就负责计算，采用单例模式。实现类的命名就是算法名+Enemy组成。
DFS:

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

public class BFS
{ 
   
    public const int XLength = MapManager.XLength;
    public const int YLength = MapManager.YLength;

    public Point[,] Grid = MapManager.Grid;
    public bool[,] Book = new bool[XLength, YLength];//用于确定该点是否来过

    public Stack<Point> PathPosStack = new Stack<Point>(); //存放最终寻路结果的栈

    public int[] StepX = new int[] { 
    1, -1, 0, 0, 1,-1, 1, -1 };//向横竖以及斜方向八个方向走
    public int[] StepY = new int[] { 
    0, 0, 1, -1,1, 1, -1, -1 };

    public static BFS Instance;
    public static BFS GetInstance
    { 
   
        get
        { 
   
            if(Instance==null)
            { 
   
                Instance = new BFS();
            }
            return Instance;
        }
    }

    /// <summary>
    /// 清除节点与节点之间的父子关系
    /// </summary>
    public void ClearPoint()
    { 
   
        for (int i = 0; i < XLength; i++)
        { 
   
            for (int j = 0; j < YLength; j++)
            { 
   
                if (!Grid[i, j].IsObstacle)
                { 
   
                    if (Grid[i, j].GameObject != null)
                    { 
   
                        Grid[i, j].ParentPoint = null;
                    }
                }
                Book[i, j] = false;
            }
        }
    }

    public Stack<Point> FindPath(Point StartPoint,Point EndPoint)
    { 
   
        //清除上一次算法留下的节点与节点之间的父子关系
        ClearPoint();

        Queue<Point> Queue = new Queue<Point>();

        Book[StartPoint.PosX, StartPoint.PosY] = true;
        Queue.Enqueue(StartPoint);

        while(Queue.Count>0)
        { 
   
            Point CurrentPoint = Queue.Dequeue();
            int X = CurrentPoint.PosX;
            int Y = CurrentPoint.PosY;

            //八个方向都尝试走一下，如果可以走则加入Queue中，否则不加入
            for(int i=0;i<8;i++)
            { 
   
                int NextX = X + StepX[i];
                int NextY = Y + StepY[i];

                if(NextX<0 || NextX>=XLength || NextY<0 || NextY>=YLength || 
                    Grid[NextX,NextY].IsObstacle==true || Book[NextX,NextY]==true)
                { 
   
                    continue;
                }

                Queue.Enqueue(Grid[NextX, NextY]);
                Grid[NextX, NextY].ParentPoint = CurrentPoint;
                Book[NextX, NextY] = true;
            }
            //到达终点，返回
            if (CurrentPoint == EndPoint)
            { 
   
                PathPosStack.Clear();
                while (CurrentPoint!=StartPoint)
                { 
   
                    PathPosStack.Push(CurrentPoint);
                    CurrentPoint = CurrentPoint.ParentPoint;
                }
                PathPosStack.Push(StartPoint);
                return PathPosStack;
            }
        }
        return null;
    }
}

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;
public class BFSEnemy : MonoBehaviour
{ 
   
    Point StartPoint;
    Point EndPoint;

    BFS MyBFS;
    Point[,] Grid;

    Stack<Point> PathPosStack;

    List<Point> ChangeColorList=new List<Point>();//负责改变Point的颜色

    static Coroutine WalkCorroutine;

    Text SearchMode;
    Text SearchTime;
    private void Start()
    { 
   
        MyBFS = BFS.GetInstance;
        Grid = MyBFS.Grid;

        SearchMode = GameObject.Find("SearchMode").GetComponent<Text>();
        SearchTime = GameObject.Find("SearchTime").GetComponent<Text>();

        SearchMode.text = "Breadth First Search";
    }
    void Update()
    { 
   
        if(Input.GetMouseButtonDown(0))
            StartPathFinding();
    }
    void StartPathFinding()
    { 
   
        //还原颜色
        if(EndPoint!=null) EndPoint.PointRenderer.material.color = Color.white;
        if(ChangeColorList.Count!=0)
        { 
   
            foreach (Point son in ChangeColorList)
                son.PointRenderer.material.color = Color.white;
        }

        Ray MouseRay = Camera.main.ScreenPointToRay(Input.mousePosition);
        if (Physics.Raycast(MouseRay, out RaycastHit Hit))
        { 
   
            if (Hit.transform.tag == "MapPoint")
            { 
   
                GameObject EndObject = Hit.transform.gameObject;
                foreach (Point MapPoint in Grid)
                { 
   
                    if (EndObject == MapPoint.GameObject)
                    { 
   
                        EndPoint = MapPoint;
                    }
                }
            }
        }

        if (Physics.Raycast(new Ray(gameObject.transform.position, Vector3.down), out RaycastHit MyHit))
        { 
   
            if (MyHit.transform.tag == "MapPoint")
            { 
   
                GameObject StartObject = MyHit.transform.gameObject;
                foreach (Point MapPoint in Grid)
                { 
   
                    if (StartObject == MapPoint.GameObject)
                    { 
   
                        StartPoint = MapPoint;
                    }
                }
            }
        }

        StartCoroutine(Timer());
        PathPosStack = MyBFS.FindPath(StartPoint, EndPoint);
        StopCoroutine(Timer());

        //变色
        ChangeColorList.Clear();
        Stack<Point> TempStack = new Stack<Point>(PathPosStack);
        while (TempStack.Count > 0)
        { 
   
            Point Point = TempStack.Pop();
            ChangeColorList.Add(Point);
            Point.PointRenderer.material.color = Color.yellow;
        }
        EndPoint.PointRenderer.material.color = Color.red;

        try 
        { 
    
            StopCoroutine(WalkCorroutine);
        } catch { 
    }//停止之前的协程

        WalkCorroutine = StartCoroutine(Walk());
    }
    
    /// <summary>
    /// cube移动的协程
    /// </summary>
    /// <returns></returns>
    IEnumerator Walk()
    { 
   
        Point TargetPos = StartPoint;
        while (true)
        { 
   
            if (TargetPos.GameObject.transform.position.x == gameObject.transform.position.x
                && TargetPos.GameObject.transform.position.z == gameObject.transform.position.z && PathPosStack.Count > 0)
            { 
   
                TargetPos = PathPosStack.Peek();
                PathPosStack.Pop();
            }
            Vector3 dis = new Vector3(TargetPos.GameObject.transform.position.x,
            gameObject.transform.position.y,
            TargetPos.GameObject.transform.position.z);
            gameObject.transform.position = Vector3.MoveTowards(gameObject.transform.position, dis, 5 * Time.deltaTime);
            yield return null;
        }
    }
    IEnumerator Timer()
    { 
   
        float MyTime = 0;
        MyTime += Time.deltaTime;

        SearchTime.text = "Time: "+MyTime.ToString();

        yield return null;
    }
}

Dijkstra:

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

public class Dijkstra
{ 
   
    public const int XLength = MapManager.XLength;
    public const int YLength = MapManager.YLength;

    public Point[,] Grid = MapManager.Grid;

    public Stack<Point> PathPosStack = new Stack<Point>();

    public static Dijkstra Instance;
    public static Dijkstra GetInstance
    { 
   
        get
        { 
   
            if (Instance == null)
            { 
   
                Instance = new Dijkstra();
            }
            return Instance;
        }
    }
    /// <summary>
    /// 清除节点与节点之间的父子关系
    /// </summary>
    public void ClearPoint()
    { 
   
        for (int i = 0; i < XLength; i++)
        { 
   
            for (int j = 0; j < YLength; j++)
            { 
   
                if (!Grid[i, j].IsObstacle)
                { 
   
                    if (Grid[i, j].GameObject != null)
                    { 
   
                        Grid[i, j].ParentPoint = null;
                    }
                }
            }
        }
    }

    public Stack<Point> FindPath(Point StartPoint, Point EndPoint)
    { 
   
        //清除上一次算法留下的节点与节点之间的父子关系
        ClearPoint();

        //初始化Open表和Close表
        List<Point> OpenList = new List<Point>();
        List<Point> CloseList = new List<Point>();

        //开始时将起点加入Open表
        OpenList.Add(StartPoint);

        while (OpenList.Count > 0)
        { 
   
            //寻找Open表中G值最小的节点
            Point MinPoint = FindMinPoint(OpenList);

            OpenList.Remove(MinPoint);

            CloseList.Add(MinPoint);

            //寻找MinPoint周围的点（边界和障碍物不会算在内）
            List<Point> SurroundPoints = FindSurroundPoints(MinPoint);

            //如果SurroundPoints中的点在Close表中出现过，则移除这些点
            foreach (Point ClosePoint in CloseList)
            { 
   
                if (SurroundPoints.Contains(ClosePoint))
                { 
   
                    SurroundPoints.Remove(ClosePoint);
                }
            }

            //遍历SurroundPoints中的点
            foreach (Point Son in SurroundPoints)
            { 
   
                //若该点在Open表中出现过，则检查这条路径是否更优，
                //也就是说经由当前方格(我们选中的方格) 到达那个方格是否具有更小的 G 值。
                if (OpenList.Contains(Son))
                { 
   
                    float NewPathG = CalcG(Son, MinPoint);
                    //如果 G 值更小，则把那个方格的父亲设为当前方格 ( 我们选中的方格 ) ，
                    //然后重新计算那个方格的G 值
                    if (NewPathG < Son.G)
                    { 
   
                        Son.ParentPoint = MinPoint;
                        Son.G = NewPathG;
                    }
                    //如果没有，不做任何操作。
                }
                else
                { 
   
                    //若该点没有在Open表中出现过，则直接计算G值存入点内，且将该点的父亲设置为minPoint
                    Son.G=CalcG(Son, MinPoint);
                    Son.ParentPoint = MinPoint;
                    OpenList.Add(Son);
                }
            }

            //若已经到达终点，则退出循环
            if (OpenList.IndexOf(EndPoint) > -1)
            { 
   
                break;
            }
        }
        //返回寻路结果
        return GetPathWay(StartPoint, EndPoint);
    }

    /// <summary>
    /// 将寻路结果装入pathStack栈中
    /// </summary>
    /// <param name="startPoint">起点</param>
    /// <param name="endPoint">终点</param>
    /// <returns></returns>
    Stack<Point> GetPathWay(Point startPoint, Point endPoint)
    { 
   
        PathPosStack.Clear();

        Point temp = endPoint;
        while (temp.ParentPoint != null)
        { 
   
            PathPosStack.Push(temp);
            temp = temp.ParentPoint;
        }
        return PathPosStack;
    }

    /// <summary>
    /// 寻找list表中G值最小的节点
    /// </summary>
    /// <param name="list"></param>
    /// <returns></returns>
    Point FindMinPoint(List<Point> list)
    { 
   
        float G = list[0].G;
        Point ret = null;
        foreach (Point point in list)
        { 
   
            if (point.G <= G)
            { 
   
                G = point.G;
                ret = point;
            }
        }
        return ret;
    }
    /// <summary>
    /// 寻找point周围的节点加入List中，包括垂直方向和斜向共八个方向
    /// </summary>
    /// <param name="point"></param>
    /// <returns></returns>
    List<Point> FindSurroundPoints(Point point)
    { 
   
        List<Point> ret = new List<Point>();
        Point up = null, down = null, left = null, right = null;
        Point lu = null, ru = null, ld = null, rd = null;

        //如果是边界，就不加入List中
        if (point.PosY < YLength - 1)
        { 
   
            up = Grid[point.PosX, point.PosY + 1];
        }
        if (point.PosY > 0)
        { 
   
            down = Grid[point.PosX, point.PosY - 1];
        }
        if (point.PosX < XLength - 1)
        { 
   
            right = Grid[point.PosX + 1, point.PosY];
        }
        if (point.PosX > 0)
        { 
   
            left = Grid[point.PosX - 1, point.PosY];
        }

        if (left != null && down != null)
        { 
   
            ld = Grid[point.PosX - 1, point.PosY - 1];
        }
        if (left != null && up != null)
        { 
   
            lu = Grid[point.PosX - 1, point.PosY + 1];
        }
        if (right != null && down != null)
        { 
   
            rd = Grid[point.PosX + 1, point.PosY - 1];
        }
        if (right != null && up != null)
        { 
   
            ru = Grid[point.PosX + 1, point.PosY + 1];
        }

        //上下左右方向，如果是障碍物就不加入list中
        if (left != null && left.IsObstacle == false)
        { 
   
            ret.Add(left);
        }
        if (right != null && right.IsObstacle == false)
        { 
   
            ret.Add(right);
        }
        if (up != null && up.IsObstacle == false)
        { 
   
            ret.Add(up);
        }
        if (down != null && down.IsObstacle == false)
        { 
   
            ret.Add(down);
        }
        //这里规定了如果上下左右方向有障碍，则斜方向不能寻路过去，读者可以不加入这个条件
        if (lu != null && lu.IsObstacle == false && ret.Contains(left) && ret.Contains(up))
        { 
   
            ret.Add(lu);
        }
        if (ld != null && ld.IsObstacle == false && ret.Contains(left) && ret.Contains(down))
        { 
   
            ret.Add(ld);
        }
        if (ru != null && ru.IsObstacle == false && ret.Contains(right) && ret.Contains(up))
        { 
   
            ret.Add(ru);
        }
        if (rd != null && rd.IsObstacle == false && ret.Contains(right) && ret.Contains(down))
        { 
   
            ret.Add(rd);
        }
        return ret;

    }

    //计算G值
    float CalcG(Point surroundPoint, Point minPoint)
    { 
   
        return Vector2.Distance(surroundPoint.Position, minPoint.Position) + minPoint.G;
    }

}

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

public class DijkstraEnemy : MonoBehaviour
{ 
   
    Point StartPoint;
    Point EndPoint;

    Dijkstra MyDijkstra;
    Point[,] Grid;

    Stack<Point> PathPosStack;

    List<Point> ChangeColorList = new List<Point>();//负责改变Point的颜色

    static Coroutine WalkCorroutine;

    Text SearchMode;
    Text SearchTime;
    private void Start()
    { 
   
        MyDijkstra = Dijkstra.GetInstance;
        Grid = MyDijkstra.Grid;

        SearchMode = GameObject.Find("SearchMode").GetComponent<Text>();
        SearchTime = GameObject.Find("SearchTime").GetComponent<Text>();

        SearchMode.text = "Dijkkstra";
    }
    void Update()
    { 
   
        if (Input.GetMouseButtonDown(0))
            StartPathFinding();
    }
    void StartPathFinding()
    { 
   
        //还原颜色
        if (EndPoint != null) EndPoint.PointRenderer.material.color = Color.white;
        if (ChangeColorList.Count != 0)
        { 
   
            foreach (Point son in ChangeColorList)
                son.PointRenderer.material.color = Color.white;
        }

        //获取StartPoint和EndPoint，StartPoint为当前物体所在的位置，EndPoint为鼠标点击的位置
        Ray MouseRay = Camera.main.ScreenPointToRay(Input.mousePosition);
        if (Physics.Raycast(MouseRay, out RaycastHit Hit))
        { 
   
            if (Hit.transform.tag == "MapPoint")
            { 
   
                GameObject EndObject = Hit.transform.gameObject;
                foreach (Point MapPoint in Grid)
                { 
   
                    if (EndObject == MapPoint.GameObject)
                    { 
   
                        EndPoint = MapPoint;
                    }
                }
            }
        }

        if (Physics.Raycast(new Ray(gameObject.transform.position, Vector3.down), out RaycastHit MyHit))
        { 
   
            if (MyHit.transform.tag == "MapPoint")
            { 
   
                GameObject StartObject = MyHit.transform.gameObject;
                foreach (Point MapPoint in Grid)
                { 
   
                    if (StartObject == MapPoint.GameObject)
                    { 
   
                        StartPoint = MapPoint;
                    }
                }
            }
        }

        StartCoroutine(Timer());
        PathPosStack = MyDijkstra.FindPath(StartPoint, EndPoint);
        StopCoroutine(Timer());

        //变色
        ChangeColorList.Clear();
        Stack<Point> TempStack = new Stack<Point>(PathPosStack);
        while (TempStack.Count > 0)
        { 
   
            Point Point = TempStack.Pop();
            ChangeColorList.Add(Point);
            Point.PointRenderer.material.color = Color.yellow;
        }
        EndPoint.PointRenderer.material.color = Color.red;

        try
        { 
   
            StopCoroutine(WalkCorroutine);
        }
        catch { 
    }//停止之前的协程

        WalkCorroutine = StartCoroutine(Walk());
    }

    /// <summary>
    /// cube移动的协程
    /// </summary>
    /// <returns></returns>
    IEnumerator Walk()
    { 
   
        Point TargetPos = StartPoint;
        while (true)
        { 
   
            if (TargetPos.GameObject.transform.position.x == gameObject.transform.position.x
                && TargetPos.GameObject.transform.position.z == gameObject.transform.position.z && PathPosStack.Count > 0)
            { 
   
                TargetPos = PathPosStack.Peek();
                PathPosStack.Pop();
            }
            Vector3 dis = new Vector3(TargetPos.GameObject.transform.position.x,
            gameObject.transform.position.y,
            TargetPos.GameObject.transform.position.z);
            gameObject.transform.position = Vector3.MoveTowards(gameObject.transform.position, dis, 5 * Time.deltaTime);
            yield return null;
        }
    }
    IEnumerator Timer()
    { 
   
        float MyTime = 0;
        MyTime += Time.deltaTime;

        SearchTime.text = "Time: " + MyTime.ToString();

        yield return null;
    }
}

Best-First

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

public class BestFirst
{ 
   
    public const int XLength = MapManager.XLength;
    public const int YLength = MapManager.YLength;

    public Point[,] Grid = MapManager.Grid;

    public Stack<Point> PathPosStack = new Stack<Point>();

    public static BestFirst Instance;
    public static BestFirst GetInstance
    { 
   
        get
        { 
   
            if (Instance == null)
            { 
   
                Instance = new BestFirst();
            }
            return Instance;
        }
    }
    public BestFirst()
    { 
   

    }
    /// <summary>
    /// 清除节点与节点之间的父子关系
    /// </summary>
    public void ClearPoint()
    { 
   
        for (int i = 0; i < XLength; i++)
        { 
   
            for (int j = 0; j < YLength; j++)
            { 
   
                if (!Grid[i, j].IsObstacle)
                { 
   
                    if (Grid[i, j].GameObject != null)
                    { 
   
                        Grid[i, j].ParentPoint = null;
                    }
                }
            }
        }
    }

    public Stack<Point> FindPath(Point StartPoint, Point EndPoint)
    { 
   
        //清除上一次算法留下的节点与节点之间的父子关系
        ClearPoint();

        //初始化Open表和Close表
        List<Point> OpenList = new List<Point>();
        List<Point> CloseList = new List<Point>();

        //开始时将起点加入Open表
        OpenList.Add(StartPoint);

        while (OpenList.Count > 0)
        { 
   
            //寻找Open表中H值最小的节点
            Point MinPoint = FindMinPoint(OpenList);

            OpenList.Remove(MinPoint);

            CloseList.Add(MinPoint);

            //寻找MinPoint周围的点（边界和障碍物不会算在内）
            List<Point> SurroundPoints = FindSurroundPoints(MinPoint);

            //如果SurroundPoints中的点在Close表中出现过，则移除这些点
            foreach (Point ClosePoint in CloseList)
            { 
   
                if (SurroundPoints.Contains(ClosePoint))
                { 
   
                    SurroundPoints.Remove(ClosePoint);
                }
            }

            //遍历SurroundPoints中的点
            foreach (Point Son in SurroundPoints)
            { 
               
                //若该点没有在Open表中出现过，则直接计算G值存入点内，且将该点的父亲设置为minPoint
                Son.H = CalcH(Son, EndPoint);
                Son.ParentPoint = MinPoint;
                OpenList.Add(Son);
                
            }

            //若已经到达终点，则退出循环
            if (OpenList.IndexOf(EndPoint) > -1)
            { 
   
                break;
            }
        }
        //返回寻路结果
        return GetPathWay(StartPoint, EndPoint);
    }

    /// <summary>
    /// 将寻路结果装入pathStack栈中
    /// </summary>
    /// <param name="startPoint">起点</param>
    /// <param name="endPoint">终点</param>
    /// <returns></returns>
    Stack<Point> GetPathWay(Point startPoint, Point endPoint)
    { 
   
        PathPosStack.Clear();

        Point temp = endPoint;
        while (temp.ParentPoint != null)
        { 
   
            PathPosStack.Push(temp);
            temp = temp.ParentPoint;
        }
        return PathPosStack;
    }

    /// <summary>
    /// 寻找list表中H值最小的节点
    /// </summary>
    /// <param name="list"></param>
    /// <returns></returns>
    Point FindMinPoint(List<Point> list)
    { 
   
        float H = list[0].H;
        Point ret = null;
        foreach (Point point in list)
        { 
   
            if (point.H <= H)
            { 
   
                H = point.H;
                ret = point;
            }
        }
        return ret;
    }
    /// <summary>
    /// 寻找point周围的节点加入List中，包括垂直方向和斜向共八个方向
    /// </summary>
    /// <param name="point"></param>
    /// <returns></returns>
    List<Point> FindSurroundPoints(Point point)
    { 
   
        List<Point> ret = new List<Point>();
        Point up = null, down = null, left = null, right = null;
        Point lu = null, ru = null, ld = null, rd = null;

        //如果是边界，就不加入List中
        if (point.PosY < YLength - 1)
        { 
   
            up = Grid[point.PosX, point.PosY + 1];
        }
        if (point.PosY > 0)
        { 
   
            down = Grid[point.PosX, point.PosY - 1];
        }
        if (point.PosX < XLength - 1)
        { 
   
            right = Grid[point.PosX + 1, point.PosY];
        }
        if (point.PosX > 0)
        { 
   
            left = Grid[point.PosX - 1, point.PosY];
        }

        if (left != null && down != null)
        { 
   
            ld = Grid[point.PosX - 1, point.PosY - 1];
        }
        if (left != null && up != null)
        { 
   
            lu = Grid[point.PosX - 1, point.PosY + 1];
        }
        if (right != null && down != null)
        { 
   
            rd = Grid[point.PosX + 1, point.PosY - 1];
        }
        if (right != null && up != null)
        { 
   
            ru = Grid[point.PosX + 1, point.PosY + 1];
        }

        //上下左右方向，如果是障碍物就不加入list中
        if (left != null && left.IsObstacle == false)
        { 
   
            ret.Add(left);
        }
        if (right != null && right.IsObstacle == false)
        { 
   
            ret.Add(right);
        }
        if (up != null && up.IsObstacle == false)
        { 
   
            ret.Add(up);
        }
        if (down != null && down.IsObstacle == false)
        { 
   
            ret.Add(down);
        }
        //这里规定了如果上下左右方向有障碍，则斜方向不能寻路过去，读者可以不加入这个条件
        if (lu != null && lu.IsObstacle == false && ret.Contains(left) && ret.Contains(up))
        { 
   
            ret.Add(lu);
        }
        if (ld != null && ld.IsObstacle == false && ret.Contains(left) && ret.Contains(down))
        { 
   
            ret.Add(ld);
        }
        if (ru != null && ru.IsObstacle == false && ret.Contains(right) && ret.Contains(up))
        { 
   
            ret.Add(ru);
        }
        if (rd != null && rd.IsObstacle == false && ret.Contains(right) && ret.Contains(down))
        { 
   
            ret.Add(rd);
        }
        return ret;

    }

    //计算H值
    float CalcH(Point surroundPoint, Point minPoint)
    { 
   
        return Vector2.Distance(surroundPoint.Position, minPoint.Position);
    }
}

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;
public class BestFirstEnemy : MonoBehaviour
{ 
   
    Point StartPoint;
    Point EndPoint;

    BestFirst MyBestFirst;
    Point[,] Grid;

    Stack<Point> PathPosStack;

    List<Point> ChangeColorList = new List<Point>();//负责改变Point的颜色

    static Coroutine WalkCorroutine;

    Text SearchMode;
    Text SearchTime;
    private void Start()
    { 
   
        MyBestFirst = BestFirst.GetInstance;
        Grid = MyBestFirst.Grid;

        SearchMode = GameObject.Find("SearchMode").GetComponent<Text>();
        SearchTime = GameObject.Find("SearchTime").GetComponent<Text>();

        SearchMode.text = "Best First Search";
    }
    void Update()
    { 
   
        if (Input.GetMouseButtonDown(0))
            StartPathFinding();
    }
    void StartPathFinding()
    { 
   
        //还原颜色
        if (EndPoint != null) EndPoint.PointRenderer.material.color = Color.white;
        if (ChangeColorList.Count != 0)
        { 
   
            foreach (Point son in ChangeColorList)
                son.PointRenderer.material.color = Color.white;
        }

        //获取StartPoint和EndPoint，StartPoint为当前物体所在的位置，EndPoint为鼠标点击的位置
        Ray MouseRay = Camera.main.ScreenPointToRay(Input.mousePosition);
        if (Physics.Raycast(MouseRay, out RaycastHit Hit))
        { 
   
            if (Hit.transform.tag == "MapPoint")
            { 
   
                GameObject EndObject = Hit.transform.gameObject;
                foreach (Point MapPoint in Grid)
                { 
   
                    if (EndObject == MapPoint.GameObject)
                    { 
   
                        EndPoint = MapPoint;
                    }
                }
            }
        }

        if (Physics.Raycast(new Ray(gameObject.transform.position, Vector3.down), out RaycastHit MyHit))
        { 
   
            if (MyHit.transform.tag == "MapPoint")
            { 
   
                GameObject StartObject = MyHit.transform.gameObject;
                foreach (Point MapPoint in Grid)
                { 
   
                    if (StartObject == MapPoint.GameObject)
                    { 
   
                        StartPoint = MapPoint;
                    }
                }
            }
        }

        StartCoroutine(Timer());
        PathPosStack = MyBestFirst.FindPath(StartPoint, EndPoint);
        StopCoroutine(Timer());

        //变色
        ChangeColorList.Clear();
        Stack<Point> TempStack = new Stack<Point>(PathPosStack);
        while (TempStack.Count > 0)
        { 
   
            Point Point = TempStack.Pop();
            ChangeColorList.Add(Point);
            Point.PointRenderer.material.color = Color.yellow;
        }
        EndPoint.PointRenderer.material.color = Color.red;

        try
        { 
   
            StopCoroutine(WalkCorroutine);
        }
        catch { 
    }//停止之前的协程

        WalkCorroutine = StartCoroutine(Walk());
    }

    /// <summary>
    /// cube移动的协程
    /// </summary>
    /// <returns></returns>
    IEnumerator Walk()
    { 
   
        Point TargetPos = StartPoint;
        while (true)
        { 
   
            if (TargetPos.GameObject.transform.position.x == gameObject.transform.position.x
                && TargetPos.GameObject.transform.position.z == gameObject.transform.position.z && PathPosStack.Count > 0)
            { 
   
                TargetPos = PathPosStack.Peek();
                PathPosStack.Pop();
            }
            Vector3 dis = new Vector3(TargetPos.GameObject.transform.position.x,
            gameObject.transform.position.y,
            TargetPos.GameObject.transform.position.z);
            gameObject.transform.position = Vector3.MoveTowards(gameObject.transform.position, dis, 5 * Time.deltaTime);
            yield return null;
        }
    }
    IEnumerator Timer()
    { 
   
        float MyTime = 0;
        MyTime += Time.deltaTime;

        SearchTime.text = "Time: " + MyTime.ToString();

        yield return null;
    }
}

A*

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

public class AStar
{ 
   
    public const int XLength = MapManager.XLength;
    public const int YLength = MapManager.YLength;

    public Point[,] Grid = MapManager.Grid;

    public Stack<Point> PathPosStack = new Stack<Point>();

    public static AStar Instance;
    public static AStar GetInstance
    { 
   
        get
        { 
   
            if (Instance == null)
            { 
   
                Instance = new AStar();
            }
            return Instance;
        }
    }
    public AStar()
    { 
   

    }

    /// <summary>
    /// 清除节点与节点之间的父子关系
    /// </summary>
    public void ClearPoint()
    { 
   
        for (int i = 0; i < XLength; i++)
        { 
   
            for (int j = 0; j < YLength; j++)
            { 
   
                if (!Grid[i, j].IsObstacle)
                { 
   
                    if (Grid[i, j].GameObject != null)
                    { 
   
                        Grid[i, j].ParentPoint = null;
                    }
                }
            }
        }
    }

    public Stack<Point> FindPath(Point StartPoint, Point EndPoint)
    { 
   
        //清除上一次算法留下的节点与节点之间的父子关系
        ClearPoint();

        //初始化Open表和Close表
        List<Point> OpenList = new List<Point>();
        List<Point> CloseList = new List<Point>();

        //开始时将起点加入Open表
        OpenList.Add(StartPoint);

        while (OpenList.Count > 0)
        { 
   
            //寻找Open表中F值最小的节点
            Point MinPoint = FindMinPoint(OpenList);

            OpenList.Remove(MinPoint);

            CloseList.Add(MinPoint);

            //寻找MinPoint周围的点（边界和障碍物不会算在内）
            List<Point> SurroundPoints = FindSurroundPoints(MinPoint);

            //如果SurroundPoints中的点在Close表中出现过，则移除这些点
            foreach (Point ClosePoint in CloseList)
            { 
   
                if (SurroundPoints.Contains(ClosePoint))
                { 
   
                    SurroundPoints.Remove(ClosePoint);
                }
            }

            //遍历SurroundPoints中的点
            foreach (Point Son in SurroundPoints)
            { 
   
                //若该点在Open表中出现过，则检查这条路径是否更优，
                //也就是说经由当前方格(我们选中的方格) 到达那个方格是否具有更小的 G 值。
                if (OpenList.Contains(Son))
                { 
   
                    float newPathG = CalcG(Son, MinPoint);
                    //如果 G 值更小，则把那个方格的父亲设为当前方格 ( 我们选中的方格 ) ，
                    //然后重新计算那个方格的 F 值和 G 值
                    if (newPathG < Son.G)
                    { 
   
                        Son.ParentPoint = MinPoint;
                        Son.G = newPathG;
                        Son.F = Son.G + Son.H;
                    }
                    //如果没有，不做任何操作。
                }
                else
                { 
   
                    //若该点没有在Open表中出现过，则直接计算F值存入点内，且将该点的父亲设置为minPoint
                    CalcF(Son, EndPoint);
                    Son.ParentPoint = MinPoint;
                    OpenList.Add(Son);
                }
            }

            //若已经到达终点，则退出循环
            if (OpenList.IndexOf(EndPoint) > -1)
            { 
   
                break;
            }
        }
        //返回寻路结果
        return GetPathWay(StartPoint, EndPoint);
    }

    /// <summary>
    /// 将寻路结果装入pathStack栈中
    /// </summary>
    /// <param name="startPoint">起点</param>
    /// <param name="endPoint">终点</param>
    /// <returns></returns>
    Stack<Point> GetPathWay(Point startPoint, Point endPoint)
    { 
   
        PathPosStack.Clear();

        Point temp = endPoint;
        while (temp.ParentPoint != null)
        { 
   
            PathPosStack.Push(temp);
            temp = temp.ParentPoint;
        }
        return PathPosStack;
    }

    /// <summary>
    /// 寻找list表中H值最小的节点
    /// </summary>
    /// <param name="list"></param>
    /// <returns></returns>
    Point FindMinPoint(List<Point> list)
    { 
   
        float F = list[0].F;
        Point ret = null;
        foreach (Point point in list)
        { 
   
            if (point.F <= F)
            { 
   
                F = point.F;
                ret = point;
            }
        }
        return ret;
    }
    /// <summary>
    /// 寻找point周围的节点加入List中，包括垂直方向和斜向共八个方向
    /// </summary>
    /// <param name="point"></param>
    /// <returns></returns>
    List<Point> FindSurroundPoints(Point point)
    { 
   
        List<Point> ret = new List<Point>();
        Point up = null, down = null, left = null, right = null;
        Point lu = null, ru = null, ld = null, rd = null;

        //如果是边界，就不加入List中
        if (point.PosY < YLength - 1)
        { 
   
            up = Grid[point.PosX, point.PosY + 1];
        }
        if (point.PosY > 0)
        { 
   
            down = Grid[point.PosX, point.PosY - 1];
        }
        if (point.PosX < XLength - 1)
        { 
   
            right = Grid[point.PosX + 1, point.PosY];
        }
        if (point.PosX > 0)
        { 
   
            left = Grid[point.PosX - 1, point.PosY];
        }

        if (left != null && down != null)
        { 
   
            ld = Grid[point.PosX - 1, point.PosY - 1];
        }
        if (left != null && up != null)
        { 
   
            lu = Grid[point.PosX - 1, point.PosY + 1];
        }
        if (right != null && down != null)
        { 
   
            rd = Grid[point.PosX + 1, point.PosY - 1];
        }
        if (right != null && up != null)
        { 
   
            ru = Grid[point.PosX + 1, point.PosY + 1];
        }

        //上下左右方向，如果是障碍物就不加入list中
        if (left != null && left.IsObstacle == false)
        { 
   
            ret.Add(left);
        }
        if (right != null && right.IsObstacle == false)
        { 
   
            ret.Add(right);
        }
        if (up != null && up.IsObstacle == false)
        { 
   
            ret.Add(up);
        }
        if (down != null && down.IsObstacle == false)
        { 
   
            ret.Add(down);
        }
        //这里规定了如果上下左右方向有障碍，则斜方向不能寻路过去，读者可以不加入这个条件
        if (lu != null && lu.IsObstacle == false && ret.Contains(left) && ret.Contains(up))
        { 
   
            ret.Add(lu);
        }
        if (ld != null && ld.IsObstacle == false && ret.Contains(left) && ret.Contains(down))
        { 
   
            ret.Add(ld);
        }
        if (ru != null && ru.IsObstacle == false && ret.Contains(right) && ret.Contains(up))
        { 
   
            ret.Add(ru);
        }
        if (rd != null && rd.IsObstacle == false && ret.Contains(right) && ret.Contains(down))
        { 
   
            ret.Add(rd);
        }
        return ret;

    }

    //计算G值
    float CalcG(Point surroundPoint, Point minPoint)
    { 
   
        return Vector2.Distance(surroundPoint.Position, minPoint.Position);
    }

    void CalcF(Point nowPoint, Point endPoint)
    { 
   
        float H = Mathf.Abs(endPoint.PosX - nowPoint.PosX) + Mathf.Abs(endPoint.PosY - nowPoint.PosY);
        float G = 0;
        if (nowPoint.ParentPoint == null)
        { 
   
            G = 0;
        }
        else
        { 
   
            G = Vector2.Distance(nowPoint.ParentPoint.Position, nowPoint.Position) + nowPoint.ParentPoint.G;
        }
        nowPoint.G = G;
        nowPoint.H = H;
        nowPoint.F = G + H;
    }
}

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;
public class AStarEnemy : MonoBehaviour
{ 
   
    Point StartPoint;
    Point EndPoint;

    AStar MyAStar;
    Point[,] Grid;

    Stack<Point> PathPosStack;

    List<Point> ChangeColorList = new List<Point>();//负责改变Point的颜色

    static Coroutine WalkCorroutine;

    Text SearchMode;
    Text SearchTime;
    private void Start()
    { 
   
        MyAStar = AStar.GetInstance;
        Grid = MyAStar.Grid;

        SearchMode = GameObject.Find("SearchMode").GetComponent<Text>();
        SearchTime = GameObject.Find("SearchTime").GetComponent<Text>();

        SearchMode.text = "AStar Search";
    }
    void Update()
    { 
   
        if (Input.GetMouseButtonDown(0))
            StartPathFinding();
    }
    void StartPathFinding()
    { 
   
        //还原颜色
        if (EndPoint != null) EndPoint.PointRenderer.material.color = Color.white;
        if (ChangeColorList.Count != 0)
        { 
   
            foreach (Point son in ChangeColorList)
                son.PointRenderer.material.color = Color.white;
        }

        //获取StartPoint和EndPoint，StartPoint为当前物体所在的位置，EndPoint为鼠标点击的位置
        Ray MouseRay = Camera.main.ScreenPointToRay(Input.mousePosition);
        if (Physics.Raycast(MouseRay, out RaycastHit Hit))
        { 
   
            if (Hit.transform.tag == "MapPoint")
            { 
   
                GameObject EndObject = Hit.transform.gameObject;
                foreach (Point MapPoint in Grid)
                { 
   
                    if (EndObject == MapPoint.GameObject)
                    { 
   
                        EndPoint = MapPoint;
                    }
                }
            }
        }

        if (Physics.Raycast(new Ray(gameObject.transform.position, Vector3.down), out RaycastHit MyHit))
        { 
   
            if (MyHit.transform.tag == "MapPoint")
            { 
   
                GameObject StartObject = MyHit.transform.gameObject;
                foreach (Point MapPoint in Grid)
                { 
   
                    if (StartObject == MapPoint.GameObject)
                    { 
   
                        StartPoint = MapPoint;
                    }
                }
            }
        }

        StartCoroutine(Timer());
        PathPosStack = MyAStar.FindPath(StartPoint, EndPoint);
        StopCoroutine(Timer());

        //变色
        ChangeColorList.Clear();
        Stack<Point> TempStack = new Stack<Point>(PathPosStack);
        while (TempStack.Count > 0)
        { 
   
            Point Point = TempStack.Pop();
            ChangeColorList.Add(Point);
            Point.PointRenderer.material.color = Color.yellow;
        }
        EndPoint.PointRenderer.material.color = Color.red;

        try
        { 
   
            StopCoroutine(WalkCorroutine);
        }
        catch { 
    }//停止之前的协程

        WalkCorroutine = StartCoroutine(Walk());
    }

    /// <summary>
    /// cube移动的协程
    /// </summary>
    /// <returns></returns>
    IEnumerator Walk()
    { 
   
        Point TargetPos = StartPoint;
        while (true)
        { 
   
            if (TargetPos.GameObject.transform.position.x == gameObject.transform.position.x
                && TargetPos.GameObject.transform.position.z == gameObject.transform.position.z && PathPosStack.Count > 0)
            { 
   
                TargetPos = PathPosStack.Peek();
                PathPosStack.Pop();
            }
            Vector3 dis = new Vector3(TargetPos.GameObject.transform.position.x,
            gameObject.transform.position.y,
            TargetPos.GameObject.transform.position.z);
            gameObject.transform.position = Vector3.MoveTowards(gameObject.transform.position, dis, 5 * Time.deltaTime);
            yield return null;
        }
    }
    IEnumerator Timer()
    { 
   
        float MyTime = 0;
        MyTime += Time.deltaTime;

        SearchTime.text = "Time: " + MyTime.ToString();

        yield return null;
    }
}

参考文章：
https://gameinstitute.qq.com/community/detail/117767
https://blog.csdn.net/shaocize/article/details/90082694
https://www.jianshu.com/p/5a60f921b019