• Asset Store地址:https://assetstore.unity.com/packages/tools/ai/poly-nav-2d-pathfinding-14718 用于2D游戏寻路 用法想当简单,Demo一看就懂
  • 调研了下,大概有两个插件可以用于Unity2D: 1.PolyNav - 2D Pathfinding 2.Navigation2D Pathfinding 当然,这些插件包括unity自带的Navmesh,还有那个著名的A start pathfind 插件,都是只用于客户端,不能...

            调研了下,大概有两个插件可以用于Unity2D:

    1.PolyNav - 2D Pathfinding

    2.Navigation2D Pathfinding

            当然,这些插件包括unity自带的Navmesh,还有那个著名的A start pathfind 插件,都是只用于客户端,不能用于服务器。根据AssetStore上的介绍,前者比较早,从unity5就支持了,后者对unity的版本要求是Unity2017后的版本。今天介绍的是后者。

             简单使用后,总体觉得Navigation还是比较好用。大概浏览下它的代码,应该是基于Unity原生的NavMash实现,把3D变成2D。看来核心还是原生的,各方面比较可靠。功能上支持静态的阻挡物和动态的阻挡物。但是有个核心组件NavMeshAgent2D用了少量的Linq,先介绍怎么使用,再介绍怎么修改这个组件去Linq。使用该插件文档,以及修改后的去Linq组件下载链接:NavMesh2D去Linq修改和说明文档

    一、使用

    静态阻挡物,只需要设置好原生的包围盒并设置成面板上设置Static即可。动态的阻挡物不用设置成Static,但包围盒还是需要设置,另外需要添加一个组件NavMeshObstacle2D下面是静态的阻挡物和动态的阻挡物添加组件后的示意图。

     

    添加完组件后打开NavMesh生成界面

    windows->Navigation2D

    Agent Radius 设置成0.5,这个值越小,生成的导航网格越密集,越精确

    NavMesh Extends 设置成1,如果大于1,将在包围范围外生成导航网格,这个就看需求吧

    点击"Bake"按钮,生成就会生成导航网格

     

    看了下代码,好像支持Unity2D的TileMap,但具体怎么个支持法,没细看。

    二、去Linq修改

    核心组件NavMeshAgent2D有两处用了Linq,意思都一样,就是把一个Vector3数组转成Vector2数组

        public bool CalculatePath(Vector2 targetPosition, NavMeshPath2D path)
        {
            var temp = new NavMeshPath();
            if (agent.CalculatePath(NavMeshUtils2D.ProjectTo3D(targetPosition), temp))
            {
                // convert 3D to 2D
                //path.corners = temp.corners.Select(NavMeshUtils2D.ProjectTo2D).ToArray();
                path.corners = Vector3sToVector2s(temp.corners);
                path.status = temp.status;
                return true;
            }
            return false;
        }
    

    被注释掉的那行就是原来的Linq代码,下面一行调用Vector3sToVector2s就是我新增加的去Linq的转换函数,其实也很简单

        public Vector2 [] Vector3sToVector2s(Vector3 [] array)
        {
            Vector2[] result = null;
            int length = 0;
            if (array == null || (length = array.Length) <= 0)
            {
                return result;
            }        
    
            result = new Vector2[length];
            for(int i = 0; i < length; i++)
            {
                result[i] = NavMeshUtils2D.ProjectTo2D(array[i]);
            }
    
            return result;
        }

     

    展开全文
  • 使用unity3d开发2d游戏,自动寻路可以有很多种实现方式。第一种比较传统的是使用A星寻路,它是一种比较传统的人工智能算法,在游戏开发中比 较常用到。大部分的页游和端游都用到这种技术。在Unity游戏也可以用这种...

      现在的大部分mmo游戏都有了自动寻路功能。点击场景上的一个位置,角色就会自动寻路过去。中间可能会有很多的障碍物,角色会自动绕过障碍物,最终达到终点。使用unity3d开发2d游戏,自动寻路可以有很多种实现方式。第一种比较传统的是使用A星寻路,它是一种比较传统的人工智能算法,在游戏开发中比 较常用到。大部分的页游和端游都用到这种技术。在Unity游戏也可以用这种技术,Asset Store上面已经有相关的组件了,感兴趣的同学可以自己去了解。我在后面有机会再来详细介绍了。今天我们来学习Unity官方内置的寻路插件 -Navmesh。由于内容比较多,我们将分几次来系统学习。今天先通过学习一个最简单的例子来入门unity3d开发2d游戏。

      实例

      我们要实现一个功能:点击场景中的一个位置,角色可以自动寻路过去。角色会绕过各种复杂的障碍,找到一条理论上”最短路径“。

      步骤

      1.创建地形

      2.添加角色

      3.创建多个障碍物,尽量摆的复杂一点,来检查Navmesh的可用性和效率。

      4.选中地形,在Navigation窗口中,设置Navigation Static

      5.依次选中障碍物,在avigation窗口中,设置Navigation Static

      7.Navigation窗口中,选择Bake(烘焙)界面,点击Bake按钮,进程场景烘焙,就可以烘焙出寻路网格了

      8.为角色添加NavMeshAgent组件。Component->Navigation->Nav Mesh Agent

      9.为角色新增一个脚本PlayerController.cs,实现点击目标,自动寻路功能

      using UnityEngine;

      using System.Collections;

      //Author:ken@iamcoding.com

      public class PlayerController : MonoBehaviour

      {

      private NavMeshAgent agent;

      void Start()

      {

      //获取组件

      agent = GetComponent();

      }

      void Update()

      {

      //鼠标左键点击

      if (Input.GetMouseButtonDown(0))

      {

      //摄像机到点击位置的的射线

      Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);

      RaycastHit hit;

      if (Physics.Raycast(ray, out hit))

      {

      //判断点击的是否地形

      if (!hit.collider.name.Equals("Terrain"))

      {

      return;

      }

      //点击位置坐标

      Vector3 point = hit.point;

      //转向

      transform.LookAt(new Vector3(point.x, transform.position.y, point.z));

      //设置寻路的目标点

      agent.SetDestination(point);

      }

      }

      //播放动画,判断是否到达了目的地,播放空闲或者跑步动画

      if (agent.remainingDistance == 0)

      {

      animation.Play("idle");

      }

      else

      {

      animation.Play("run");

      }

      }

      }

      完成了!这个unity3d开发2d游戏实例可以很简单的让我们学会如何最基本的使用自动寻路组件Nav。但是,这个组件还提供了更加强大的功能,比如,起始点和目标点中间出现阻断了,

    更多关于unity3d开发2d游戏的信息,可查询天地会http://bbs.9ria.com/thread-109043-1-1.html

    展开全文
  • Unity3D中的自动寻路

    2017-01-07 18:54:27
    Unity3d自动寻路基础教程

    Unity3D中自动寻路的功能:

    概述:

    别人写的教程,非常详细,细节我就不赘述了。只写一些自己的总结:

    1. 什么是导航网格:

    “导航网格”,规定了使用自动寻路的GameObject所能或者不能通过的地方。

    2. 如何生成导航网格:

    菜单栏: Window——Navigation,打开导航网络控制面板。

    选择想要生成网格的游戏物体,比如一个Plane,在”导航网格控制面板“中将“Navigation Static”打钩,点击右下角的Bake,烘焙路径,则可以看到自动生成的区域。Navigation Area则决定了这个区域是Walkable还是not Walkable或者是Jump。

    3. 如何应用导航网格:

    在自己的Player上添加一个“Nav Mesh Agent”组件,这个组件实现了自动寻路的功能,可以看做是一个封装。设计者只要使用这个组件就好了,具体可以看官方说明。

    举个例子:

    using UnityEngine;
    using System.Collections;
    
    public class SetHeroDes : MonoBehaviour
    {
        public Transform ds;//用来确定目的地坐标的游戏物体的Transform
        private Vector3 origin;//存储导航网格代理的初始位置
        private NavMeshAgent nma;//存储导航网格代理组件
    
        void Start()
        {
            nma = gameObject.GetComponent<NavMeshAgent>();   //取得导航网格代理组件
            origin = transform.position;     // 存储一下这个脚本所挂载游戏物体的初始位置
            nma.SetDestination(ds.position); // 关键点:操作NavMeshAgent组件,设置自动寻路的目标位置为我们通过ds所指定的点。
        	}
    }


    把这个脚本挂到想要自动寻路的游戏物体,并指定目标位置游戏物体。

    简单粗暴有木有?

    nma.SetDestination(ds.position);

    这句代码设置后,所挂载该脚本的游戏物体就开始依据我们通过Bake生成的导航网格自动寻路了。这个过程中,会自动绕过障碍物(通过Bake将这类游戏物体烘焙为not walked)。

    4. OffMeshLink是什么?

    按照我的理解,这个组件提供了不同的高度和导航网格中断的处理方案,详情看教程吧。


    下面是别人教程的地址,非常详细:

    有些教程里面的素材如果没有,通通用cube代替,学到东西才是真的。我看这些教程时,由于是几经转载,都看不到图的,就自己随便弄个cube,Metrial之类的搞完再说。


    Unity里面的自动寻路(一)

    Unity里面的自动寻路(二)

    unity自带寻路Navmesh入门教程(一)

    unity自带寻路Navmesh入门教程(二)

    unity自带寻路Navmesh入门教程(三)


    展开全文
  • 2D自动寻路实现.7z

    2020-06-06 23:30:09
    基于A Star实现的2D及2.5D寻路算法,有详细的工程文件及介绍。
  • Unity3D 高效A*寻路

    2019-04-12 09:56:30
    Unity Asset Store URL: http://u3d.as/1ud5 随着手机游戏不断发展, 我们需要在手机做更多的表现, 但手机的性能是有限的。每个重要模块都应尽可能地有很好的性能来提升整个表现效果。寻路算法中, 普通的a*在比较大...

    Unity Asset Store URL: http://u3d.as/1ud5

    随着手机游戏不断发展, 我们需要在手机做更多的表现, 但手机的性能是有限的。每个重要模块都应尽可能地有很好的性能来提升整个表现效果。寻路算法中, 普通的a*在比较大的地图时, 消耗性能也是具大, 因此, 我把a*作了很好的改良。这已作为简单的工具类使用即可, 插件中包括阻挡数据的生成工具, 寻路算法的使用Demo。

    本文介绍了高性能”寻路”的基本用法及其应用。

     

    Quick Start

    首先, 打开展示场景Demo/DemoSearch1并运行。

    你可以看到如下图:

    多个对象在随机地自由寻路。也可以自由点击场景, 让主角对象(红点)作寻路运行。

    主角寻路时, 会在输出面板, 输出寻路的用时。

    从图中可见, 20多个寻路对象, 在不断执行寻路逻辑的情况下, 帧率还是很高的。

     

    DemoSearch1中Inspector面板的说明参数说明:

    Scene Prefab是要加载的寻路场景预制体。

    Block Data Json是工具生成的寻路数据。

    Cell Prefab 是阻挡格用到的预制体。

    Move Count 是除主角外的移动对象数量。

    Move Speed 是全局的移动速度。

    Hero Prefab 是主角用到的预制体。

    Player Prefab 是其他移动对象的预制体。

    Hero Tail Prefab 是主角移动时, 产生拖尾的预制体。

    Player Tail Prefab 是其他移动对象移动时, 产生拖尾的预制体。

    S Camera 是主摄像机, 主要用于点击场景的处理。

     

    阻挡数据生成工具说明。

    打开Demo/Tools场景

    主要关注在Hierarchy中PlaneScene的。

    PlaneScene下有LocationGO和Plane

    LocationGO主要用于标注绘制阻挡数据的左下角起始点。

    Plane是具体展现的场景。

    其中在PlaneScene的组件有两个,BoxColider和ABlockTools。

    BoxColider的Size必须是需要绘制阻挡数据场景的大小。

    ABlockTools的一些配置属性:

    Scale Speed: 绘制阻挡数据时, 滚动鼠标中轴对场景进行缩放的速度。

    Move Speed: 按着键盘Ctrl+鼠标左键, 移动鼠标时, 场景平移的速度。

    Map W和Map H: 是地图的宽高, 必须要跟BoxColider的Size保持一致。

    Map Org V2: 就是用于确定阻挡数据的左下角起始点,参考LocationGO的坐标。

    Height Of Overlook: 是摄像机开始时, 离场景的高度距离。

    Cell W: 是每阻挡格的边长。

    Cell Prefab: 是阻挡格的预制体。

    Frame Line Prefab: 是边框线条的预制体。

     

    Tools场景运行后, 即可进行阻挡数据的绘制,如果ABlockTools组件挂的GameObject中已在AJ_Pathfinding/Resources/AJ_BlockData中有生成阻挡数据,即会读取其数据,在这基础上进行绘制。

    有右键点击PlaneScene中ABlockTools组件, 弹出工具框, 选择”Start drawing blockades” 开始进行阻挡绘制; 此时如果已绘制过阻挡路径并保存的话, 会加载已有的阻挡数据并呈现出来。

    在绘制中, 在场景上按着鼠标左键并移动生成阻挡数据; 点击鼠标右键删除阻挡数据;鼠标中轴对场景进行缩放; Ctrl+鼠标左键, 移动鼠标对场景进行平移。

    绘制完成后, 右键点击PlaneScene中ABlockTools组件, 选择”Save the blockades data”进行保存。如果不满意,可以选择”Clear the blockades data”来清空当前阻挡数据。

     

    DemoSearch2中的说明:

    打开Demo/DemoSearch2场景并运行。跟DemoSearch1类似, 此Demo中加入摄像机跟随, 更好的体现移动中的效果。

    另外送上两个人物模型, 包括站立和行走的动作。

     

    API说明:

    主要类是:JOMapGrid2DDataAJFindRoad

    JOMapGrid2DData是阻挡数据管理类

    其中提供网格坐标和世界坐标的转换

    AJFindRoad是寻路算法类

    其中提供一个寻路api

    Eg.

    创建两个主体对象

    JOMapGrid2DData mapGridData = new JOMapGrid2DData();

    AJFindRoad ajSearch = new AJFindRoad();

    设置网格的基本信息

    mapGridData.SetMapData(float mapW,float mapH,float mapOffsetX,float mapOffsetY,int cellW);

    mapW和mapH是地图的宽高。

    mapOffsetX和mapOffsetY是开始设置网格的左下角坐标。

    cellW是每格的边长。

    通过网格下标设置阻挡

    mapGridData.SetBlockIdx(int blockIdx, bool isBlock);

    通过网格的xy坐标设置阻挡

    mapGridData.SetBlock(int cellx, int celly, bool isBlock)

     

    调用寻路算法,返回路径。

    List<JOIntV2>

    ajSearch.Search(int beginX, int beginY, int endX, int endY, JOMapGrid2DData mapData);

    其中beginX, beginY和endX, endY分别是寻路的开始和结束的网络坐标。

    mapData就是以上包括阻挡信息的数据。

    函数会返回List<JOIntV2>, 如果是null即此路不通, 找到即返回网络路径。

     

    也可以参考

    Demo/Scrips/DemoSceneBase中对JOMapGrid2D的设置处理。

    Demo/Scrips/MoveGO中对JOMapGrid2D和AJFindRoad 的调用。

     

    Unity Asset Store URL:

    https://assetstore.unity.com/packages/slug/142391

    展开全文
  • 因为破游戏准备设计敌人了,苦于Unity自带的导航系统迟迟不适配2D项目,即便用最新的NavMeshSurface把3D当成2D来用,也和我的想法背道而驰,资源商店里的又动不动几百块╮( ̄▽ ̄")╭,还没有试用功能,鬼知道能不能...

    被生活++了一个多月,都没时间上来吹比了。

    因为破游戏准备设计敌人了,苦于Unity自带的导航系统迟迟不适配2D项目,即便用最新的NavMeshSurface把3D当成2D来用,也和我的想法背道而驰,资源商店里的又动不动几百块╮( ̄▽ ̄")╭,还没有试用功能,鬼知道能不能融入我这破游戏的框架里。

    那就只能自己写一个寻路了,久闻A*算法大名,网上教程也挺多的,看了几篇之后,大致了解了基本内容,最后还上油管看了个视频,东拼西凑设计出来自己的A*,虽然性能甚至比不上官方的NavMesh,180个寻路单位在普通情况下每次寻路需要10ms~20ms,不过至少能在2D上用了。为了追求性能,我甚至研究了ECS框架和Job System,不过鉴于使用限制太大(只能操作值类型,反复开辟和回收空间对性能消耗来说太蛋疼了- . -),以我的水平写出来的寻路Job性能还没不用的好,最后放弃,不过还好学会怎么在Unity上用ECS框架管理游戏对象和用Jobs优化性能了。

    言归正传,A*的基本思路我也不扯了,浪费篇幅,随便度娘一下就可以了。

    A*是基于网格的,所以最先是弄一个AStarNode类来存储点信息,实现如下:

    public class AStarNode : IHeapItem<AStarNode>
    {
        public readonly Vector3 worldPosition;
        public readonly Vector2Int gridPosition;
        public readonly float height;
    
        public bool walkable;
        public AStarNode parent;
        public int connectionLabel;
    
        public int GCost { get; set; }
        public int HCost { get; set; }
        public int FCost { get { return GCost + HCost; } }
    
    
        public int HeapIndex { get; set; }
    
        public AStarNode(Vector3 position, int gridX, int gridY, float height)
        {
            worldPosition = position;
            gridPosition = new Vector2Int(gridX, gridY);
            this.height = height;
            walkable = true;
        }
    
        public int CalculateHCostTo(AStarNode other)
        {
            //使用曼哈顿距离
            int disX = Mathf.Abs(gridPosition.x - other.gridPosition.x);
            int disY = Mathf.Abs(gridPosition.y - other.gridPosition.y);
    
            if (disX > disY)
                return 14 * disY + 10 * (disX - disY) + Mathf.RoundToInt(Mathf.Abs(height - other.height));
            else return 14 * disX + 10 * (disY - disX) + Mathf.RoundToInt(Mathf.Abs(height - other.height));
        }
    
        public bool CanReachTo(AStarNode other)
        {
            return connectionLabel > 0 && connectionLabel == other.connectionLabel;
        }
    
        public int CompareTo(AStarNode other)
        {
            if (FCost < other.FCost || (FCost == other.FCost && HCost < other.HCost) || (FCost == other.FCost && HCost == other.HCost && height < other.height))
                return -1;
            else if (FCost == other.FCost && HCost == other.HCost && height == other.height) return 0;
            else return 1;
        }
    
        public static implicit operator Vector3(AStarNode self)
        {
            return self.worldPosition;
        }
    
        public static implicit operator Vector2(AStarNode self)
        {
            return self.worldPosition;
        }
    
        public static implicit operator bool(AStarNode self)
        {
            return self != null;
        }
    }
    

    其中,IHeapItem是栈元素接口,因为A*每轮需要从Open表里选一个距离最小的点出来,用堆排性能较好,接口内容如下:

    public interface IHeapItem<T> : IComparable<T>
    {
        int HeapIndex { get; set; }
    }

    相应的,用于排序的堆实现如下:

    public class Heap<T> where T : class, IHeapItem<T>
    {
        private readonly T[] items;
        private readonly int maxSize;
        private readonly HeapType heapType;
    
        public int Count { get; private set; }
    
        public Heap(int size, HeapType heapType = HeapType.MinHeap)
        {
            items = new T[size];
            maxSize = size;
            this.heapType = heapType;
        }
    
        public void Add(T item)
        {
            if (Count >= maxSize) return;
            item.HeapIndex = Count;
            items[Count] = item;
            Count++;
            SortUpForm(item);
        }
    
        public T RemoveRoot()
        {
            if (Count < 1) return default;
            T root = items[0];
            root.HeapIndex = -1;
            Count--;
            if (Count > 0)
            {
                items[0] = items[Count];
                items[0].HeapIndex = 0;
                SortDownFrom(items[0]);
            }
            return root;
        }
    
        public bool Contains(T item)
        {
            if (item == default || item.HeapIndex < 0 || item.HeapIndex > Count - 1) return false;
            return Equals(items[item.HeapIndex], item);//用items.Contains()就等着哭吧
        }
    
        public void Clear()
        {
            Count = 0;
        }
    
        private void SortUpForm(T item)
        {
            int parentIndex = (item.HeapIndex - 1) / 2;
            while (true)
            {
                T parent = items[parentIndex];
                if (Equals(parent, item)) return;
                if (heapType == HeapType.MinHeap ? item.CompareTo(parent) < 0 : item.CompareTo(parent) > 0)
                {
                    if (!Swap(item, parent))
                        return;//交换不成功则退出,防止死循环
                }
                else return;
                parentIndex = (item.HeapIndex - 1) / 2;
            }
        }
    
        private void SortDownFrom(T item)
        {
            while (true)
            {
                int leftChildIndex = item.HeapIndex * 2 + 1;
                int rightChildIndex = item.HeapIndex * 2 + 2;
                if (leftChildIndex < Count)
                {
                    int swapIndex = leftChildIndex;
                    if (rightChildIndex < Count && (heapType == HeapType.MinHeap ?
                        items[rightChildIndex].CompareTo(items[leftChildIndex]) < 0 : items[rightChildIndex].CompareTo(items[leftChildIndex]) > 0))
                        swapIndex = rightChildIndex;
                    if (heapType == HeapType.MinHeap ? items[swapIndex].CompareTo(item) < 0 : items[swapIndex].CompareTo(item) > 0)
                    {
                        if (!Swap(item, items[swapIndex]))
                            return;//交换不成功则退出,防止死循环
                    }
                    else return;
                }
                else return;
            }
        }
    
        public void Update()
        {
            if (Count < 1) return;
            SortDownFrom(items[0]);
            SortUpForm(items[Count - 1]);
        }
    
        private bool Swap(T item1, T item2)
        {
            if (!Contains(item1) || !Contains(item2)) return false;
            items[item1.HeapIndex] = item2;
            items[item2.HeapIndex] = item1;
            int item1Index = item1.HeapIndex;
            item1.HeapIndex = item2.HeapIndex;
            item2.HeapIndex = item1Index;
            return true;
        }
    
        public static implicit operator bool(Heap<T> self)
        {
            return self != null;
        }
    
        public enum HeapType
        {
            MinHeap,
            MaxHeap
        }
    }
    

    可以看到,因为堆需要排序更新Item的HeapIndex,所以值类型绝逼是不能用了,每次传递都是复制一份,在堆里改完了数据,怎么才能写回没加入堆前的原来的对象里?除非用指针,基于指针的用于管理结构体的Heap我也实现了,不过与此文无关,不贴上来了。

    接下来是算法的核心,我单独用一个AStar类来实现:

    public class AStar
    {
        public AStar(Vector2 worldSize, float cellSize, CastCheckType castCheckType, float castRadiusMultiple,
            LayerMask unwalkableLayer, LayerMask groundLayer, bool threeD, float worldHeight, int cellHeight, GoalSelectMode goalSelectMode)
        {
            this.worldSize = worldSize;
            this.cellSize = cellSize;
            this.castCheckType = castCheckType;
            this.castRadiusMultiple = castRadiusMultiple;
            this.unwalkableLayer = unwalkableLayer;
            this.groundLayer = groundLayer;
            this.threeD = threeD;
            this.worldHeight = worldHeight;
            this.cellHeight = cellHeight;
            this.goalSelectMode = goalSelectMode;
            GridSize = Vector2Int.RoundToInt(worldSize / cellSize);
            Grid = new AStarNode[Mathf.RoundToInt(GridSize.x), Mathf.RoundToInt(GridSize.y)];
            openCache = new Heap<AStarNode>(GridSize.x * GridSize.y);
            closedCache = new HashSet<AStarNode>();
            pathCache = new List<AStarNode>();
        }
    
        private readonly bool threeD;
        private readonly Vector2 worldSize;
        private readonly float worldHeight;
        private readonly LayerMask groundLayer;
        private readonly int cellHeight;
    
        private readonly float cellSize;
        public Vector2Int GridSize { get; private set; }
        public AStarNode[,] Grid { get; private set; }
    
        private readonly LayerMask unwalkableLayer;
        private readonly CastCheckType castCheckType;
        private readonly float castRadiusMultiple;
    
        private readonly GoalSelectMode goalSelectMode;
    
        #region 网格相关
        public void CreateGrid(Vector3 axisOrigin)
        {
            for (int i = 0; i < GridSize.x; i++)
                for (int j = 0; j < GridSize.y; j++)
                    CreateNode(axisOrigin, i, j);
            RefreshGrid();
        }
    
        private void CreateNode(Vector3 axisOrigin, int gridX, int gridY)
        {
            //Debug.Log(gridX + ":" + gridY);
            Vector3 nodeWorldPos;
            if (!threeD)
            {
                nodeWorldPos = axisOrigin + Vector3.right * (gridX + 0.5f) * cellSize + Vector3.up * (gridY + 0.5f) * cellSize;
            }
            else
            {
                nodeWorldPos = axisOrigin + Vector3.right * (gridX + 0.5f) * cellSize + Vector3.forward * (gridY + 0.5f) * cellSize;
                float height;
                if (Physics.Raycast(nodeWorldPos + Vector3.up * (worldHeight + 0.01f), Vector3.down, out RaycastHit hit, worldHeight + 0.01f, groundLayer))
                    height = hit.point.y;
                else height = worldHeight + 0.01f;
                nodeWorldPos += Vector3.up * height;
            }
            Grid[gridX, gridY] = new AStarNode(nodeWorldPos, gridX, gridY, threeD ? nodeWorldPos.y : 0);
        }
    
        public void RefreshGrid()
        {
            if (Grid == null) return;
            for (int i = 0; i < GridSize.x; i++)
                for (int j = 0; j < GridSize.y; j++)
                    CheckNodeWalkable(Grid[i, j]);
            CalculateConnections();
        }
    
        public void RefreshGrid(Vector3 fromPoint, Vector3 toPoint)
        {
            if (Grid == null) return;
            AStarNode fromNode = WorldPointToNode(fromPoint);
            AStarNode toNode = WorldPointToNode(toPoint);
            if (fromNode == toNode)
            {
                CheckNodeWalkable(fromNode);
                return;
            }
            AStarNode min = fromNode.gridPosition.x <= toNode.gridPosition.x && fromNode.gridPosition.y <= toNode.gridPosition.y ? fromNode : toNode;
            AStarNode max = fromNode.gridPosition.x > toNode.gridPosition.x && fromNode.gridPosition.y > toNode.gridPosition.y ? fromNode : toNode;
            fromNode = min;
            toNode = max;
            //Debug.Log(string.Format("From {0} to {1}", fromNode.GridPosition, toNode.GridPosition));
            if (toNode.gridPosition.x - fromNode.gridPosition.x <= toNode.gridPosition.y - fromNode.gridPosition.y)
                for (int i = fromNode.gridPosition.x; i <= toNode.gridPosition.x; i++)
                    for (int j = fromNode.gridPosition.y; j <= toNode.gridPosition.y; j++)
                        CheckNodeWalkable(Grid[i, j]);
            else for (int i = fromNode.gridPosition.y; i <= toNode.gridPosition.y; i++)
                    for (int j = fromNode.gridPosition.x; j <= toNode.gridPosition.x; j++)
                        CheckNodeWalkable(Grid[i, j]);
            CalculateConnections();
        }
    
        public AStarNode WorldPointToNode(Vector3 position)
        {
            if (Grid == null || (threeD && position.y > worldHeight)) return null;
            int gX = Mathf.RoundToInt((GridSize.x - 1) * Mathf.Clamp01((position.x + worldSize.x / 2) / worldSize.x));
            //gX怎么算:首先利用坐标系原点的 x 坐标来修正该点的 x 轴坐标,然后除以世界宽度,获得该点的 x 坐标在网格坐标系上所处的区域,用不大于 1 分数来表示,
            //然后获得相同区域的网格的 x 坐标即 gX,举个例子:
            //假设 x 坐标为 -2,而世界起点的 x 坐标为 -24, 即实际坐标原点 x 坐标 0 减去世界宽度的一半,则修正 x 坐标为 x + 24 = 22,这就是它在A*坐标系上虚拟的修正了的位置 x', 
            //以上得知世界宽度为48,那么 22 / 48 = 11/24,说明 x' 在世界宽度轴 11/24 的位置上,所以,该位置相应的格子的 x 坐标也在网格宽度轴的11/24位置上,
            //假设网格宽度为也为48,则 gX = 48 * 11/24 = 22,看似正确,其实,假设上面算得的 x' 是48,那么 48 * 48/48 = 48,而网格坐标最多到47,因为数组下标从0开始,
            //所以这时就会发生越界错误,反而用 gX = (48 - 1) * 48/48 = 47 * 1 = 47 来代替就对了,回过头来,x' 是 22,则 47 * 11/24 = 21.54 ≈ 22,位于 x' 轴左数第 23 个格子上,
            //再假设算出的 x' 是 30,则 gX = 47 * 15/24 = 29.38 ≈ 29,完全符合逻辑,为什么不用 48 算完再减去 1 ?如果 x' 是 0, 48 * 0/48 - 1 = -1,又越界了
            int gY;
            if (!threeD) gY = Mathf.RoundToInt((GridSize.y - 1) * Mathf.Clamp01((position.y + worldSize.y / 2) / worldSize.y));
            else gY = Mathf.RoundToInt((GridSize.y - 1) * Mathf.Clamp01((position.z + worldSize.y / 2) / worldSize.y));
            return Grid[gX, gY];
        }
    
        private bool CheckNodeWalkable(AStarNode node)
        {
            if (!node) return false;
            if (!threeD)
            {
                RaycastHit2D[] hit2Ds = new RaycastHit2D[0];
                switch (castCheckType)
                {
                    case CastCheckType.Box:
                        hit2Ds = Physics2D.BoxCastAll(node.worldPosition,
                            Vector2.one * cellSize * castRadiusMultiple * 2, 0, Vector2.zero, Mathf.Infinity, unwalkableLayer);
                        break;
                    case CastCheckType.Sphere:
                        hit2Ds = Physics2D.CircleCastAll(node.worldPosition,
                            cellSize * castRadiusMultiple, Vector2.zero, Mathf.Infinity, unwalkableLayer);
                        break;
                }
                node.walkable = hit2Ds.Length < 1 || hit2Ds.Where(h => !h.collider.isTrigger && h.collider.tag != "Player").Count() < 1;
            }
            else
            {
                RaycastHit[] hits = new RaycastHit[0];
                switch (castCheckType)
                {
                    case CastCheckType.Box:
                        hits = Physics.BoxCastAll(node.worldPosition, Vector3.one * cellSize * castRadiusMultiple,
                            Vector3.up, Quaternion.identity, (cellHeight - 1) * cellSize, unwalkableLayer, QueryTriggerInteraction.Ignore);
                        break;
                    case CastCheckType.Sphere:
                        hits = Physics.SphereCastAll(node.worldPosition, cellSize * castRadiusMultiple,
                            Vector3.up, (cellHeight - 1) * cellSize, unwalkableLayer, QueryTriggerInteraction.Ignore);
                        break;
                }
                node.walkable = node.height < worldHeight && (hits.Length < 1 || hits.Where(h => h.collider.tag != "Player").Count() < 1);
            }
            return node.walkable;
        }
    
        public bool WorldPointWalkable(Vector3 point)
        {
            return CheckNodeWalkable(WorldPointToNode(point));
        }
    
        private AStarNode GetClosestSurroundingNode(AStarNode node, AStarNode closestTo, int ringCount = 1)
        {
            var neighbours = GetSurroundingNodes(node, ringCount);
            if (ringCount >= Mathf.Max(GridSize.x, GridSize.y)) return null;//突破递归
            AStarNode closest = neighbours.FirstOrDefault(x => x.walkable);
            if (closest)
                using (var neighbourEnum = neighbours.GetEnumerator())
                {
                    while (neighbourEnum.MoveNext())
                        if (neighbourEnum.Current == closest) break;
                    while (neighbourEnum.MoveNext())
                    {
                        AStarNode neighbour = neighbourEnum.Current;
                        if (Vector3.Distance(closestTo.worldPosition, neighbour.worldPosition) < Vector3.Distance(closestTo.worldPosition, closest.worldPosition))
                            if (neighbour.walkable) closest = neighbour;
                    }
                }
            if (!closest) return GetClosestSurroundingNode(node, closestTo, ringCount + 1);
            else return closest;
        }
    
        private readonly List<AStarNode> neighbours = new List<AStarNode>();
        private List<AStarNode> GetSurroundingNodes(AStarNode node, int ringCount/*圈数*/)
        {
            neighbours.Clear();
            if (node != null && ringCount > 0)
            {
                int neiborX;
                int neiborY;
                for (int x = -ringCount; x <= ringCount; x++)
                    for (int y = -ringCount; y <= ringCount; y++)
                    {
                        if (Mathf.Abs(x) < ringCount && Mathf.Abs(y) < ringCount) continue;//对于圈内的结点,总有其x和y都小于圈数,所以依此跳过
    
                        neiborX = node.gridPosition.x + x;
                        neiborY = node.gridPosition.y + y;
    
                        if (neiborX >= 0 && neiborX < GridSize.x && neiborY >= 0 && neiborY < GridSize.y)
                            neighbours.Add(Grid[neiborX, neiborY]);
                    }
            }
            return neighbours;
        }
    
        private List<AStarNode> GetReachableNeighbours(AStarNode node)
        {
            neighbours.Clear();
            if (node != null)
            {
                int neiborX;
                int neiborY;
                for (int x = -1; x <= 1; x++)
                    for (int y = -1; y <= 1; y++)
                    {
                        if (x == 0 && y == 0) continue;
    
                        neiborX = node.gridPosition.x + x;
                        neiborY = node.gridPosition.y + y;
    
                        if (neiborX >= 0 && neiborX < GridSize.x && neiborY >= 0 && neiborY < GridSize.y)
                            if (Reachable(Grid[neiborX, neiborY]))
                                neighbours.Add(Grid[neiborX, neiborY]);
                    }
            }
            return neighbours;
    
            bool Reachable(AStarNode neighbour)
            {
                if (neighbour.gridPosition.x == node.gridPosition.x || neighbour.gridPosition.y == node.gridPosition.y) return neighbour.walkable;
                if (!neighbour.walkable) return false;
                if (neighbour.gridPosition.x > node.gridPosition.x && neighbour.gridPosition.y > node.gridPosition.y)//右上角
                {
                    int leftX = node.gridPosition.x;
                    int leftY = neighbour.gridPosition.y;
                    AStarNode leftNode = Grid[leftX, leftY];
                    if (leftNode.walkable)
                    {
                        int downX = neighbour.gridPosition.x;
                        int downY = node.gridPosition.y;
                        AStarNode downNode = Grid[downX, downY];
                        if (!downNode.walkable) return false;
                        else return true;
                    }
                    else return false;
                }
                else if (neighbour.gridPosition.x > node.gridPosition.x && neighbour.gridPosition.y < node.gridPosition.y)//右下角
                {
                    int leftX = node.gridPosition.x;
                    int leftY = neighbour.gridPosition.y;
                    AStarNode leftNode = Grid[leftX, leftY];
                    if (leftNode.walkable)
                    {
                        int upX = neighbour.gridPosition.x;
                        int upY = node.gridPosition.y;
                        AStarNode upNode = Grid[upX, upY];
                        if (!upNode.walkable) return false;
                        else return true;
                    }
                    else return false;
                }
                else if (neighbour.gridPosition.x < node.gridPosition.x && neighbour.gridPosition.y > node.gridPosition.y)//左上角
                {
                    int rightX = node.gridPosition.x;
                    int rightY = neighbour.gridPosition.y;
                    AStarNode rightNode = Grid[rightX, rightY];
                    if (rightNode.walkable)
                    {
                        int downX = neighbour.gridPosition.x;
                        int downY = node.gridPosition.y;
                        AStarNode downNode = Grid[downX, downY];
                        if (!downNode.walkable) return false;
                        else return true;
                    }
                    else return false;
                }
                else if (neighbour.gridPosition.x < node.gridPosition.x && neighbour.gridPosition.y < node.gridPosition.y)//左下角
                {
                    int rightX = node.gridPosition.x;
                    int rightY = neighbour.gridPosition.y;
                    AStarNode rightNode = Grid[rightX, rightY];
                    if (rightNode.walkable)
                    {
                        int upX = neighbour.gridPosition.x;
                        int upY = node.gridPosition.y;
                        AStarNode upNode = Grid[upX, upY];
                        if (!upNode.walkable) return false;
                        else return true;
                    }
                    else return false;
                }
                else return true;
            }
        }
    
        private bool CanGoStraight(Vector3 from, Vector3 to)
        {
            Vector3 dir = (to - from).normalized;
            float dis = Vector3.Distance(from, to);
            float checkRadius = cellSize * castRadiusMultiple;
            float radiusMultiple = 1;
            if (castCheckType == CastCheckType.Box)//根据角度确定两个端点的偏移量
            {
                float x, y, angle;
                if (!threeD)
                {
                    if (from.x < to.x)
                        angle = Vector2.Angle(Vector2.right.normalized, dir);
                    else
                        angle = Vector2.Angle(Vector2.left.normalized, dir);
                }
                else
                {
                    if (from.x < to.x)
                        angle = Vector3.Angle(Vector3.right.normalized, new Vector3(dir.x, 0, dir.z));
                    else
                        angle = Vector3.Angle(Vector3.left.normalized, new Vector3(dir.x, 0, dir.z));
                }
                if (angle < 45)
                {
                    x = 1;
                    y = Mathf.Tan(angle * Mathf.Deg2Rad);
                }
                else if (angle == 90)
                {
                    x = 0;
                    y = 1;
                }
                else
                {
                    y = 1;
                    x = 1 / Mathf.Tan(angle * Mathf.Deg2Rad);
                }
                radiusMultiple = Mathf.Sqrt(x * x + y * y);
            }
            if (!threeD)
            {
                bool hit = Physics2D.Raycast(from, dir, dis, unwalkableLayer);
                if (!hit)//射不中,则进行第二次检测
                {
                    float x1 = -dir.y / dir.x;
                    Vector3 point1 = from + new Vector3(x1, 1).normalized * checkRadius * radiusMultiple;
                    bool hit1 = Physics2D.Raycast(point1, dir, dis, unwalkableLayer);
                    if (!hit1)//射不中,进行第三次检测
                    {
                        float x2 = dir.y / dir.x;
                        Vector3 point2 = from + new Vector3(x2, -1).normalized * checkRadius * radiusMultiple;
                        bool hit2 = Physics2D.Raycast(point2, dir, dis, unwalkableLayer);
                        if (!hit2) return true;
                        else return false;
                    }
                    else return false;
                }
                else return false;
            }
            else
            {
                bool hit = Physics.Raycast(from, dir, dis, unwalkableLayer, QueryTriggerInteraction.Ignore);
                if (!hit)
                {
                    float x1 = -dir.z / dir.x;
                    Vector3 point1 = from + new Vector3(x1, 0, 1).normalized * checkRadius * radiusMultiple;//左边
                    bool hit1 = Physics.Raycast(point1, dir, dis, unwalkableLayer, QueryTriggerInteraction.Ignore);
                    if (!hit1)
                    {
                        float x2 = dir.z / dir.x;
                        Vector3 point2 = from + new Vector3(x2, 0, -1).normalized * checkRadius * radiusMultiple;//右边
                        bool hit2 = Physics.Raycast(point2, dir, dis, unwalkableLayer, QueryTriggerInteraction.Ignore);
                        if (!hit2)
                        {
                            float x3 = -dir.y / dir.x;
                            Vector3 point3 = from + new Vector3(x3, 1, 0).normalized * checkRadius;//底部
                            bool hit3 = Physics.Raycast(point3, dir, dis, unwalkableLayer, QueryTriggerInteraction.Ignore);
                            if (!hit3)
                            {
                                for (int i = 1; i <= cellHeight; i++)//上部
                                {
                                    float x4 = -dir.y / dir.x;
                                    Vector3 point4 = from + new Vector3(x4, -1, 0).normalized * (checkRadius * (1 + 2 * (i - 1)));
                                    bool hit4 = Physics.Raycast(point4, dir, dis, unwalkableLayer, QueryTriggerInteraction.Ignore);
                                    if (hit4) return false;
                                }
                                return true;
                            }
                            else return false;
                        }
                        else return false;
                    }
                    else return false;
                }
                else return false;
            }
        }
    
        private AStarNode GetEffectiveGoal(AStarNode startNode, AStarNode goalNode)
        {
            switch (goalSelectMode)
            {
                case GoalSelectMode.ByRing:
                    return GetEffectiveGoalByRing(startNode, goalNode);
                case GoalSelectMode.ByLine:
                    return GetEffectiveGoalByLine(startNode, goalNode);
                case GoalSelectMode.None:
                default:
                    return goalNode;
            }
        }
    
        private AStarNode GetEffectiveGoalByLine(AStarNode startNode, AStarNode goalNode)
        {
            AStarNode newGoalNode = null;
            int startNodeNodeX = startNode.gridPosition.x, startNodeY = startNode.gridPosition.y;
            int goalNodeX = goalNode.gridPosition.x, goalNodeY = goalNode.gridPosition.y;
            int xDistn = Mathf.Abs(goalNode.gridPosition.x - startNode.gridPosition.x);
            int yDistn = Mathf.Abs(goalNode.gridPosition.y - startNode.gridPosition.y);
            float deltaX, deltaY;
            if (xDistn >= yDistn)
            {
                deltaX = 1;
                deltaY = yDistn / (xDistn * 1.0f);
            }
            else
            {
                deltaY = 1;
                deltaX = xDistn / (yDistn * 1.0f);
            }
    
            bool CheckNodeReachable(float fX, float fY)
            {
                int gX = Mathf.RoundToInt(fX);
                int gY = Mathf.RoundToInt(fY);
                if (Grid[gX, gY].CanReachTo(startNode))
                {
                    newGoalNode = Grid[gX, gY];
                    return true;
                }
                else return false;
            }
    
            if (startNodeNodeX >= goalNodeX && startNodeY >= goalNodeY)//起点位于终点右上角
                for (float x = goalNodeX + deltaX, y = goalNodeY + deltaY; x <= startNodeNodeX && y <= startNodeY; x += deltaX, y += deltaY)
                {
                    if (CheckNodeReachable(x, y)) break;
                }
            else if (startNodeNodeX >= goalNodeX && startNodeY <= goalNodeY)//起点位于终点右下角
                for (float x = goalNodeX + deltaX, y = goalNodeY - deltaY; x <= startNodeNodeX && y >= startNodeY; x += deltaX, y -= deltaY)
                {
                    if (CheckNodeReachable(x, y)) break;
                }
            else if (startNodeNodeX <= goalNodeX && startNodeY >= goalNodeY)//起点位于终点左上角
                for (float x = goalNodeX - deltaX, y = goalNodeY + deltaY; x >= startNodeNodeX && y <= startNodeY; x -= deltaX, y += deltaY)
                {
                    if (CheckNodeReachable(x, y)) break;
                }
            else if (startNodeNodeX <= goalNodeX && startNodeY <= goalNodeY)//起点位于终点左下角
                for (float x = goalNodeX - deltaX, y = goalNodeY - deltaY; x >= startNodeNodeX && y >= startNodeY; x -= deltaX, y -= deltaY)
                {
                    if (CheckNodeReachable(x, y)) break;
                }
            return newGoalNode;
        }
    
        private AStarNode GetEffectiveGoalByRing(AStarNode startNode, AStarNode goalNode, int ringCount = 1)
        {
            var neighbours = GetSurroundingNodes(goalNode, ringCount);
            if (ringCount >= Mathf.Max(GridSize.x, GridSize.y)) return null;//突破递归
            AStarNode newGoalNode = neighbours.FirstOrDefault(x => x.CanReachTo(startNode));
            if (newGoalNode)
                using (var neighbourEnum = neighbours.GetEnumerator())
                {
                    while (neighbourEnum.MoveNext())
                        if (neighbourEnum.Current == newGoalNode) break;
                    while (neighbourEnum.MoveNext())
                    {
                        AStarNode neighbour = neighbourEnum.Current;
                        if (Vector3.Distance(goalNode.worldPosition, neighbour.worldPosition) < Vector3.Distance(goalNode.worldPosition, newGoalNode.worldPosition))
                            if (neighbour.CanReachTo(startNode)) newGoalNode = neighbour;
                    }
                }
            if (!newGoalNode) return GetEffectiveGoalByRing(startNode, goalNode, ringCount + 1);
            else return newGoalNode;
        }
        #endregion
    
        #region 路径相关
        private readonly Heap<AStarNode> openCache;
        private readonly HashSet<AStarNode> closedCache;
        private readonly List<AStarNode> pathCache;
    
        public void FindPath(PathRequest request, Action<PathResult> callback)
        {
            System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
            stopwatch.Start();
            AStarNode startNode = WorldPointToNode(request.start);
            AStarNode goalNode = WorldPointToNode(request.goal);
            if (startNode == null || goalNode == null)
            {
                stopwatch.Stop();
                callback(new PathResult(null, false, request.callback));
                return;
            }
    
            IEnumerable<Vector3> pathResult = null;
            bool findSuccessfully = false;
    
            if (!goalNode.walkable)
            {
                goalNode = GetClosestSurroundingNode(goalNode, startNode);
                if (goalNode == default)
                {
                    stopwatch.Stop();
                    callback(new PathResult(null, false, request.callback));
                    //Debug.Log("找不到合适的终点" + request.goal);
                    return;
                }
            }
            if (!startNode.walkable)
            {
                startNode = GetClosestSurroundingNode(startNode, goalNode);
                if (startNode == default)
                {
                    stopwatch.Stop();
                    callback(new PathResult(null, false, request.callback));
                    //Debug.Log("找不到合适的起点" + request.start);
                    return;
                }
            }
            if (startNode == goalNode)
            {
                stopwatch.Stop();
                callback(new PathResult(null, false, request.callback));
                //Debug.Log("起始相同");
                return;
            }
            if (!startNode.CanReachTo(goalNode))
            {
                goalNode = GetEffectiveGoal(startNode, goalNode);
                if (!goalNode || !startNode.CanReachTo(goalNode))
                {
                    stopwatch.Stop();
                    //Debug.Log("检测到目的地不可到达");
                    callback(new PathResult(pathResult, false, request.callback));
                    return;
                }
            }
    
            if (CanGoStraight(startNode, goalNode))
            {
                findSuccessfully = true;
                pathResult = new Vector3[] { goalNode };
                stopwatch.Stop();
                //Debug.Log("耗时 " + stopwatch.ElapsedMilliseconds + "ms,通过直走找到路径");
            }
    
            if (!findSuccessfully)
            {
                openCache.Clear();
                closedCache.Clear();
                openCache.Add(startNode);
                while (openCache.Count > 0)
                {
                    AStarNode current = openCache.RemoveRoot();
                    if (current == default || current == null)
                    {
                        callback(new PathResult(null, false, request.callback));
                        return;
                    }
                    closedCache.Add(current);
                    if (current == goalNode)
                    {
                        findSuccessfully = true;
                        stopwatch.Stop();
                        //Debug.Log("耗时 " + stopwatch.ElapsedMilliseconds + "ms,通过搜索 " + closedList.Count + " 个结点找到路径");
                        break;
                    }
    
                    using (var nodeEnum = GetReachableNeighbours(current).GetEnumerator())
                        while (nodeEnum.MoveNext())
                        {
                            AStarNode neighbour = nodeEnum.Current;
                            if (!neighbour.walkable || closedCache.Contains(neighbour)) continue;
                            int costStartToNeighbour = current.GCost + current.CalculateHCostTo(neighbour);
                            if (costStartToNeighbour < neighbour.GCost || !openCache.Contains(neighbour))
                            {
                                neighbour.GCost = costStartToNeighbour;
                                neighbour.HCost = neighbour.CalculateHCostTo(goalNode);
                                neighbour.parent = current;
                                if (!openCache.Contains(neighbour))
                                    openCache.Add(neighbour);
                                else openCache.Update();
                            }
                        }
                }
                if (!findSuccessfully)
                {
                    stopwatch.Stop();
                    //Debug.Log("耗时 " + stopwatch.ElapsedMilliseconds + "ms,搜索 " + closedList.Count + " 个结点后找不到路径");
                }
                else
                {
                    stopwatch.Start();
                    AStarNode pathNode = goalNode;
                    pathCache.Clear();
                    while (pathNode != startNode)
                    {
                        pathCache.Add(pathNode);
                        AStarNode temp = pathNode;
                        pathNode = pathNode.parent;
                        temp.parent = null;
                        temp.HeapIndex = -1;
                    }
                    pathResult = GetWaypoints(pathCache);
                    stopwatch.Stop();
                    //Debug.Log("耗时 " + stopwatch.ElapsedMilliseconds + "ms,通过搜索 " + closedList.Count + " 个结点后取得实际路径");
                }
            }
            callback(new PathResult(pathResult, findSuccessfully, request.callback));
        }
    
        public bool TryGetPath(Vector3 start, Vector3 goal, out IEnumerable<Vector3> pathResult)
        {
            //略
        }
    
        public bool TryGetPath(Vector3 start, Vector3 goal)
        {
            //略
        }
    
        private List<Vector3> GetWaypoints(List<AStarNode> path)
        {
            List<Vector3> waypoints = new List<Vector3>();
            if (path.Count < 1) return waypoints;
            PathToWaypoints();
            StraightenPath();
            waypoints.Reverse();
            return waypoints;
    
            void PathToWaypoints(bool simplify = true)
            {
                if (simplify)
                {
                    Vector2 oldDir = Vector3.zero;
                    for (int i = 1; i < path.Count; i++)
                    {
                        Vector2 newDir = path[i - 1].gridPosition - path[i].gridPosition;
                        if (newDir != oldDir)//方向不一样时才使用前面的点
                            waypoints.Add(path[i - 1]);
                        else if (i == path.Count - 1) waypoints.Add(path[i]);//即使方向一样,也强制把起点也加进去
                        oldDir = newDir;
                    }
                }
                else foreach (AStarNode node in path)
                        waypoints.Add(node);
            }
    
            void StraightenPath()
            {
                if (waypoints.Count < 1) return;
                //System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
                //stopwatch.Start();
                List<Vector3> toRemove = new List<Vector3>();
                Vector3 from = waypoints[0];
                for (int i = 2; i < waypoints.Count; i++)
                    if (CanGoStraight(from, waypoints[i]))
                        toRemove.Add(waypoints[i - 1]);
                    else from = waypoints[i - 1];
                foreach (Vector3 point in toRemove)
                    waypoints.Remove(point);
                //stopwatch.Stop();
                //Debug.Log("移除 " + toRemove.Count + " 个导航点完成路径直化");
            }
        }
        #endregion
    
        #region 四邻域连通检测算法
        private readonly Dictionary<int, HashSet<AStarNode>> Connections = new Dictionary<int, HashSet<AStarNode>>();
    
        private void CalculateConnections()
        {
            Connections.Clear();//重置连通域字典
    
            int[,] gridData = new int[GridSize.x, GridSize.y];
    
            for (int x = 0; x < GridSize.x; x++)
                for (int y = 0; y < GridSize.y; y++)
                    if (Grid[x, y].walkable) gridData[x, y] = 1;//大于0表示可行走
                    else gridData[x, y] = 0;//0表示有障碍
    
            int label = 1;
            for (int y = 0; y < GridSize.y; y++)//从下往上扫
            {
                for (int x = 0; x < GridSize.x; x++)//从左往右扫
                {
                    //若该数据的标记不为0,即该数据表示的位置没有障碍
                    if (gridData[x, y] != 0)
                    {
                        int labelNeedToChange = 0;//记录需要更改的标记
                        if (y == 0)//第一行,只用看当前数据点的左边
                        {
                            //若该点是第一行第一个,前面已判断不为0,直接标上标记
                            if (x == 0)
                            {
                                gridData[x, y] = label;
                                label++;
                            }
                            else if (gridData[x - 1, y] != 0)//若该点的左侧数据的标记不为0,那么当前数据的标记标为左侧的标记,表示同属一个连通域
                                gridData[x, y] = gridData[x - 1, y];
                            else//否则,标上新标记
                            {
                                gridData[x, y] = label;
                                label++;
                            }
                        }
                        else if (x == 0)//网格最左边,不可能出现与左侧形成衔接的情况
                        {
                            if (gridData[x, y - 1] != 0) gridData[x, y] = gridData[x, y - 1]; //若下方数据不为0,则当前数据标上下方标记的标记
                            else
                            {
                                gridData[x, y] = label;
                                label++;
                            }
                        }
                        else if (gridData[x, y - 1] != 0)//若下方标记不为0
                        {
                            gridData[x, y] = gridData[x, y - 1];//则用下方标记来标记当前数据
                            if (gridData[x - 1, y] != 0) labelNeedToChange = gridData[x - 1, y]; //若左方数据不为0,则被左方标记所标记的数据都要更改
                        }
                        else if (gridData[x - 1, y] != 0)//若左侧不为0
                            gridData[x, y] = gridData[x - 1, y];//则用左侧标记来标记当前数据
                        else
                        {
                            gridData[x, y] = label;
                            label++;
                        }
    
                        if (!Connections.ContainsKey(gridData[x, y])) Connections.Add(gridData[x, y], new HashSet<AStarNode>());
                        Connections[gridData[x, y]].Add(Grid[x, y]);
                        //将对应网格结点的连通域标记标为当前标记
                        Grid[x, y].connectionLabel = gridData[x, y];
                        //Struct.Grid.CoverOrInsert(x, y, Grid[x, y].Structed);//更新结构体
    
                        //如果有需要更改的标记,且其与当前标记不同
                        if (labelNeedToChange > 0 && labelNeedToChange != gridData[x, y])
                        {
                            foreach (AStarNode node in Connections[labelNeedToChange])//把对应连通域合并到当前连通域
                            {
                                gridData[node.gridPosition.x, node.gridPosition.y] = gridData[x, y];
                                Connections[gridData[x, y]].Add(node);
                                node.connectionLabel = gridData[x, y];
                                //Struct.Grid.CoverOrInsert(x, y, node.Structed);
                            }
                            Connections[labelNeedToChange].Clear();
                            Connections.Remove(labelNeedToChange);
                        }
                    }
                }
            }
        }
    
        private bool ACanReachB(AStarNode nodeA, AStarNode nodeB)
        {
            if (!nodeA || !nodeB) return false;
            var first = Connections.FirstOrDefault(x => x.Value.Contains(nodeA));
            if (default(KeyValuePair<string, AStarNode>).Equals(first)) return false;
            var second = Connections.FirstOrDefault(x => x.Value.Contains(nodeB));
            if (default(KeyValuePair<string, AStarNode>).Equals(second)) return false;
            return first.Key == second.Key;
        }
        #endregion
    
        public static implicit operator bool(AStar self)
        {
            return self != null;
        }
    }
    

    该类的核心是FindPath()算法,通过传入一个寻路请求和寻路回调来计算和反馈路径,而拓展方法TryGetPath()则可有可无,我也不贴上来了,复制粘贴前者稍改一下就行了。FindPath()开头,首先检查起点和终点是否都是可行走的,如果不行就都换个有效的。由于基本A*算法存在一个致命性的弱点,那就是当终点被封闭空间包围时,算法会搜索所有结点来寻找路径,却找不到可用路径,极其浪费资源,为了解决这个情况,我想到了用连通域来检查起点和终点是否连通,如果不连通,说明起点或终点是被包围起来了的,所以用到了四邻域联通检测算法CalculateConnections(),给同个连通域的结点标识一样的连通域编号,所以当两个结点的连通域编号一样时,互相可达,反之就不行。所以,在寻路算法的接下来一步,用一个CanReachTo()来检查连通性,如果不能连通,则根据自己的选择,退出算法或再另找一个有效可达的终点。再下去,检查起点可否直走到终点,如果可以就不用浪费时间去计算路径了,直接过去就行了。起点和终点的处理就到此为止了,接下来就是A*算法的基本内容了,没什么好解释的。

    其中,寻路请求和回馈都是结构体,如下:

    public struct PathRequest
    {
        public readonly Vector3 start;
        public readonly Vector3 goal;
        public readonly Vector2Int unitSize;
        public readonly Action<IEnumerable<Vector3>, bool> callback;
    
        public PathRequest(Vector3 start, Vector3 goal, Vector2Int unitSize, Action<IEnumerable<Vector3>, bool> callback)
        {
            this.start = start;
            this.goal = goal;
            this.unitSize = unitSize;
            this.callback = callback;
        }
    }
    
    public struct PathResult
    {
        public readonly IEnumerable<Vector3> waypoints;
        public readonly bool findSuccessfully;
        public readonly Action<IEnumerable<Vector3>, bool> callback;
    
        public PathResult(IEnumerable<Vector3> waypoints, bool findSuccessfully, Action<IEnumerable<Vector3>, bool> callback)
        {
            this.waypoints = waypoints;
            this.findSuccessfully = findSuccessfully;
            this.callback = callback;
        }
    }
    

    到此,已经完成大半内容了,这时候就要用一个mono来处理请求和反馈,我管这玩意儿叫AStarManager,实现如下:

    public class AStarManager : MonoBehaviour
    {
        private static AStarManager instance;
        public static AStarManager Instance
        {
            get
            {
                if (!instance || !instance.gameObject)
                    instance = FindObjectOfType<AStarManager>();
                return instance;
            }
        }
    
        #region Gizmos相关
        [SerializeField]
        private bool gizmosEdge = true;
        [SerializeField]
        private Color edgeColor = Color.white;
    
        [SerializeField]
        private bool gizmosGrid = true;
        [SerializeField]
        private Color gridColor = new Color(Color.white.r, Color.white.g, Color.white.b, 0.15f);
    
        [SerializeField]
        private bool gizmosCast = true;
        [SerializeField]
        private Color castColor = new Color(Color.white.r, Color.white.g, Color.white.b, 0.1f);
        #endregion
    
        [SerializeField, Tooltip("长和宽都推荐使用2的幂数")]
        private Vector2 worldSize = new Vector2(48, 48);
    
        [SerializeField]
        private bool threeD;
        public bool ThreeD
        {
            get
            {
                return threeD;
            }
        }
    
        [SerializeField, Range(0.2f, 2f)]
        private float baseCellSize = 1;
        public float BaseCellSize
        {
            get
            {
                return baseCellSize;
            }
        }
    
        [SerializeField]
        private float worldHeight = 20.0f;
    
        [SerializeField]
        private LayerMask groundLayer = ~0;
    
        [SerializeField, Tooltip("以单元格倍数为单位,至少是 1 倍,2D空间下 Y 数值无效")]
        private Vector2Int[] unitSizes;
    
        [SerializeField]
        private LayerMask unwalkableLayer = ~0;
        public LayerMask UnwalkableLayer
        {
            get
            {
                return unwalkableLayer;
            }
        }
    
        [SerializeField, Tooltip("以单元格倍数为单位"), Range(0.25f, 0.5f)]
        private float castRadiusMultiple = 0.5f;
    
        [SerializeField]
    #if UNITY_EDITOR
        [EnumMemberNames("方形[精度较低]", "球形[性能较低]")]
    #endif
        private CastCheckType castCheckType = CastCheckType.Box;
    
        [SerializeField, Tooltip("当终点无法到达时,如何选取近似有效终点?")]
    #if UNITY_EDITOR
        [EnumMemberNames("不选取", "按圈选取", "直线选取")]
    #endif
        private GoalSelectMode goalSelectMode = GoalSelectMode.ByRing;
    
        #region 实时变量
        public Dictionary<Vector2Int, AStar> AStars { get; private set; } = new Dictionary<Vector2Int, AStar>();
    
        private readonly Queue<PathResult> results = new Queue<PathResult>();
        #endregion
    
        #region 网格相关
        public AStar GetAStar(Vector2Int unitSize)
        {
            if (unitSize.x < 1 || unitSize.y < 1) return null;
            if (!AStars.ContainsKey(unitSize))
            {
                CreateAStar(unitSize);
            }
            AStars[unitSize].RefreshGrid();
            return AStars[unitSize];
        }
    
        private void CreateAStars()
        {
            foreach (Vector2Int unitSize in unitSizes)
                CreateAStar(unitSize);
        }
    
        public void CreateAStar(Vector2Int unitSize)
        {
            if (unitSize.x < 1 || unitSize.y < 1 || AStars.ContainsKey(unitSize)) return;
            //System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
            //stopwatch.Start();
    
            Vector3 axisOrigin;
            if (!ThreeD)
                axisOrigin = new Vector3(Mathf.RoundToInt(transform.position.x), Mathf.RoundToInt(transform.position.y), 0)
                    - Vector3.right * (worldSize.x / 2) - Vector3.up * (worldSize.y / 2);
            else
                axisOrigin = new Vector3Int(Mathf.RoundToInt(transform.position.x), 0, Mathf.RoundToInt(transform.position.z))
                    - Vector3.right * (worldSize.x / 2) - Vector3.forward * (worldSize.y / 2);
    
            AStar AStar = new AStar(worldSize, BaseCellSize * unitSize.x, castCheckType, castRadiusMultiple, UnwalkableLayer, groundLayer,
                                   ThreeD, worldHeight, unitSize.y, goalSelectMode);
            AStar.CreateGrid(axisOrigin);
            AStars.Add(unitSize, AStar);
    
            //stopwatch.Stop();
            //Debug.Log("为规格为 " + unitSize + " 的单位建立寻路基础,耗时 " + stopwatch.ElapsedMilliseconds + "ms");
        }
    
        public void UpdateAStars()
        {
            foreach (AStar AStar in AStars.Values)
            {
                AStar.RefreshGrid();
            }
        }
    
        public void UpdateAStars(Vector3 fromPoint, Vector3 toPoint)
        {
            foreach (AStar AStar in AStars.Values)
            {
                AStar.RefreshGrid(fromPoint, toPoint);
            }
        }
    
        public void UpdateAStar(Vector2Int unitSize)
        {
            if (unitSize.x < 1 || unitSize.y < 1 || !AStars.ContainsKey(unitSize)) return;
            AStars[unitSize].RefreshGrid();
        }
    
        public void UpdateAStar(Vector3 fromPoint, Vector3 toPoint, Vector2Int unitSize)
        {
            if (unitSize.x < 1 || unitSize.y < 1 || !AStars.ContainsKey(unitSize)) return;
            AStars[unitSize].RefreshGrid(fromPoint, toPoint);
        }
    
        public AStarNode WorldPointToNode(Vector3 position, Vector2Int unitSize)
        {
            if (unitSize.x < 1 || unitSize.y < 1) return null;
            if (!AStars.ContainsKey(unitSize))
            {
                CreateAStar(unitSize);
            }
            return AStars[unitSize].WorldPointToNode(position);
        }
    
        public bool WorldPointWalkable(Vector3 point, Vector2Int unitSize)
        {
            if (unitSize.x < 1 || unitSize.y < 1) return false;
            if (!AStars.ContainsKey(unitSize))
            {
                CreateAStar(unitSize);
            }
            return AStars[unitSize].WorldPointWalkable(point);
        }
        #endregion
    
        #region 路径相关
        public bool TryGetPath(Vector3 startPos, Vector3 goalPos, Vector2Int unitSize)
        {
            if (unitSize.x < 1 || unitSize.y < 1)
            {
                return false;
            }
            if (!AStars.ContainsKey(unitSize))
            {
                CreateAStar(unitSize);
            }
            return AStars[unitSize].TryGetPath(startPos, goalPos);
        }
    
        public bool TryGetPath(Vector3 startPos, Vector3 goalPos, out IEnumerable<Vector3> pathResult, Vector2Int unitSize)
        {
            if (unitSize.x < 1 || unitSize.y < 1)
            {
                pathResult = null;
                return false;
            }
            if (!AStars.ContainsKey(unitSize))
            {
                CreateAStar(unitSize);
            }
            return AStars[unitSize].TryGetPath(startPos, goalPos, out pathResult);
        }
    
        public void RequestPath(PathRequest request)
        {
            if (!AStars.ContainsKey(request.unitSize))
            {
                CreateAStar(request.unitSize);
            }
            lock (AStars[request.unitSize])
                ((ThreadStart)delegate
                {
                    AStars[request.unitSize].FindPath(request, GetResult);
                }).Invoke();
        }
    
        public void GetResult(PathResult result)
        {
            lock (results)
            {
                results.Enqueue(result);
            }
        }
        #endregion
    
        #region MonoBehaviour
        private void Awake()
        {
            CreateAStars();
            StarCoroutine(HandlingResults());
        }
    
        private IEnumerator HandlingResults()
        {
            while(true)
            {
                if (results.Count > 0)
                {
                    int resultsCount = results.Count;
                    lock (results)
                        for (int i = 0; i < resultsCount; i++)
                        {
                            PathResult result = results.Dequeue();
                            result.callback(result.waypoints, result.findSuccessfully);
                        }
                }
                yield return null;
            }
        }
    
        private void OnDrawGizmos()
        {
            if (gizmosGrid)
            {
                if (AStars != null && AStars.ContainsKey(Vector2Int.one))
                {
                    AStarNode[,] Grid = AStars[Vector2Int.one].Grid;
                    for (int x = 0; x < AStars[Vector2Int.one].GridSize.x; x++)
                        for (int y = 0; y < AStars[Vector2Int.one].GridSize.y; y++)
                        {
                            Gizmos.color = gridColor;
                            if (!Grid[x, y].walkable)
                            {
                                Gizmos.color = new Color(Color.red.r, Color.red.g, Color.red.b, gridColor.a);
                                Gizmos.DrawCube(Grid[x, y], ThreeD ? Vector3.one : new Vector3(1, 1, 0) * BaseCellSize * 0.95f);
                            }
                            else if (!ThreeD) Gizmos.DrawWireCube(Grid[x, y], new Vector3(1, 1, 0) * BaseCellSize);
                            else Gizmos.DrawCube(Grid[x, y], Vector3.one * BaseCellSize * 0.95f);
                            if (gizmosCast)
                            {
                                Gizmos.color = castColor;
                                if (castCheckType == CastCheckType.Sphere) Gizmos.DrawWireSphere(Grid[x, y], BaseCellSize * castRadiusMultiple);
                                else Gizmos.DrawWireCube(Grid[x, y], Vector3.one * BaseCellSize * castRadiusMultiple * 2);
                            }
                        }
                }
                else
                {
                    Vector2Int gridSize = Vector2Int.RoundToInt(worldSize / BaseCellSize);
                    Vector3 nodeWorldPos;
                    Vector3 axisOrigin;
                    if (!ThreeD)
                        axisOrigin = new Vector3(Mathf.RoundToInt(transform.position.x), Mathf.RoundToInt(transform.position.y), 0)
                            - Vector3.right * (worldSize.x / 2) - Vector3.up * (worldSize.y / 2);
                    else
                        axisOrigin = new Vector3Int(Mathf.RoundToInt(transform.position.x), 0, Mathf.RoundToInt(transform.position.z))
                            - Vector3.right * (worldSize.x / 2) - Vector3.forward * (worldSize.y / 2);
    
                    for (int x = 0; x < gridSize.x; x++)
                        for (int y = 0; y < gridSize.y; y++)
                        {
                            Gizmos.color = gridColor;
                            if (!ThreeD)
                            {
                                nodeWorldPos = axisOrigin + Vector3.right * (x + 0.5f) * BaseCellSize + Vector3.up * (y + 0.5f) * BaseCellSize;
                                Gizmos.DrawWireCube(nodeWorldPos, new Vector3(1, 1, 0) * BaseCellSize);
                            }
                            else
                            {
                                nodeWorldPos = axisOrigin + Vector3.right * (x + 0.5f) * BaseCellSize + Vector3.forward * (y + 0.5f) * BaseCellSize;
                                float height;
                                if (Physics.Raycast(nodeWorldPos + Vector3.up * (worldHeight + 0.01f), Vector3.down, out RaycastHit hit, worldHeight + 0.01f, groundLayer))
                                    height = hit.point.y;
                                else height = worldHeight + 0.01f;
                                if (height > worldHeight) Gizmos.color = new Color(Color.red.r, Color.red.g, Color.red.b, gridColor.a);
                                nodeWorldPos += Vector3.up * height;
                                Gizmos.DrawCube(nodeWorldPos, Vector3.one * BaseCellSize * 0.95f);
                            }
                            if (gizmosCast)
                            {
                                Gizmos.color = castColor;
                                if (castCheckType == CastCheckType.Sphere) Gizmos.DrawWireSphere(nodeWorldPos, BaseCellSize * castRadiusMultiple);
                                else Gizmos.DrawWireCube(nodeWorldPos, Vector3.one * BaseCellSize * castRadiusMultiple * 2);
                            }
                        }
                }
            }
            if (gizmosEdge)
            {
                Gizmos.color = edgeColor;
                if (ThreeD) Gizmos.DrawWireCube(transform.position + Vector3.up * worldHeight / 2, new Vector3(worldSize.x, worldHeight, worldSize.y));
                else Gizmos.DrawWireCube(transform.position, new Vector3(worldSize.x, worldSize.y, 0));
            }
        }
        #endregion
    }
    

    这个类实际内容没有多少,也没什么值得解释的地方,只是Gizmos浪费了大量篇幅罢了。因为寻路网格没有必要实时更新,所以提供了UpdateXXX()方法来根据需要更新,比如说在场景上新创建了一个新的碰撞器,就需要更新一下了。稍微自定义了一下这个mono的检视器,成品是这样了:

    有了寻路算法,就需要一个类似NavMeshAgent的组件来就行寻路,我起名叫AStarUnit,实现如下:

    public class AStarUnit : MonoBehaviour
    {
        [SerializeField, Tooltip("以单元格倍数为单位,至少是 1 倍,2D空间下 Y 数值无效")]
        private Vector2Int unitSize = Vector2Int.one;
        [SerializeField]
        private Vector3 footOffset;
        [SerializeField, Tooltip("位置近似范围半径,最小建议值为0.1")]
        private float fixedOffset = 0.125f;
    
        [SerializeField]
        private Transform target;
        [SerializeField]
        private Vector3 targetFootOffset;
        [SerializeField, Tooltip("目标离开原位置多远之后开始修正跟随?")]
        private float targetFollowStartDistance = 5;
    
    
        [SerializeField]
    #if UNITY_EDITOR
        [EnumMemberNames("普通位移(推荐)[物理效果差]", "刚体位移[性能消耗高]", "控制器位移")]
    #endif
        private UnitMoveMode moveMode = UnitMoveMode.MovePosition;
        [SerializeField]
        private new Rigidbody rigidbody;
        [SerializeField]
        private new Rigidbody2D rigidbody2D;
        [SerializeField]
        private CharacterController controller;
    
        public float moveSpeed = 10f;
        public float turnSpeed = 10f;
        [SerializeField]
        private float slopeLimit = 45.0f;
        [SerializeField]
        public float stopDistance = 1;
        [SerializeField]
        public bool autoRepath = true;
    
        [SerializeField]
        private LineRenderer pathRenderer;
    
        [SerializeField]
        private Animator animator;
        [SerializeField]
        private string animaHorizontal = "Horizontal";
        [SerializeField]
        private string animaVertical = "Vertical";
        [SerializeField]
        private string animaMagnitude = "Move";
    
        [SerializeField]
        private bool drawGizmos;
    
        #region 实时变量
        private Vector3[] path;
        private int targetWaypointIndex;
        private Vector3 oldPosition;
    
        private bool isFollowingPath;
        public bool IsFollowingPath
        {
            get => isFollowingPath;
            set
            {
                bool origin = isFollowingPath;
                isFollowingPath = value;
                if (!origin && isFollowingPath) StartFollowingPath();
                else if (origin && !isFollowingPath)
                {
                    if (pathFollowCoroutine != null) StopCoroutine(pathFollowCoroutine);
                    pathFollowCoroutine = null;
                }
            }
        }
    
        private Coroutine pathFollowCoroutine;
    
        private bool isFollowingTarget;
        public bool IsFollowingTarget
        {
            get => isFollowingTarget;
            set
            {
                bool origin = isFollowingTarget;
                isFollowingTarget = value;
                if (!origin && isFollowingTarget) StartFollowingTarget();
                else if (origin && !isFollowingTarget)
                {
                    if (targetFollowCoroutine != null) StopCoroutine(targetFollowCoroutine);
                    targetFollowCoroutine = null;
                    IsFollowingPath = false;
                }
            }
        }
    
        private Coroutine targetFollowCoroutine;
    
        private Vector3 gizmosTargetPos = default;
    
        public bool HasPath
        {
            get
            {
                return path != null && path.Length > 0;
            }
        }
    
        public bool IsStop => DesiredVelocity.magnitude == 0;
    
        public Vector3 OffsetPosition
        {
            get { return transform.position + footOffset; }
            private set { transform.position = value - footOffset; }
        }
    
        public Vector3 TargetPosition
        {
            get
            {
                if (target)
                    return target.position + targetFootOffset;
                return OffsetPosition;
            }
        }
    
        public Vector3 DesiredVelocity//类似于NavMeshAgent.desiredVelocity
        {
            get
            {
                if (path == null || path.Length < 1)
                {
                    return Vector3.zero;
                }
                if (targetWaypointIndex >= 0 && targetWaypointIndex < path.Length)
                {
                    Vector3 targetWaypoint = path[targetWaypointIndex];
                    if (!IsFollowingPath && OffsetPosition.x >= targetWaypoint.x - fixedOffset && OffsetPosition.x <= targetWaypoint.x + fixedOffset
                        && (AStarManager.Instance.ThreeD ? true : OffsetPosition.y >= targetWaypoint.y - fixedOffset && OffsetPosition.y <= targetWaypoint.y + fixedOffset)
                        && (AStarManager.Instance.ThreeD ? OffsetPosition.z >= targetWaypoint.z - fixedOffset && OffsetPosition.z <= targetWaypoint.z + fixedOffset : true))
                    //因为多数情况无法准确定位,所以用近似值表示达到目标航点
                    {
                        targetWaypointIndex++;
                        if (targetWaypointIndex >= path.Length) return Vector3.zero;
                        if (autoRepath)
                            if (!AStarManager.Instance.WorldPointWalkable(path[targetWaypointIndex], unitSize))
                                RequestPath(Destination);
                    }
                    if (targetWaypointIndex < path.Length)
                    {
                        if (AStarManager.Instance.ThreeD && MyUtilities.Slope(transform.position, path[targetWaypointIndex]) > slopeLimit)
                            return Vector3.zero;
                        if (Vector3.Distance(OffsetPosition, Destination) <= stopDistance)
                        {
                            ResetPath();
                            return Vector3.zero;
                        }
                        return (path[targetWaypointIndex] - OffsetPosition).normalized * moveSpeed;
                    }
                }
                return Vector3.zero;
            }
        }
    
        public Vector3 Velocity => IsFollowingTarget || IsFollowingPath ? (OffsetPosition - oldPosition).normalized * moveSpeed : Vector3.zero;
    
        private Vector3 Destination
        {
            get
            {
                if (path == null || path.Length < 1) return OffsetPosition;
                return path[path.Length - 1];
            }
        }
        #endregion
    
        #region MonoBehaviour
        private void Awake()
        {
            if (controller && moveMode == UnitMoveMode.MoveController) controller.slopeLimit = slopeLimit;
            ShowPath(false);
        }
    
        private void Start()
        {
            //Debug only
            SetTarget(target, targetFootOffset, true);
        }
    
        private void Update()
        {
            if (pathRenderer && path != null && path.Length > 0)
            {
                LinkedList<Vector3> leftPoint = new LinkedList<Vector3>(path.Skip(targetWaypointIndex).ToArray());
                leftPoint.AddFirst(OffsetPosition);
                pathRenderer.positionCount = leftPoint.Count;
                pathRenderer.SetPositions(leftPoint.ToArray());
                if (Vector3.Distance(OffsetPosition, Destination) < stopDistance) ShowPath(false);
            }
            if (animator)
            {
                Vector3 animaInput = DesiredVelocity.normalized;
                if (animaInput.magnitude > 0)
                {
                    animator.SetFloat(animaHorizontal, animaInput.x);
                    animator.SetFloat(animaVertical, animaInput.y);
                }
                animator.SetFloat(animaMagnitude, animaInput.magnitude);
            }
        }
    
        private void LateUpdate()
        {
            oldPosition = OffsetPosition;
        }
    
        private void OnEnable()
        {
            if (!AStarManager.Instance) enabled = false;
            oldPosition = OffsetPosition;
        }
    
        private void OnDrawGizmos()
        {
            if (drawGizmos)
            {
                if (path != null)
                    for (int i = targetWaypointIndex; i >= 0 && i < path.Length; i++)
                    {
                        if (i != path.Length - 1) Gizmos.color = new Color(Color.cyan.r, Color.cyan.g, Color.cyan.b, 0.5f);
                        else Gizmos.color = new Color(Color.green.r, Color.green.g, Color.green.b, 0.5f);
                        Gizmos.DrawSphere(path[i], 0.25f);
    
                        if (i == targetWaypointIndex)
                            Gizmos.DrawLine(OffsetPosition, path[i]);
                        else Gizmos.DrawLine(path[i - 1], path[i]);
                    }
                if (gizmosTargetPos != default && AStarManager.Instance)
                {
                    Gizmos.color = new Color(Color.black.r, Color.black.g, Color.black.b, 0.75f);
                    Gizmos.DrawCube(new Vector3(gizmosTargetPos.x, gizmosTargetPos.y, 0), Vector3.one * AStarManager.Instance.BaseCellSize * unitSize.x * 0.95f);
                }
            }
        }
        #endregion
    
        #region 路径相关
        public void SetPath(IEnumerable<Vector3> newPath, bool followImmediate = false)
        {
            if (newPath == null || !AStarManager.Instance) return;
            ResetPath();
            IsFollowingPath = followImmediate;
            OnPathFound(newPath, true);
        }
    
        public void ResetPath()
        {
            path = null;
            if (pathFollowCoroutine != null) StopCoroutine(pathFollowCoroutine);
            pathFollowCoroutine = null;
            targetWaypointIndex = 0;
            isFollowingPath = false;
            ShowPath(false);
            gizmosTargetPos = default;
        }
    
        private void RequestPath(Vector3 destination)
        {
            if (!AStarManager.Instance || destination == OffsetPosition) return;
            AStarManager.Instance.RequestPath(new PathRequest(OffsetPosition, destination, unitSize, OnPathFound));
        }
    
        private void OnPathFound(IEnumerable<Vector3> newPath, bool findSuccessfully)
        {
            if (findSuccessfully && newPath != null && newPath.Count() > 0)
            {
                path = newPath.ToArray();
                if (pathRenderer)
                {
                    LinkedList<Vector3> path = new LinkedList<Vector3>(this.path);
                    path.AddFirst(OffsetPosition);
                    pathRenderer.positionCount = path.Count;
                    pathRenderer.SetPositions(path.ToArray());
                }
                targetWaypointIndex = 0;
                if (IsFollowingPath)
                {
                    StartFollowingPath();
                }
            }
        }
    
        private void StartFollowingPath()
        {
            if (pathFollowCoroutine != null) StopCoroutine(pathFollowCoroutine);
            pathFollowCoroutine = StartCoroutine(FollowPath());
        }
    
        private IEnumerator FollowPath()
        {
            if (path == null || path.Length < 1 || !IsFollowingPath)
            {
                yield break; //yield break相当于普通函数空return
            }
            Vector3 targetWaypoint = path[0];
            while (IsFollowingPath)//模拟更新函数
            {
                if (path.Length < 1)//如果在追踪过程中,路线没了,直接退出追踪
                {
                    ResetPath();
                    yield break;
                }
                if (OffsetPosition.x >= targetWaypoint.x - fixedOffset && OffsetPosition.x <= targetWaypoint.x + fixedOffset//因为很多情况下无法准确定位,所以用近似值
                    && (AStarManager.Instance.ThreeD ? true : OffsetPosition.y >= targetWaypoint.y - fixedOffset && OffsetPosition.y <= targetWaypoint.y + fixedOffset)
                    && (AStarManager.Instance.ThreeD ? OffsetPosition.z >= targetWaypoint.z - fixedOffset && OffsetPosition.z <= targetWaypoint.z + fixedOffset : true))
                {
                    targetWaypointIndex++;//标至下一个航点
                    if (targetWaypointIndex >= path.Length) yield break;
                    targetWaypoint = path[targetWaypointIndex];
                    if (autoRepath)
                        if (!AStarManager.Instance.WorldPointWalkable(targetWaypoint, unitSize))//自动修复路线
                        {
                            //Debug.Log("Auto fix path");
                            RequestPath(Destination);
                            yield break;
                        }
                }
                if (AStarManager.Instance.ThreeD && MyUtilities.Slope(OffsetPosition, targetWaypoint) > slopeLimit) yield break;
                if (Vector3.Distance(OffsetPosition, Destination) <= stopDistance)
                {
                    ResetPath();
                    //Debug.Log("Stop");
                    ShowPath(false);
                    yield break;
                }
                if (moveMode == UnitMoveMode.MovePosition)
                {
                    if (AStarManager.Instance.ThreeD)
                    {
                        Vector3 targetDir = new Vector3(DesiredVelocity.x, 0, DesiredVelocity.z).normalized;//获取平面上的朝向
                        if (!targetDir.Equals(Vector3.zero))
                        {
                            Quaternion targetRotation = Quaternion.LookRotation(targetDir, Vector3.up);//计算绕Vector3.up使transform.forward对齐targetDir所需的旋转量
                            Quaternion lerpRotation = Quaternion.Lerp(transform.rotation, targetRotation, turnSpeed * Time.deltaTime);//平滑旋转
                            transform.rotation = lerpRotation;
                        }
                    }
                    OffsetPosition = Vector3.MoveTowards(OffsetPosition, targetWaypoint, Time.deltaTime * moveSpeed);
                    yield return null;//相当于以上步骤在Update()里执行,至于为什么不直接放在Update()里,一句两句说不清楚,感兴趣的自己试一试有什么区别
                }
                else if (moveMode == UnitMoveMode.MoveRigidbody)
                {
                    if (AStarManager.Instance.ThreeD && rigidbody)
                    {
                        Vector3 targetDir = new Vector3(DesiredVelocity.x, 0, DesiredVelocity.z).normalized;
                        if (!targetDir.Equals(Vector3.zero))
                        {
                            Quaternion targetRotation = Quaternion.LookRotation(targetDir, Vector3.up);
                            Quaternion lerpRotation = Quaternion.Lerp(rigidbody.rotation, targetRotation, turnSpeed * Time.deltaTime);
                            rigidbody.MoveRotation(lerpRotation);
                        }
                        rigidbody.MovePosition(rigidbody.position + DesiredVelocity * Time.deltaTime);
                    }
                    else if (!AStarManager.Instance.ThreeD && rigidbody2D)
                    {
                        rigidbody2D.MovePosition((Vector3)rigidbody2D.position + DesiredVelocity * Time.deltaTime);
                    }
                    yield return new WaitForFixedUpdate();//相当于以上步骤在FiexdUpdate()里执行
                }
                else
                {
                    if (AStarManager.Instance.ThreeD)
                    {
                        Vector3 targetDir = new Vector3(DesiredVelocity.x, 0, DesiredVelocity.z).normalized;
                        if (!targetDir.Equals(Vector3.zero))
                        {
                            Quaternion targetRotation = Quaternion.LookRotation(targetDir, Vector3.up);
                            Quaternion lerpRotation = Quaternion.Lerp(transform.rotation, targetRotation, turnSpeed * Time.deltaTime);
                            transform.rotation = lerpRotation;
                        }
                        controller.SimpleMove(DesiredVelocity - Vector3.up * 9.8f);
                    }
                    yield return new WaitForFixedUpdate();
                }
            }
        }
    
        public void ShowPath(bool value)
        {
            if (!pathRenderer) return;
            pathRenderer.positionCount = 0;
            pathRenderer.enabled = value;
        }
        #endregion
    
        #region 目标相关
        public void SetDestination(Vector3 destination, bool gotoImmediately = true)//类似NavMeshAgent.SetDestination(),但不建议逐帧使用
        {
            if (drawGizmos) gizmosTargetPos = destination;
            if (!AStarManager.Instance) return;
            if (drawGizmos)
            {
                AStarNode goal = AStarManager.Instance.WorldPointToNode(destination, unitSize);
                if (goal) gizmosTargetPos = goal;
            }
            IsFollowingPath = gotoImmediately;
            RequestPath(destination);
        }
    
        public void SetTarget(Transform target, Vector3 footOffset, bool followImmediately = false)
        {
            if (!target || !AStarManager.Instance) return;
            this.target = target;
            targetFootOffset = footOffset;
            if (!followImmediately) SetDestination(TargetPosition, false);
            else
            {
                isFollowingTarget = followImmediately;
                StartFollowingTarget();
            }
        }
    
        public void SetTarget(Transform target, bool followImmediately = false)
        {
            if (!target || !AStarManager.Instance) return;
            this.target = target;
            targetFootOffset = Vector3.zero;
            if (!followImmediately) SetDestination(TargetPosition, false);
            else
            {
                isFollowingTarget = followImmediately;
                StartFollowingTarget();
            }
        }
    
        public void ResetTarget()
        {
            target = null;
            if (targetFollowCoroutine != null) StopCoroutine(targetFollowCoroutine);
            targetFollowCoroutine = null;
            IsFollowingTarget = false;
        }
    
        private void StartFollowingTarget()
        {
            if (targetFollowCoroutine != null) StopCoroutine(targetFollowCoroutine);
            targetFollowCoroutine = StartCoroutine(FollowTarget());
        }
    
        private IEnumerator FollowTarget()
        {
            if (!target) yield break;
            Vector3 oldTargetPosition = TargetPosition;
            SetDestination(TargetPosition);
            while (target)
            {
                yield return new WaitForSeconds(0.1f);
                if (Vector3.Distance(oldTargetPosition, TargetPosition) > targetFollowStartDistance)
                {
                    oldTargetPosition = TargetPosition;
                    SetDestination(TargetPosition);
                }
            }
        }
        #endregion
    
        private enum UnitMoveMode
        {
            MovePosition,
            MoveRigidbody,
            MoveController
        }
    }

    寻路单位的移动函数使用协程完成,方便中断,也不用为刚体移动和Transform移动分开写移动函数并分别放在FixedUpdate()和Update()调用。整个寻路系统最大的性能消耗在于FollowTarget()的MoveNext(),因为在里边调用了寻路函数,知识有限,目前还没有想到什么好的优化办法,归根到底是寻路算法巨额消耗的锅。Unity虽然可以支持多线程操作,但是别想使用UnityEngine里面的API了,各种红字报错,在底层它自己lock了,用Thread Ninja插件貌似可以飞起,但是没时间去研究了,而且是14年的插件,不知道现在管不管用,比较新的一个Easy Threading也是2年前的了,也没研究。因此,寻路性能成为问题,所以大佬们写的寻路插件都能解决了这个问题,卖这么贵是有道理的=  =

    这就是一直提到的寻路单位了,自定义了一下检视器后,成品如下:

    寻路效果动图我就不贴上来了,放个静态图意思意思:

    基础A*寻出来的路走起来折来折去的,转向太大,怪别扭的,估计后面我会优化一下。

    就先记到这里了。又要告一段落了,不知道什么是才能再上来写博了╮( ̄▽ ̄")╭,如果不需要这么精确的寻路,可以稍微改一下Unit的代码,直接把目的地加入路径中,让Unit径直走过去,这种做法普遍适用于小怪,甚至不需要寻路算法,只不过整合起来用显得比较装逼而已。

    理论上可行的优化方案:使用“池”技术,也就是广度优先给每个格子预先计算它到其它格子的路径,并使用带双重索引的数据结构存储起来,同时在计算指定格子到目标格子的路径时,如果该格子已经在其他某一格子到目标格子的路径上,则截取已知路径作为该格子到目标格子的路径,省去寻路计算,最后提供一个刷新函数来更新池子。而仅仅是30×30的网格就会有多达900个格子,可想而知,预处理这些内容在启动游戏时得有多卡_(:3J∠)_,所以也只是一个理论方案。

    19/6/11补充:时至今日我才知道PathFinding Project有free版,只不过Asset Srore没上架而已,要去官网下载,功能足够用了,性能比我自己写的好太多太多,2D、3D都能用,也很容易融合(●´∀`●)

    展开全文
  • 《【Unity3D】自动寻路》(点击打开链接)万般好,但锁死Y轴这点导致非常蛋疼的一个问题,我需要在自动寻路的过程允许游戏主角进行跳跃。毕竟玩家都说了,在3D游戏里面不让主角跳跃是一个很严重的问题,就像《阿玛拉...
  • (为了让各位能更容易读懂此文,此文仍会继续补充。 现在我将所有源码都存放在了Github上,请各位跟随我到Github... ...   国庆闲来没事把NavMesh巩固一下。以Unity3D引擎为例写一个底层c# NavMesh寻路。因为Unity3D...
  • 前言 一个简单的人工智能WayPoint WayPoint: 游戏中敌人根据几个巡逻点自动巡逻,在巡逻过程中,时刻监听英雄(敌人)和自己距离是否达到追击范围(不巡逻,最近英雄),在追击过程中,监听是否达到攻击范围(不...
  • 在游戏中,从一点到另一点的操作有时需要游戏系统自动完成,在一些带有rpg元素的游戏中,敌人在发现玩家位置后会自动向玩家的位置移动。...本文将介绍寻路算法中的A*算法,并在unity中用C#脚本来实现寻路功能。
  • UNITY地图寻路及服务器解决方案 多边形寻路算法简单介绍 ... UNITY3D MMO服务器寻路 http://www.pathengine.com/ 用UNITY做无界面寻路server 命令行 .exe -batchmode ...
  • Unity3D实现A*寻路算法

    2015-05-05 15:56:45
    目录(?)[+] ...A算法复习实现NodePriorityQueueGridManagerAStarTestCode ClassScene setupTesting总结 ...在本章中,我们将在Unity3D环境中使用C#实现A*算法.尽管有很多其他算法,像Dijkstra算法,
  • 自动寻路人物惯性问题,容易滑动,按括号里的来可以解决这个问题 点击往鼠标点到的地方移动脚本ClickToMove.csusing UnityEngine; using UnityEngine.AI;// Use physics raycast hit from mouse click to set agent ...
  • Unity3D引擎为例写一个底层c# NavMesh寻路。因为Unity3D中本身自带的NavMesh寻路不能很好的融入到游戏项目当中,所以重写一个NavMesh寻路是个必经之路。NavMesh在很多游戏中应用广泛,不同种类的框架下NavMesh寻路...
  • Unity3d 中的 A*寻路

    2014-08-07 14:36:22
    在本章中,我们将在Unity3D环境中使用C#实现A*算法.尽管有很多其他算法,像Dijkstra算法,但A*算法以其简单性和有效性而广泛的应用于游戏和交互式应用中.我们之前在第一章AI介绍中短暂的涉及到了该算法.不过现在我们从...
  • unity3d 各大插件评测

    2018-01-30 15:00:43
    原创文章如需转载请注明:转载自风宇冲Unity3D教程学院 引言:想用Unity3D制作优秀的游戏,插件是必不可少的。工欲善其事必先利其器。本文主旨是告诉使用Unity3D引擎的同学们如何根据需求选择适当的工具...
  • 在游戏中,我们经常会用到角色自动寻路这个功能,
  • 简介:当制作动作类攻击游戏时,会用到敌人的自动攻击及自动寻找攻击目标,如何实现自动攻击和自动寻路呢?下面简单的讲解我对这方面的理解。 当你已经导入了敌人的模型并制作好了敌人动画控制状态机,接下来...
1 2 3 4 5 ... 20
收藏数 650
精华内容 260
关键字:

2d寻路 unity3d