三维网格寻路算法

㈠ 如何使用Unity3D做游戏中的寻路导航

现在的大部分mmo游戏都有了自动寻路功能。点击场景上的一个位置，角色就会自动寻路过去。中间可能会有很多的障碍物，角色会自动绕过障碍物，最终达到终点。使用Unity来开发手游，自动寻路可以有很多种实现方式。
最近，一名海外开发者在博客中分享了自己用Unity引擎重做此前研发的Flash游戏寻路导航的心得，希望可以给大家带来帮助：
大家好，最近我一直都在忙于把2006年的一款Flash游戏用Unity引擎重做出来，尽管我们在《Arrival in Hell》这个项目已经工作了一年多，但这里我希望从头开始来写开发者博客，因为这样才能让读者们有比较完整的印象。
如果你们不太熟悉这款游戏的话，我这里做几句话的介绍，我们在对2006年我和朋友Eardo Mojica以及Richard Rout三人研发的一款Flash游戏进行重做，这是一款点击式操作的冒险游戏，我们将用Unity引擎进行重做。我做编程和研发游戏已经有十年左右的经验，但这是我使用Unity引擎做的首款游戏。
在其他事情之前，我首先想要说的就是玩家角色的移动，由于这款游戏现在是真正的3D，因此玩家角色需要在3D空间里寻路。幸运的是，Unity引擎已经有了一些不错的内置寻路功能，你只要打开窗口-导航（Navigation），选择你想要使用的物体并且放到路径中，然后把他们标记为‘导航静态（Navigation static）’这就会告诉Unity这些物体是静态的（非移动），在寻路的时候应该被考虑进去。

把物体设置为‘导航静态’
这里我想要说一说这个功能有多么强大。过去，我和大多数的游戏开发者一样，都必须打造自己的寻路系统，我之前就做过一个A*tile和基于节点的寻路系统，在两种情况下，特别是基于节点系统的寻路所产生的walls让人非常头痛。在基于节点的寻路系统中，你必须手动地把AI使用的点在两者之间进行导航。Unity不仅做导航功能，还使用了导航网格（Navigation meshes），这比手动放置节点更有效率而且更流畅。更重要的是，你还可以一键重新计算整个导航网格，彻底摆脱了手动修改导航节点的做法。

我用基于节点系统做的失败的寻路系统之一
在把静态物体加入了导航网格之后，你可以选择一系列的设定然后点击bake按钮，比如在考虑加入一堵墙之前确定坡有多陡以及台阶应该多高。这样你就可以获得可以预览的视图。值得注意的一件事是，不要仅仅因为物体存在在场景中就意味着它是导航网格的一部分。比如说在这款游戏中，我不在乎玩家们是否会踩到瓦砾，所以我并没有把任何瓦砾标识为导航静态，这加快了当行网格的生成速度。

《Arrival in Hell》中其实是有数值的
在导航网格生成之后，我简单地给玩家模型增加了一个NavMeshAgent组件，这款游戏现在就可以进行寻路了，唯一剩下的就是增加鼠标输入控制NavMeshAgent的目的地。

用NavMesh做的bake

NavMeshAgent设定
为了告诉NavMeshAgent导航我做了以下指令：
1.注意听取鼠标输入
2.把鼠标放进屏幕空间
3.把屏幕空间转变成来自摄像头的一束光
4.在光达到地面的时候把它移除
5.把NavMeshAgent的目的地设定到地板的对应位置。
C#代码是这样的：

可视化视图下的目的地与路径
这就解决了我这款游戏的大多数导航需求，唯一的例外就是导航网格由于游戏内的一些活动而发生改变的时候。比如第一个房间的们最开始是关闭的，后来当它打开的时候，当行网格需要更新反映此次变化，允许玩家从新开的们中走过去。我并没有在游戏运行的时候rebake完整的静态导航网格，而是使用了NavMeshObstacle组件，该组件可以让你把寻路过程中的动态物体加进去，如果物体移动，Unity的寻路算法就会根据实际情况而更新。

导航路径会根据NavMeshObstacle的变化而自动发生改变

可视化视图
所以，游戏寻路导航就这么做好了，这就是《Arrival in Hell》游戏中的导航工作原理，这一些只需要Unity内自带的导航功能就可以完成了。

㈡ 有哪些应用于移动机器人路径规划的算法

机器人家上了解到，在二维二值地图（FREE or OCCUPIED）场景下进行路径规划的方法。我看之前有同学在回答的时候配上了这幅图：

这幅图上的算法罗列的还是很全面的，体现了各个算法的出生顺序。但是并不能很好的对他们进行一个本质的分类。刚刚那位同学说的graph-based和sampling-based的分类方法我感觉有点概念重叠不能够对规划算法进行这样的分类，下面通过自己这一年多的研究和实践对规划算法进行一个简单的分类：

这幅图上的算法罗列的还是很全面的，体现了各个算法的出生顺序。但是并不能很好的对他们进行一个本质的分类。刚刚那位同学说的graph-based和sampling-based的分类方法我感觉有点概念重叠不能够对规划算法进行这样的分类，下面通过自己这一年多的研究和实践对规划算法进行一个简单的分类：

两大类：
1. 完备的（complete)
2. 基于采样的（sampling-based）又称为概率完备的

一 完备的规划算法

A*算法

所谓完备就是要达到一个systematic的标准，即：如果在起始点和目标点间有路径解存在那么一定可以得到解，如果得不到解那么一定说明没有解存在。
这一大类算法在移动机器人领域通常直接在occupancy grid网格地图上进行规划（可以简单理解成二值地图的像素矩阵）以深度优先寻路算法、广度优先寻路算法、Dijkstra(迪杰斯特拉)算法为始祖，以A*算法(Dijstra算法上以减少计算量为目的加上了一个启发式代价)最为常用，近期的Theta*算法是在A*算法的基础上增加了line-of-sight优化使得规划出来的路径不完全依赖于单步的栅格形状（答主以为这个算法意义不大，不就是规划了一条路径再简单平滑了一下么）。
完备的算法的优势在与它对于解的捕获能力是完全的，但是由此产生的缺点就是算法复杂度较大。这种缺点在二维小尺度栅格地图上并不明显，但是在大尺度，尤其是多维度规划问题上，比如机械臂、蛇形机器人的规划问题将带来巨大的计算代价。这样也直接促使了第二大类算法的产生。

二 基于采样的规划算法

RRT-connect算法
这种算法一般是不直接在grid地图进行最小栅格分辨率的规划，它们采用在地图上随机撒一定密度的粒子来抽象实际地图辅助规划。如PRM算法及其变种就是在原始地图上进行撒点，抽取roadmap在这样一个拓扑地图上进行规划；RRT以及其优秀的变种RRT-connect则是在地图上每步随机撒一个点，迭代生长树的方式，连接起止点为目的，最后在连接的图上进行规划。这些基于采样的算法速度较快，但是生成的路径代价（可理解为长度）较完备的算法高，而且会产生“有解求不出”的情况（PRM的逢Narrow space卒的情况）。这样的算法一般在高维度的规划问题中广泛运用。

三 其他规划算法
除了这两类之外还有间接的规划算法：Experience-based（Experience Graph经验图算法）算法：基于经验的规划算法，这是一种存储之前规划路径，建立知识库，依赖之进行规划的方法，题主有兴趣可以阅读相关文献。这种方法牺牲了一定的空间代价达到了速度与完备兼得的优势。此外还有基于广义Voronoi图的方法进行的Fast-marching规划，类似dijkstra规划和势场的融合，该方法能够完备地规划出位于道路中央，远离障碍物的路径。答主最近也在研究此类算法相关的工作。

APF（人工势场）算法

至于D* 、势场法、DWA(动态窗口法)、SR-PRM属于在动态环境下为躲避动态障碍物、考虑机器人动力学模型设计的规划算法。

㈢ 有关A* 寻路算法。 看了这个算法 大致都明白。就是有点不大清楚。

1. B的G值是指从起点A开始，到达该点的最短距离，和B在不在最短路径上没有关系。

2. 不是遍历所有路径，而是所有点。对于m*n的矩阵， 遍历所有点的复杂度是m*n（多项式复杂度），而遍历所有路径的复杂度是4的(m*n)次幂(每个点都有4个可能的方向)。从幂指数复杂度降低到多项式复杂度，这就是A*算法的意义所在。

3. 最优路径是要从终点一步步倒退回来。比如终点的G值是k，那么最多需要4*k次查找，依然是多项式复杂度。但多数问题(对于纯算法题来说)只是需要知道到达终点的步骤，很少要你找出固定路径的。

㈣ 梦幻西游自动寻路的寻路算法怎么算

A*寻路算法 A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。
公式表示为： f(n)=g(n)+h(n),
其中f(n) 是节点n从初始点到目标点的估价函数，
g(n) 是在状态空间中从初始节点到n节点的实际代价，
h(n)是从n到目标节点最佳路径的估计代价。
保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：
估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。
如果 估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
估价值与实际值越接近，估价函数取得就越好。
例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索过程：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->
While(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
else
{
if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值; //取最小路径的估价值
if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于CLOSE表的估价值 )
更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值
if(X not in both)
求X的估价值;
并将X插入OPEN表中; //还没有排序
}
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的
节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，便没有舍弃节点（除非该节点是死节点），在每一步的估价
中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最
好优先的算法。只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！
我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：
f'(n) = g'(n) + h'(n)
这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最断路经的启发值。由于这个f'(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做
近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可（这一点特别的重要）。可以证明应用这样的估价
函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。哈。你懂了吗？肯定没懂。接着看。
举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是
。当然它是一种最臭的A*算法。
再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函
数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计
算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。
}

㈤ A星寻路算法和Unity自带的寻路相比有什么优势

在理解Navigation的时候，首先要明确两个知识点：

AStar：AStar是路点寻路算法中的一种，同时AStar不属于贪婪算法，贪婪算法适合动态规划，寻找局部最优解，不保证最优解。AStar是静态网格中求解最短路最有效的方法。也是耗时的算法，不宜寻路频繁的场合。一般来说适合需求精确的场合。

性能和内存占用率都还行，和启发式的搜索一样，能够根据改变网格密度、网格耗散来进行调整精确度。

A Star一般使用场景：

• 策略游戏的策略搜索

• 方块格子游戏中的格子寻路

Navigation：网格寻路算法，严格意义上它属于”拐角点算法”，效率是比较高的，但是不保证最优解算法。Navigation相对来说消耗内存更大，性能的话还不错。

Navigation一般使用场景：

• 游戏场景的怪物寻路

• 动态规避障碍

它们二者事件的实现方式和原理都不同。

AStar的话，

㈥ 3D空间寻路

A*算法，无论你是2D的还是3D的，甚至是4D的，
只要增加方向向量就行了。

生成网格后，肯定可以查询到每个点的旁边一共有哪些点是可行走的，走过去需要多少代价。因此也不需要考虑空间结构，只要写好查询周边点的函数就行了。

对已查询到的点，进行行走代价的堆排序，取出顶点计算是否可到达目的，不能则查询周围点，加入堆中。然后继续取顶点。

具体程序写法要自己研究下。

A*算法：http://ke..com/view/7850.htm

㈦ A*搜寻算法的简介

速度和精确度之间的选择前不是静态的。你可以基于CPU的速度、用于路径搜索的时间片数、地图上物体（units）的数量、物体的重要性、组（group）的大小、难度或者其他任何因素来进行动态的选择。取得动态的折衷的一个方法是，建立一个启发式函数用于假定通过一个网格空间的最小代价是1，然后建立一个代价函数（cost function）用于测量（scales）：
g’(n) = 1 + alpha * ( g(n) – 1 )
如果alpha是0，则改进后的代价函数的值总是1。这种情况下，地形代价被完全忽略，A*工作变成简单地判断一个网格可否通过。如果alpha是1，则最初的代价函数将起作用，然后你得到了A*的所有优点。你可以设置alpha的值为0到1的任意值。
你也可以考虑对启发式函数的返回值做选择：绝对最小代价或者期望最小代价。例如，如果你的地图大部分地形是代价为2的草地，其它一些地方是代价为1的道路，那么你可以考虑让启发式函数不考虑道路，而只返回2*距离。
速度和精确度之间的选择并不是全局的。在地图上的某些区域，精确度是重要的，你可以基于此进行动态选择。例如，假设我们可能在某点停止重新计算路径或者改变方向，则在接近当前位置的地方，选择一条好的路径则是更重要的，因此为何要对后续路径的精确度感到厌烦？或者，对于在地图上的一个安全区域，最短路径也许并不十分重要，但是当从一个敌人的村庄逃跑时，安全和速度是最重要的。
在游戏中，路径潜在地花费了许多存储空间，特别是当路径很长并且有很多物体需要寻路时。路径压缩，导航点和beacons通过把多个步骤保存为一个较小数据从而减少了空间需求。Waypoints rely on straight-line segments being common so that we have to store only the endpoints, while beacons rely on there being well-known paths calculated beforehand between specially marked places on the map.如果路径仍然用了许多存储空间，可以限制路径长度，这就回到了经典的时间-空间折衷法：为了节省空间，信息可以被丢弃，稍后才重新计算它。

㈧ 三维点最短路径寻路算法求助

题目描述得不够清楚啊，若干个点就是能作为中途点的那些点么？

如果所有的点都能作为中途点，当然走直径，直接走A到B的直线。

否则，如果只有几个，只能用启发式或者广度搜索吧，因为还有可能根本就没有解。
如果中途点不多的话，可以直接从A出发，计算不超过L距离的那些中途点，然后以那些中途点为出发点，继续计算不超过L距离的点（走过的点就不计入），直到遇到B为止。这种方法就是广度搜索，在同一层距离最短的则为最短路径。
如果中途点过多，无法这样计算的话，限定范围。

㈨ 游戏中的常用的寻路算法有哪些

f(n)=g(n)+h(n) 从起始点到目的点的最佳评估值
– 每次都选择f(n)值最小的结点作为下一个结点，
直到最终达到目的结点
– A*算法的成功很大程度依赖于h(n)函数的构建
?;) = g(n? 在各种游戏中广泛应用 Open列表和Closed列表
– Open列表
A*算法
? h(n) = 从结点n到目的结点的耗费评估值，启发函数
?，程序返回n
else 生成结点n的每一个后继结点n;
foreach 结点n的后继结点n;{
将n’的父结点设置为n
计算启发式评估函数h(n‘)值，评估从n‘到node_goal的费用
计算g(n‘) = g(n) + 从n’到n的开销
计算f(n?? 在算法启动时，Closed列表为空 A* 算法伪代码初始化OPEN列表
初始化CLOSED列表
创建目的结点；称为node_goal
创建起始结点；称为node_start
将node_start添加到OPEN列表
while OPEN列表非空{
从OPEN列表中取出f(n)值最低的结点n
将结点n添加到CLOSED列表中
if 结点n与node_goal相等then 我们找到了路径;)
if n‘位于OPEN或者CLOSED列表and 现有f(n)较优then丢弃n’ ;) + h(n?? 包含我们还没有处理到的结点
? g(n) = 从初始结点到结点n的耗费
?? 包含我们已经处理过的结点
，处理后继n’
将结点n‘从OPEN和CLOSED中删除
添加结点n‘到OPEN列表
}
}
return failure （我们已经搜索了所有的结点?? 启发式搜索
– 在搜索中涉及到三个函数
??? 我们最开始将起始结点放入到Open列表中
– Closed列表
?

㈩ unity导航网格里哪个函数是获取路线的

在Unity3d中，我们一般常用的寻路算法：
1.A*算法插件
与贪婪算法不一样，贪婪算法适合动态规划，寻找局部最优解，不保证最优解。A*是静态网格中求解最短路最有效的方法。也是耗时的算法，不宜寻路频繁的场合。一般来说适合需求精确的场合。
与启发式的搜索一样，能够根据改变网格密度、网格耗散来进行调整精确度。
使用较好的地方：
a.策略游戏的策略搜索
b.方块格子游戏中的格子寻路
2.U3D自带的导航网格系统
U3D内置了NavMesh导航网格系统，一般来说导航网格算法大多是“拐角点算法”，具体大家可以去查下。效率是比较高的，但是不保证最优解算法。
使用较好的地方：
a.游戏场景的怪物寻路
b.动态规避障碍
3.WayPoint寻路插件
速度最快，但相应来说表现也非常局限，它常常走“Z”型的轨迹，并不适合复杂场合的使用。例如它不能根据宽度、高度、路径点耗散等来改变行进路径。
使用较好的地方：
a.塔防怪物行进路径
b.AI巡逻路线