[游戏开发]支持云端渲染的两种寻路思路

总述

NavMeshAgent是unity的内置组件，该组件附加在游戏中一个可移动的人物上，从而允许它使用NavMesh在Scene中导航。简单地说，该组件提供了自动寻路的功能。
以下是官方文档，如果需要可以作为参考。
NavMeshAgent组件官方文档：https://docs.unity3d.com/cn/current/ScriptReference/AI.NavMeshAgent.html
但在进行云端渲染时，寻路需要在多台设备之间保持一致，NavMeshAgent组件并不支持实时返回当前位置完成移动这一操作的校正与同步，其内部代码闭源，也无法进行二次开发使其实现帧同步。因此，目前调研了两种可行方案，会在下文进行详细介绍。

Recastnavigation寻路

Recsat 是先进的游戏导航网格制作工具。它具有以下几个优点：

• 自动生成，可输入任意关卡几何体并会生成网格。
• 快速，可快速生成关卡数据。
• 代码开放，可自定义核心数据。

Recast 先用关卡几何体生成体素模型，然后再生成导航网格覆盖它。处理过程有三步组成：

1. 构建体素模型
2. 把模型划分到简单的区域
3. 用多边形替换这些区域

体素模型是将输入的三角面栅格化到多层高度域，并简单剔角色不会移动的位置而成。
可移动区被划分为多层二维区域。这些区域都有唯一的非重叠等高线，这样可以简化最后一步的处理过程。
用多边形替换这些区域是指导航多边形沿着这些区域的边界被剥离并简化。

Recastnavigation久负盛名，其代码在GitHub上完全开源，详细地址如下https://github.com/recastnavigation/recastnavigation，但因为它是基于C++的，而unity支持的语言是C#，因此需要要使用C#的P/Invoke来调用它的dll来实现寻路。

接下来介绍Recastnavigation接入unity的流程，主要目的是将其寻路过程暴露出来让帧同步服务器接管，从而实现寻路过程的云端渲染。

前言

Premake认识：https://blog.csdn.net/wuguyannian/article/details/92175725

SDL认识：https://baike.baidu.com/item/SDL/224181?fr=aladdin

P/Invoke认识：https://zhuanlan.zhihu.com/p/30746354

环境

• VS 2019以及完整的C++编译环境（如果没有请自行查阅资料安装）
• Unity 2020.3.3f1c1 (64-bit)，下载unity hub安装对应版本或使用更高版本即可，unity hub下载地址如下https://unity.com/download
• .Net Core 2.2，下载地址如下https://dotnet.microsoft.com/en-us/download/dotnet/2.2，也可以使用VS进行安装
• recastnavigation master，下载地址如下https://github.com/recastnavigation/recastnavigation

正文

1.解压下载的文件

2.将下载的SDL库改名并放到指定路径

解压后的原始路径

复制到recastnavigation-master\RecastDemo\Contrib路径，并改名为SDL

3.将解压的premake5.exe放入指定路径

解压后的原始路径

复制到recastnavigation-master\RecastDemo路径

4.通过命令行控制premake编译recastnavigation为sln工程

# 切换到指定目录
cd E:\recastnavigation-master\RecastDemo
# 运行编译命令
premake5 vs2019

然后目录中会生成一个Build文件夹，里面是我们编译出来的sln工程
路径为recastnavigation-master\RecastDemo\Build\vs2019\recastnavigation.sln
注意项目所有文件目录要保证为全英文，否则可能会出现编译错误

5.构建完成

用VS打开新生成的sln文件，不出意外的话就可以构建并运行RecastDemo工程，也就是我们在它的Github首页看到的渲染图片。

构建用于P/Invoke的dll文件

上述过程是为了运行测试demo，保证项目处于正常可使用的状态，而在unity中使用是我们的最终目标，这需要我们对项目工程进行再次编译，生成可供unity使用的dll文件。

1.新建工程

在VS中新建名为RecastNavDll的工程目录

2.项目配置

将以下四个文件移入recastnavigation-master\RecastDemo\Build\vs2019\RecastNavDll

选中四个文件，右键单击，选择包括在项目中

选中工程，右键单击，添加>引用>选择Detour和Recast两个工程，完成引用
最后选中工程右键，点击生成，dll文件将生成于路径recastnavigation-master\RecastDemo\Build\vs2019\Debug
至此，生成的dll文件可以在unity中进行调用，实现各项功能。

3.与unity桥接

首先将dll文件放入unity项目的plugins文件夹内，然后编写桥接文件，暴露各个方法，使unity工程可以进行调用

public class RecastInterface
    {
        private const string RecastDLL = "RecastNavDll";

        [DllImport(RecastDLL, CallingConvention = CallingConvention.Cdecl)]
        private static extern bool recast_init();

        [DllImport(RecastDLL, CallingConvention = CallingConvention.Cdecl)]
        private static extern void recast_fini();

        [DllImport(RecastDLL, CallingConvention = CallingConvention.Cdecl)]
        private static extern bool recast_loadmap(int id, char[] path);

        [DllImport(RecastDLL, CallingConvention = CallingConvention.Cdecl)]
        private static extern bool recast_freemap(int id);

        [DllImport(RecastDLL, CallingConvention = CallingConvention.Cdecl)]
        private static extern int recast_findpath(int id, float[] spos, float[] epos);

        [DllImport(RecastDLL, CallingConvention = CallingConvention.Cdecl)]
        private static extern bool recast_smooth(int id, float step_size, float slop);

        [DllImport(RecastDLL, CallingConvention = CallingConvention.Cdecl)]
        private static extern int recast_raycast(int id, float[] spos, float[] epos);

        [DllImport(RecastDLL, CallingConvention = CallingConvention.Cdecl)]
        private static extern int recast_getcountpoly(int id);

        [DllImport(RecastDLL, CallingConvention = CallingConvention.Cdecl)]
        private static extern int recast_getcountsmooth(int id);

        [DllImport(RecastDLL, CallingConvention = CallingConvention.Cdecl)]
        private static extern IntPtr recast_getpathpoly(int id);

        [DllImport(RecastDLL, CallingConvention = CallingConvention.Cdecl)]
        private static extern IntPtr recast_getpathsmooth(int id);

        [DllImport(RecastDLL, CallingConvention = CallingConvention.Cdecl)]
        private static extern IntPtr recast_getfixposition(int id, float[] pos);

        [DllImport(RecastDLL, CallingConvention = CallingConvention.Cdecl)]
        private static extern IntPtr recast_gethitposition(int id);

        public static bool HasInited = false;
        
        /// <summary>
        /// 初始化Recast引擎
        /// </summary>
        /// <returns></returns>
        public static bool Init()
        {
            if (HasInited)
            {
                return true;
            }
            else
            {
                HasInited = true;
                return recast_init();
            }
        }

        /// <summary>
        /// 结束化Recast引擎
        /// </summary>
        public static void Fini()
        {
            recast_fini();
        }

        /// <summary>
        /// 加载地图数据，支持同时加载多张地图
        /// </summary>
        /// <param name="id">地图Id</param>
        /// <param name="path">地图文件名（包含路径）</param>
        /// <returns></returns>
        public static bool LoadMap(int id, char[] path)
        {
            if (path == null || path.Length == 0)
                return false;
            return recast_loadmap(id, path);
        }

        /// <summary>
        /// 释放地图数据
        /// </summary>
        /// <param name="id">地图Id</param>
        /// <returns></returns>
        public static bool FreeMap(int id)
        {
            return recast_freemap(id);
        }

        public static Vector3 SPos = new Vector3();
        public static Vector3 EPos = new Vector3();

        /// <summary>
        /// 寻路
        /// </summary>
        /// <param name="id">地图Id</param>
        /// <param name="spos">起点三维坐标</param>
        /// <param name="epos">终点三维坐标</param>
        /// <returns></returns>
        public static bool FindPath(int id, Vector3 spos, Vector3 epos)
        {
            {
                float[] fixPos = fixposition(id, spos);
                if (fixPos != null)
                {
                    spos.y = fixPos[1];
                }
                else
                {
                    Console.WriteLine(string.Concat("错误:", ($"Recast寻路 FindPath Error：- 起点非法 - spos:{spos} - MapId:{id}")));
                }

                SPos = spos;
            }
            {
                float[] fixPos = fixposition(id, epos);
                if (fixPos != null)
                {
                    epos.y = fixPos[1];
                }
                else
                {
                    Console.WriteLine(string.Concat("错误:",($"Recast寻路 FindPath Error：- 终点非法 - epos:{epos} - MapId:{id}")));
                }

                EPos = epos;
            }
            dtStatus status = (dtStatus) recast_findpath(id, new[] { -spos.x, spos.y, spos.z }, new[] { -epos.x, epos.y, epos.z });
            if (dtStatusFailed(status))
            {
                dtStatus statusDetail = status & dtStatus.DT_STATUS_DETAIL_MASK;
                string _strLastError = $"Recast寻路 FindPath Error：寻路失败！错误码<" + statusDetail + $"> - MapId:{id}";
                if (statusDetail == dtStatus.DT_COORD_INVALID)
                {
                    _strLastError += " - 坐标非法！From<" + spos + "> To<" + epos + $"> - MapId:{id}";
                }
                Console.WriteLine(string.Concat("错误:",_strLastError));
                return false;
            }
            else if (dtStatusInProgress(status))
            {
                string _strLastError = $"Recast寻路 Error：寻路尚未结束!- MapId:{id}";
                Console.WriteLine(string.Concat("错误:",_strLastError));
                return false;
            }

            return true;
        }

        /// <summary>
        /// 寻路以后，需要调用本函数，得到真实路径，这条路径可以是很平滑的路径
        /// BUG FIX：如果Smooth函数的第一个参数设置为5，则可能找到的路线非常长（节点达到2048）
        /// </summary>
        /// <param name="id">地图Id</param>
        /// <param name="step_size">平滑系数，数值越小，越平滑；如果给0，则自动变为0.5</param>
        /// <param name="slop">用途不明（但肯定不影响平滑），如果给0，则自动变为0.01</param>
        /// <returns></returns>
        public static bool Smooth(int id, float step_size, float slop)
        {
            return recast_smooth(id, step_size, slop);
        }

        /// <summary>
        /// 射线检测
        /// </summary>
        /// <param name="id">地图Id</param>
        /// <param name="spos">起点三维坐标</param>
        /// <param name="epos">终点三维坐标</param>
        /// <returns></returns>
        public static bool Raycast(int id, Vector3 spos, Vector3 epos)
        {
            dtStatus status = (dtStatus) recast_raycast(id, new float[] { -spos.x, spos.y, spos.z }, new float[] { -epos.x, epos.y, epos.z });
            if (dtStatusFailed(status))
            {
                dtStatus statusDetail = status & dtStatus.DT_STATUS_DETAIL_MASK;
                string _strLastError = "Recast寻路 Raycast Error：寻路失败！错误码<" + statusDetail + $"> - MapId:{id}";
                if (statusDetail == dtStatus.DT_COORD_INVALID)
                {
                    _strLastError += " - 坐标非法！From<" + spos + "> To<" + epos + $"> - MapId:{id}";
                }
                Console.WriteLine(string.Concat("错误:",_strLastError));
                return false;
            }
            else if (dtStatusInProgress(status))
            {
                string _strLastError = $"Recast寻路 Error：寻路尚未结束! - MapId:{id}";
                Console.WriteLine(string.Concat("错误:",_strLastError));
                return false;
            }

            return true;
        }

        /// <summary>
        /// 获取射线检测的碰撞点
        /// <param name="id">地图Id</param>
        /// <returns></returns>
        public static float[] getHitPosition(int id)
        {
            unsafe
            {
                try
                {
                    IntPtr hitPos = recast_gethitposition(id);
                    float[] arrHitPos = new float[3];
                    if (hitPos.ToPointer() != null)
                    {
                        Marshal.Copy(hitPos, arrHitPos, 0, 3);
                        arrHitPos[0] = -arrHitPos[0];
                        return arrHitPos;
                    }
                    else
                    {
                        return null;
                    }
                }
                catch (Exception e)
                {
                    Console.WriteLine(string.Concat("错误:",($"RecstInterface getHitPosition Exception! - {e}")));
                    return null;
                }
            }
        }

        /// <summary>
        /// 在mesh中修正坐标高度
        /// 如果你给的Y坐标太低了，则可能会落到附近其他更低的地方
        /// <param name="id">地图Id</param>
        /// <returns></returns>
        public static float[] fixposition(int id, Vector3 pos)
        {
            unsafe
            {
                try
                {
                    IntPtr fixPos = recast_getfixposition(id, new float[] { -pos.x, pos.y, pos.z }); // （pos.y+1）抬高一点计算
                    float[] arrFixPos = new float[3];
                    if (fixPos.ToPointer() != null)
                    {
                        Marshal.Copy(fixPos, arrFixPos, 0, 3);
                        arrFixPos[0] = -arrFixPos[0];
                        return arrFixPos;
                    }
                    else
                    {
                        return null;
                    }
                }
                catch (Exception e)
                {
                    Console.WriteLine(string.Concat("错误:",($"RecstInterface fixposition Exception! - {e}")));
                    return null;
                }
            }
        }

        public static int[] GetPathPoly(int id, out int polyCount)
        {
            unsafe
            {
                try
                {
                    polyCount = recast_getcountpoly(id);
                    IntPtr polys = recast_getpathpoly(id);
                    if (polys.ToPointer() != null)
                    {
                        int[] arrPolys = new int[polyCount];
                        Marshal.Copy(polys, arrPolys, 0, polyCount);
                        return arrPolys;
                    }

                    return null;
                }
                catch (Exception e)
                {
                    polyCount = 0;
                    Console.WriteLine(string.Concat("错误:",($"RecstInterface fixposition Exception! - {e}")));
                    return null;
                }
            }
        }

        public static float[] GetPathSmooth(int id, out int smoothCount)
        {
            unsafe
            {
                try
                {
                    int polyCount = recast_getcountpoly(id);
                    smoothCount = recast_getcountsmooth(id);
                    IntPtr smooths = recast_getpathsmooth(id);
                    float[] arrSmooths = new float[smoothCount * 3];
                    Marshal.Copy(smooths, arrSmooths, 0, smoothCount * 3);
                    for (int i = 0; i < smoothCount; ++i)
                    {
                        arrSmooths[i * 3] = -arrSmooths[i * 3];
                    }

                    return arrSmooths;
                }
                catch (Exception e)
                {
                    smoothCount = 0;
                    Console.WriteLine(string.Concat("错误:",($"RecstInterface fixposition Exception! - {e}")));
                    return null;
                }
            }
        }

        [Flags]
        public enum dtStatus
        {
            DT_FAILURE = 1 << 31,
            DT_SUCCESS = 1 << 30,
            DT_IN_PROGRESS = 1 << 29,
            DT_STATUS_DETAIL_MASK = 0x0ffffff,
            DT_WRONG_MAGIC = 1 << 0,
            DT_WRONG_VERSION = 1 << 1,
            DT_OUT_OF_MEMORY = 1 << 2,
            DT_INVALID_PARAM = 1 << 3,
            DT_BUFFER_TOO_SMALL = 1 << 4,
            DT_OUT_OF_NODES = 1 << 5,
            DT_PARTIAL_RESULT = 1 << 6,
            DT_ALREADY_OCCUPIED = 1 << 7,
            DT_COORD_INVALID = 1 << 13,
        }

        // Returns true of status is success.
        public static bool dtStatusSucceed(dtStatus status)
        {
            return (status & dtStatus.DT_SUCCESS) != 0;
        }

        // Returns true of status is failure.
        public static bool dtStatusFailed(dtStatus status)
        {
            return (status & dtStatus.DT_FAILURE) != 0;
        }

        // Returns true of status is in progress.
        public static bool dtStatusInProgress(dtStatus status)
        {
            return (status & dtStatus.DT_IN_PROGRESS) != 0;
        }

        // Returns true if specific detail is set.
        public static bool dtStatusDetail(dtStatus status, uint detail)
        {
            return ((uint) status & detail) != 0;
        }
    }

4.简单测试

public static void BenchmarkSample()
{
    BenchmarkHelper.Profile("寻路100000次", BenchmarkRecast, 100000);
}

private static void BenchmarkRecast()
{
    if (RecastInterface.FindPath(100,
        new System.Numerics.Vector3(-RandomHelper.RandomNumber(2, 50) - RandomHelper.RandFloat(),
            RandomHelper.RandomNumber(-1, 5) + RandomHelper.RandFloat(), RandomHelper.RandomNumber(3, 20) + RandomHelper.RandFloat()),
        new System.Numerics.Vector3(-RandomHelper.RandomNumber(2, 50) - RandomHelper.RandFloat(),
            RandomHelper.RandomNumber(-1, 5) + RandomHelper.RandFloat(), RandomHelper.RandomNumber(3, 20) + RandomHelper.RandFloat())))
    {
        RecastInterface.Smooth(100, 2f, 0.5f);
        {
            int smoothCount = 0;
            float[] smooths = RecastInterface.GetPathSmooth(100, out smoothCount);
            List<Vector3> results = new List<Vector3>();
            for (int i = 0; i < smoothCount; ++i)
            {
                Vector3 node = new Vector3(smooths[i * 3], smooths[i * 3 + 1], smooths[i * 3 + 2]);
                results.Add(node);
            }
        }
    }
}

各个方法的具体功能可以配合代码以及其简要的工作流程进行阅读学习

1. 初始化Recast引擎——recast_init
2. 加载地图——recast_loadmap(int id, const char* path)，id为地图的id，因为我们某些游戏中可能会有 多个地图寻路实例，例如Moba游戏，每一场游戏中的地图寻路都是独立的，需要id来区分，path就是寻路数据的完整路径（包含文件名），这个寻路数据我们可以通过RecastDemo来得到
3. 寻路——recast_findpath(int id, const float* spos, const float* epos)，寻路的结果其实只是返回从起点到终点之间所有经过的凸多边形的序号，id为地图id，spos为起始点，epos为中点，我们可以把它们理解为C#中的Vector3
4. 计算实际路径——recast_smooth(int id, float step_size, float slop)，计算平滑路径，其实是根据findpath得到的【从起点到终点所经过的凸多边形的序号】，得到真正的路径（三维坐标），所以这一步是不可缺少的
5. 得到凸多边形id序列——recast_getpathpoly(int id)，得到pathfind以后，从起点到终点所经过的所有凸多边形id的序列
6. 得到寻路路径坐标序列——recast_getpathsmooth(int id)，得到smooth以后，路线的三维坐标序列
   释放地图——recast_freemap(int id)，游戏结束后记得释放地图寻路数据资源嗷
7. 释放Recast引擎——recast_fini()，如果我们在客户端使用，游戏流程结束要使用这个释放Recast引擎
   后续需要实现上述过程的帧同步。
   本文参考工程：https://gitee.com/NKG_admin/NKGMobaBasedOnET

基于Navmesh的Astar算法寻路

未完待续~~