技术特征：
1.一种路径规划方法，其特征在于，所述方法包括：响应于任一虚拟对象的路径规划请求，基于所述任一虚拟对象在三维场景地图的当前位置和预存储的路径序列，确定所述任一虚拟对象在所述三维场景地图中对应的目标路线，并向所述任一虚拟对象返回所述目标路线；其中，所述路径序列包括用于构成骨架线的至少两个骨架线关键点、以及所述至少两个骨架线关键点之间的连通关系；所述骨架线用于指示所述三维场景地图中的可移动区域的空间结构；其中，所述路径序列的生成方式包括：基于从所述三维场景地图中至少两个起点发射线段的过程，获取所述三维场景地图中的发射点集合，所述发射点集合用于指示所述可移动区域的空间范围；基于所述发射点集合，构建无向图，并存储所述无向图中每个节点及与其连接的节点之间的相对位置，所述无向图用于指示所述可移动区域中各个发射点之间的连通关系，所述无向图中相连接的两个节点所对应的发射点之间具备连通关系；基于所述无向图中各个节点之间的相对位置，删除所述无向图中符合冗余条件的骨架线冗余点，将所述无向图中剩余节点确定为构成所述骨架线的骨架线关键点，得到所述路径序列，所述冗余条件用于衡量所述无向图中节点对构成所述骨架线是否冗余。2.根据权利要求1所述的路径规划方法，其特征在于，所述基于从所述三维场景地图中至少两个起点发射线段的过程，获取所述三维场景地图中的发射点集合，包括：通过迭代以下步骤扩展发射点集合，直至所述三维场景地图中没有新的发射点：遍历所述三维场景地图中的至少一个起点，并从每个起点发射至少两条线段；响应于任一线段在发射过程中未碰撞障碍物、且所述任一线段的终点的目标范围内存在到达点，获取所述到达点对应的候选发射点；响应于所述候选发射点与发射点集合中的每个发射点之间距离符合目标条件，将所述候选发射点作为发射点添加至所述发射点集合中。3.根据权利要求2所述的路径规划方法，其特征在于，所述遍历所述三维场景地图中的至少一个起点，包括以下任一项：基于模拟对象在所述三维场景地图的当前位置，获取所述模拟对象对应的至少一个起点，所述模拟对象用于模拟虚拟对象进入虚拟游戏场景中进行游戏；将上一次迭代过程得到的发射点作为当前迭代过程的至少一个起点。4.根据权利要求3所述的路径规划方法，其特征在于，所述从每个起点发射至少两条线段，包括：按照至少两个方向各自对应的线段长度，从每个起点向所述至少两个方向发射至少两条线段；相应的，所述基于所述发射点集合，构建无向图，并存储所述无向图中每个节点及与其连接的节点之间的相对位置，包括：根据所述各个发射点、以及每个发射点对应在每个方向的线段的终点，生成所述无向图；对于每个节点，存储所述节点及与其在至少一个方向相连接的节点之间的相对位置。5.根据权利要求1所述的路径规划方法，其特征在于，所述基于所述无向图中各个节点
之间的相对位置，删除所述无向图中符合冗余条件的骨架线冗余点，包括：对于每个节点，基于所述节点及与其相连接的节点之间的相对位置，以所述节点为发射中心确定所述节点的邻域点集合，所述邻域点集合包括所述节点在至少两个方向的线段的终点所对应的节点；基于所述邻域点集合所包括节点的数量、所述邻域点集合中各个节点之间的相对位置，删除所述无向图中符合冗余条件的骨架线冗余点。6.根据权利要求5所述的路径规划方法，其特征在于，对于每个节点p1，所述节点p1的邻域点集合包括节点p
i
，i∈[2,9]；当所述节点在对应方向存在线段的终点所对应的节点时，p
i
＝1；当所述节点在对应方向不存在线段的终点所对应的节点时，p
i
为空时，p
i
＝0；相应的，所述基于所述邻域点集合所包括节点的数量、所述邻域点集合中各个节点之间的相对位置，删除所述无向图中符合冗余条件的骨架线冗余点，包括：对应每个节点p1，响应于所述p1对应的pi满足以下三项条件，删除所述p1：第1项：2≤p2 p3 p4 p5 p6 p7 p8 p9≤6；第2项：s(p1)＝1，s(p1)表示以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序时，所述p
i
由p
i
＝0变为p
i
＝1的变化次数；第3项：p2×
p4×
p6＝0且p4×
p6×
p8＝0，pi以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序。7.根据权利要求5所述的路径规划方法，其特征在于，对于每个节点p1，所述节点p1的邻域点集合包括节点p
i
，i∈[2,9]；当所述节点在对应方向存在线段的终点所对应的节点时，p
i
＝1；当所述节点在对应方向不存在线段的终点所对应的节点时，p
i
为空时，p
i
＝0；相应的，所述基于所述邻域点集合所包括节点的数量、所述邻域点集合中各个节点之间的相对位置，删除所述无向图中符合冗余条件的骨架线冗余点，包括：对应每个节点p1，响应于所述p1对应的p
i
满足以下三项条件，删除所述p1：第1项：2≤p2 p3 p4 p5 p6 p7 p8 p9≤6；第2项：s(p1)＝1，s(p1)表示以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序时，所述p
i
由p
i
＝0变为p
i
＝1的变化次数；第3项：p2×
p4×
p8＝0且p2×
p6×
p8＝0，pi以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序。8.根据权利要求1所述的路径规划方法，其特征在于，所述基于所述任一虚拟对象在三维场景地图的当前位置和预存储的路径序列，确定所述任一虚拟对象在所述三维场景地图中对应的目标路线，包括：确定所述当前位置在所述路径序列中对应的骨架线关键点；在首次遍历时，以所述当前位置对应的骨架线关键点为起点，执行以广度优先遍历的方式、遍历所述路径序列中与所述起点连通的下一骨架线关键点的遍历步骤，并记录从所述起点到所述下一骨架线关键点的当前路线；在首次遍历之后的每次遍历时，继续以所述当前路线的末尾点为起点，再次执行所述遍历步骤，并更新所记录的当前路线，直至达到遍历结束条件时停止遍历，得到所述目标路线。9.一种路径规划装置，其特征在于，所述装置包括：路径规划模块，用于响应于任一虚拟对象的路径规划请求，基于所述任一虚拟对象在三维场景地图的当前位置和预存储的路径序列，确定所述任一虚拟对象在所述三维场景地
图中对应的目标路线，并向所述任一虚拟对象返回所述目标路线；其中，所述路径序列包括用于构成骨架线的至少两个骨架线关键点、以及所述至少两个骨架线关键点之间的连通关系；所述骨架线用于指示所述三维场景地图中的可移动区域的空间结构；其中，所述装置还用于生成路径序列，所述装置在生成路径序列时，包括：发射点集合获取模块，用于基于从所述三维场景地图中至少两个起点发射线段的过程，获取所述三维场景地图中的发射点集合，所述发射点集合用于指示所述可移动区域的空间范围；构建模块，用于基于所述发射点集合，构建无向图，并存储所述无向图中每个节点及与其连接的节点之间的相对位置，所述无向图用于指示所述可移动区域中各个发射点之间的连通关系，所述无向图中相连接的两个节点所对应的发射点之间具备连通关系；删除模块，用于基于所述无向图中各个节点之间的相对位置，删除所述无向图中符合冗余条件的骨架线冗余点，将所述无向图中剩余节点确定为构成所述骨架线的骨架线关键点，得到所述路径序列，所述冗余条件用于衡量所述无向图中节点对构成所述骨架线是否冗余。10.一种计算机设备，包括存储器、处理器及存储在存储器上的计算机程序，其特征在于，所述处理器执行所述计算机程序以实现权利要求1至8任一项所述的路径规划方法。11.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至8任一项所述的路径规划方法。12.一种计算机程序产品，包括计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至8任一项所述的路径规划方法。
技术总结
本申请提供一种路径规划方法、装置、计算机设备、存储介质及程序产品，涉及云技术、网络游戏、地图、自动驾驶等技术领。通过基于虚拟对象在三维场景地图的当前位置和预存储的路径序列，确定目标路线；从而实现自动规划路径的过程。通过基于从三维场景地图中至少两个起点发射线段的过程，获取发射点集合；基于该发射点集合构建无向图，并基于各个节点之间的相对位置，删除符合冗余条件的骨架线冗余点，将无向图中剩余节点确定构成骨架线的骨架线关键点，以得到路径序列；通过该冗余条件可删除构成该可移动区域的骨架线时的冗余点，可提高路径规划的速度，减少需探索的位置点数量，提高了路径规划的处理效率。了路径规划的处理效率。了路径规划的处理效率。
技术研发人员：黄超 周洪斌 严明 梅维一
受保护的技术使用者：腾讯科技（深圳）有限公司
技术研发日：2022.03.28
技术公布日：2023/10/10