一种高效寻路的处理方法、装置、设备及介质与流程

1.本技术涉及人工智能技术领域，具体涉及一种高效寻路的处理方法、装置、设备及介质。


背景技术：

2.智能寻路技术是人工智能在游戏领域中一个重要的应用，可以增加游戏的可玩性、增强游戏的逼真效果，从而为创造更加真实的虚拟世界起着至关重要的作用。在智能寻路研究领域，a*算法是使用最广泛的智能寻路算法，也是最有效的最短路径搜索算法。但是，针对不同的游戏类型、地图类型和策略玩法等，采用单一的寻路策略难以做到完全适应，从而难以提高寻路效率。


技术实现要素：

3.本技术实施例公开了一种高效寻路的处理方法、装置、设备及介质，可以有效提高寻路效率。
4.本技术实施例公开一种高效寻路的处理方法，包括以下步骤：
5.根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略，构建所述寻路策略下所述当前地图的地图模型，以及从所述寻路策略中确定所述地图模型的目标寻路算法，其中，所述寻路策略包括格子寻路、路点寻路、导航网格寻路中的一种或多种的组合；
6.通过所述目标寻路算法在所述当前地图模型中确定目标路径。
7.可选地，所述根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略，构建所述寻路策略下所述当前地图的地图模型，以及从所述寻路策略中确定所述地图模型的目标寻路算法，包括：
8.若所述当前地图的地图类型为2d地图且所述当前地图上障碍物分布存在动态变化，确定所述寻路策略为格子寻路，并构建所述当前地图的地图模型为格子地图，确定所述格子地图的目标寻路算法为a*算法/jps跳点寻路算法。
9.可选地，若所述目标寻路算法为a*算法，所述通过所述目标寻路算法在所述当前地图模型中确定目标路径，包括：
10.通过兰森汉姆算法预先判断格子地图上的指定点之间是否能够直接通行，若是，则直接返回两点的直线路径，反之，则执行a*算法寻路；
11.和/或
12.预先建立节点池，若所述a*算法执行过程中触发节点空间分配，从节点池中取出处于空闲状态的节点进行计算，并在计算完成后重新放入所述节点池；
13.和/或
14.通过完全二叉树优化开放列表，以在每次插入或删除节点后，所述开放列表中最小的估价函数值对应的节点位于二叉树的根节点；
15.和/或
16.基于关键点优化算法删除目标路径上转角位置的多余节点，以平滑所述目标路径。
17.可选地，所述根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略，构建所述寻路策略下所述当前地图的地图模型，以及从所述寻路策略中确定所述地图模型的目标寻路算法，包括：
18.若所述当前地图的地图类型为2d地图、所述当前地图的地形唯一以及所述当前地图上不存在障碍物，确定所述寻路策略为路点寻路，并构建所述当前地图的地图模型为路点地图，确定所述路点地图的目标寻路算法为路点寻路算法。
19.可选地，所述根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略，构建所述寻路策略下所述当前地图的地图模型，以及从所述寻路策略中确定所述地图模型的目标寻路算法，包括：
20.若所述当前地图的地图类型为3d地图，确定所述寻路策略为导航网格寻路，并构建所述当前地图的地图模型为导航网格地图。
21.可选地，若所述导航网格地图的目标寻路算法为a*算法，所述通过所述目标寻路算法在所述当前地图模型中确定目标路径，包括：
22.确定所述目标路径经过的节点后，将所述目标路径经过的所有边的端点分为左端点和右端点；
23.对所述目标路径经过的节点依次执行以下步骤：
24.将当前节点向所述目标路径经过的当前边的左端点和右端点分别发出射线形成夹角；
25.若当前节点与下一条边的左端点的连线位于夹角内，则将下一条边的左端点作为当前边的左端点；若当前节点与下一条边的左端点的连线位于夹角右边，则当前边的右端点为拐点；
26.若当前节点与下一条边的右端点的连线位于夹角内，则将下一条边的右端点作为当前边的右端点；若当前节点与下一条边的右端点的连线位于夹角左边，则当前边的左端点为拐点；
27.连接各拐点后对所述目标路径进行调整。
28.可选地，所述通过所述目标寻路算法在所述当前地图模型中确定目标路径，包括：
29.预先离线计算处理所述地图模型上指定点之间的路径，得到指定路径；
30.在所述指定路径上分别确定出距离所述目标路径的起点最近的第一路径点，以及距离所述目标路径的终点最近的第二路径点，将所述第一路径点与所述第二路径点之间的路径作为所述目标路径的中间路径；
31.通过所述目标寻路算法在所述当前地图模型中分别计算确定所述起点与所述第一路径点之间的第一路径，以及所述终点与所述第二路径点之间的第二路径，将所述第一路径、所述第二路径与所述中间路径拼接得到所述目标路径。
32.本技术实施例公开了一种高效寻路的处理装置，包括：
33.第一模块，用于根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略，构建所述寻路策略下所述当前地图的地图模型，以及从所述寻路策略中确定所述地
图模型的目标寻路算法，其中，所述寻路策略包括格子寻路、路点寻路、导航网格寻路中的一种或多种的组合；
34.第二模块，用于通过所述目标寻路算法在所述当前地图模型中确定目标路径。
35.本技术实施例公开一种终端设备，包括：存储器及处理器，所述存储器中存储有计算机程序，所述计算机程序被所述处理器执行时，使得所述处理器实现本技术实施例公开的任一方法。
36.本技术实施例公开一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现本技术实施例公开的任一方法。
37.本技术实施例还公开了一种计算机程序产品，当计算机程序产品在终端设备上运行时，使得终端设备执行时实现本技术实施例公开的任一方法。
38.与现有技术相比，本技术实施例具有以下有益效果：
39.通过根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略后，构建该寻路策略下当前地图的地图模型，然后从寻路策略中确定地图模型的目标寻路算法，以使目标寻路算法可以有效适应于当前地图模型，从而可以在通过目标寻路算法在当前地图模型中确定目标路径时，有效提高寻路效率。
附图说明
40.为了更清楚地说明本技术实施例中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本技术的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
41.图1是本技术一实施例提供的高效寻路的处理方法的实现流程图；
42.图2是本技术一实施例提供的格子表示法的建模示意图；
43.图3是本技术一实施例提供的路点表示法的建模示意图；
44.图4是本技术一实施例提供的导航网格法的建模示意图；
45.图5是本技术一实施例提供的强迫邻居示意图；
46.图6是本技术一实施例提供的体素化的示意图；
47.图7是本技术一实施例提供的高效寻路的处理装置的模块示意图；
48.图8是本技术一实施例提供的终端设备的结构示意图。
具体实施方式
49.以下描述中，为了说明而不是为了限定，提出了诸如特定系统结构、技术之类的具体细节，以便透彻理解本技术实施例。然而，本领域的技术人员应当清楚，在没有这些具体细节的其它实施例中也可以实现本技术。在其它情况中，省略对众所周知的系统、装置、电路以及方法的详细说明，以免不必要的细节妨碍本技术的描述。
50.应当理解，当在本技术说明书和所附权利要求书中使用时，术语“包括”指示所描述特征、整体、步骤、操作、元素和/或组件的存在，但并不排除一个或多个其它特征、整体、步骤、操作、元素、组件和/或其集合的存在或添加。
51.还应当理解，在本技术说明书和所附权利要求书中使用的术语“和/或”是指相关
联列出的项中的一个或多个的任何组合以及所有可能组合，并且包括这些组合。
52.如在本技术说明书和所附权利要求书中所使用的那样，术语“如果”可以依据上下文被解释为“当...时”或“一旦”或“响应于确定”或“响应于检测到”。类似地，短语“如果确定”或“如果检测到[所描述条件或事件]”可以依据上下文被解释为意指“一旦确定”或“响应于确定”或“一旦检测到[所描述条件或事件]”或“响应于检测到[所描述条件或事件]”。
[0053]
另外，在本技术说明书和所附权利要求书的描述中，术语“第一”、“第二”、“第三”等仅用于区分描述，而不能理解为指示或暗示相对重要性。
[0054]
在本技术说明书中描述的参考“一个实施例”或“一些实施例”等意味着在本技术的一个或多个实施例中包括结合该实施例描述的特定特征、结构或特点。由此，在本说明书中的不同之处出现的语句“在一个实施例中”、“在一些实施例中”、“在其他一些实施例中”、“在另外一些实施例中”等不是必然都参考相同的实施例，而是意味着“一个或多个但不是所有的实施例”，除非是以其他方式另外特别强调。术语“包括”、“包含”、“具有”及它们的变形都意味着“包括但不限于”，除非是以其他方式另外特别强调。
[0055]
在本技术实施例中，流程的执行主体包括终端设备。该终端设备包括但不限于：服务器、计算机、智能手机以及平板电脑等能够执行本技术公开的高效寻路的处理方法的设备。图1示出了本技术第一实施例公开的高效寻路的处理方法的实现流程图，详述如下：
[0056]
步骤s110、根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略，构建寻路策略下所述当前地图的地图模型，以及从寻路策略中确定地图模型的目标寻路算法，其中，寻路策略包括格子寻路、路点寻路、导航网格寻路中的一种或多种的组合；
[0057]
步骤s120、通过目标寻路算法在当前地图模型中确定目标路径。
[0058]
在本技术实施例中，构建地图模型的方式包括但不限于格子表示法、路点表示法和导航网格法。可以理解的是，如图2所示，格子表示法(grid)是将场景均匀划分成一个个小的正方形的集合，将场景抽象成一个二维数组，每一个小的正方形为数组的一个元素。格子表示法适合用于简单的2d场景，这种方法非常的简单清晰，也非常容易和a*等算法结合起来使用。本实施例只需要划分好格子的粒度，然后使用地图编辑器标记每个格子的是否可通过等状态就可以实现寻路和避障，如果有动态障碍加入，只需要修改二维数组中元素的阻挡位然后重新寻路即可。但是使用这种方式划分出来的网格，游戏物体在其中移动是不连续的，这会导致有些时候移动的不是很自然。对特别大的地图如果不做分块等优化，相应的内存占用和寻路时间都会增加。
[0059]
如图3所示，路点表示法是将场景中设置的路点集合抽象为一张图，每个路点即为图中的一个节点。寻路只能发生在路点和路点之间，在计算机中表示为一张连通图。其优点是速度非常快；实现简单且内存和计算开销低，路点只用到了真实可行走区域的一部分，与格子相比，牺牲了路线的灵活性，换取较低的内存和计算开销。缺点是一些复杂的游戏地图需要的路点数量庞大，维护比较麻烦；有时候会是寻路单位走z型路径，看起来不自然；不能根据单位特效(不同宽度、高度)改变路径；不能保存地形附加信息，如地表高度、地面特征；不能方便的处理动态障碍。
[0060]
如图4所示，导航网格法是使用一系列算法将地图转换成三角形网格的集合，网格和网格之间构成连通关系用于寻路。在计算机中表示为顶点的集合，以及三个顶点索引一组(边)的集合。其优点是能精确的表征地图世界，比格子和路点都更精确。缺点是建立网格
的过程耗时且耗内存，与格子和路点不同，前两者的建模过程几乎是瞬时完成，但是建立导航网格则非常的复杂且耗时，这导致在初始化和加入动态障碍后重建导航网格信息时候会比较耗时。
[0061]
基于上述地图模型的构建方法，本技术实施例可以根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略，构建寻路策略下所述当前地图的地图模型，以及从寻路策略中确定所述地图模型的目标寻路算法。可以理解的是，当前地图的地图类型为2d地图且当前地图上障碍物分布存在动态变化，确定寻路策略为格子寻路，并构建当前地图的地图模型为格子地图，确定格子地图的目标寻路算法为a*算法或者jps跳点寻路算法。具体地，在算法选择上，a*算法依赖于计算格子的权重来寻路，计算公式(1)(f(p)＝g(p)+h(p))，而jps跳点寻路算法是基于跳点的确定来寻路，虽然也需要格子的权重，但相对较少，因此如果网格模型中本身多数格子已有权重，可选a*算法，反之如果只有少部分甚至格子均没有权重，可以选择改进后的jps跳点寻路算法来提高效率。若当前地图的地图类型为2d地图、当前地图的地形唯一以及当前地图上不存在障碍物，即在寻路路线比较固定、没有障碍，且也不考虑真实地形影响情况下，构建当前地图的地图模型为路点地图，确定路点地图的目标寻路算法为路点寻路算法。对于基于格子长距离寻路，中间又有很多障碍物时，a*算法会遇到瓶颈，此时，本实施例可以把中间很长一段距离的计算过程离线预处理好，当地图加载时将将离线的路径放到内存中，当角色需要寻路到过个节点时，从已经预处理好的点对点数据中寻找离起始点和终点最近的两个点，然后取出这两个点之间预处理好的路径，然后在拼接上起始点和终点到这两个点之间的实时路径，就形成了完整的路径，这样节省了中间很长一段路径的计算量。若当前地图的地图类型为3d地图，即在大型的3d场景中，地图很大且对模拟真实世界要求非常高时，确定寻路策略为导航网格寻路，并构建当前地图的地图模型为导航网格地图。
[0062]
在一些实施例中，在游戏人工智能领域中，a*寻路算法是最常用的寻路算法，a*寻路算法是把常规算法(如dijkstra)和启发式方法(如最佳优先搜索算法)结合在一起的算法，是一种更为折中的算法。除了对单一游戏对象的寻路行为进行控制，还衍生出群体寻路、掩护、动态路径计算等很多扩展领域。a*寻路算法是一种启发式的搜索算法，对查找节点形成搜索状态空间，用启发函数来评估当前节点与目标节点的路径情况，由于路径是不可预知的，所以估价函数是一个近似正确的评估函。其中，评估函数的表达式如公式(1)所示：
[0063]
f(p) ＝ g(p) + h(p)
ꢀꢀꢀꢀ
公式(1)
[0064]
其中，f(p)是节点p从开始点到结束点的估价函数，g(p)是在搜索空间中从开始点到当前节点p的实际代价，h(p)是从当前点p到结束点最佳路径的估计代价。
[0065]
在本实施例中，a*寻路算法的执行过程如下：
[0066]
a)将开始节点记录为当前点p；
[0067]
b)将当前点p放入关闭列表；
[0068]
c)寻找当前点p的所有邻近点，若某个邻近点没有在开放列表或者关闭列表中，计算出该邻近点的估价函数值(f值)，并设父节点为当前点p，然后将该邻近点加入到开放列表；
[0069]
d)判断开放列表是否存在节点，如果不存在，则说明在到结束点之前已经找完了
所有可能的路径点，寻路失败，算法结束；否则继续步骤e)；
[0070]
e)从开放列表拿出一个f值最小的节点，作为寻路路径的下一步；
[0071]
f)判断f值最小的节点是否为结束点，如果是，则寻路成功，算法结束，否则继续执行步骤g)；
[0072]
g)将步骤f)中f值最小的节点设置为当前节点p，跳回到步骤c。
[0073]
在本技术实施例中，a*算法相比传统的启发式寻路技术比如dijkstra、floyd算法，无论是时间复杂度还是空间复杂度都要更优秀，因此大部分寻路算法都是基于a*来改进的。本实施例对上述a*寻路算法进行了改进。
[0074]
第一点、对内存空间进行改进。具体地，当需要进行内存分配时，从节点池中获取空闲节点参与内存分配。可以理解的是，在a*寻路算法中，主要的工作就是扩展节点，所以操作的节点数量庞大，如果所有节点都进行内存分配来记录节点信息，但是真正用到的却只有最终生成路径的那些节点，这会造成非常大的浪费，因此，为了节省内存空间，本实施例通过预先建立一个节点池，当a*算法执行过程中触发节点空间分配，从节点池中取出处于空闲状态的节点进行计算，并在计算完成后将该节点重新放入节点池，循环利用。由于每次操作的节点数量很小，这样既可以提高搜索效率，又可以节省内存空间。
[0075]
第二点、对数据结构进行改进。具体地，通过完全二叉树优化开放列表；其中，完全二叉树用于保证每次插入或删除节点后，开放列表中最小的估价函数值对应的节点位于二叉树的根节点。可以理解的是，在a*寻路算法中，开放列表起到了关键作用，寻路过程需要频繁的对开放列表中的节点的f值进行排序。由于节点每次加入开放列表后，开放列表就不再是有序的队列了，所以每次去拿最小f值节点的时候都需要重新排序。排序的时间消耗随着队列的长度的增加而增大。但是寻路过程只是要找到f值最小的节点，并不关心其他节点的顺序。所以本实施例使用最小堆这种完全二叉树来优化开放列表，保证每次插入和删除操作后f值最小的节点都在在二叉树的根节点。
[0076]
第三点、对平滑路径进行改进。可以理解的是，通常情况下寻路算法都用网格来建模搜索空间，在网格上使用a*寻路算法寻路出来的路径，经常会呈现出锯齿状，有些转角也显得僵硬而不够自然。本实施例通过使用关键点优化算法来对其就行优化，这是一种比较简单且容易实现的算法。通过删除目标路径上转角位置的多余节点，即删除一些不必要的节点来使得目标路径变得更加的平滑。
[0077]
第四点、在a*寻路这种频繁调用的算法中，一个小小的性能消耗就能放大很多倍，因此算法中做到能不调用函数的不要调用函数，能简化公式的简化公式，能用位运算代替的加减乘除尽量用位运算代替。另外，本实施例采用通过兰森汉姆算法预先判断格子地图上的指定点之间是否能够直接通行，若是，则直接返回两点的直线路径，反之，则执行a*算法寻路，从而提高寻路效率。
[0078]
在本技术实施例中，大部分加速a*寻路的技术都关注于对扩展节点的裁剪。针对无权重的网格模型，使用jps跳点寻路能大大减少需要扩展的节点。jps跳点寻路算法是通过选择网格中特定的节点来进行寻路，这些节点称为跳点。该jps跳点寻路算法的重点就是如何确定跳点。其中，跳点的确定需要引入强迫邻居的概念。具体地，如图5所示，节点x的8个邻居中有障碍(如图5的黑色填充方块)，且x的父节点p经过x到达n的距离代价比不经过x到达的n的任意路径的距离代价小，则称n是x的强迫邻居(如图5中圆圈区域)。
[0079]
在本实施例中，跳点的选择需要满足以下三个条件中的其中一个：
[0080]
条件1、节点x是起点或终点；
[0081]
条件2、节点x至少有一个强迫邻居；
[0082]
条件3、如果父节点在斜线方向，节点x的水平或垂直方向上有满足条件1，条件2条件的节点。
[0083]
在本技术实施例中，在完成跳点的选择后，jps跳点寻路算法的寻路过程如下：
[0084]
a)、开放列表取一个权重最低的节点，开始搜索。
[0085]
b)、搜索过程中，先进行直线搜索，然后再斜向搜索，如果期间某个方向搜索到跳点或者碰到障碍点和边界，则当前方向搜索完成，如果有搜索到跳点，就添加到开放列表中。
[0086]
c)、如若斜方向没有完成搜索，则斜方向前进一步，重复上述过程。
[0087]
d)、如若所有方向已经完成搜索，则认为当前节点搜索完毕，将当前节点移除开放列表，加入到关闭列表中。
[0088]
e)、重复选取开放列表中权重最低的节点搜索，直到开放列表为空或者找到了结束点。
[0089]
具体地，jps跳点寻路算法在绝大多数地图上都会比a*寻路算法的寻路速度快，且内存占用也更小。本实施例对上述jps跳点寻路算法的寻路过程进行了改进，得到jps+跳点寻路算法。可以理解的是，jps+跳点寻路算法的本质也是jps跳点寻路算法，只是加上了预处理来进行改进，从而使寻路更加快速。
[0090]
可以理解的是，jps+跳点寻路算法的预处理过程如下：
[0091]
a)首先对地图每个节点进行跳点判断，找出所有主要跳点。
[0092]
b)然后对每个节点进行跳点的直线可达性判断，记录好跳点的直线可达性。
[0093]
c)如果直线可到达，则记录下跳点的直线距离作为正数距离。
[0094]
d)类似的，对每个节点进行跳点斜方向距离的记录。
[0095]
e)剩余各个方向如果不可到达跳点的数据记录为0或者负数距离；如若在对应的方向上移动一步后就碰到了边界或者障碍，那么将其记录为0；如若移动x+1步后会碰到边界或者障碍，那么将其数据记录为-x。
[0096]
f)每个节点的邻近8个方向的节点都记录完毕。
[0097]
在完成预处理过程后，执行jps+跳点寻路算法的寻路过程。例如，以某个搜索方向为例：
[0098]
a)对正数距离的x，直接将x步远的节点作为跳点加进开放列表。
[0099]
b)对距离为0的也就是当前无法移动的节点，则无需在该方向上继续搜索。
[0100]
c)对于负数距离-x也就是距离障碍或者边界x格的节点，直接将n步远的节点进行一次跳点判断。
[0101]
在本技术实施例中，导航网格也称为行走面，是一种用于复杂空间中导航寻路、标记哪些地方可以行走的多边形网格数据结构。很多时候，它被用于承载更多的功能，比如标记该位置的地形、该位置角色应该采取什么样的动作，如行走、游泳、攀爬等。要实现导航网格寻路，首先是生成导航网格，导航网格的生成依赖于场景模型的设计，有手动生成，有自动生成，有两种方式相结合的方式。如果场景简单，那么可以由场景设计师在构造场景模型
时，手动拉一个场景的导航网格。但对于大规模复杂的场景，一般会让设计师剔除大量不可能到达的建筑、装饰物，做出一个简化的逻辑面模型，再根据这个模型去自动化生成导航网格。
[0102]
在导航网络寻路过程中，首先建立三角导航网格，然后通过改进后的a*寻路算法在所述三角导航网格上进行路径搜索，再对路径搜索过程得到的拐点进行优化。
[0103]
可以理解的是，建立三角导航网格的过程如下：
[0104]
步骤1、对三维图像网格进行体素化，得到三维空间区域。具体地，如图6所示，使用固定的宽度和深度(xzcellsize)将盒子沿着垂直方向切割成列。每列就是一个格子。接下来，使用固定的高度增量(ycellsize)切割每一列，将每一列都分割成小的轴对齐包围盒。每个盒子就是一个体素。位于盒子角落的8个顶点就是顶点集。
[0105]
对三维图像网格进行体素化，形成的实心高度域将完全包裹3d网格，而本实施例需要的区域是高度域的上方区间，作为可行走的表面，最终，三维空间的网格被体素化为三维空间区域。
[0106]
在这一步过程中，本实施例给高度域增加可行走标记：
[0107]
a)、添加可行走区间标记。将与多边形有交集的体素单位当作区间，判断体素和网格多边形相交的截面倾斜度是否可行走
[0108]
b)、合并剔除。相交的截面取最高和最低点，得到占据比例和在y轴的投影，那么可以将y轴投影有重叠的区间进行合并，判断新的可行走标记，抛弃旧的
[0109]
c)、容纳高度剔除。若区间a上空仍有一个区间b阻挡，且两者之间的空余不足以让设定大小的物体经过时，则将区间b的可行走标记去除
[0110]
d)、凸起剔除。若区间顶端距离相邻区间的顶端下降的距离超过阈值，则该区间认为是凸起，是不可行走区域
[0111]
步骤2、生成地区。本实施例通过体素化，可以对开放区间(可行走空间)以体素为基本单位进行分析。将每个体素大小的区域作为一个区间，首先计算每个区间同邻近的4个区间的连通性；对于一些特殊结构，将高度差不超过设置的最大垂直步长的相邻区间也当作可连通的合法区间，以兼容一些特殊结构，如楼梯等)其次，创建距离场，计算每个区间到边缘或障碍物的最短距离，将此距离与给定阈值比较之后，剔除太靠近边缘的不可行走区域。最后，将剩余的合法的可连通区域合并成一个大的面片，每个面片为一个地区。
[0112]
步骤3、生成轮廓。本实施例通过沿着构建出来的地图面片的边缘，构建简单多边形，储存边的矢量。具体执行过程如下：
[0113]
a)、遍历所有的区间，邻近区间中有其他地区的区间的话，该区间为边缘区间，选出边缘区间后，按照一个方向(如顺时针)选出地区的轮廓
[0114]
b)、当3d场景下，相邻的边缘区间的高度不一样时，取最高的点作为轮廓的连接点，保证最终的网格在模型网格表面之上，最终将体素空间转换为了矢量空间
[0115]
c)、轮廓优化。具体是以体素为基本单位得到的多边形轮廓太精细，实际上不需要这么多顶点，只需要保留必须点即可，例如多个地区边界的交接点。只保留必须点可能会过于简化轮廓，本实施例用douglas-peucker算法对原轮廓线条进行再拟合，给定maxedgedistance，希望旧曲线上的所有点距离新的轮廓线的距离都应该小于max的值。那么取新轮廓线段对应的旧轮廓线段里面的最远的点p，若它与新线段的距离大于max的值，
那么将它作为新的顶点插入到新轮廓线里面形成新的折线，更新了轮廓线之后再重复上面流程，直到所有距离都在maxedgedistance以内，那么就可以得到更接近原轮廓的拟合了。在拟合过程中，可能会导致生成凸多边形的时候长生较多狭长的三角形，所以，在这步确定顶点的时候，将对与长度大于maxedgelen的边进行折断，即在中点插入新的顶点。
[0116]
步骤四、生成凸多边形。本步骤的具体过程如下：
[0117]
a)多边形三角化：
[0118]
①
遍历所有边，根据每组三个顶点，检测能否连接成一个有效的在区块内部的三角形；
[0119]
②
在所有的有效分割，选出生成新边最短的，生成新的边和三角形，重复过程。
[0120]
b)将三角形合并成尽可能大的凸多边形：
[0121]
①
遍历所有的边，找出所有能两两合并的多边形，选出有最长公共边的两个合并，重复过程；
[0122]
②
合并的时候需要注意，合并之后是否仍然是凸多边形，可以根据如下规则判断，因为凸多边形的任意顶点之间的连线都在凸多边形的内部，那么若合并的公共边的顶点，满足该顶点在合并后多边形中的相邻两个顶点所连城的线，在合并后的多边形内部，则为有效合并。
[0123]
c)合并完成后，我们对新划分的区域生成连通信息即可生成一个导航网格。
[0124]
在完成上述处理后，通过上述改进后的a*寻路算法进行寻路。具体地，在寻路过程中，寻路算法得到途径的多边形节点之后，最终得到的行走路线仍需要优化，否则可能会出现s型的行走路线，而要得到平滑且尽可能短的行走路线，需要让路线靠近拐点。因此，本实施例对路径搜索过程得到的拐点进行优化。其中，优化过程如下：
[0125]
确定目标路径经过的节点，将目标路径经过的所有边的端点分为左端点left和右端点right；
[0126]
在每个循环过程中，将当前节点向当前边的左端点和右端点分别发出射线，两条所述射线形成夹角t；
[0127]
若当前节点与下一条边的左端点的连线位于夹角t内，则将下一条边的左端点作为当前边的左端点；若当前节点与下一条边的左端点的连线位于夹角t右边，则当前边的右端点为拐点；
[0128]
若当前节点与下一条边的右端点的连线位于夹角t内，则将下一条边的右端点作为当前边的右端点；若当前节点与下一条边的右端点的连线位于夹角t左边，则当前边的左端点为拐点。
[0129]
通过上述迭代处理后，可以查找出所有拐点，连接各拐点后对目标路径进行调整，以得到一条更短的行走路径。具体地，调整是指将各拐点连接得到的路径替换目标路径。
[0130]
在一些实施例中，在通过目标寻路算法在当前地图模型中确定目标路径时，本实施例还可以通过预处理好的点对点数据来确定目标路径作为实时路径。具体地，本步骤的处理过程包括但不限于：
[0131]
预先离线计算处理地图模型上指定点之间的路径，得到指定路径；
[0132]
在指定路径上分别确定出距离目标路径的起点最近的第一路径点，以及距离目标路径的终点最近的第二路径点，将第一路径点与第二路径点之间的路径作为目标路径的中
间路径；
[0133]
通过目标寻路算法在当前地图模型中分别计算确定起点与第一路径点之间的第一路径，以及终点与第二路径点之间的第二路径，将第一路径、第二路径与中间路径拼接得到目标路径。
[0134]
可以理解的是，本实施例提出的上述寻路方法，可以应用于游戏智能寻路、路网寻路、避险救灾等领域。而随着互联网技术的进一步发展以及人工智能技术的日益发达，智能汽车行业的兴起。寻路技术被更多的应用到了日常生活中。比如智能家居中的扫地机器人，智能扫地机器人可以在主人不在家的情况下自动检测到地面上的灰尘，并自动清理。通过高效的寻路技术，可以为智能扫地机器人提供更合理的路线规划，保证找到可以清理灰尘的最短路径，从而快速的清理房间，同时达到省电目的。当然，绕过障碍物也是必须要拥有的技能。这些正好是高效寻路所擅长的。另外伴随这智能汽车行业的兴起，自动驾驶也成为了研究的热门，而自动驾驶中路径规划也是相当重要的一环，是实现无人化驾驶的关键技术之一。路径规划模块性能的高低直接关系着智能汽车行驶路径选择的优劣和行驶流畅度。
[0135]
参照图7，本技术实施例公开一种高效寻路的处理装置，包括：
[0136]
第一模块，用于根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略，构建所述寻路策略下所述当前地图的地图模型，以及从所述寻路策略中确定所述地图模型的目标寻路算法，其中，所述寻路策略包括格子寻路、路点寻路、导航网格寻路中的一种或多种的组合；
[0137]
第二模块，用于通过所述目标寻路算法在所述当前地图模型中确定目标路径。
[0138]
对应于上文实施例所述的方法，图7示出了本技术一实施例公开的装置的结构示意图，为了便于说明，仅示出了与本技术实施例相关的部分。
[0139]
需要说明的是，上述装置之间的信息交互、执行过程等内容，由于与本技术方法实施例基于同一构思，其具体功能及带来的技术效果，具体可参见方法实施例部分，此处不再赘述。
[0140]
所属领域的技术人员可以清楚地了解到，为了描述的方便和简洁，仅以上述各功能单元、模块的划分进行举例说明，实际应用中，可以根据需要而将上述功能分配由不同的功能单元、模块完成，即将所述装置的内部结构划分成不同的功能单元或模块，以完成以上描述的全部或者部分功能。实施例中的各功能单元、模块可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中，上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。另外，各功能单元、模块的具体名称也只是为了便于相互区分，并不用于限制本技术的保护范围。上述系统中单元、模块的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。
[0141]
图8示出了本技术一实施例公开的终端设备的结构示意图。如图8所示，该实施例的终端设备8包括：至少一个处理器80(图8中仅示出一个处理器)、存储器81以及存储在所述存储器81中并可在所述至少一个处理器80上运行的计算机程序82，所述处理器80执行所述计算机程序82时实现上述任意各个方法实施例中的步骤。
[0142]
所述终端设备8可以是桌上型计算机、笔记本、掌上电脑及云端服务器等计算设备。该终端设备可包括，但不仅限于，处理器80、存储器81。本领域技术人员可以理解，图8仅
仅是终端设备8的举例，并不构成对终端设备8的限定，可以包括比图示更多或更少的部件，或者组合某些部件，或者不同的部件，例如还可以包括输入输出设备、网络接入设备等。
[0143]
所称处理器80可以是中央处理单元(central processing unit，cpu)，该处理器80还可以是其他通用处理器、数字信号处理器(digital signal processor，dsp)、专用集成电路(application specific integrated circuit，asic)、现成可编程门阵列(field-programmable gate array，fpga)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等。通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等。
[0144]
所述存储器81在一些实施例中可以是所述终端设备8的内部存储单元，例如终端设备8的硬盘或内存。所述存储器81在另一些实施例中也可以是所述终端设备8的外部存储设备，例如所述终端设备8上配备的插接式硬盘，智能存储卡(smart media card,smc)，安全数字(secure digital,sd)卡，闪存卡(flash card)等。进一步地，所述存储器81还可以既包括所述终端设备8的内部存储单元也包括外部存储设备。所述存储器81用于存储操作系统、应用程序、引导装载程序(bootloader)、数据以及其他程序等，例如所述计算机程序的程序代码等。所述存储器81还可以用于暂时地存储已经输出或者将要输出的数据。
[0145]
本技术实施例还公开了一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时实现可实现上述各个方法实施例中的步骤。
[0146]
本技术实施例公开了一种计算机程序产品，当计算机程序产品在移动终端上运行时，使得移动终端执行时实现可实现上述各个方法实施例中的步骤。
[0147]
所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本技术实现上述实施例方法中的全部或部分流程，可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一计算机可读存储介质中，该计算机程序在被处理器执行时，可实现上述各个方法实施例的步骤。其中，所述计算机程序包括计算机程序代码，所述计算机程序代码可以为源代码形式、对象代码形式、可执行文件或某些中间形式等。所述计算机可读介质至少可以包括：能够将计算机程序代码携带到拍照装置/终端设备的任何实体或装置、记录介质、计算机存储器、只读存储器(rom，read-only memory)、随机存取存储器(ram，random access memory)、电载波信号、电信信号以及软件分发介质。例如u盘、移动硬盘、磁碟或者光盘等。在某些司法管辖区，根据立法和专利实践，计算机可读介质不可以是电载波信号和电信信号。
[0148]
在上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述或记载的部分，可以参见其它实施例的相关描述。
[0149]
本领域普通技术人员可以意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、或者计算机软件和电子硬件的结合来实现。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本技术的范围。
[0150]
在本技术所公开的实施例中，应该理解到，所揭露的装置/终端设备和方法，可以
通过其它的方式实现。例如，以上所描述的装置/终端设备实施例仅仅是示意性的，例如，所述模块或单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通讯连接可以是通过一些接口，装置或单元的间接耦合或通讯连接，可以是电性，机械或其它的形式。
[0151]
所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。
[0152]
以上所述实施例仅用以说明本技术的技术方案，而非对其限制；尽管参照前述实施例对本技术进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本技术各实施例技术方案的精神和范围，均应包含在本技术的保护范围之内。

技术特征：
1.一种高效寻路的处理方法，其特征在于，包括以下步骤：根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略，构建所述寻路策略下所述当前地图的地图模型，以及从所述寻路策略中确定所述地图模型的目标寻路算法，其中，所述寻路策略包括格子寻路、路点寻路或导航网格寻路；通过所述目标寻路算法在所述当前地图模型中确定目标路径。2.根据权利要求1所述的一种高效寻路的处理方法，其特征在于，所述根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略，构建所述寻路策略下所述当前地图的地图模型，以及从所述寻路策略中确定所述地图模型的目标寻路算法，包括：若所述当前地图的地图类型为2d地图且所述当前地图上障碍物分布存在动态变化，确定所述寻路策略为格子寻路，并构建所述当前地图的地图模型为格子地图，确定所述格子地图的目标寻路算法为a*算法或者jps跳点寻路算法。3.根据权利要求2所述的一种高效寻路的处理方法，其特征在于，若所述目标寻路算法为a*算法，所述通过所述目标寻路算法在所述当前地图模型中确定目标路径，包括：通过兰森汉姆算法预先判断格子地图上的指定点之间是否能够直接通行，若是，则直接返回两点的直线路径，反之，则执行a*算法寻路；和/或预先建立节点池，若所述a*算法执行过程中触发节点空间分配，从节点池中取出处于空闲状态的节点进行计算，并在计算完成后重新放入所述节点池；和/或通过完全二叉树优化开放列表，以在每次插入或删除节点后，所述开放列表中最小的估价函数值对应的节点位于二叉树的根节点；和/或基于关键点优化算法删除目标路径上转角位置的多余节点，以平滑所述目标路径。4.根据权利要求1所述的一种高效寻路的处理方法，其特征在于，所述根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略，构建所述寻路策略下所述当前地图的地图模型，以及从所述寻路策略中确定所述地图模型的目标寻路算法，包括：若所述当前地图的地图类型为2d地图、所述当前地图的地形唯一以及所述当前地图上不存在障碍物，确定所述寻路策略为路点寻路，并构建所述当前地图的地图模型为路点地图，确定所述路点地图的目标寻路算法为路点寻路算法。5.根据权利要求1所述的一种高效寻路的处理方法，其特征在于，所述根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略，构建所述寻路策略下所述当前地图的地图模型，以及从所述寻路策略中确定所述地图模型的目标寻路算法，包括：若所述当前地图的地图类型为3d地图，确定所述寻路策略为导航网格寻路，并构建所述当前地图的地图模型为导航网格地图。6.根据权利要求5所述的一种高效寻路的处理方法，其特征在于，若所述导航网格地图的目标寻路算法为a*算法，所述通过所述目标寻路算法在所述当前地图模型中确定目标路径，包括：确定所述目标路径经过的节点后，将所述目标路径经过的所有边的端点分为左端点和右端点；
对所述目标路径经过的节点依次执行以下步骤：将当前节点向所述目标路径经过的当前边的左端点和右端点分别发出射线形成夹角；若当前节点与下一条边的左端点的连线位于夹角内，则将下一条边的左端点作为当前边的左端点；若当前节点与下一条边的左端点的连线位于夹角右边，则当前边的右端点为拐点；若当前节点与下一条边的右端点的连线位于夹角内，则将下一条边的右端点作为当前边的右端点；若当前节点与下一条边的右端点的连线位于夹角左边，则当前边的左端点为拐点；连接各拐点后对所述目标路径进行调整。7.根据权利要求1所述的一种高效寻路的处理方法，其特征在于，所述通过所述目标寻路算法在所述当前地图模型中确定目标路径，包括：预先离线计算处理所述地图模型上指定点之间的路径，得到指定路径；在所述指定路径上分别确定出距离所述目标路径的起点最近的第一路径点，以及距离所述目标路径的终点最近的第二路径点，将所述第一路径点与所述第二路径点之间的路径作为所述目标路径的中间路径；通过所述目标寻路算法在所述当前地图模型中分别计算确定所述起点与所述第一路径点之间的第一路径，以及所述终点与所述第二路径点之间的第二路径，将所述第一路径、所述第二路径与所述中间路径拼接得到所述目标路径。8.一种高效寻路的处理装置，其特征在于，包括：第一模块，用于根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略，构建所述寻路策略下所述当前地图的地图模型，以及从所述寻路策略中确定所述地图模型的目标寻路算法，其中，所述寻路策略包括格子寻路、路点寻路、导航网格寻路中的一种或多种的组合；第二模块，用于通过所述目标寻路算法在所述当前地图模型中确定目标路径。9.一种终端设备，其特征在于，包括：存储器及处理器，所述存储器中存储有计算机程序，所述计算机程序被所述处理器执行时，使得所述处理器实现如权利要求1至7任一所述的方法。10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现如权利要求1至7任一所述的方法。

技术总结
本申请适用于人工智能技术领域，公开了一种高效寻路的处理方法、装置、设备及介质，所述方法包括：根据当前地图的地图类型、地形信息和障碍物分布信息确定寻路策略，构建寻路策略下当前地图的地图模型，以及从寻路策略中确定地图模型的目标寻路算法，通过目标寻路算法在所述当前地图模型中确定目标路径，其中，寻路策略包括格子寻路、路点寻路、导航网格寻路中的一种或多种的组合。本申请能够使目标寻路算法可以有效适应于当前地图模型，从而可以在通过目标寻路算法在当前地图模型中确定目标路径时，有效提高寻路效率。有效提高寻路效率。有效提高寻路效率。


技术研发人员：陈潜
受保护的技术使用者：广州三七极梦网络技术有限公司
技术研发日：2023.06.09
技术公布日：2023/9/20