cat
Shioho
首页 Unity

# 洗脑循环 ing...

# 前言

最近在写双端，在考虑实现服务端寻路实现时想参考 Unity NavMesh 的实现方案，基于 Unity NavMesh 实现一套包含地图数据 -> 寻路的工作流（虽然最终由于种种原因还是采用了二维网格，但还是记录一下调研结果吧～

项目 Git

# 感谢

先感谢一下以下大佬们的文章～

Recast Navigation 源码分析：导航网格 Navmesh 的生成原理
基于 NavMesh 寻路、漏斗寻路、RVO 动态避障自创的服务器大规模寻路 + 动态避障算法的实现

# 导出自定义 NavMesh 数据

# 如何创建一个 Terrain 以及生成 NavMesh 网格我就不写了，毕竟是 Unity 基础

# Unity 内 NavMesh 数据格式如下

public struct NavMeshTriangulation
  {
    // 所有三角形顶点
    public Vector3[] vertices;
    // 组成三角形的顶点索引的顺时针顺序
    public int[] indices;
    // 索引三角形所在的区域值
    public int[] areas;
  }
# 写一个简单的编辑器代码，将上方数据处理后生成 json 导出即可
# 三角形数据
// 三角形网格数据（填充了一些 a * 寻路数据，用于客户端算法寻路可视化）
 public class ServerMapTriangle 
    {
        public int Id;
        // 三角形三个顶点 (顺时针)
        public Vector3 A;
        public Vector3 B;
        public Vector3 C;
        public int Area;
        // 寻路用
        public ServerMapTriangle NeighborA;
        public ServerMapTriangle NeighborB;
        public ServerMapTriangle NeighborC;
        public ServerMapTriangle Father;
        public ServerMapTriangle Next;
        public float F;
        public float H;
        public float G;
        public bool Finished;
        
        public void Reset()
        {
            F = 0f;
            H = 0f;
            G = 0f;
            NeighborA = null;
            NeighborB = null;
            NeighborC = null;
            Father = null;
            Next = null;
            Finished = false;
        }
        
        public Vector3 GetCenterPosition()
        {
            float a = (B - C).magnitude;
            float b = (B - C).magnitude;
            float c = (B - C).magnitude;
            Vector3 Center = new Vector3((a * A.x + b * B.x + c * C.x) / (a + b + c),
                (a * A.y + b * B.y + c * C.y) / (a + b + c),
                (a * A.z + b * B.z + c * C.z) / (a + b + c));
            return Center;
        }
        
        public bool IsPointInTriangle(Vector3 p)
        {
            // 忽略 y 轴
            var calA = new Vector3(A.x, 0, A.z);
            var calB = new Vector3(B.x, 0, B.z);
            var calC = new Vector3(C.x, 0, C.z);
            var calP = new Vector3(p.x, 0, p.z);
            // 顺时针反向皆在右侧则在三角形内 (AB-AP、BC-BP、CA-CP)
            if (Vector3.Cross(calB - calA, calP - calA).y < 0)
                return false;
            if (Vector3.Cross(calC - calB, calP - calB).y < 0)
                return false;
            if (Vector3.Cross(calA - calC, calP - calC).y < 0)
                return false;
        
            return true;
        }
        
        public void Draw(Color col)
        {
            Handles.color = col;
            Handles.DrawLine(A, B);
            Handles.DrawLine(B, C);
            Handles.DrawLine(C, A);
        }
    }
# 读取数据生成网格地图
注意：由于 NavMesh 产生的三角形可能存在非连续的情况，即分成多个三角形组，因此下方多了一步选择一个三角形索引（这里采用面积最大的那个三角形）然后计算所有与此三角形连通成组的方法，会剔除部分非连通部分。
  • 生成所有三角形数据（包括非连通部分）、选择默认三角形

public List<ServerMapTriangle> Triangles { get; private set; }
    public ServerMapTriangle SelectedTriangle { get; private set; }
    private readonly float _minDis = 0.05f;
    // 三角形面积
    private float CalculateTriangleArea(float x1, float y1, float x2, float y2, float x3, float y3)
    {
        return Math.Abs((float)(0.5 * (x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))));
    }
    // 添加所有寻路三角形
    public void GenTriangle()
    {
        // 读取当前场景的 Terrain 数据
        NavMeshTriangulation nmt = NavMesh.CalculateTriangulation();
        float area = 0;
        int areaIdx = 0;
        int id = 0;
        for (int i = 0; i < nmt.indices.Length; i += 3)
        {
            ServerMapTriangle t = new ServerMapTriangle();
            t.Id = id;
            t.A = nmt.vertices[nmt.indices[i]];
            t.B = nmt.vertices[nmt.indices[i + 1]];
            t.C = nmt.vertices[nmt.indices[i + 2]];
            t.Area = nmt.areas[id];
            Triangles.Add(t);
            var tempArea = CalculateTriangleArea(t.A.x, t.A.z, t.B.x, t.B.z,t.C.x, t.C.z);
            if (tempArea > area)
            {
                areaIdx = id;
                area = tempArea;
            }
            id++;
        }
        SetSelectTriangle(areaIdx.ToString());
        Debug.Log("生成三角形：" + Triangles.Count);
        Debug.Log("选择默认三角形：" + areaIdx);
    }
    public void SetSelectTriangle(string str)
    {
        int idx;
        if (!Int32.TryParse(str, out idx)) return;
        if (idx < 0 || idx >= Triangles.Count) return;
        SelectedTriangle = Triangles[idx];
    }
  • 剔除非连通部分
public void CalEliminateMap()
    {
        if (SelectedTriangle == null || Triangles.Count <= 0) return;
        // 拷贝，用于遍历
        List<ServerMapTriangle> copyList = new List<ServerMapTriangle>();
        for (int i = 0; i < Triangles.Count; i++)
        {
            copyList.Add(Triangles[i]);
        }
        List<ServerMapTriangle> neighbourList = new List<ServerMapTriangle>();
        neighbourList.Add(SelectedTriangle);
        copyList.Remove(SelectedTriangle);
        for (int i = 0; i < neighbourList.Count; ++i)
        {
            var data1 = neighbourList[i];
            for (int j = 0; j < copyList.Count; ++j)
            {
                var data2 = copyList[j];
                if ((data1.A - data2.A).magnitude < _minDis ||
                    (data1.A - data2.B).magnitude < _minDis ||
                    (data1.A - data2.C).magnitude < _minDis ||
                    (data1.B - data2.A).magnitude < _minDis ||
                    (data1.B - data2.B).magnitude < _minDis ||
                    (data1.B - data2.C).magnitude < _minDis ||
                    (data1.C - data2.A).magnitude < _minDis ||
                    (data1.C - data2.B).magnitude < _minDis ||
                    (data1.C - data2.C).magnitude < _minDis)
                {
                    neighbourList.Add(copyList[j]);
                    copyList.RemoveAt(j);
                    --j;
                }
            }
        }
        // 根据 Id 排序
        neighbourList.Sort((x, y) => x.Id.CompareTo(y.Id));
        // 重置 Id
        for (int i = 0; i < neighbourList.Count; ++i)
        {
            neighbourList[i].Id = i;
        }
        Triangles = neighbourList;
        Debug.Log("导航网格生成:" + Triangles.Count);
    }
  • 你已经获取了连通三角形数据组了，用你想要的格式导出 json 吧（数据量若过大可以考虑 gzip 下哈
//output = 你要的 json 格式 如：{Triangles : Triangles} 
    string json = JsonConvert.SerializeObject(output);
    byte[] jsonBytes = Encoding.UTF8.GetBytes(json);
    var outFile = new FileStream("保存路径",FileMode.Create, FileAccess.ReadWrite);
    outFile.Write(jsonBytes, 0, jsonBytes.Length);
    outFile.Close();
    //gzip
    private byte[] Compress(byte[] jsonBytes)
    {
        using (var ms = new MemoryStream())
        {
            using (var gs = new GZipStream(ms, CompressionMode.Compress))
            {
                gs.Write(jsonBytes, 0, jsonBytes.Length);
            }
            return ms.ToArray();
        }
    }
# 基于 NavMesh 的 A * 算法
因为最后改成了二维网格的实现方案，因此并没写 NavMesh 的 go 的代码，只写了客户端的实现，go 只要翻译一下就好了，这里用上方生成完毕的 List<ServerMapTriangle> Triangles 直接实现哈～
# 绘制类
public struct Line
{
    public Vector3 From;
    public Vector3 To;
}
public class Ray
{
    public Vector3 From;
    public Vector3 Dir;
    public Color Col;
}
public class MapDrawer
{
    public List<ServerMapTriangle> Map => _mapDraw;
    public Vector3 StartPos => _startPos;
    public Vector3 EndPos => _endPos;
    // 地图网格
    public bool IsDrawMap;
    private List<ServerMapTriangle> _mapDraw;
    private ServerMapTriangle _selectedTriangle;
    
    // 二维网格
    public bool IsDrawArrMap;
    public List<GridData> GridDatas => _gridDatas;
    private List<GridData> _gridDatas;
    public Vector3 TerrainSize;
    public float GirdSize { get; private set; }
    // 寻路
    public bool IsDrawPath;
    private Vector3 _startPos;
    private Vector3 _endPos;
    private List<Line> _pathList;
    private List<Line> _gridPathList;
    private Dictionary<string, List<Ray>> _pathRayMap;
    private List<Ray> _viewRay;
    private int _viewRayIdx;
    private static MapDrawer _instance;
    public MapDrawer()
    {
        _mapDraw = new List<ServerMapTriangle>();
        _pathList = new List<Line>();
        _gridPathList = new List<Line>();
        _pathRayMap = new Dictionary<string, List<Ray>>();
        _viewRay = new List<Ray>();
        _gridDatas = new List<GridData>();
    }
    public static MapDrawer GetInstance()
    {
        if (_instance == null)
        {
            _instance = new MapDrawer();
        }
        return _instance;
    }
    public void Clear()
    {
        ClearPath();
        _mapDraw.Clear();
        _gridDatas.Clear();
        _selectedTriangle = null;
    }
    public void AddMapTriangle(ServerMapTriangle t)
    {
        _mapDraw.Add(t);
    }
    public void SetSelectTriangle(int idx)
    {
        if (idx < 0 || idx >= _mapDraw.Count) return;
        _selectedTriangle = _mapDraw[idx];
    }
    public void CalNeighbourMap()
    {
        if (_selectedTriangle == null || _mapDraw.Count <= 0) return;
        float dis = 0.05f;
        // 拷贝，用于遍历
        List<ServerMapTriangle> copyList = new List<ServerMapTriangle>();
        for (int i = 0; i < _mapDraw.Count; i++)
        {
            copyList.Add(_mapDraw[i]);
        }
        List<ServerMapTriangle> neighbourList = new List<ServerMapTriangle>();
        neighbourList.Add(_selectedTriangle);
        copyList.Remove(_selectedTriangle);
        for (int i = 0; i < neighbourList.Count; ++i)
        {
            var data1 = neighbourList[i];
            for (int j = 0; j < copyList.Count; ++j)
            {
                var data2 = copyList[j];
                if ((data1.A - data2.A).magnitude < dis ||
                    (data1.A - data2.B).magnitude < dis ||
                    (data1.A - data2.C).magnitude < dis ||
                    (data1.B - data2.A).magnitude < dis ||
                    (data1.B - data2.B).magnitude < dis ||
                    (data1.B - data2.C).magnitude < dis ||
                    (data1.C - data2.A).magnitude < dis ||
                    (data1.C - data2.B).magnitude < dis ||
                    (data1.C - data2.C).magnitude < dis)
                {
                    neighbourList.Add(copyList[j]);
                    copyList.RemoveAt(j);
                    --j;
                }
            }
        }
        // 根据 Id 排序
        neighbourList.Sort((x, y) => x.Id.CompareTo(y.Id));
        // 重置 Id
        for (int i = 0; i < neighbourList.Count; ++i)
        {
            neighbourList[i].Id = i;
        }
        _mapDraw = neighbourList;
    }
    public void SetStartPos(string str)
    {
        int x, y;
        var arr = str.Split(",");
        if (!Int32.TryParse(arr[0], out x) || !Int32.TryParse(arr[1], out y)) return;
        _startPos = new Vector3(x, 0, y);
    }
    public void SetEndPos(string str)
    {
        int x, y;
        var arr = str.Split(",");
        if (!Int32.TryParse(arr[0], out x) || !Int32.TryParse(arr[1], out y)) return;
        _endPos = new Vector3(x, 0, y);
    }
    public void SetGridSize(string str)
    {
        float size;
        if(!float.TryParse(str,out size)) return;
        GirdSize = size;
    }
    public void ClearPath()
    {
        _gridPathList.Clear();
        _pathList.Clear();
        _pathRayMap.Clear();
        _viewRay.Clear();
        _viewRayIdx = -1;
    }
    public void AddPath(Line line)
    {
        _pathList.Add(line);
    }
    public void AddGridPath(Line line)
    {
        _gridPathList.Add(line);
    }
    public void AddRay(string k, Ray ray)
    {
        if (!_pathRayMap.ContainsKey(k))
        {
            _pathRayMap[k] = new List<Ray>();
        }
        _pathRayMap[k].Add(ray);
    }
    public void PreView()
    {
        _viewRayIdx--;
        if (_viewRayIdx < 0)
        {
            _viewRayIdx = 0;
        }
        _viewRay.Clear();
        _viewRay.Add(_pathRayMap["v1"][_viewRayIdx]);
        _viewRay.Add(_pathRayMap["v2"][_viewRayIdx]);
        _viewRay.Add(_pathRayMap["v3"][_viewRayIdx]);
        _viewRay.Add(_pathRayMap["v4"][_viewRayIdx]);
        var cross = _pathRayMap["cross"][_viewRayIdx];
        if (cross != null)
        {
            _viewRay.Add(cross);
        }
    }
    public void NextView()
    {
        _viewRayIdx++;
        if (_viewRayIdx >= _pathRayMap["v1"].Count)
        {
            _viewRayIdx = _pathRayMap["v1"].Count - 1;
        }
        _viewRay.Clear();
        _viewRay.Add(_pathRayMap["v1"][_viewRayIdx]);
        _viewRay.Add(_pathRayMap["v2"][_viewRayIdx]);
        _viewRay.Add(_pathRayMap["v3"][_viewRayIdx]);
        _viewRay.Add(_pathRayMap["v4"][_viewRayIdx]);
        var cross = _pathRayMap["cross"][_viewRayIdx];
        if (cross != null)
        {
            _viewRay.Add(cross);
        }
    }
    public void SetArrGridMap(List<GridData> map)
    {
        _gridDatas = map;
    }
    public void DrawAll()
    {
        // 地图
        if (IsDrawMap)
        {
            for (int i = 0; i < _mapDraw.Count; i++)
            {
                _mapDraw[i].Draw(Color.green);
            }
            // 选中三角形块
            if (_selectedTriangle != null)
            {
                _selectedTriangle.Draw(Color.yellow);
            }
        }
        // 初始位置
        if (IsDrawPath)
        {
            Handles.color = Color.blue;
            Handles.DrawLine(_startPos, new Vector3(_startPos.x, 100, _startPos.z));
            Handles.DrawLine(_endPos, new Vector3(_endPos.x, 100, _endPos.z));
            for (int i = 0; i < _pathList.Count; i++)
            {
                Handles.DrawLine(_pathList[i].From, _pathList[i].To);
            }
            Handles.color = Color.red;
            for (int i = 0; i < _gridPathList.Count; i++)
            {
                Handles.DrawLine(_gridPathList[i].From, _gridPathList[i].To);
            }
            for (int i = 0; i < _viewRay.Count; i++)
            {
                var ray = _viewRay[i];
                Debug.DrawRay(ray.From, ray.Dir, ray.Col);
            }
        }
        if (IsDrawArrMap)
        {
            foreach (var kv in _gridDatas)
            {
                kv.Draw();
            }
        }
    }
}
# 寻路类
public class MapPath
{
    private static List<ServerMapTriangle> _listcheck = new List<ServerMapTriangle>();
    private static List<ServerMapTriangle> _listfinish = new List<ServerMapTriangle>();
    public static void CountPath()
    {
        // 获取初始和目标点位置
        var startPos = MapDrawer.GetInstance().StartPos;
        var endPos = MapDrawer.GetInstance().EndPos;
        var startIdx = GetMapIdx(startPos);
        var endIdx = GetMapIdx(endPos);
        Debug.Log("startIdx:" + startIdx + ",endIdx:" + endIdx);
        Debug.Assert(startIdx >= 0, "startPos寻路点不在地图内:" + startIdx);
        Debug.Assert(endIdx >= 0, "endPos寻路点不在地图内:" + endIdx);
        if (startIdx < 0 || endIdx < 0)
        {
            return;
        }
        Debug.Log("开始寻路");
        MapDrawer.GetInstance().ClearPath();
        var maps = MapDrawer.GetInstance().Map;
        //1. 清空寻路缓存，设置相邻关系点图
        float dis = 0.05f;
        for (int i = 0; i < maps.Count; ++i)
        {
            maps[i].Reset();
        }
        for (int i = 0; i < maps.Count; ++i)
        {
            var data1 = maps[i];
            for (int j = 0; j < maps.Count; ++j)
            {
                var data2 = maps[j];
                if (i == j)
                {
                    continue;
                }
                int bingleCount = 0;
                bool hitA = false;
                bool hitB = false;
                bool hitC = false;
                if ((data1.A - data2.A).magnitude < dis ||
                    (data1.A - data2.B).magnitude < dis ||
                    (data1.A - data2.C).magnitude < dis)
                {
                    ++bingleCount;
                    hitA = true;
                }
                if ((data1.B - data2.A).magnitude < dis ||
                    (data1.B - data2.B).magnitude < dis ||
                    (data1.B - data2.C).magnitude < dis)
                {
                    ++bingleCount;
                    hitB = true;
                }
                if ((data1.C - data2.A).magnitude < dis ||
                    (data1.C - data2.B).magnitude < dis ||
                    (data1.C - data2.C).magnitude < dis)
                {
                    ++bingleCount;
                    hitC = true;
                }
                if (bingleCount > 1)
                {
                    TryToAddNeighbour(data1, data2, hitA, hitB, hitC);
                }
            }
        }
        //2. 计算预估代价
        _listcheck.Clear();
        _listfinish.Clear();
        ServerMapTriangle nowTriangle;
        TryToAddToListcheck(maps[startIdx]);
        int ci = 0;
        while ((nowTriangle = GetPbByMinF()) != null)
        {
            ++ci;
            //Debug.Log(ci);
            ServerMapTriangle pbend = maps[endIdx];
            if (nowTriangle.NeighborA == pbend ||
                nowTriangle.NeighborB == pbend ||
                nowTriangle.NeighborC == pbend)
            {
                _listfinish.Add(pbend);
                pbend.Father = nowTriangle;
                while (pbend.Father != null)
                {
                    // 这是网格路径
                    MapDrawer.GetInstance().AddGridPath(new Line
                    {
                        From = pbend.GetCenterPosition(),
                        To = pbend.Father.GetCenterPosition()
                    });
                    pbend.Father.Next = pbend;
                    pbend = pbend.Father;
                }
                // 网格结合
                OptimizationPath(pbend, startPos, endPos);
                break;
            }
            if (CountNeighbourF(nowTriangle, nowTriangle.NeighborA))
            {
                nowTriangle.NeighborA.H =
                    (nowTriangle.NeighborA.GetCenterPosition() - pbend.GetCenterPosition()).magnitude;
                nowTriangle.NeighborA.F = nowTriangle.NeighborA.H + nowTriangle.NeighborA.G;
            }
            if (CountNeighbourF(nowTriangle, nowTriangle.NeighborB))
            {
                nowTriangle.NeighborB.H =
                    (nowTriangle.NeighborB.GetCenterPosition() - pbend.GetCenterPosition()).magnitude;
                nowTriangle.NeighborB.F = nowTriangle.NeighborB.H + nowTriangle.NeighborB.G;
            }
            if (CountNeighbourF(nowTriangle, nowTriangle.NeighborC))
            {
                nowTriangle.NeighborC.H =
                    (nowTriangle.NeighborC.GetCenterPosition() - pbend.GetCenterPosition()).magnitude;
                nowTriangle.NeighborC.F = nowTriangle.NeighborC.H + nowTriangle.NeighborC.G;
            }
            AddToFinish(nowTriangle);
        }
        Debug.Log("寻路完成");
    }
    // 中心点到下一个临近三角形的顺时针顶点与向量（Unity 的 NavMesh 数据三角形为顺时针排列）
    private static void CaculateV(Vector3 startPosition, ServerMapTriangle tCount, ref Vector3 v1, ref Vector3 v2,
        ref Vector3 p1,
        ref Vector3 p2)
    {
        if (tCount == null)
        {
            return;
        }
        if (tCount.Next != null)
        {
            if (tCount.Next == tCount.NeighborA)
            {
                v1 = tCount.B - startPosition;
                v2 = tCount.C - startPosition;
                p1 = tCount.B;
                p2 = tCount.C;
            }
            else if (tCount.Next == tCount.NeighborB)
            {
                v1 = tCount.A - startPosition;
                v2 = tCount.C - startPosition;
                p1 = tCount.A;
                p2 = tCount.C;
            }
            else if (tCount.Next == tCount.NeighborC)
            {
                v1 = tCount.B - startPosition;
                v2 = tCount.A - startPosition;
                p1 = tCount.B;
                p2 = tCount.A;
            }
            //start Position 和另一个 V，在同一个边上则边就确定了，从这个三角形中心找左右
            if (Vector3.Cross(new Vector3(v1.x, 0, v1.z), new Vector3(v2.x, 0, v2.z)).y == 0)
            {
                Vector3 vcp_1 = p1 - tCount.GetCenterPosition();
                Vector3 vcp_2 = p2 - tCount.GetCenterPosition();
                // 边反了
                if (Vector3.Cross(new Vector3(vcp_1.x, 0, vcp_1.z), new Vector3(vcp_2.x, 0, vcp_2.z)).y < 0)
                {
                    v1 = p2 - startPosition;
                    v2 = p1 - startPosition;
                    Vector3 pswitch = p1;
                    p1 = p2;
                    p2 = pswitch;
                }
                else
                {
                    v1 = p1 - startPosition;
                    v2 = p2 - startPosition;
                }
            }
            // 左手坐标系，所以小于等于
            else if (Vector3.Cross(new Vector3(v1.x, 0, v1.z), new Vector3(v2.x, 0, v2.z)).y < 0)
            {
                Vector3 vswitch = v1;
                Vector3 pswitch = p1;
                v1 = v2;
                v2 = vswitch;
                p1 = p2;
                p2 = pswitch;
            }
        }
        else
        {
            v1 = v2 = tCount.GetCenterPosition() - startPosition;
            p1 = p2 = tCount.GetCenterPosition();
        }
    }
    private static void CountNext(ref List<Vector3> listpath, ref ServerMapTriangle t)
    {
        if (t.Next == null)
        {
            listpath.Add(t.GetCenterPosition());
        }
        t = t.Next;
    }
    private static void OptimizationPath(ServerMapTriangle start, Vector3 startPos, Vector3 endPos)
    {
        Vector3 v1 = new Vector3();
        Vector3 v2 = new Vector3();
        Vector3 v3 = new Vector3();
        Vector3 v4 = new Vector3();
        Vector3 p1 = new Vector3();
        Vector3 p2 = new Vector3();
        Vector3 p3 = new Vector3();
        Vector3 p4 = new Vector3();
        ServerMapTriangle g1 = start;
        ServerMapTriangle g2 = start;
        List<Vector3> listpath = new List<Vector3>();
        Vector3 startPosition = start.GetCenterPosition();
        listpath.Add(startPosition);
        ServerMapTriangle tCount = start.Next;
        CaculateV(startPosition, start, ref v1, ref v2, ref p1, ref p2);
        while (tCount != null)
        {
            CaculateV(startPosition, tCount, ref v3, ref v4, ref p3, ref p4);
            // 当前视野
            MapDrawer.GetInstance().AddRay("v1", new Ray
            {
                From = startPosition + Vector3.up,
                Dir = v1,
                Col = new Color(186 / 255f, 62 / 255f, 224 / 255f)
            });
            MapDrawer.GetInstance().AddRay("v2", new Ray
            {
                From = startPosition + Vector3.up,
                Dir = v2,
                Col = new Color(21 / 255f, 107 / 255f, 141 / 255f)
            });
            // 下一视野
            MapDrawer.GetInstance().AddRay("v3", new Ray
            {
                From = startPosition,
                Dir = v3,
                Col = new Color(246 / 255f, 133 / 255f, 59 / 255f)
            });
            MapDrawer.GetInstance().AddRay("v4", new Ray
            {
                From = startPosition,
                Dir = v4,
                Col = new Color(228 / 255f, 6 / 255f, 27 / 255f)
            });
            // 这里的算法是 v1,v2 范围包含 v3,v4, 如果不包含，说明出现拐点
            // 左手坐标系，所以小于等于
            if (Vector3.Cross(new Vector3(v3.x, 0, v3.z), new Vector3(v2.x, 0, v2.z)).y <= 0)
            {
                // startPosition = p2;
                // listpath.Add(g2.GetCenterPosition());
                startPosition = g2.GetCenterPosition();
                tCount = g2;
                g2 = tCount.Next;
                CaculateV(startPosition, tCount, ref v1, ref v2, ref p1, ref p2);
                listpath.Add(startPosition);
                CountNext(ref listpath, ref tCount);
                MapDrawer.GetInstance().AddRay("cross", new Ray
                {
                    From = startPosition,
                    Dir = Vector3.up * 100,
                    Col = Color.yellow
                });
                continue;
            }
            // 左手坐标系，所以大于等于
            if (Vector3.Cross(new Vector3(v4.x, 0, v4.z), new Vector3(v1.x, 0, v1.z)).y >= 0)
            {
                // startPosition = p1;
                // listpath.Add(g1.GetCenterPosition());
                startPosition = g1.GetCenterPosition();
                tCount = g1;
                g1 = tCount.Next;
                CaculateV(startPosition, tCount, ref v1, ref v2, ref p1, ref p2);
                listpath.Add(startPosition);
                CountNext(ref listpath, ref tCount);
                MapDrawer.GetInstance().AddRay("cross", new Ray
                {
                    From = startPosition,
                    Dir = Vector3.up * 100,
                    Col = Color.black
                });
                continue;
            }
            MapDrawer.GetInstance().AddRay("cross", null);
            // 左手坐标系，所以小于等于（但不能反向）
            var v3_1_normal = Vector3.Cross(new Vector3(v3.x, 0, v3.z), new Vector3(v1.x, 0, v1.z));
            if (v3_1_normal.y < 0 || (v3_1_normal.y == 0 && Vector3.Normalize(v3).Equals(Vector3.Normalize(v1))))
            {
                v1 = v3;
                p1 = p3;
                g1 = tCount.Next;
            }
            // 左手坐标系，所以小于等于
            var v4_2_normal = Vector3.Cross(new Vector3(v4.x, 0, v4.z), new Vector3(v2.x, 0, v2.z));
            if (v4_2_normal.y > 0 || (v4_2_normal.y == 0 && Vector3.Normalize(v4).Equals(Vector3.Normalize(v2))))
            {
                v2 = v4;
                p2 = p4;
                g2 = tCount.Next;
            }
            CountNext(ref listpath, ref tCount);
        }
        // 头尾改为目标点
        listpath[0] = startPos;
        listpath[listpath.Count - 1] = endPos;
        for (int i = 0; i < listpath.Count - 1; ++i)
        {
            MapDrawer.GetInstance().AddPath(new Line
            {
                From = listpath[i],
                To = listpath[i + 1]
            });
        }
    }
    private static bool CountNeighbourF(ServerMapTriangle a, ServerMapTriangle neighbour)
    {
        if (neighbour == null || neighbour.Finished)
        {
            return false;
        }
        float G = CountDis(a, neighbour);
        if (neighbour.G == 0f || (a.G + G) < neighbour.G)
        {
            neighbour.G = a.G + G;
            neighbour.Father = a;
            TryToAddToListcheck(neighbour);
            return true;
        }
        return false;
    }
    private static float CountDis(ServerMapTriangle ta, ServerMapTriangle tb)
    {
        Vector3 ACenter = ta.GetCenterPosition();
        Vector3 BCenter = tb.GetCenterPosition();
        return (ACenter - BCenter).magnitude;
    }
    private static void AddToFinish(ServerMapTriangle t)
    {
        t.Finished = true;
        _listfinish.Add(t);
        _listcheck.Remove(t);
    }
    private static ServerMapTriangle GetPbByMinF()
    {
        ServerMapTriangle pb = null;
        for (int i = 0; i < _listcheck.Count; ++i)
        {
            if (pb == null || pb.F > _listcheck[i].F)
            {
                pb = _listcheck[i];
            }
        }
        return pb;
    }
    private static void TryToAddToListcheck(ServerMapTriangle t)
    {
        for (int i = 0; i < _listfinish.Count; ++i)
        {
            if (t.Id == _listfinish[i].Id)
            {
                return;
            }
        }
        for (int i = 0; i < _listcheck.Count; ++i)
        {
            if (t.Id == _listcheck[i].Id)
            {
                return;
            }
        }
        _listcheck.Add(t);
    }
    private static int GetMapIdx(Vector3 pos)
    {
        var maps = MapDrawer.GetInstance().Map;
        for (int i = 0; i < maps.Count; i++)
        {
            var t = maps[i];
            if (t.IsPointInTriangle(pos))
            {
                return i;
            }
        }
        return -1;
    }
    private static void TryToAddNeighbour(ServerMapTriangle baseTriangle, ServerMapTriangle neighbour, bool hitA, bool hitB,
        bool hitC)
    {
        if (hitA && hitB)
        {
            baseTriangle.NeighborC = neighbour;
        }
        else if (hitA && hitC)
        {
            baseTriangle.NeighborB = neighbour;
        }
        else if (hitC && hitB)
        {
            baseTriangle.NeighborA = neighbour;
        }
    }
}
红色线为A*寻路实际路径，蓝色线为优化后的路径点

# 总结
由于 NavMesh 这一套并没有正式落地，因此很多方面都没有再详细研究下去，如漏斗寻路、RVO 动态避障、甚至动态 NavMesh 生成，总之，先记录到这啦！
有空再写一下基于 TileMap 的客户端服务端二维网格工作流吧～
 更新于   阅读次数  次
请我喝[茶]~(￣▽￣)~*
汘帆 微信
微信
汘帆 支付宝
支付宝