1.本技术涉及云技术、网络游戏、地图、自动驾驶等技术领域，本技术涉及一种路径规划方法、装置、计算机设备、存储介质及程序产品。
背景技术：
2.许多网络游戏提供有三维场景地图，三维场景地图中包括了按照一定位置排布的虚拟建筑物、树木、交通道路等多种元素，虚拟对象可以在三维场景地图中进行移动。在一些网络游戏中，可以利用三维场景地图自动为虚拟对象规划路径。
3.相关技术中，路径规划的过程可以包括：一款游戏可以对应有多张三维场景地图，游戏开发人员通过人工方式、依次标记每张三维场景地图中的每个关键点；虚拟对象进入虚拟游戏场景后，可以基于三维场景地图中的关键点向虚拟对象提供路径；以便虚拟对象自动按照所提供的路径移动，从而实现对三维场景地图的探索。
4.然而，上述路径规划过程需要大量人工成本，一旦游戏地图发生变更，仍需人工对关键点进行维护，导致上述路径规划方法的效率较低。
技术实现要素：
5.本技术提供了一种路径规划方法、装置、计算机设备、存储介质及程序产品，可以提高路径规划过程的效率。所述技术方案如下：
6.一方面，提供了一种路径规划方法，所述方法包括：
7.响应于任一虚拟对象的路径规划请求，基于所述任一虚拟对象在三维场景地图的当前位置和预存储的路径序列，确定所述任一虚拟对象在所述三维场景地图中对应的目标路线，并向所述任一虚拟对象返回所述目标路线；
8.其中，所述路径序列包括用于构成骨架线的至少两个骨架线关键点、以及所述至少两个骨架线关键点之间的连通关系；所述骨架线用于指示所述三维场景地图中的可移动区域的空间结构；
9.其中，所述路径序列的生成方式包括：
10.基于从所述三维场景地图中至少两个起点发射线段的过程，获取所述三维场景地图中的发射点集合，所述发射点集合用于指示所述可移动区域的空间范围；
11.基于所述发射点集合，构建无向图，并存储所述无向图中每个节点及与其连接的节点之间的相对位置，所述无向图用于指示所述可移动区域中各个发射点之间的连通关系，所述无向图中相连接的两个节点所对应的发射点之间具备连通关系；
12.基于所述无向图中各个节点之间的相对位置，删除所述无向图中符合冗余条件的骨架线冗余点，将所述无向图中剩余节点确定为构成所述骨架线的骨架线关键点，得到所述路径序列，所述冗余条件用于衡量所述无向图中节点对构成所述骨架线是否冗余。
13.另一方面，提供了一种路径规划装置，所述装置包括：
14.路径规划模块，用于响应于任一虚拟对象的路径规划请求，基于所述任一虚拟对
象在三维场景地图的当前位置和预存储的路径序列，确定所述任一虚拟对象在所述三维场景地图中对应的目标路线，并向所述任一虚拟对象返回所述目标路线；
15.其中，所述路径序列包括用于构成骨架线的至少两个骨架线关键点、以及所述至少两个骨架线关键点之间的连通关系；所述骨架线用于指示所述三维场景地图中的可移动区域的空间结构；
16.其中，所述装置还用于生成路径序列，所述装置在生成路径序列时，包括：
17.发射点集合获取模块，用于基于从所述三维场景地图中至少两个起点发射线段的过程，获取所述三维场景地图中的发射点集合，所述发射点集合用于指示所述可移动区域的空间范围；
18.构建模块，用于基于所述发射点集合，构建无向图，并存储所述无向图中每个节点及与其连接的节点之间的相对位置，所述无向图用于指示所述可移动区域中各个发射点之间的连通关系，所述无向图中相连接的两个节点所对应的发射点之间具备连通关系；
19.删除模块，用于基于所述无向图中各个节点之间的相对位置，删除所述无向图中符合冗余条件的骨架线冗余点，将所述无向图中剩余节点确定为构成所述骨架线的骨架线关键点，得到所述路径序列，所述冗余条件用于衡量所述无向图中节点对构成所述骨架线是否冗余。
20.在一种可能实现方式中，所述发射点集合获取模块，还用于：
21.通过迭代以下步骤扩展发射点集合，直至所述三维场景地图中没有新的发射点：
22.遍历所述三维场景地图中的至少一个起点，并从每个起点发射至少两条线段；
23.响应于任一线段在发射过程中未碰撞障碍物、且所述任一线段的终点的目标范围内存在到达点，获取所述到达点对应的候选发射点；
24.响应于所述候选发射点与发射点集合中的每个发射点之间距离符合目标条件，将所述候选发射点作为发射点添加至所述发射点集合中。
25.在一种可能实现方式中，所述发射点集合获取模块，还用于以下任一项：
26.基于模拟对象在所述三维场景地图的当前位置，获取所述模拟对象对应的至少一个起点，所述模拟对象用于模拟虚拟对象进入虚拟游戏场景中进行游戏；
27.将上一次迭代过程得到的发射点作为当前迭代过程的至少一个起点。
28.在一种可能实现方式中，所述发射点集合获取模块，还用于按照至少两个方向各自对应的线段长度，从每个起点向所述至少两个方向发射至少两条线段；
29.相应的，所述构建模块，用于根据所述各个发射点、以及每个发射点对应在每个方向的线段的终点，生成所述无向图；对于每个节点，存储所述节点及与其在至少一个方向相连接的节点之间的相对位置。
30.在一种可能实现方式中，所述删除模块，还用于：
31.对于每个节点，基于所述节点及与其相连接的节点之间的相对位置，以所述节点为发射中心确定所述节点的邻域点集合，所述邻域点集合包括所述节点在至少两个方向的线段的终点所对应的节点；
32.基于所述邻域点集合所包括节点的数量、所述邻域点集合中各个节点之间的相对位置，删除所述无向图中符合冗余条件的骨架线冗余点，得到所述路径序列。
33.在一种可能实现方式中，对于每个节点p1，所述节点p1的邻域点集合包括节点pi，i
∈[2,9]；当所述节点在对应方向存在线段的终点所对应的节点时，pi＝1；当所述节点在对应方向不存在线段的终点所对应的节点时，pi为空时，pi＝0；
[0034]
相应的，所述删除模块，还用于：
[0035]
对应每个节点p1，响应于所述p1对应的pi满足以下三项条件，删除所述p1：
[0036]
第1项：2≤p2 p3 p4 p5 p6 p7 p8 p9≤6；
[0037]
第2项：s(p1)＝1，s(p1)表示以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序时，所述pi由pi＝0变为pi＝1的变化次数；
[0038]
第3项：p2×
p4×
p6＝0且p4×
p6×
p8＝0，pi以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序。
[0039]
在一种可能实现方式中，对于每个节点p1，所述节点p1的邻域点集合包括节点pi，i∈[2,9]；当所述节点在对应方向存在线段的终点所对应的节点时，pi＝1；当所述节点在对应方向不存在线段的终点所对应的节点时，pi为空时，pi＝0；
[0040]
相应的，所述删除模块，还用于：
[0041]
对应每个节点p1，响应于所述p1对应的pi满足以下三项条件，删除所述p1：
[0042]
第1项：2≤p2 p3 p4 p5 p6 p7 p8 p9≤6；
[0043]
第2项：s(p1)＝1，s(p1)表示以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序时，所述pi由pi＝0变为pi＝1的变化次数；
[0044]
第3项：p2×
p4×
p8＝0且p2×
p6×
p8＝0，pi以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序。
[0045]
在一种可能实现方式中，所述路径规划模块，还用于：
[0046]
确定所述当前位置在所述路径序列中对应的骨架线关键点；
[0047]
在首次遍历时，以所述当前位置对应的骨架线关键点为起点，执行以广度优先遍历的方式、遍历所述路径序列中与所述起点连通的下一骨架线关键点的遍历步骤，并记录从所述起点到所述下一骨架线关键点的当前路线；
[0048]
在首次遍历之后的每次遍历时，继续以所述当前路线的末尾点为起点，再次执行所述遍历步骤，并更新所记录的当前路线，直至达到遍历结束条件时停止遍历，得到所述目标路线。
[0049]
另一方面，提供了一种计算机设备，包括存储器、处理器及存储在存储器上的计算机程序，所述处理器执行所述计算机程序以实现上述的路径规划方法。
[0050]
另一方面，提供了一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现上述的路径规划方法。
[0051]
另一方面，提供了一种计算机程序产品，包括计算机程序，所述计算机程序被处理器执行时实现上述的路径规划方法。
[0052]
本技术实施例提供的技术方案带来的有益效果是：
[0053]
本技术实施例提供的路径规划方法，通过在接收到任一虚拟对象的路径规划请求时，基于该任一虚拟对象在三维场景地图中的当前位置和预存储的路径序列，确定目标路线，从而在无需人力成本情况下、实现自动规划路径的过程。而该路径序列包括构成骨架线的至少两个骨架线关键点、以及至少两个骨架线关键点之间的连通关系，骨架线用于指示三维场景地图中的可移动区域的空间结构，具体该路径序列的生成过程是：先通过基于从三维场景地图中至少两个起点发射线段的过程，获取发射点集合；基于该发射点集合构建无向图，并基于无向图中各个节点之间的相对位置，删除无向图中符合冗余条件的骨架线
冗余点，将无向图中剩余节点确定构成骨架线的骨架线关键点，最终得到路径序列；通过该冗余条件可删除构成骨架线的冗余点，从而减少自动化探索地图过程中需探索的位置点的数量，降低了路径序列的冗余度，可提高路径规划的速度，进而提高了路径规划的处理效率。
附图说明
[0054]
为了更清楚地说明本技术实施例中的技术方案，下面将对本技术实施例描述中所需要使用的附图作简单地介绍。
[0055]
图1为本技术实施例提供的一种实现路径规划方法的实施环境示意图；
[0056]
图2为本技术实施例提供的一种路径序列生成方法的流程示意图；
[0057]
图3为本技术实施例提供的一种邻域点集合示意图；
[0058]
图4为本技术实施例提供的一种邻域点集合示意图；
[0059]
图5为本技术实施例提供的一种邻域点集合示意图；
[0060]
图6为本技术实施例提供的一种三维场景地图中的某片场景地图的示意图；
[0061]
图7为本技术实施例提供的一种三维场景地图的可移动区域示意图；
[0062]
图8为本技术实施例提供的一种骨架线的示意图；
[0063]
图9为本技术实施例提供的一种路径规划方法的信令交互图；
[0064]
图10为本技术实施例提供的一种路径序列的寻路示意图；
[0065]
图11为本技术实施例提供的一种路径规划流程示意图；
[0066]
图12为本技术实施例提供的一种路径规划装置的结构示意图；
[0067]
图13为本技术实施例提供的一种计算机设备的结构示意图。
具体实施方式
[0068]
下面结合本技术中的附图描述本技术的实施例。应理解，下面结合附图所阐述的实施方式，是用于解释本技术实施例的技术方案的示例性描述，对本技术实施例的技术方案不构成限制。
[0069]
以下，对本技术涉及的术语进行解释。
[0070]
三维场景地图：用于提供游戏中虚拟游戏场景；三维场景地图包括多种虚拟的游戏场景元素，三维场景地图可以是对真实世界的仿真环境地图、半仿真半虚构的环境、或者纯虚构的环境。该三维场景地图可以是二维虚拟游戏场景的场景地图、2.5维虚拟游戏场景的场景地图和三维虚拟游戏场景的场景地图中的任意一种，本技术对此不加以限定。该三维场景地图可以包括天空、陆地、海洋等，该陆地可以包括沙漠、城市等环境元素，玩家可以控制虚拟对象在该虚拟游戏场景中进行移动、跑步、跳跃等。
[0071]
路径规划：是指为虚拟对象规划可移动的路线。
[0072]
骨架线：用于指示该三维场景地图中的可移动区域的空间结构，是采用曲线对该可移动区域的空间结构的线形表示。
[0073]
骨架线关键点：用于构成骨架线的必不可少的点。
[0074]
骨架线冗余点：对于构成骨架线而言，是冗余的点。
[0075]
路径序列：包括用于构成该骨架线的至少两个骨架线关键点、以及该至少两个骨
架线关键点之间的连通关系。
[0076]
图1为本技术提供的一种路径规划方法的实施环境示意图。如图1所示，该实施环境包括：服务器101和终端102。
[0077]
在一个可能场景示例中，该服务器101可以为游戏服务器，该终端102可以安装有游戏应用或显示云游戏页面。以游戏应用为例，玩家可以登录该游戏应用中的游戏账号，并控制游戏中的虚拟对象在三维场景地图中进行游戏。该游戏应用提供有自动规划路径的功能，该终端102可以向服务器101发送路径规划请求，该服务器101可以基于终端102的路径规划请求，向该终端102返回所规划的目标路线，以使虚拟对象按照所规划的目标路线在三维场景地图中移动。
[0078]
该虚拟对象可以是代表该玩家在游戏中的虚拟形象。该游戏应用可以为提供有三维场景地图、支持虚拟对象在三维场景地图中移动的任一款游戏，例如，该游戏应用可以包括但不限于：第三人称射击游戏、第一人称射击游戏、枪战类游戏、竞技游戏、竞速游戏、单机游戏、多人在线战术竞技游戏、即时战略游戏等一种或多种游戏应用。
[0079]
需要说明的是，本技术实施例涉及的游戏可以是游戏应用或云游戏，上述仅以游戏应用为例进行说明，但本技术的路径规划方法对云游戏也适用。应理解的是，云游戏(cloud gaming)又可称为游戏点播(gaming on demand)，是一种以云计算技术为基础的在线游戏技术。云游戏技术使图形处理与数据运算能力相对有限的轻端设备(thin client)能运行高品质游戏。在云游戏场景下，游戏并不在玩家游戏终端，而是在云端服务器中运行，并由云端服务器将游戏场景渲染为视频音频流，通过网络传输给玩家游戏终端。玩家游戏终端无需拥有强大的图形运算与数据处理能力，仅需拥有基本的流媒体播放能力与获取玩家输入指令并发送给云端服务器的能力即可。
[0080]
服务器可以是独立的物理服务器，也可以是多个物理服务器构成的服务器集群或者分布式系统，还可以是提供云服务、云数据库、云计算、云函数、云存储、网络服务、云通信、中间件服务、域名服务、安全服务、cdn(content delivery network，内容分发网络)、以及大数据和人工智能平台等基础云计算服务的云服务器或服务器集群。上述网络可以包括但不限于：有线网络，无线网络，其中，该有线网络包括：局域网、城域网和广域网，该无线网络包括：蓝牙、wi-fi及其他实现无线通信的网络。终端可以是智能手机(如android手机、ios手机等)、平板电脑、笔记本电脑、数字广播接收器、mid(mobile internet devices，移动互联网设备)、pda(个人数字助理)、台式计算机、车载终端(例如车载导航终端、车载电脑等)、智能家电、飞行器、智能音箱、智能手表等，终端以及服务器可以通过有线或无线通信方式进行直接或间接地连接，但并不局限于此。具体也可基于实际应用场景需求确定，在此不作限定。
[0081]
本技术实施例提供的路径方法，涉及以下人工智能、计算机视觉等技术示例性的，例如，利用人工智能技术中的云计算、大数据处理等技术，遍历三维场景地图中的发射点、生成路径序列。例如，利用计算机视觉技术中3d技术、地图构建等技术，实现从三维场景地图中的发射起点向周围发射线段的过程。
[0082]
应理解，人工智能(artificial intelligence，ai)是利用数字计算机或者数字计算机控制的机器模拟、延伸和扩展人的智能，感知环境、获取知识并使用知识获得最佳结果的理论、方法、技术及应用系统。换句话说，人工智能是计算机科学的一个综合技术，它企图
了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器。人工智能也就是研究各种智能机器的设计原理与实现方法，使机器具有感知、推理与决策的功能。
[0083]
人工智能技术是一门综合学科，涉及领域广泛，既有硬件层面的技术也有软件层面的技术。人工智能基础技术一般包括如传感器、专用人工智能芯片、云计算、分布式存储、大数据处理技术、操作/交互系统、机电一体化等技术。人工智能软件技术主要包括计算机视觉技术、语音处理技术、自然语言处理技术以及机器学习/深度学习、自动驾驶、智慧交通等几大方向。
[0084]
应理解，计算机视觉技术(computer vision，cv)计算机视觉是一门研究如何使机器“看”的科学，更进一步的说，就是指用摄影机和电脑代替人眼对目标进行识别和测量等机器视觉，并进一步做图形处理，使电脑处理成为更适合人眼观察或传送给仪器检测的图像。作为一个科学学科，计算机视觉研究相关的理论和技术，试图建立能够从图像或者多维数据中获取信息的人工智能系统。计算机视觉技术通常包括图像处理、图像识别、图像语义理解、图像检索、ocr、视频处理、视频语义理解、视频内容/行为识别、三维物体重建、3d技术、虚拟现实、增强现实、同步定位与地图构建、自动驾驶、智慧交通等技术，还包括常见的人脸识别、指纹识别等生物特征识别技术。
[0085]
为使本技术的目的、技术方案和优点更加清楚，下面将结合附图对本技术实施方式作进一步地详细描述。
[0086]
图2为本技术实施例提供的一种路径序列生成方法的流程示意图。该方法的执行主体可以为计算机设备。如图2所示，该方法包括以下步骤。
[0087]
步骤201、计算机设备基于从该三维场景地图中至少两个起点发射线段的过程，获取该三维场景地图中的发射点集合。
[0088]
该发射点集合用于指示三维场景地图中的可移动区域的空间范围。
[0089]
本步骤中，该计算机设备可以从起点向周围发射线段，以获取三维场景地图中该起点对应的移动范围。步骤201可以包括：该计算机设备可以获取该三维场景地图中的至少两个起点，按照预配置的线段发射规则，从每个起点发射线段，基于每个起点对应的线段发射结果，获取该发射点集合。在一种可能实现方式中，该计算机设备可以迭代的方式，遍历得到该发射点集合，步骤201可以包括：该计算机设备通过迭代以下步骤s1至步骤s3扩展发射点集合，直至该三维场景地图中没有新的发射点：
[0090]
步骤s1、该计算机设备遍历该三维场景地图中的至少一个起点，并从每个起点发射至少两条线段；
[0091]
步骤s2、该计算机设备响应于任一线段在发射过程中未碰撞障碍物、且该任一线段的终点的目标范围内存在到达点，获取该到达点对应的候选发射点；
[0092]
步骤s3、该计算机设备响应于该候选发射点与发射点集合中的每个发射点之间距离符合目标条件，将该候选发射点作为发射点添加至该发射点集合中。
[0093]
其中，步骤s1中，该计算机设备遍历该三维场景地图中起点的方式可以包括以下方式一和方式二两种，下面结合步骤s1的两种实现方式，对步骤s1至步骤s3的迭代过程进行说明。
[0094]
方式一、该计算机设备基于模拟对象在该三维场景地图的当前位置，获取该模拟
对象对应的至少一个起点。
[0095]
该模拟对象用于模拟虚拟对象进入虚拟游戏场景中进行游戏。该计算机设备可以预先配置模拟对象，并通过该模拟对象模拟虚拟对象进入游戏的场景，以便于定位到三维场景地图中虚拟对象可到达的某个位置，从该位置开始进行线段检测。
[0096]
该计算机设备获取模拟对象进入游戏时在三维场景地图中的当前位置，根据该当前位置以及预配置的跳跃高度，确定该模拟对象对应的起点。该跳跃高度是指模拟对象跳跃过程可到达的高度。
[0097]
例如，该三维场景地图可以是一个三维坐标系，可以采用该三维坐标系中位置坐标来表示。计算机设备可通过游戏应用的定位接口，获取虚拟对象在三维场景地图中位置坐标(x，y，z)，其中，x、y、z分别代表虚拟对象在三维场景地图中的横轴位置、纵轴位置和高度位置。由于虚拟对象可以通过跳跃到达障碍物顶端，因此，可以在z轴方向的位置增加跳跃高度，以避免直接基于位置坐标发射线段时与周围障碍物碰撞。该跳跃距离可以为0.8米，基于此，该计算机设备可以将(x，y，z 跳跃距离0.8米)作为起点。
[0098]
在一种可能实现方式中，该计算机设备中可以预配置有线段发射规则，可按照该线段发射规则来发射线段。例如，该线段发射规则可以包括线段发射方向和各个方向的线段发射长度。在一个可能示例中，该计算机设备从每个起点发射至少两条线段的步骤包括：该计算机设备按照至少两个方向各自对应的线段长度，从该每个起点向该至少两个方向发射至少两条线段。其中，该至少两个方向也可以为预配置的方向。例如，该至少两个方向可以包括8个方向，相邻方向的线段间隔角度可以为45度，则该至少两个方向可以包括：东、南、西、北方向、以及对角线上的东北、东南、西北、西南方向。其中，东、南、西、北方向对应的线段长度可以为0.6米；对角线上的东北、东南、西北、西南方向对应的线段长度可以为0.85米。当然，该至少两个方向以及各个方向各自对应的线段长度可以基于需要进行配置，本技术仅以上述举例进行说明，本技术对线段发射方向以及各方向对应的线段长度并不做限定。
[0099]
需要说明的是，在步骤s1中遍历三维场景地图中的起点时，通过模拟对象来模拟虚拟对象进入三维场景地图，基于该模拟对象在三维场景地图的当前位置获取起点，从而基于虚拟对象在三维场景地图中可到达的位置点来定位开始遍历的起点，使得获取的起点能够更贴合于虚拟对象的实际游戏过程，保证后续遍历的发射点集合的有效性和准确性，提高了路径序列的准确性。
[0100]
并且，还可以按照设定的线段发射规则发射线段，例如从至少两个方向、按照各个方向对应的线段长度向周围发射至少两条线段，从而检测出各个发射点在多个方向上、一定距离内的可移动情况，提高了发射线段的效率和准确性，进而提高了后续遍历发射点集合的准确性和遍历效率。
[0101]
该计算机设备基于方式一获取起点后，该计算机设备从该起点发射至少两条线段。并且，该计算机设备可以基于该线段发射结果，执行步骤s2至步骤s3，以更新发射点集合。
[0102]
在一种可能实现方式中，在步骤s2中，该计算机设备响应于任一线段在发射过程中未碰撞障碍物、且该任一线段的终点的目标范围内存在到达点，获取该到达点对应的候选发射点。一示例中，该到达点表示沿该线段轨迹移动时可到达的位置点。对于每个方向的
线段，该到达点可以用于模拟虚拟对象从该起点出发、沿该线段移动到达终点后的落脚点。例如，从起点a发射的正北方向的线段的终点为b，该终点b的下方1.2米范围内存在落脚点c(x1，y1，z1)，则到达点即可以指落脚点c。一示例中，该计算机设备可以根据该到达点以及预配置的跳跃高度，获取该到达点对应的候选发射点。例如，将落脚点c(x1，y1，z1)对应的点d(x1，y1，z1 跳跃距离0.8米 跳跃距离0.8米)作为候选发射点。当然，从起点a发射的其他方向的线段发射结果也可能对应有发射点，上述仅以正北方向发射线段的结果对应的点d为例进行说明。
[0103]
在一种可能实现方式中，在步骤s3中，该计算机设备响应于该候选发射点与发射点集合中的每个发射点之间距离符合目标条件，将该候选发射点作为发射点添加至该发射点集合中。一示例中，该计算机设备可以获取该候选发射点与发射点集合已包括的每个发射点之间的距离，如果该候选发射点与每个发射点之间的距离均满足目标条件，则将该候选发射点作为发射点添加至发射点集合中。其中，该目标条件可以包括但不限于：该候选发射点与该发射点集合中任一发射点之间的距离不超过目标距离阈值、该候选发射点与该任一发射点之间的距离位于目标距离范围内等。例如，将该候选发射点与发射点集合中已有的发射点进行对比，如果候选发射点与每个发射点之间的距离大于阈值0.6米，则将该候选发射点放入发射起点集合中，以更新该发射点集合；如果距离不大于0.6米，也即是该距离太接近，说明曾经探索过该候选发射点附近的位置，不需要再重复探索。
[0104]
方式二、该计算机设备将上一次迭代过程得到的发射点作为当前迭代过程的至少一个起点。
[0105]
以上一次迭代过程为方式一中对应迭代过程为例，也即是，上一次迭代过程为该计算机设备基于上述方式一执行的发射点集合更新过程。在一种可能实现方式中，该计算机设备可以将基于方式一执行迭代时所添加至发射点集合中的发射点，作为当前迭代过程的至少一个起点。例如，将发射点d作为本次迭代的其中一个起点，以从发射点d为起点，执行从该起点发射至少两条线段，并执行步骤s2和步骤s3的过程。需要说明的是，基于方式二的步骤之后所继续执行的迭代过程，与基于方式一的步骤之后所执行的迭代过程同理，此处不再一一赘述。
[0106]
该计算机设备可以将方式一获得的起点作为初始位置，基于该初始位置，以线段检测方式，遍历该三维场景地图中的发射点。并基于每次迭代所产生的发射点为起点，继续进行下一次迭代，直至没有新的发射点，也即是无需再更新发射点集合，确定迭代结束，得到最终的发射点集合。通过上述步骤201的方式得到的发射点集合，能够表示该三维场景地图提供给虚拟对象的可移动区域。其中，该直至该三维场景地图中没有新的发射点可以是指三维场景地图中的可行区域中的发射点均已添加至发射点集合中；例如，连续目标次数的迭代过程中，所产生的候选发射点均存在与已有的发射点之间距离不符合目标条件，则可确定该三维场景地图中没有新的发射点。又例如，连续目标次数的迭代过程中，均未得到候选发射点，则可确定该三维场景地图中没有新的发射点。
[0107]
需要说明的是，通过上述步骤s1从遍历的每个起点发射至少两条线段，并结合线段的发射情况进一步筛选得到发射点集合，具体将未碰撞到障碍物且线段终点在目标范围内存在到达点时，获取到达点对应的候选发射点，如线段终点下方一定距离内存在落脚点，则基于落脚点得到候选发射点，从而结合了虚拟对象可能的移动情况初步得到候选发射
点。继而将候选发射点与已有的发射点进行对比，具体基于候选发射点与已有发射点之间的距离若符合目标条件才将其作为发射点，如距离过近则说明候选发射点近距离范围内已被探索过，从而避免了近距离区域内的重复探索，提高了获取发射点集合的处理效率。同时也使得发射点集合中各个发射点的分布不会过于密集，减少了后续生成路径序列时的运算量，提高了处理效率。
[0108]
步骤202、计算机设备基于该发射点集合，构建无向图，并存储该无向图中每个节点及与其连接的节点之间的相对位置。
[0109]
该无向图用于指示该可移动区域中各个发射点之间的连通关系。该无向图中相连接的两个节点所对应的发射点之间具备连通关系。两个发射点之间具备连通关系说明三维场景地图中存在从一个发射点到另一发射点的移动路径；也即是，对于具备连通关系的两个发射点，虚拟对象可以从其中一个发射点移动至另一个发射点。例如，三维场景地图中位置点a和位置点b之间具备连通关系，则虚拟对象可以从位置点a朝位置点b的方向跳跃，通过一次跳跃动作到达位置点b。
[0110]
该计算机设备可以发射点集合中的发射点为节点，以发射点之间是否存在线段发射关系作为两节点之间是否建立连线的判断依据，构建该无向图。在一种可能的实现方式中，该计算机设备可以根据该各个发射点、以及每个发射点对应在每个方向的线段的终点，生成该无向图。例如，当两个发射点之间存在线段发射关系时，该两个发射点所对应的两个节点之间存在连线。
[0111]
在一种可能实现方式中，对于每个节点，该计算机设备可以存储该节点及与其在至少一个方向相连接的节点之间的相对位置。由于每两个相连接的节点所对应的发射点之间存在线段发射关系，因此，该相对位置是指两个节点中一个节点相对于另一个节点的线段发射方向。例如，节点1和节点2相连接，节点1对应于发射点m，节点2对应于发射点n，从发射点m向正北方向发射线段的结果，得到发射点n，则节点1和节点2之间的相对位置可以包括：节点2位于节点1的正北方向；当然，节点1位于节点2的正南方向。
[0112]
本步骤中，通过基于发射点集合构建无向图，从而以逻辑图的表示了可移动区域中各个发射点之间的逻辑关系，便于后续直接基于无向图所表示的各个节点之间逻辑关系得到路径序列，从而保证后续高效生成路径序列。
[0113]
步骤203、计算机设备基于该无向图中各个节点之间的相对位置，删除该无向图中符合冗余条件的骨架线冗余点，将该无向图中剩余节点确定为构成该骨架线的挂架线关键点，得到该路径序列。
[0114]
该冗余条件用于衡量该无向图中节点对构成该骨架线是否冗余，该骨架线用于指示该可移动区域的空间结构，该路径序列包括用于构成该骨架线的至少两个骨架线关键点、以及该至少两个骨架线关键点之间的连通关系。该计算机设备可以基于该无向图中每个节点和该节点的邻域点之间的相对位置，筛选出该无向图所包括的节点中符合冗余条件的节点，将所筛选出的节点作为骨架线冗余点进行删除；并且，将该无向图中删除骨架线冗余点之后剩余的节点作为骨架线关键点；基于该骨架线关键点以及各个骨架线关键点之间的连通关系，得到路径序列。其中，该骨架线可以是由多个骨架线关键点构成的曲线。该路径序列包括了该多个骨架线关键点之间的连通关系，例如，该路径序列可以包括：点1-点2-点3-点4-点5-点6-点8，另外，点5还与点7相连接。
[0115]
在一种可能实现方式中，该计算机设备可以针对每个节点，以每个节点的邻域点集合为依据，来判断该节点在构成骨架线时是否冗余。相应的，本步骤可以包括步骤2031和步骤2032。
[0116]
步骤2031、对于每个节点，该计算机设备基于该节点及与其相连接的节点之间的相对位置，以该节点为发射中心确定该节点的邻域点集合。
[0117]
该邻域点集合包括该节点在至少两个方向的线段的终点所对应的节点。对于每个节点e，以该节点e对应的发射点e为起点发射的至少两个方向的线段，对于其中任一方向的线段，该任一方向线段的终点对应的发射点为f，则f对应的节点f为节点e的邻域点，以此方式得到包括多个邻域点的邻域点集合。例如，如图3所示，将当前处理的节点表示为节点p1，周围的邻域点集合可以沿顺时针顺序依次表示为p2、p3、p4、p5、p6、p7、p8、p9，顺时针方向的各个点依次位于节点p1的正北方向、东北方向、正东方向、东南方向、正南方向、西南方向、正西方向、西北方向。
[0118]
步骤2032、该计算机设备基于该邻域点集合所包括节点的数量、该邻域点集合中各个节点之间的相对位置，删除该无向图中符合冗余条件的骨架线冗余点，得到该路径序列。
[0119]
通过基于节点之间的相对位置确定节点的邻域集合，进一步结合邻域点所包括的节点数量、相对位置等情况，判断是否将该节点作为冗余点进行删除，从而精准定位了各个节点对构成骨架线是否冗余，提高了对各个节点冗余判断的准确性，保证删除后的剩余节点为构成骨架线的必要节点，尽可能的精简了路径序列中骨架线关键点的数量，且保证了各个挂架线关键点之间的连通性，提高了所生成的路径序列的精确性，提高了基于该路径序列进行寻路的效率。并且，通过删除冗余点，精简路径序列中骨架线关键点的数量，使得后续生成的目标路线中也不会包括骨架线冗余点，提高了虚拟对象沿目标路线进行移动的移动效率，进而提高了虚拟对象在游戏探索三维场景地图的地图探索效率。
[0120]
在一种可能的技术实现中，以图3所示的邻域点集合排列方式为例，对于每个节点p1，该节点p1的邻域点集合包括节点pi，当然，i为正整数，i∈[2,9]；当该节点在对应方向存在线段的终点所对应的节点时，pi＝1；当该节点在对应方向不存在线段的终点所对应的节点时，pi为空时，pi＝0；
[0121]
相应的，步骤2032可以包括：步骤2032a、对应每个节点p1，响应于该p1对应的pi满足以下三项条件，删除该p1：
[0122]
第1项：2≤p2 p3 p4 p5 p6 p7 p8 p9≤6；
[0123]
第2项：s(p1)＝1，s(p1)表示以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序时，该pi由pi＝0变为pi＝1的变化次数；
[0124]
第3项：p2×
p4×
p6＝0且p4×
p6×
p8＝0，pi以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序。
[0125]
该冗余条件可以包括步骤2032a中的上述三项条件。
[0126]
其中，在第1项中，大于等于2是为了保证p1不是端点(周围只有1个值为1的节点)或孤立点(周围没有值为1的节点)，小于等于6保证p1是一个边界点，而不是一个内部点，如图4所示，图4中(a)示出了端点的情况，如果p1的邻域点集合中仅存在一个正北方向的相连接的节点，也即是，只有p2＝1，其余取值均为0，则p1属于端点；图4中(b)示出了内部点的情况，如果p1的邻域点集合中只有p4＝0，其余取值均为1，则p1属于内部点。
[0127]
在第2项中，p2到p9的顺时针排序中，各个点的取值由0变化为1的变化次数的总数为1，则满足第2项。例如，比如p2为0，p3为1，则为0
→
1的一次变化。可以分别判断p2和p3、p3和p4、p4和p5、p5和p6、p6和p7、p7和p8、p8和p9、p9和p2是否满足0
→
1的变化模式，并将满足该变化的变化次数进行累加。通过第2项的判断方式，可以保证删除当前节点后的连通性。例如，如图5所示，图5的(a)中，0
→
1的变化次数累加为2；图5的(b)中0
→
1的变化次数累加为2；也即是，0
→
1的变化次数累加大于1，如果删除当前节点p1，则无法保证该邻域点集合所对应的连通性。
[0128]
在第3项中，p2×
p4×
p6＝0同时p4×
p6×
p8＝0，只要p4和p6中的任一个取值为0，则符合该第3项的条件。通过该第3项可以过滤掉位于东南方向的边界点。
[0129]
需要说明的是，该计算机设备可以基于上述步骤2032a，执行一次迭代过程，该计算机设备还可以基于以下步骤2032b，执行第二次迭代过程。
[0130]
在一种可能技术实现中，以图3所示的邻域点集合排列方式为例，步骤2032可以包括：步骤2032b、该基于该邻域点集合所包括节点的数量、该邻域点集合中各个节点之间的相对位置，删除该无向图中符合冗余条件的骨架线冗余点，包括：
[0131]
对应每个节点p1，响应于该p1对应的pi满足以下三项条件，删除该p1：
[0132]
第1项：2≤p2 p3 p4 p5 p6 p7 p8 p9≤6；
[0133]
第2项：s(p1)＝1，s(p1)表示以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序时，该pi由pi＝0变为pi＝1的变化次数；
[0134]
第3项：p2×
p4×
p8＝0且p2×
p6×
p8＝0，pi以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序。
[0135]
该冗余条件还可以包括步骤2032b中的上述三项条件。
[0136]
需要说明的是，步骤2032b中的第1项和第2项，与上述步骤2032a中的第1项和第2项同理的过程，此处不再一一赘述。
[0137]
对于步骤2032b中的第3项，p2×
p4×
p8＝0同时p2×
p6×
p8＝0，只要p2和p8中的任一个取值为0，则符合该第3项的条件。通过该第3项可以过滤掉位于西北方向的边界点。
[0138]
该计算机设备每基于上述步骤2032a和步骤2032b执行两次迭代，可以作为对冗余点进行过滤的一次细化过程，该计算机设备可以重复执行多次细化过程，直至满足目标过滤条件时，停止迭代，生成该三维场景地图的骨架线。其中，该目标过滤条件可以包括但不限于：连续第一指定数目次过滤过程中过滤的冗余点为0、当前过滤过程的执行次数超过第二指定数目次等。通过删除三维骨架线的冗余点，采用尽可能少的骨架线关键点来表示可移动区域的空间结构，减少了路径规划过程中需探索的位置点的数量，实现高效率的自动化探索地图的过程。
[0139]
通过基于上述步骤2032a的三项条件过滤骨架线冗余点，如通过第1项，可以将端点、孤立点、内部点排除在冗余条件之外，保证符合冗余条件的节点属于边界点，而符合第2项的节点为删除后不影响周围邻域点集合的连通性的节点，通过第1、2、3项可过滤掉东南方向的边界点，且过滤后不影响周围点的连通性，从而结合节点的周围邻域点集合，尽可能的过滤掉不影响连通性的冗余点。并且，还可以基于步骤2032b的三项条件迭代过滤掉冗余点，通过步骤2032b中第1、2、3项可过滤掉西北方向的边界点，且删除后不影响周围点的连通性。通过依次执行上述步骤2032a和步骤2032b，从而两次迭代删除东南、西北的边界点，完成一次细化过程。并通过多次重复上述步骤2032a和步骤2032b，以实现多次细化过程，提
高冗余点过滤的准确性，从而尽可能的降低剩余节点的冗余度，进而降低路径序列中骨架线关键点的冗余度。并且，后续基于该路径序列来遍历路线时，可大大提高遍历路线的效率，使得遍历的路线中各个位置点是构成骨架线的必要关键点、而非冗余点，虚拟对象沿该遍历路线探索地图，可提高虚拟对象探索地图的效率。
[0140]
如图6所示，图6为本技术实施例提供的一种三维场景地图中的某片场景地图，在该区域中有些位置可移动，例如，前方的道路；而有些位置不可移动，例如，两侧的房屋墙壁。该计算机设备可以基于上述步骤201的过程，获取该片场景地图中的发射点集合。如图7所示，图7中采用点集的方式标记了游戏场景中的可移动区域位置，也即是，图7中的点的分布位置对应为图6中可移动区域所在的位置。该计算机设备基于该图7中所展示的发射点生成无向图，并基于上述步骤203，对该无向图中节点进行过滤，以删除构成骨架线时的冗余点，保留骨架线关键点。其中，基于步骤203的多次迭代，最终得到的骨架线如图8所示。图8中各个骨架线关键点构成了可移动区域对应的骨架线，结合图7和图8可得到，基于该骨架线，可以形象、准确的勾勒出图7中可移动区域的空间结构。
[0141]
图9提供了一种路径规划方法的信令交互图。该路径规划方法可以由服务器和终端交互实现。如图9所示，该路径规划方法可以包括以下步骤。
[0142]
步骤901、终端显示包括虚拟对象的游戏画面，并向服务器发送路径规划请求。
[0143]
该终端可以运行游戏应用，玩家可以在游戏应用中，控制游戏画面中的虚拟对象进行游戏。例如，控制虚拟对象进行跑步、跳跃、飞行、骑行、乘坐载具、后退等移动行为。该三维场景地图中的可移动区域即为该虚拟对象的移动行为可到达的区域。一示例中，当该虚拟对象进入三维场景地图时，该终端可以向该服务器发送路径规划请求。当然，也可以在该游戏应用中用于触发自动规划路径功能的控件被触发时，该终端向该服务器发送路径规划请求。
[0144]
步骤902、服务器接收该路径规划请求。
[0145]
步骤903、服务器响应于接收到的路径规划请求，基于该虚拟对象在三维场景地图的当前位置和预存储的路径序列，确定该任一虚拟对象在三维场景地图中对应的目标路线。
[0146]
该路径序列包括用于构成骨架线的至少两个骨架线关键点、以及该至少两个骨架线关键点之间的连通关系；该骨架线用于指示该三维场景地图中的可移动区域的空间结构。该服务器可以该当前位置在路径序列中对应的骨架线关键点为起点，在路径序列中遍历目标路线。
[0147]
在一种可能实现方式中，该服务器可以采用广度优先的方式，在路径序列中迭代遍历路线中的各个点，以最终得到目标路线。一示例中，步骤902的过程可以包括：该服务器确定该当前位置在该路径序列中对应的骨架线关键点；在首次遍历时，该服务器以该当前位置对应的骨架线关键点为起点，执行以广度优先遍历的方式、遍历该路径序列中与该起点连通的下一骨架线关键点的遍历步骤，并记录从该起点到该下一骨架线关键点的路线；在首次遍历之后的每次遍历时，该服务器继续以当前路线的末尾点为起点，再次执行该遍历步骤，并更新所记录的路线，直至达到遍历结束条件时停止遍历，得到该目标路线。
[0148]
示例性的，该当前位置对应的骨架线关键点可以为该路径序列所包括的多个骨架线关键点中符合目标位置条件的骨架线关键点。例如，该目标位置条件可以包括但不限于：
各个骨架线关键点中距离该当前位置最近的骨架线关键点、距离该当前位置不超过目标长度的骨架线关键点等。例如，该服务器还可以结合该虚拟对象在三维场景地图的移动方向，确定当前位置对应的骨架线关键点，该服务器根据该虚拟对象的移动方向、当前位置，从该路径序列中筛选出沿该移动方向分布的多个第一骨架线关键点，并从该多个第一骨架线关键点中筛选出符合目标位置条件的第二骨架线关键点，将该第二骨架线关键点作为该当前位置对应的骨架线关键点。例如，服务器可以结合虚拟对象的摇杆方向以及在地图中的位置坐标，匹配出沿该摇杆方向、且距离该位置最近的骨架线关键点。
[0149]
示例性的，首次遍历时，该服务器以该当前位置对应的骨架线关键点为起点执行遍历步骤，得到从起点到遍历出的下一骨架线关键点的当前路线。在首次遍历之后的每次遍历时，则以当前路线中的末尾点为起点，再次执行该遍历步骤；也即是，每次遍历时，采用广度优先遍历的方式，从该起点位置遍历路径序列中与该起点相连接的下一个骨架线关键点，以此循环，直至达到遍历结束条件时停止遍历。其中，该遍历结束条件可以包括但不限于：该路径序列中被遍历的骨架线关键点的比例超过第一阈值、遍历时长超过第二阈值等。当然，该第一阈值、第二阈值可以基于需要进行配置，本技术实施例对此不做限定。例如，该第一阈值可以为100％、99％等；该第二阈值可以为0.01秒、0.05秒等。在一个可能示例，该广度优先遍历的方式可以为优先遍历距离起点更近的点，该服务器可采用bfs(breadth first search，宽度优先搜索)算法遍历与起点连通的下一骨架线关键点；例如，当有至少两个骨架线关键点与该起点相连接时，该服务器可以先遍历与该起点相连接的每个骨架线关键点；再基于此继续往下遍历。
[0150]
例如，如图10所示，该路径序列可以包括：点1-点2-点3-点4-点5-点6-点8，另外，在点5位置开始分叉，点5不仅与点6连接，点5还与点7相连接；如果该虚拟对象的当前位置所对应的骨架线关键点位点1，则该服务器以点1为起点进行寻路，依次遍历得到点2-点3-点4-点5，当基于点5继续遍历得到点6和点7，可以从点6继续遍历得到点8，并记录点7，再从点8返回遍历得到点6-点5，从点5遍历至所记录的点7，基于此可以遍历得到路线为点1-点2-点3-点4-点5-点6-点8-点6-点5-点7。
[0151]
通过以当前位置对应的骨架线关键点为起点，采用广度优先遍历的方式进行寻路，并实时记录当前路线，能够快速获取从该虚拟对象当前位置出发的移动路径，提高确定目标路线的效率和准确性，提高路径规划效率，进而提高虚拟对象自动化探索地图的效率。
[0152]
步骤904、服务器向该终端返回目标路线。
[0153]
步骤905、终端接收该服务器返回的目标路线。
[0154]
步骤906、终端在游戏画面中显示虚拟对象沿该目标路线在三维场景地图中进行移动的过程。
[0155]
终端基于该目标路线，控制虚拟对象沿目标路线进行移动，例如，通过调用游戏函数以获取虚拟对象的位置，并计算该虚拟对象的移动方向；从而控制虚拟对象向路径当前的目标点移动，该目标点可以是目标路线中位于当前所到达点的下一个点；当虚拟对象到达目标点后，从目标路线中获取下一个点，并下一个点作为当前需到达的目标点，以此循环，以继续向下一个目标点移动。
[0156]
如图11所示，本技术实施例提供的路径规划方法可以包括如图11所示的流程，例如，可以由服务器基于三维场景地图获取发射点集合，以生成地图可行区域；然后，利用冗
余条件，删除无向图中的骨架线冗余点，获得可行区域的三维骨架线，得到可行区域的路径序列。当接收到任一对象的路径规划请求时，基于该路径序列为其规划在地图中的移动路径。
[0157]
需要说明的是，上述步骤902至步骤904的过程，可以是步骤“响应于任一虚拟对象的路径规划请求，基于该任一虚拟对象在三维场景地图的当前位置和预存储的路径序列，确定该任一虚拟对象在该三维场景地图中对应的目标路线，并向该任一虚拟对象返回该目标路线；”的一种可能实现方式，上述实现方式实际上是基于终端和服务器之间的交互场景进行的路径规划过程。在另一种可能场景中，本技术的路径规划方法也可以适用于云游戏场景，例如，该云游戏场景中可以包括第一服务器和第二服务器，该第一服务器可以负责基于玩家在游戏画面的操作实时运行游戏应用并生成待显示的游戏画面的渲染数据。该第二服务器可以用于为一种或多种游戏提供路径规划服务，例如，该第二服务器可以为云计算中心的服务器。则该第一服务器可以向第二服务器发送路径规划请求，该第二服务器基于该路径规划请求，执行步骤903的过程，以得到目标路线，该第二服务器向该第一服务器返回该目标路线。后续可以有第一服务器基于该目标路线生成对应游戏画面的渲染数据，并向终端发送该渲染数据，以使终端持续显示虚拟对象在该三维场景地图中的移动过程，实现对地图的探索。
[0158]
本技术实施例提供的路径规划方法，通过在接收到任一虚拟对象的路径规划请求时，基于该任一虚拟对象在三维场景地图中的当前位置和预存储的路径序列，确定目标路线，从而在无需人力成本情况下、实现自动规划路径的过程。而该路径序列包括构成骨架线的至少两个骨架线关键点、以及至少两个骨架线关键点之间的连通关系，骨架线用于指示三维场景地图中的可移动区域的空间结构，具体该路径序列的生成过程是：先通过基于从三维场景地图中至少两个起点发射线段的过程，获取发射点集合；基于该发射点集合构建无向图，并基于无向图中各个节点之间的相对位置，删除无向图中符合冗余条件的骨架线冗余点，将无向图中剩余节点确定构成骨架线的骨架线关键点，最终得到路径序列；通过该冗余条件可删除构成骨架线的冗余点，从而减少自动化探索地图过程中需探索的位置点的数量，降低了路径序列的冗余度，可提高路径规划的速度，进而提高了路径规划的处理效率。
[0159]
图12为本技术实施例提供的一种路径规划装置的结构示意图。如图12所示，该装置包括：
[0160]
路径规划模块1201，用于响应于任一虚拟对象的路径规划请求，基于该任一虚拟对象在三维场景地图的当前位置和预存储的路径序列，确定该任一虚拟对象在该三维场景地图中对应的目标路线，并向该任一虚拟对象返回该目标路线；
[0161]
其中，该路径序列包括用于构成骨架线的至少两个骨架线关键点、以及该至少两个骨架线关键点之间的连通关系；该骨架线用于指示该三维场景地图中的可移动区域的空间结构；
[0162]
其中，该装置还用于生成路径序列，该装置在生成路径序列时，包括：
[0163]
发射点集合获取模块1202，用于基于从该三维场景地图中至少两个起点发射线段的过程，获取该三维场景地图中的发射点集合，该发射点集合用于指示该可移动区域的空间范围；
[0164]
构建模块1203，用于基于该发射点集合，构建无向图，并存储该无向图中每个节点及与其连接的节点之间的相对位置，该无向图用于指示该可移动区域中各个发射点之间的连通关系，该无向图中相连接的两个节点所对应的发射点之间具备连通关系；
[0165]
删除模块1204，用于基于该无向图中各个节点之间的相对位置，删除该无向图中符合冗余条件的骨架线冗余点，将该无向图中剩余节点确定为构成该骨架线的骨架线关键点，得到该路径序列，该冗余条件用于衡量该无向图中节点对构成该骨架线是否冗余。
[0166]
在一种可能实现方式中，该发射点集合获取模块1202，还用于：
[0167]
通过迭代以下步骤扩展发射点集合，直至该三维场景地图中没有新的发射点：
[0168]
遍历该三维场景地图中的至少一个起点，并从每个起点发射至少两条线段；
[0169]
响应于任一线段在发射过程中未碰撞障碍物、且该任一线段的终点的目标范围内存在到达点，获取该到达点对应的候选发射点；
[0170]
响应于该候选发射点与发射点集合中的每个发射点之间距离符合目标条件，将该候选发射点作为发射点添加至该发射点集合中。
[0171]
在一种可能实现方式中，该发射点集合获取模块1202，还用于以下任一项：
[0172]
基于模拟对象在该三维场景地图的当前位置，获取该模拟对象对应的至少一个起点，该模拟对象用于模拟虚拟对象进入虚拟游戏场景中进行游戏；
[0173]
将上一次迭代过程得到的发射点作为当前迭代过程的至少一个起点。
[0174]
在一种可能实现方式中，该发射点集合获取模块1202，还用于按照至少两个方向各自对应的线段长度，从每个起点向该至少两个方向发射至少两条线段；
[0175]
相应的，该构建模块1203，用于根据该各个发射点、以及每个发射点对应在每个方向的线段的终点，生成该无向图；对于每个节点，存储该节点及与其在至少一个方向相连接的节点之间的相对位置。
[0176]
在一种可能实现方式中，该删除模块1204，还用于：
[0177]
对于每个节点，基于该节点及与其相连接的节点之间的相对位置，以该节点为发射中心确定该节点的邻域点集合，该邻域点集合包括该节点在至少两个方向的线段的终点所对应的节点；
[0178]
基于该邻域点集合所包括节点的数量、该邻域点集合中各个节点之间的相对位置，删除该无向图中符合冗余条件的骨架线冗余点，得到该路径序列。
[0179]
在一种可能实现方式中，对于每个节点p1，该节点p1的邻域点集合包括节点pi，i∈[2,9]；当该节点在对应方向存在线段的终点所对应的节点时，pi＝1；当该节点在对应方向不存在线段的终点所对应的节点时，pi为空时，pi＝0；
[0180]
相应的，该删除模块1204，还用于：
[0181]
对应每个节点p1，响应于该p1对应的pi满足以下三项条件，删除该p1：
[0182]
第1项：2≤p2 p3 p4 p5 p6 p7 p8 p9≤6；
[0183]
第2项：s(p1)＝1，s(p1)表示以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序时，该pi由pi＝0变为pi＝1的变化次数；
[0184]
第3项：p2
×
p4
×
p6＝0且p4
×
p6
×
p8＝0，pi以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序。
[0185]
在一种可能实现方式中，对于每个节点p1，该节点p1的邻域点集合包括节点pi，i
∈[2,9]；当该节点在对应方向存在线段的终点所对应的节点时，pi＝1；当该节点在对应方向不存在线段的终点所对应的节点时，pi为空时，pi＝0；
[0186]
相应的，该删除模块1204，还用于：
[0187]
对应每个节点p1，响应于该p1对应的pi满足以下三项条件，删除该p1：
[0188]
第1项：2≤p2 p3 p4 p5 p6 p7 p8 p9≤6；
[0189]
第2项：s(p1)＝1，s(p1)表示以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序时，该pi由pi＝0变为pi＝1的变化次数；
[0190]
第3项：p2
×
p4
×
p8＝0且p2
×
p6
×
p8＝0，pi以p2、p3、p4、p5、p6、p7、p8、p9、p2为顺序。
[0191]
在一种可能实现方式中，该路径规划模块1201，还用于：
[0192]
确定该当前位置在该路径序列中对应的骨架线关键点；
[0193]
在首次遍历时，以该当前位置对应的骨架线关键点为起点，执行以广度优先遍历的方式、遍历该路径序列中与该起点连通的下一骨架线关键点的遍历步骤，并记录从该起点到该下一骨架线关键点的当前路线；
[0194]
在首次遍历之后的每次遍历时，继续以该当前路线的末尾点为起点，再次执行该遍历步骤，并更新所记录的当前路线，直至达到遍历结束条件时停止遍历，得到该目标路线。
[0195]
本技术实施例提供的路径规划装置，通过在接收到任一虚拟对象的路径规划请求时，基于该任一虚拟对象在三维场景地图中的当前位置和预存储的路径序列，确定目标路线，从而在无需人力成本情况下、实现自动规划路径的过程。而该路径序列包括构成骨架线的至少两个骨架线关键点、以及至少两个骨架线关键点之间的连通关系，骨架线用于指示三维场景地图中的可移动区域的空间结构，具体该路径序列的生成过程是：先通过基于从三维场景地图中至少两个起点发射线段的过程，获取发射点集合；基于该发射点集合构建无向图，并基于无向图中各个节点之间的相对位置，删除无向图中符合冗余条件的骨架线冗余点，将无向图中剩余节点确定构成骨架线的骨架线关键点，最终得到路径序列；通过该冗余条件可删除构成骨架线的冗余点，从而减少自动化探索地图过程中需探索的位置点的数量，降低了路径序列的冗余度，可提高路径规划的速度，进而提高了路径规划的处理效率。
[0196]
本技术实施例的装置可执行本技术实施例所提供的方法，其实现原理相类似，本技术各实施例的装置中的各模块所执行的动作是与本技术各实施例的方法中的步骤相对应的，对于装置的各模块的详细功能描述具体可以参见前文中所示的对应方法中的描述，此处不再赘述。
[0197]
图13是本技术实施例中提供了一种计算机设备的结构示意图。如图13所示，该计算机设备包括：存储器、处理器及存储在存储器上的计算机程序，该处理器执行上述计算机程序以实现路径规划方法的步骤，与相关技术相比可实现：
[0198]
本技术实施例提供的路径规划方法，通过在接收到任一虚拟对象的路径规划请求时，基于该任一虚拟对象在三维场景地图中的当前位置和预存储的路径序列，确定目标路线，从而在无需人力成本情况下、实现自动规划路径的过程。而该路径序列包括构成骨架线的至少两个骨架线关键点、以及至少两个骨架线关键点之间的连通关系，骨架线用于指示
三维场景地图中的可移动区域的空间结构，具体该路径序列的生成过程是：先通过基于从三维场景地图中至少两个起点发射线段的过程，获取发射点集合；基于该发射点集合构建无向图，并基于无向图中各个节点之间的相对位置，删除无向图中符合冗余条件的骨架线冗余点，将无向图中剩余节点确定构成骨架线的骨架线关键点，最终得到路径序列；通过该冗余条件可删除构成骨架线的冗余点，从而减少自动化探索地图过程中需探索的位置点的数量，降低了路径序列的冗余度，可提高路径规划的速度，进而提高了路径规划的处理效率。
[0199]
在一个可选实施例中提供了一种计算机设备，如图13所示，图13所示的计算机设备1300包括：处理器1301和存储器1303。其中，处理器1301和存储器1303相连，如通过总线1302相连。可选地，计算机设备1300还可以包括收发器1304，收发器1304可以用于该计算机设备与其他计算机设备之间的数据交互，如数据的发送和/或数据的接收等。需要说明的是，实际应用中收发器1304不限于一个，该计算机设备1300的结构并不构成对本技术实施例的限定。
[0200]
处理器1301可以是cpu(central processing unit，中央处理器)，通用处理器，dsp(digital signal processor，数据信号处理器)，asic(application specific integrated circuit，专用集成电路)，fpga(field programmable gate array，现场可编程门阵列)或者其他可编程逻辑器件、晶体管逻辑器件、硬件部件或者其任意组合。其可以实现或执行结合本技术公开内容所描述的各种示例性的逻辑方框，模块和电路。处理器1301也可以是实现计算功能的组合，例如包含一个或多个微处理器组合，dsp和微处理器的组合等。
[0201]
总线1302可包括一通路，在上述组件之间传送信息。总线1302可以是pci(peripheral component interconnect，外设部件互连标准)总线或eisa(extended industry standard architecture，扩展工业标准结构)总线等。总线1302可以分为地址总线、数据总线、控制总线等。为便于表示，图13中仅用一条粗线表示，但并不表示仅有一根总线或一种类型的总线。
[0202]
存储器1303可以是rom(read only memory，只读存储器)或可存储静态信息和指令的其他类型的静态存储设备，ram(random access memory，随机存取存储器)或者可存储信息和指令的其他类型的动态存储设备，也可以是eeprom(electrically erasable programmable read only memory，电可擦可编程只读存储器)、cd-rom(compact disc readonly memory，只读光盘)或其他光盘存储、光碟存储(包括压缩光碟、激光碟、光碟、数字通用光碟、蓝光光碟等)、磁盘存储介质\其他磁存储设备、或者能够用于携带或存储计算机程序并能够由计算机读取的任何其他介质，在此不做限定。
[0203]
存储器1303用于存储执行本技术实施例的计算机程序，并由处理器1301来控制执行。处理器1301用于执行存储器1303中存储的计算机程序，以实现前述方法实施例所示的步骤。
[0204]
其中，电子设备包括但不限于：服务器、云计算中心设备等。
[0205]
本技术实施例提供了一种计算机可读存储介质，该计算机可读存储介质上存储有计算机程序，计算机程序被处理器执行时可实现前述方法实施例的步骤及相应内容。
[0206]
本技术实施例还提供了一种计算机程序产品，包括计算机程序，计算机程序被处
理器执行时可实现前述方法实施例的步骤及相应内容。
[0207]
可以理解的是，在本技术的具体实施方式中，涉及到的虚拟对象的当前位置等任何与对象相关的数据，当本技术以上实施例运用到具体产品或技术中时，需要获得对象许可或者同意，且相关数据的收集、使用和处理需要遵守相关国家和地区的相关法律法规和标准。
[0208]
本技术领域技术人员可以理解，除非特意声明，这里使用的单数形式“一”、“一个”、“所述”和“该”也可包括复数形式。本技术实施例所使用的术语“包括”以及“包含”是指相应特征可以实现为所呈现的特征、信息、数据、步骤、操作，但不排除实现为本技术领域所支持其他特征、信息、数据、步骤、操作等。
[0209]
本技术的说明书和权利要求书及上述附图中的术语“第一”、“第二”、“第三”、“第四”、“1”、“2”等(如果存在)是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。应该理解这样使用的数据在适当情况下可以互换，以便这里描述的本技术的实施例能够以除图示或文字描述以外的顺序实施。
[0210]
应该理解的是，虽然本技术实施例的流程图中通过箭头指示各个操作步骤，但是这些步骤的实施顺序并不受限于箭头所指示的顺序。除非本文中有明确的说明，否则在本技术实施例的一些实施场景中，各流程图中的实施步骤可以按照需求以其他的顺序执行。此外，各流程图中的部分或全部步骤基于实际的实施场景，可以包括多个子步骤或者多个阶段。这些子步骤或者阶段中的部分或全部可以在同一时刻被执行，这些子步骤或者阶段中的每个子步骤或者阶段也可以分别在不同的时刻被执行。在执行时刻不同的场景下，这些子步骤或者阶段的执行顺序可以根据需求灵活配置，本技术实施例对此不限制。
[0211]
以上所述仅是本技术部分实施场景的可选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本技术的方案技术构思的前提下，采用基于本技术技术思想的其他类似实施手段，同样属于本技术实施例的保护范畴。