Unity dynamic pathfinding using A* Pathfinding Project | Unity动态更新导航使用A* Pathfinding Project

最近遇到不少坑,比如在用OpenGL写一个烂俗的魔方的大作业,发现GLUT的pop-up menu,居然GLFW没有,还没想好怎么办。还有一个坑是Unity动态更新导航(Rebake Navigation on runtime)。Unity自带的NavMesh功能固然好用,但有两个缺陷:
1. 只能根据NavMeshObstacle更新NavMesh,NavMesh的烘培只能在Editor里,不能动态更新NavMesh
2. NavMesh固定Y为垂直方向

这就无法满足最近在做的项目的需求了,
1. 需要动态加载场景,也就是不仅障碍物是动态的,道路也是动态加载的。当然稍微好做一点是因为这个项目里动态加载的都是模块Prefab,这要是全部Procedural场景目测要复杂不少。。
2. 重力方向要runtime改变,不过稍微简单一点的是其实重力方向只有六种可能X+, X-, Y+, Y-, Z+, Z-. 其实一种权宜之计是runtime转模型就成了,保持重力朝向Y-。但这个项目里不行,因为是要用Vuforia做AR,真实世界的重力又不能变。。。当然这就导致CharacterController不能用,因为它不能变重力方向。。。所以还要重写一个controller。。。

MD怎么办啊。Unity Answers上面有一个回答想了想找了找,发现了一个Unity扩展包,A* Pathfinding Project

那么可以先讲一下背景,A*搜索算法

笔者其实对这个搜索算法并不陌生。计辅上过人工智能导论,还自己写过A*,没想到居然在游戏导航里有这么大应用。大意就是作为一个考虑路径耗散的搜索问题(就像最短怎么走出迷宫),可以用贪心算法解决。对每一个状态给出一个目标函数h(n),根据目标函数来深度优先搜索。但这有一个问题就是贪心只能找到局部最优解,所以A*做了改进,目标函数写成f(n)=g(n)+h(n),目标函数除了一项到达目的的评估函数,还有一项从上一个状态到这个状态的评估函数。

关于游戏中寻路的A*有文章比较好:Introduction to A star

有一些资料:A* Pathfinding官网,以及文档下载地址在此

Pro版是100刀,笔者这个用免费版就够了。示例文件在下下来的unitypackage里面都有,操作在文档中也比较详细。下面先快速入个门讲一下基本概念。

这个插件里有五种导航方式,
1. Grid Based

就是做了个投影网格,搜索也都是基于这个网格的。优点是runtime更新比较快,但是问题是免费版里面这个只有一层,而且是必须Y是垂直方向。
2. NavMesh

这个和Unity自带的NavMesh基本一致。相比于GridBased,节点少,搜索起来快。但这个mesh需要手动建模出来,不像unity里可以自动生成。
3. Node Based

和上面不一样的是,这个直接node作为搜索的节点。也就是说这些node是可以到达的,node间的连接作为被搜索的图。所以这个自由度很大。但问题是可行走的区域是用node定义的,是一个点,不是一个面。。。另外node也能太疏松,要不然玩家点的位置不精确就跑到障碍物另一边去了。。。

  1. RecastGraph

    这个pro版才有,没用过。看介绍是用体素(voxel)的方式生成NavMesh。欸那是不是跟Unity的NavMesh差不多。。。

  2. Layer Based Grid

    就是一个可以有很多层的Grid Based,比如房子有很多层就可以用这个。但作者说这个还不能update。。。

笔者这个项目又要动态更新,又有重力变换,那就只好用Node Based的咯。具体可以是每一个场景的模块都预制好node,贴好tag。加载进去直接撸连接。

GraphNode类里面可以AddConnection,这就可以脚本里增加连接了。

具体的实现就不贴啦。国庆假期就要结束啦,上学上班愉快!

发表评论

电子邮件地址不会被公开。 必填项已用*标注