unity 游戏中的寻路与导航系统（5种寻路算法详解） |
您所在的位置：网站首页 › 游戏地图转化为a星寻路地图插件 › unity 游戏中的寻路与导航系统（5种寻路算法详解） |
unity 游戏中的寻路与导航系统（5种寻路算法详解）
|
@了解游戏中常见的寻路方式 通常来讲一般是根据建模方式来决定寻路方式 常见的寻路方式——建模方式这里提供一下三种建模方式的示意图，如下 ，分别对应着，原图、Grid、WayPoint、NavMesh 从三个角度来分别比较一下三种建模 1.实现复杂度：NavMesh > Gird > WayPoint; 2.内催和计算机开销: Gird >NavMesh > WayPoint; 3.表达精确性: NavMesh > Gird > WayPoint; Grid（格子）:实际上是通过把原始地图分割称为格子，在计算机中标识唯一个二维数组，用0和1分别表示障碍和可行走区域格子的密度在一定程度上代表了寻路的精度。 1. 优点 ： 1. 容易实现 2. 容易动态修改 1. 如果需要动态加入障碍，只需要确定障碍物会张勇那些格子，然后重新寻路即可 3. 缺点： 1. 内存和计算机开销大 1. 越大的地图，所分割出来的格子就越多，那么响应的内存占用和计算机开销就会变得很大。 2. 分割格子大小的度量也不容易确定，分的大了，会缩小可以行走的区域，如果定的小了，又会增加内存与计算机的开销） 2. 可能需要做额外的平滑 1. 由于地图都是通过格子分割出来的，那么在寻路的时候，角色所能行走的路线中，同样也会出现90度的拐角，甚至可能有连续的多个拐角，这样的话会导致这种游戏寻路变得很僵硬，所以需要做额外的平滑。 3. 并不是很适合3D地图 1. 格子寻路最早是针对与2D地图寻路提出来的，并没有涉及到高度的问题，可以设想一下，在3D地图中，地表面是起起伏伏的，比如说可能回有城墙，如果使用格子寻路的话，他可能会忽略这个高度，而直接将城墙所在的位置标识为可以到达的区域，因此，格子寻路并不适合3D地图 WayPoint （这种方法会在地图中标注一些路点，寻路只能发生在路点和路点之间，在计算机中表示为一张连通图。）点的密度可以代表寻路精度 1. 优点 1. 实现简单 2. 内存和计算机开销低 1. 路点寻路只是使用到了真是可行走区域的一小部分，与格子相比，牺牲了路线的灵活性，换取交第的内存和计算机开销，可以观察一下上图（c），只要两个黑点之间是连通的，那么角色就可以按照黑点所在的位置到达目标黑点的位置。 2. 缺点 1. 需要人工参与 （因为需要人工标注路店位置和可行走的路线） 2. 局限性比较大 1. 通过以上的解释，可以看出来，路点寻路实际上是非常僵硬的，他必须按照游戏设定初期，人为规定好的路线去行走，这样的话，有可能会给玩家这样的体验，明明可以直接到达的地方，通过寻路只能绕来绕去，花费了很多不必要的时间，当然，如果对于那些通过上线时间来获取利润或者其他奖励的游戏，无可厚非（但只是特例） 2. 对于起始点不在路点图中的情况，还必须要找到最近的路点，然后再移动到角色想要到达的目的路点 3. 路点并不考虑实际的底层地图，比如说，我在游戏中有一个坐标是，角色只能通过条约才能过去的路障，那么就有可能出现这样的情况，角色在移动过程中，可能会被某些阻碍物阻挡而卡住的情况； NavMesh （ 这种方法使用一系列算法将原始地图转换成三角形网格的集合，网格和网格之间构成连通关系用于寻路。在计算机中表示为顶点的集合，以及三个顶点索引一组（边）的集合。） 1. 优点 1. 精确表达世界 1. 虽然导航网格无法做到还原全部地图，但是他实际上比上述说的两种导航更为精确。 2. 这种导航建模引入了高度星系，这样的话就可以很方便的表示3D地图 2. 内存和计算机开销小 1. 导航网格在形成的时候，会将地图抽象成三角网格，也就是顶点和边的模型，消耗的性能要比较小。 2. 缺点 1. 复杂、难以实现和修改，自己从头开始创建一个导航网格系统的确是特别复杂的，需要很多集合算法的知识，**unity可以自动烘培一个网格系统，所以对unity开发人员来说，，这点不算什么（当然如果人工制作这个网格系统的话，就很麻烦了）** 在很大的地图中的寻路，一般可以用Waypoint 与其他的寻路方式结合使用 总结1.gird 一般适合2D地图 2.Waypoint一般是与其他寻路方式结合，可以用来做2D地图，也可以3D地图，比如说，在游戏中寻路从我到北京的路径，我当前所在位置距离苏州很近，那么就可以先用Navmesh寻路我到苏州的最短路径，然后再使用waypoint 提前设定一条苏州到北京的路径，也是比较好的方案 3.Navmesh 一般用作3D地图 总结，三种寻路方式的优缺点在上文已经讲述了，其实寻路方案没有最好，只要适合你就行了，读者可以根据自己的情况进行选择 常见的寻路方式——算法*（以下的算法一般都使用在gird上）1.数据结构 1.树 2.图 2.算法 1.深度优先 2.广度优先 3.dijkstra 4.A* 2D格子 结合深度优先或者广度优先 5.B* 接下来具体的解释一下这几种算法，先来看两张图，分别是正常的游戏地图与开发人员眼中的地图 
图的正则表达式是G=(V,E)其代表了顶点的集合，EheV是一种二元关系，可以简单的理解为边，比如说有条边是从顶点A到顶点D结束，那么就可以用（A，D）来表示，图的大致分类有两种，有向图和无向图，如下 无向图 E（G）= {（V1,V2），（V1，V3），（V2，V6），（V2，V5），（V2，V4），（V4，V3），（V3，V5），（V5，V6）} 有向图 E（G）= {，，，，，，，，，} 简单的了解了一下数据结构之后，我们来看一下算法 在进行寻路系统的制作的时候，选择一个好的算法尤其重要，他不单单要考虑复杂度，还要考虑内存与计算机的开销等等因素。 寻路算法1.深度优先搜索（邻接矩阵实现） 深度优先（DFS）是一种遍历树或者图的算法，假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点（未连通），则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 递归实现的伪代码 （1）访问顶点v；visited[v]=1；//算法执行前visited[n]=0 （2）w=顶点v的第一个邻接点； （3）while（w存在） if（w未被访问） 从顶点w出发递归执行该算法； w=顶点v的下一个邻接点；非递归实现的伪代码 （1）栈S初始化；visited[n]=0； （2）访问顶点v；visited[v]=1；顶点v入栈S （3）while(栈S非空) x=栈S的顶元素(不出栈)； if(存在并找到未被访问的x的邻接点w) 访问w；visited[w]=1； w进栈; else x出栈；但是由于这个算法计算的并不是最短路径，所以在寻路算法中基本不用 广度优先遍历广度优先遍历类似于树的层序遍历 从图中某顶点触出发进行广度优先遍历的基本思想是 1.先访问顶点v 2.依次访问v的各个未被访问的邻接点 3.分别从上一步中的邻接点中依次出发访问他们未被访问的邻接点，具体如下图 从上述的解释中可以看出，他的效率很低，时间复杂度是T（n） = O（n2），顶点与顶点之间没有权重，没有办法定义优先级，所以不能找到最优路线，比如说，如果在地图中遇到高山，那么算法应该是绕过去而不是遍历。 从上述的广度优先遍历来看，他并不会避免那些角色不能到达的位置，所以我们解决的痛点就是怎样才能在遍历的时候避免这样的情况，这也就是Dijkstra算法所解决的事情——为每一条边添加一个权重，重复的更新最短路径 Dijkstra 算法用来求出单元点最短路径问题，他是由迪杰斯特拉踢出的一种按照路径长度递增的次序产生最颠路径的算法，其基本思想是，设置一个集合S存放已经找到的最短路径的顶点，S的初始状态只包含远点V对Vi属于V-S，假设从远点V到Vi的有向边为最短路径，以后没球德一条最短路径V。。。Vk，就将Vk加入集合S中，并将路径V。。。Vi与原来的假设相比较，取路径长度较小者为当前最短路径，重复上述过程，一直到集合V中所有顶点加入到集合S中。 |
对于一张地图，开发人员需要通过一定的方案将其转换称为数据对象，最常见的就是将地图切割成为网格，或者切割称为多边形，这取决于你的游戏地图，一般情况下，同等面积的地图中采用更少的顶点，寻路算法会更快，而寻路算法中最常见的数据结构就是图，我们先来了解一下图
V（G）= {V1，V2，V3，V4，V5，V6}
V（G）= {V1，V2，V3，V4，V5，V6}
首先访问V0，然后将V0入队，然后V0取出，一次访问他的邻接点V1,V2,V5,并将这三个邻接点依次入队，将V1取出，依次访问V1的所有未被访问的邻接点V4，然后V4入队，重复上述过程，访问完所有图中的顶点； 从上述的解释中可以看出，BFS（广度优先遍历）是一种盲目搜寻的办法，她并不考虑结果的可能位置，而是彻底的搜索整张地图，一直到他找到结果为止
下面来说一下DIjkstra算法基于的储存结构 1.图的储存结构，因为在算法执行过程中，需要快速的球的任意两个顶点之间边上的权值，所以采取邻接矩阵储存 2.辅助数组dist[n]；元素dist[i]表示当前所找到的从原点v到终点vi的最短路已经长度，初态：若从v到vi由弧，则dist[i]表示为弧上的权值；否则则置dist[i]为无穷大，若当前求得的终点为vk，则根据下式进行迭代：dist[i] = min {dist[i],dist[k]+arc[k][i] 0【本文地址】