2d的寻路方式 unity3d

2017-01-07 18:31:39 grf123 阅读数 1849

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入门教程(三)


2019-06-09 21:05:18 hzt9565 阅读数 856

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

因为破游戏准备设计敌人了,苦于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都能用,也很容易融合(●´∀`●)

2014-01-02 10:51:40 u013265457 阅读数 11535

  现在的大部分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

2019-03-02 10:20:03 wuming2016 阅读数 2705

        调研了下,大概有两个插件可以用于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;
    }

 

2019-04-01 15:47:03 gozldream 阅读数 1426

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