网格寻路算法

㈠ unity2d 做横版平台游戏有什么好的寻路算法或插件

并没一种寻路适合所有场合，选择都是基于需求而定的。

1. A* 算法与贪婪算法不一样，贪婪算法适合动态规划，寻找局部最优解，不保证最优解。
A*是静态网格中求解最短路最有效的方法。也是耗时的算法，不宜寻路频繁的场合。一般来说适合需求精确的场合。
与启发式的搜索一样，能够根据改变网格密度、网格耗散来进行调整精确度。
使用的地方：
a. 策略游戏的策略搜索
b. 方块格子源歼肆雹轿游戏中的格子寻路

2. Unity 自带的导航网格系统
Unity 内置了NavMesh导航网格改告系统，一般来说导航网格算法大多是“拐角点算法”。
效率是比较高的，但是不保证最优解算法。
使用的地方：
a.游戏场景的怪物寻路
b.动态规避障碍

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

机器人家上了解到，在二维二值地图（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属于在动态环境下为躲避动态障碍物、考虑机器人动力学模型设计的规划算法。

㈢ 3D空间寻路

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

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

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

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

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

㈣ 凸面多边形寻路算法

凸多边形是一个内部为凸集的简单多边形。凸多边形（Convex Polygon）指如果把一个多边形的所有边中，任意一条边向两方无限延长成为一直线时，其他各边都在此直线的同旁，那么这个多边形就叫做凸多边形，其内角应该全不是钝角，任意两个顶点间的线段蔽晌位于多边形的内部或边上。

凸面多边形一条边上的任意一点到另外一条边上的任意一点总是可达的。

http://blog.csdn.net/qq_35644234/article/details/60875818

地图网格就是一个凸面多边形的集合
如果可视化就是这样

三维向量(Vector3)：

顶点(Vertex)：

边(Edge)：

凸面(Convex)：

网格(Mesh)：

UML:

1.数据预处理
2.通过floyd算法生成P矩阵
3.利用P矩阵求出路径列表
4.优化路径
5.输出

1.遍历Mesh中每个Convex，生成多边形所有的边
2.将每条边进行切割生成对应的点
3.将位于同一个Convex的点之间建立连通关系并计算权值（通过距离）

1.初始化floyd算法需要的D矩阵和P矩阵
2.通过之前的连通图执行floyd算法
3.生成P矩阵

1.输入起点from，终点to
2.在P矩阵中查找P[from][to]查询下一步的节点next
3.将查询到的结果记录下来，并让from = next
4.循环以上操作获得路径列表

未优化的路径：
[图片上传失败...(image-6fc23e-1538123978488)]
优化后的路径：
[图片上传失败...(image-796ae3-1538123978488)]
1.优化后经过的节点数更少
2.优化后路径更自然
3.优化后路迟顷径更短

首先我们挨个判断每个点是否需要保留。这里通过一种基于视点范围的方法来判断，
我们首先令from点为视点（viewPosition）（及路径中的第一个点），
那么第二个点则为cur点，
我们令cur所在edge的两端点到视点的向量为最小左视野（minLegLeft）和最小右视野（minLegRight）。

现在将cur赋值为第三个点，
我们令cur所在edge的两端点到视点的向量为左视野（legLeft）和右视野（legRight）。
如果cur到viewPosition的向量没有在最小视野当中，证明cur是不可达的，
那么此时最小左视野所在边上的路径点就叫做拐点。
我们首先调整拐点位置，将拐点加入优化后的路径表中，并将拐点作为viewPosition重新进行上述循环。
如果legLeft在minLegLeft右边那么我们令minLegLeft = legLeft
如果legRight在minLegLeft左边那么我们令minLegRight = legRight

调整拐点位置是为了使路径更自然，所以我们应该让视点到拐点与下一个到拐点的向量的夹角变小。
如果此时拐点到下一点的连线在最小宏旦锋左视野左边则拐点往左移，反之往右移。

㈤ 谁能介绍一下JPS寻路算法的思想

这是一个近年来发现的高效寻路算法。不过有一个限制就是只能在规则的网格地图上寻路，而且图上的点或边不能带权重，也就是不能有复杂的地形，只支持平坦和障碍两种地形。

其
思想就是跳过矩形平坦区域的大量对称路径，只寻找所谓的跳跃点，作为搜索的节点。这样做的好处是裁剪了矩形区域内大量的节点，使open
list中的节点数相对较少。要知道，通常启发式搜索算法如A*，大量时间耗费在对open
list的操作上。实现得好的A*算法会使用优先队列，甚至HOT(heap on top）来对操作进行优化。但当open
list中的节点过多，这些操作还是会变得很昂贵。不过JPS有个缺点是每生成一个节点，也就是要找到一个跳跃点，相比较A*算法，是比较昂贵的。幸好通
常来说，得到的收益更多些。所以，在适用的情况下，还是推荐使用JPS的。

具体的实现，主要有两部分。第一部分，从open list中取一个最佳节点，然后从几个特定方向展开搜索，把每个方向得到的跳跃点，加入open list里。第二部分，就是找到一个跳跃点。

对于起始点，可以向所有方向展开搜索。对于其他节点，要看父节点指向本节点的方向，向所有自然邻居和被迫邻居节点方向进行搜索。
例如下图的例子，对于节点n和父节点p和障碍x，+是n的自然邻居，也就是说从p到n到+是最佳路径。如果x不是障碍，从p到n到-不是最佳路径，因为从p到x到-最近。但是如果x是障碍，那么从p到n到-就是最佳路径了，所以这时候称-为被迫邻居。
- + +
x n +
p x -
以上是n和p对角的例子。还有种情况是n和p是直线：
x x -
p n +
x x -

搜
寻跳跃点是递归进行的。首先判断一个节点是否是跳跃点。如果这个点有被迫邻居，那么这个节点就是跳跃点。第二种情况，如果这个节点是目的地节点那么也当作
跳跃点。如果不是，那么就递归地沿本来方向继续搜寻下去。对于对角方向要额外多做两步，即先对其相应的（左右两个）直线方向进行搜索，如果找到跳跃点，就
把自身也当作跳跃点返回。如果直线没找到，那么就一样继续按对角方向递归寻找跳跃点，并返回那个跳跃点。

㈥ 算法 & 数据结构——导航网格

这是之前写的寻路算法 《栅格导航寻路》

生成网格：
将区域用多边形划分，产生可用于寻路的网格信息。通前枯常多边形的顶点都是有序的，这样有利于算法实现。其次虽然多边形的大小不用一致，但使用大小相差不大的多边形也有利于算法实现。

搜索路径：
通过任意一种寻路算法，从网格信息中锁定一组网格路径，这组网格路径就是导航网格，再通过这组导航网格确定一条最快的路径。

本文使用相关算法与数据结构：
网格生成算法：德洛内三角剖分
锁定导航网格算法：A*
导航网格寻路算法：拐角算法

参考博文中是这样描述的：

思路还算简单。

运行效果：

内部有圆圈的三角形为可走区域，空白为不可走区域，红圈表示被锁定的导航网格，红线是最优梁圆路径。

GitHub 包含橡悔塌寻路&网格生成两部分，附带已编译好的exe文件bin/目录下

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

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

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

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

A Star一般使用场景：

• 策略游戏的策略搜索

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

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

Navigation一般使用场景：

• 游戏场景的怪物寻路

• 动态规避障碍

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

AStar的话，

㈧ mesh的map设置

Mesh Map是指根据已知点的位置和它们之间的连接关系，构建一个图形结构或者地图结构。在游带困明戏中，Mesh Map通常会用于路径规划和碰撞检测等方面，是非常重要的一种数据结构。以下是Mesh Map的设置步骤：

1. 创建一个MeshMap数据结构，并初始化所有节点。蠢告节点包括二维平面上的网格坐标和一个节点类型。

2. 对于每个节点，查找它与相邻节点之间的连接关系，建立相应的边。可以使用A*寻路算法、Dijkstra算法等方法来确定两个节点之间的最短路径。

3. 对于多个MeshMap，可以使用Merge算法将各个MeshMap合并成一个更大的MeshMap。

4. 使用MeshMap进行路径规划，并且可以通过MeshMap上的节点来确定是否到达了目标位置。

5. 针对不同的游戏场景，需要对MeshMap进行尺侍不断的优化，以确保其具有更高的效率和精度。例如，可以将MeshMap划分为不同的区域，并为不同区域设置不同的参数