场景数据的处理方法、虚拟资源的投放方法及装置与流程

1.本技术涉及计算机技术领域，特别涉及一种场景数据的处理方法、装置、计算机设备及存储介质。


背景技术：

2.随着计算机技术的发展和终端功能的多样化，在终端上能够进行的游戏种类越来越多。在游戏对局中，经常需要对游戏地图的场景数据进行处理，以实现虚拟资源的局内投放或者虚拟对象的局内刷新，其中，虚拟资源如虚拟宝箱、虚拟物资、虚拟道具、虚拟物品等，虚拟对象如陪玩ai(artificial intelligence，人工智能)、npc(non-player character，非玩家角色)、野怪等游戏机器人。
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.第三确定模块，用于对所述场景导航数据中的每个网格，基于所述网格所属的区域，确定所述网格的区域参数，所述区域参数用于指示所述虚拟对象在所述虚拟场景中的对应网格活动的通达度。
34.在一种可能实施方式中，所述第三确定模块包括：
35.第三确定单元，用于在所述网格位于所述第一目标区域之外的情况下，将所述网格的区域参数确定为第一数值；
36.所述第三确定单元，还用于在所述网格位于所述第一目标区域的情况下，将所述网格的区域参数确定为第二数值，其中，区域参数为第二数值对应的通达度大于第一数值
对应的通达度。
37.在一种可能实施方式中，所述第三确定单元还用于：
38.对所述第一目标区域中包含的多个第二候选区域，按照包含的网格数量从大到小的顺序进行排序，每个第二候选区域为所述虚拟对象从对应根节点出发所能够到达且能够返回的双向连通区域；
39.对所述第一目标区域中的每个网格，将所述网格的区域参数确定为所述网格所属的第二候选区域在所述排序中的序号。
40.在一种可能实施方式中，所述装置还包括：
41.投放模块，用于响应于对所述虚拟场景中虚拟资源的投放请求，将所述虚拟资源投放至所述虚拟场景中的所述第二目标区域。
42.在一种可能实施方式中，所述装置还包括：
43.第四确定模块，用于响应于对所述虚拟场景中虚拟对象的路径规划请求，确定所述路径规划请求的起点网格和终点网格；
44.第五确定模块，用于在所述起点网格和所述终点网格位于同一双向连通区域，或者所述终点网格位于所述第二目标区域时，确定所述虚拟对象从所述起点网格到所述终点网格的移动合法。
45.一方面，提供了一种虚拟资源的投放装置，所述装置包括：
46.获取模块，用于响应于虚拟资源的投放请求，获取虚拟场景的场景导航数据，所述场景导航数据用于指示所述虚拟场景中可供虚拟对象移动的空间；
47.所述获取模块，还用于获取基于所述场景导航数据确定得到的第二目标区域，所述第二目标区域用于指示所述虚拟场景中所述虚拟对象能够到达且能够返回的双向连通区域；
48.投放模块，用于向所述虚拟场景中位于所述第二目标区域的目标位置投放所述虚拟资源。
49.一方面，提供了一种计算机设备，该计算机设备包括一个或多个处理器和一个或多个存储器，该一个或多个存储器中存储有至少一条计算机程序，该至少一条计算机程序由该一个或多个处理器加载并执行以实现如上述任一种可能实现方式的场景数据的处理方法或虚拟资源的投放方法。
50.一方面，提供了一种存储介质，该存储介质中存储有至少一条计算机程序，该至少一条计算机程序由处理器加载并执行以实现如上述任一种可能实现方式的场景数据的处理方法或虚拟资源的投放方法。
51.一方面，提供一种计算机程序产品或计算机程序，所述计算机程序产品或所述计算机程序包括一条或多条程序代码，所述一条或多条程序代码存储在计算机可读存储介质中。计算机设备的一个或多个处理器能够从计算机可读存储介质中读取所述一条或多条程序代码，所述一个或多个处理器执行所述一条或多条程序代码，使得计算机设备能够执行上述任一种可能实施方式的场景数据的处理方法或虚拟资源的投放方法。
52.本技术实施例提供的技术方案带来的有益效果至少包括：
53.通过对虚拟场景的场景导航数据进行后处理，先从虚拟场景中划分出虚拟对象能够到达的第一目标区域，以粗略排除掉一些虚拟对象完全无法行走的孤立区域，接着，在第
一目标区域中划分出虚拟对象能够到达且能够返回的第二目标区域，以精细排除掉一些虚拟对象移动过去之后无法返回的区域，这样能够保证后处理得到的第二目标区域具有很高的通达度，通过第二目标区域来指导对虚拟场景中虚拟资源的投放、虚拟对象的刷新以及虚拟对象的路径规划中各类下游业务需求，能够避免虚拟资源或虚拟对象出现到一些玩家无法到达的区域，并且无需进行人工布点，能够节约场景数据处理的人力成本、提高数据处理的准确性。
附图说明
54.为了更清楚地说明本技术实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本技术的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还能够根据这些附图获得其他的附图。
55.图1是本技术实施例提供的一种场景数据的处理方法的实施环境示意图；
56.图2是本技术实施例提供的一种场景数据的处理方法的流程图；
57.图3是本技术实施例提供的一种场景数据的处理方法的流程图；
58.图4是本技术实施例提供的一种navmesh导航网格数据的后处理方法的流程图；
59.图5是本技术实施例提供的一种原始navmesh数据的示意图；
60.图6是本技术实施例提供的一种去除不可达区域后的navmesh数据的示意图；
61.图7是本技术实施例提供的一种navmesh数据中标记为1的poly的示意图；
62.图8是本技术实施例提供的一种navmesh数据中标记大于1的poly的示意图；
63.图9是本技术实施例通过的一种虚拟资源的投放方法的流程图；
64.图10是本技术实施例通过的一种虚拟对象的路径规划方法的流程图；
65.图11是本技术实施例提供的一种场景数据的处理装置的结构示意图；
66.图12是本技术实施例通过的一种虚拟资源的投放装置的结构示意图；
67.图13是本技术实施例提供的一种计算机设备的结构示意图；
68.图14是本技术实施例提供的一种计算机设备的结构示意图。
具体实施方式
69.为使本技术的目的、技术方案和优点更加清楚，下面将结合附图对本技术实施方式作进一步地详细描述。
70.本技术中术语“第一”“第二”等字样用于对作用和功能基本相同的相同项或相似项进行区分，应理解，“第一”、“第二”、“第n”之间不具有逻辑或时序上的依赖关系，也不对数量和执行顺序进行限定。
71.本技术中术语“至少一个”是指一个或多个，“多个”的含义是指两个或两个以上，例如，多个第一位置是指两个或两个以上的第一位置。
72.本技术中术语“包括a或b中至少一项”涉及如下几种情况：仅包括a，仅包括b，以及包括a和b两者。
73.本技术中涉及到的用户相关的信息(包括但不限于用户的设备信息、资料信息、行为信息等)、数据(包括但不限于用于分析的数据、存储的数据、展示的数据等)以及信号，当
以本技术实施例的方法运用到具体产品或技术中时，均为经过用户许可、同意、授权或者经过各方充分授权的，且相关信息、数据以及信号的收集、使用和处理需要遵守相关国家和地区的相关法律法规和标准。例如，本技术中涉及到的用户所玩游戏的场景导航数据都是在充分授权的情况下获取的。
74.虚拟场景：是应用程序在终端上运行时显示(或提供)的虚拟环境。该虚拟场景可以是对真实世界的仿真环境，也可以是半仿真半虚构的虚拟环境，还可以是纯虚构的虚拟环境。虚拟场景可以是二维虚拟场景、2.5维虚拟场景或者三维虚拟场景中的任意一种，本技术实施例对虚拟场景的维度不加以限定。例如，虚拟场景可以包括天空、陆地、海洋等，该陆地可以包括沙漠、城市等环境元素，用户可以控制虚拟对象在该虚拟场景中进行移动。可选地，该虚拟场景还可以用于至少两个虚拟对象之间的虚拟场景对抗，在该虚拟场景中具有可供至少两个虚拟对象使用的虚拟资源。
75.虚拟对象：是指在虚拟场景中的可活动对象。该可活动对象可以是虚拟人物、虚拟动物、动漫人物等，比如：在虚拟场景中显示的人物、动物、植物、油桶、墙壁、石块等。该虚拟对象可以是该虚拟场景中的一个虚拟的用于代表用户的虚拟形象。虚拟场景中可以包括多个虚拟对象，每个虚拟对象在虚拟场景中具有自身的形状和体积，占据虚拟场景中的一部分空间。可选地，当虚拟场景为三维虚拟场景时，可选地，虚拟对象可以是一个三维立体模型，该三维立体模型可以是基于三维人体骨骼技术构建的三维角色，同一个虚拟对象可以通过穿戴不同的皮肤来展示出不同的外在形象。在一些实施例中，虚拟对象也可以采用2.5维或2维模型来实现，本技术实施例对此不加以限定。
76.可选地，该虚拟对象可以是通过客户端上的操作进行控制的玩家角色，也还可以是设置在虚拟场景中能够进行互动的非玩家角色(non-player character，npc)、中立虚拟对象(如能够提供增益buff的野怪)，还可以是设置在虚拟场景中的游戏机器人(如陪玩ai机器人)。示意性地，该虚拟对象是在虚拟场景中进行竞技的虚拟人物。可选地，该虚拟场景中参与互动的虚拟对象的数量可以是预先设置的，也可以是根据加入互动的客户端的数量动态确定的。
77.虚拟资源：指玩家在游戏对局中能够控制虚拟对象进行拾取或绑定的一类竞技资源，可选地，有些虚拟资源会在游戏开局时就已经被预先投放到虚拟场景中，或者，有些虚拟资源会在游戏对局进行中按照预设的逻辑被投放到虚拟场景中，其中，虚拟资源的投放逻辑包括但不限于：基于时间的定时投放逻辑(例如开局后5分钟投放)、基于触发条件的投放逻辑(例如击败第一个敌方虚拟对象之后30秒投放)等，本技术实施例不对投放逻辑进行具体限定，在虚拟资源被投放到虚拟场景中之后，玩家能够控制虚拟对象在虚拟场景中搜寻并拾取虚拟资源。可选地，虚拟资源包括但不限于：虚拟宝箱、虚拟物资、虚拟物品、虚拟道具等，本技术实施例不对虚拟资源的资源类型进行具体限定。
78.射击类游戏(shooter game，stg)：是指虚拟对象使用热兵器类虚拟道具进行远程攻击的一类游戏，射击类游戏是动作类游戏的一种，带有很明显的动作类游戏特点。可选地，射击类游戏包括但不限于第一人称射击游戏、第三人称射击游戏、俯视射击游戏、平视射击游戏、平台射击游戏、卷轴射击游戏、键鼠射击游戏、射击场游戏等，本技术实施例不对射击类游戏的类型进行具体限定。
79.第一人称射击(first-person shooting，fps)游戏：第一人称射击游戏是指用户
能够以第一人称视角进行的射击游戏，游戏中的虚拟场景的画面是以终端操控的虚拟对象的视角对虚拟场景进行观察的画面。在游戏中，至少两个虚拟对象在虚拟场景中进行单局对抗模式，虚拟对象通过躲避其他虚拟对象发起的伤害和虚拟场景中存在的危险(比如，沼泽地等)来达到在虚拟场景中存活的目的，当虚拟对象在虚拟场景中的生命值为零时，虚拟对象在虚拟场景中的生命结束，最后存活在虚拟场景中的虚拟对象是获胜方。可选地，上述对抗以第一个终端加入对局的时刻作为开始时刻，以最后一个终端退出对局的时刻作为结束时刻，每个终端可以控制虚拟场景中的一个或多个虚拟对象。可选地，对抗的竞技模式可以包括单人对抗模式、双人小组对抗模式或者多人大组对抗模式等，本技术实施例对竞技模式不进行具体限定。
80.以射击类游戏为例，用户能够控制虚拟对象在该虚拟场景的天空中自由下落、滑翔或者打开降落伞进行下落等，在陆地上中跑动、跳动、爬行、弯腰前行等，也能够控制虚拟对象在海洋中游泳、漂浮或者下潜等，当然，用户也能够控制虚拟对象乘坐虚拟载具在该虚拟场景中进行移动，例如，该虚拟载具包括虚拟汽车、虚拟飞行器、虚拟游艇等，在此仅以上述场景进行举例说明，本技术实施例对此不作具体限定。用户也能够控制虚拟对象通过虚拟道具与其他虚拟对象进行互动，例如，该虚拟道具包括：经过投掷后才能生效的投掷类道具，发射某一发射物后才能生效的射击类道具，以及用于近距离对抗的互动道具。用户还能够控制虚拟对象在虚拟场景中搜寻并拾取虚拟资源，例如，该虚拟资源包括：虚拟宝箱、虚拟物资、虚拟物品、虚拟道具等。用户还能够控制虚拟对象与虚拟场景中的游戏机器人进行互动，例如，控制虚拟对象与陪玩ai一起进行游戏，或者控制虚拟对象击败野怪等中立虚拟对象以获取到某种增益效果。
81.以下，对本技术涉及的系统架构进行介绍。
82.图1是本技术实施例提供的一种场景数据的处理方法的实施环境示意图。参见图1，该实施环境包括：第一终端120、服务器140和第二终端160。
83.第一终端120安装和运行有支持虚拟场景的应用程序。可选地，该应用程序包括：fps游戏、第三人称射击游戏、moba(multiplayer online battle arena，多人在线战术竞技)游戏、虚拟现实应用程序、三维地图程序或者多人器械类生存游戏中的任意一种。在一些实施例中，第一终端120是第一用户使用的终端，当第一终端120运行该应用程序时，第一终端120的屏幕上显示应用程序的用户界面，并基于第一用户在用户界面中的开局操作，在应用程序中加载并显示虚拟场景，第一用户使用第一终端120操作位于虚拟场景中的第一虚拟对象进行活动，该活动包括但不限于：调整身体姿态、爬行、步行、奔跑、骑行、跳跃、驾驶、拾取、射击、攻击、投掷、对抗中的至少一种。示意性的，第一虚拟对象是第一虚拟人物，比如仿真人物角色或动漫人物角色。
84.第一终端120以及第二终端160通过无线网络或有线网络与服务器140进行直接或间接地通信连接。
85.服务器140包括一台服务器、多台服务器、云计算平台或者虚拟化中心中的至少一种。服务器140用于为支持虚拟场景的应用程序提供后台服务。可选地，服务器140承担主要计算工作，第一终端120和第二终端160承担次要计算工作；或者，服务器140承担次要计算工作，第一终端120和第二终端160承担主要计算工作；或者，服务器140、第一终端120和第二终端160三者之间采用分布式计算架构进行协同计算。
86.可选地，服务器140是独立的物理服务器，或者是多个物理服务器构成的服务器集群或者分布式系统，或者是提供云服务、云数据库、云计算、云函数、云存储、网络服务、云通信、中间件服务、域名服务、安全服务、内容分发网络(content delivery network，cdn)以及大数据和人工智能平台等基础云计算服务的云服务器。
87.第二终端160安装和运行有支持虚拟场景的应用程序。可选地，该应用程序包括fps游戏、第三人称射击游戏、moba游戏、虚拟现实应用程序、三维地图程序或者多人器械类生存游戏中的任意一种。在一些实施例中，第二终端160是第二用户使用的终端，当第二终端160运行该应用程序时，第二终端160的屏幕上显示应用程序的用户界面，并基于第二用户在用户界面中的开局操作，在应用程序中加载并显示虚拟场景，第二用户使用第二终端160操作位于虚拟场景中的第二虚拟对象进行活动，该活动包括但不限于：调整身体姿态、爬行、步行、奔跑、骑行、跳跃、驾驶、拾取、射击、攻击、投掷、对抗中的至少一种。示意性的，第二虚拟对象是第二虚拟人物，比如仿真人物角色或动漫人物角色。
88.可选地，第一终端120控制的第一虚拟对象和第二终端160控制的第二虚拟对象处于同一虚拟场景中，此时第一虚拟对象能够在虚拟场景中与第二虚拟对象进行互动。
89.示意性地，上述第一虚拟对象以及第二虚拟对象为敌对关系，例如，第一虚拟对象与第二虚拟对象属于不同的阵营，敌对关系的虚拟对象之间，能够在陆地上进行对抗方式的互动，比如互相扔出投掷类道具。在另一些实施例中，第一虚拟对象以及第二虚拟对象为队友关系，例如，第一虚拟人物和第二虚拟人物属于同一个阵营、同一个队伍、具有好友关系或具有临时性的通讯权限。
90.可选地，第一终端120和第二终端160上安装的应用程序是相同的，或两个终端上安装的应用程序是不同操作系统平台的同一类型应用程序。第一终端120和第二终端160均泛指多个终端中的一个，本技术实施例仅以第一终端120和第二终端160来举例说明。
91.第一终端120和第二终端160的设备类型相同或不同，该设备类型包括：智能手机、平板电脑、智能音箱、智能手表、智能掌机、便携式游戏设备、车载终端、膝上型便携计算机和台式计算机中的至少一种，但并不局限于此。例如，第一终端120和第二终端160均是智能手机，或者其他手持便携式游戏设备。以下实施例，以终端包括智能手机来举例说明。
92.本领域技术人员能够知晓，上述终端的数量为更多或更少。比如上述终端仅为一个，或者上述终端为几十个或几百个，或者更多数量。本技术实施例对终端的数量和设备类型不加以限定。
93.以下，对本技术实施例涉及的术语进行说明。
94.游戏引擎：指一些已编写好的可编辑电脑游戏系统或者一些交互式实时图像应用程序的核心组件。这些系统为游戏设计者提供各种编写游戏所需的各种工具，其目的在于让游戏设计者能容易和快速地做出游戏程式而不用由零开始。游戏引擎包含以下系统：渲染引擎(即“渲染器”，含二维图像引擎和三维图像引擎)、物理引擎、碰撞检测系统、音效、脚本引擎、电脑动画、人工智能、网络引擎以及场景管理。
95.虚幻引擎(unreal engine，ue)：一种由游戏公司epic开发的业界领先的游戏引擎，是一个面向下一代游戏机和directx 9个人电脑的完整的游戏开发平台，提供了游戏开发者需要的大量的核心技术、数据生成工具和基础支持。
96.在虚幻引擎中，提供有对游戏ai机器人的寻路功能(也称为导航功能)，寻路是游
戏ai的一个基础组成部分，寻路的基本目标是给定一个起始点和目标点，生成一条个体可以到达的路径。通常的寻路方法包括：基于路点(pathnode)，基于导航网格(navigation mesh，简称navmesh)，基于势力场(potential field)，本技术实施例涉及到基于navmesh实现寻路。
97.recastnavigation：一款非常强大的寻路系统，被广泛的应用于各大游戏引擎(例如unity、ue4等)中，是一种业内较为流行的游戏内基于虚拟场景实现导航的解决方案。换一种表述，recastnavigation是一个导航寻路工具集，使用邻接的凸多边形集合描述一个3d虚拟场景，其中，a*寻路算法使3d虚拟场景的可达性得到保证。recastnavigation系统具有如下功能：能表达一个3d虚拟场景；能接近精确的赋予游戏对象3维坐标属性；能判断3d场景表面2个点的可达性；能动态改变3d场景地形。
98.导航网格(navmesh)：铺满游戏地图上可行走空间的一种数据结构。
99.poly：一片polygon凸多边形，是导航网格navmesh的组成单位，也称为是recastnavigation系统的基本寻路单元。
100.a*寻路算法：是一种用于静态位置高效搜索算法，是在平面中两点之间去寻找一条可以到达的最短路径算法。
101.广度优先搜索(breadth first search，bfs)：也称为宽度优先搜索，是图论中的一种经典算法。
102.强连通分量(strongly connected components，scc)：图论中的一种概念，针对图数据中的任意两个顶点vi和vj，如果存在一条从vi到vj的有向路径，同时还存在一条从vj到vi的有向路径，则称两个顶点vi和vj强连通(strongly connected)。进一步的，如果有向图g的每两个顶点都强连通，称g是一个强连通图。而针对属于非强连通图的有向图，在该有向图中的极大强连通子图，称为强连通分量。
103.弱连通图：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。
104.环境查询系统(environment query system，eqs)：虚幻引擎中的一种技术，是虚幻4引擎中提供给游戏ai机器人，用于收集游戏当前的环境数据，进行筛选分析，寻找到最符合条件要求的结果。例如，在某一游戏开局时，游戏ai如虚拟怪物会自动在随机位置上面生成(称为野怪刷新、野怪投放)，一旦玩家控制的虚拟对象进入到虚拟怪物的搜索区域，虚拟怪物就会追过来，eqs的作用就是提供给虚拟怪物使用、让虚拟怪物找到一个合适的目标点并向前移动。
105.在游戏开发中，经常需要存在将虚拟资源投放到虚拟场景中的某些位置，或者要投放一些虚拟对象到虚拟场景中的某些位置的情况，其中，虚拟资源如虚拟宝箱、虚拟物资、虚拟道具、虚拟物品等，虚拟对象如陪玩ai(artificial intelligence，人工智能)、npc(non-player character，非玩家角色)、野怪等游戏机器人。
106.在上述虚拟资源或虚拟对象的投放过程中，针对一些结构简单、规模较小的虚拟场景以及较为简单的虚拟对象移动方式，传统的物理检测、人工布点的方式能够取得一定效果，物理检测是指检测虚拟对象投放到虚拟场景中会碰到地面还是山体等，从而判断是否向当前位置投放，人工布点则是指人工在虚拟场景中预设多个备选点，从这些预设的备选点中随机选取部分备选点来投放虚拟资源或刷新虚拟对象。
107.然而，在涉及到攀爬、滑索、飞行等较为复杂的虚拟对象移动方式的情况下，物理检测的方式也不能带来更好的和准确性；此外，针对一些面积巨大、地形错综复杂的虚拟场景，人工布点的方式会带来巨大的人力成本；此外，不管是人工布点还是物理检测的方式，经常会出现虚拟资源被投放到一些玩家无法到达的位置(如高台上、缝隙中)，或者虚拟对象刷新在一些玩家无法到达的位置(如高台上、缝隙中)导致无法与玩家进行互动的各类情况，因此人力成本高、准确性差，严重影响玩家的游戏体验。
108.有鉴于此，本技术实施例结合图论的相关概念，将bfs算法和tarjan scc算法结合在一起，提出了一种针对navmesh导航网格的后处理方法即场景数据的处理方法，能够针对navmesh导航网格上的区域按照可达性(即通达度)进行划分，能够从虚拟场景中确定单向可达的第一目标区域，以及双向可达的第二目标区域，在拥有了针对每个poly网格按照可达性划分的区域数据(即区域参数)之后，能够很容易地从虚拟场景中识别出玩家所控制的虚拟对象或者游戏机器人无法到达的地方，从而能够合理地规划虚拟资源的投放位置，还能够合理规划游戏机器人的行走路径，能够体大改善玩家的游戏体验。
109.以下，对本技术实施例的场景数据的处理方法的整体流程进行简单介绍。
110.图2是本技术实施例提供的一种场景数据的处理方法的流程图。参见图2，该实施例由计算机设备执行，以计算机设备为服务器为例进行说明，该实施例包括：
111.201、服务器获取虚拟场景的场景导航数据，该场景导航数据用于指示该虚拟场景中可供虚拟对象移动的空间。
112.服务器是指用于向支持虚拟场景的应用程序提供后台服务的计算机设备，包括一台服务器、多台服务器、云计算平台或者虚拟化中心中的至少一种，本技术实施例以游戏服务器为例进行说明。
113.本技术实施例涉及的虚拟场景，是指应用程序在终端上运行时所提供的虚拟环境，包括对真实世界的仿真环境、半仿真半虚构的虚拟环境或者纯虚构的虚拟环境等，此外，虚拟场景可以是二维虚拟场景、2.5维虚拟场景或者三维虚拟场景等，本技术实施例对此不进行具体限定。示意性地，虚拟场景包括天空、陆地、山丘、悬崖、峡谷、海洋、河流、湖泊、城市、沙漠等环境元素，受玩家控制的虚拟对象以及受机器提供的行为逻辑(可以是预设逻辑或者ai行为模型)控制的虚拟对象均能够在虚拟场景中进行移动等。
114.本技术实施例涉及的虚拟对象，是指在虚拟场景中具有自身的形状和体积、占据一部分空间的可活动对象，可选地，虚拟对象包括玩家通过客户端上的操作进行控制的玩家角色、服务器设置在虚拟场景中的npc、服务器投放到虚拟环境中的中立虚拟对象(如虚拟怪物即野怪)或者服务器投放到虚拟场景中的游戏机器人(如陪玩ai机器人)，本技术实施例对虚拟对象的类型不进行具体限定。示意性地，虚拟场景为虚拟场景为三维虚拟场景时，虚拟对象是一个三维立体模型，该三维立体模型是基于三维人体骨骼技术构建的三维角色。
115.本技术实施例涉及的场景导航数据，是指基于游戏引擎对虚拟场景进行分析和处理所得到的用于进行场景内导航或寻路的数据，以游戏引擎为ue引擎或unity引擎为例，游戏引擎能够针对搭建完毕的虚拟场景分析得到navmesh导航网格数据，这一navmesh导航网络数据就是本技术实施例所涉及的场景导航数据，需要说明的是，在不同的游戏引擎中场景导航数据可具有不同的名称或数据结构，本技术实施例对此不进行具体限定。
116.在一些实施例中，服务器针对任一游戏应用所支持的虚拟场景，利用游戏引擎中对虚拟场景的原始场景数据进行分析和处理，得到该虚拟场景的场景导航数据。
117.示意性地，以ue引擎或unity引擎为例，引擎能够对每个虚拟场景中的虚拟物体(如环境、建筑物、障碍物、道具等)进行标记和路径烘培，产生虚拟场景的mesh数据，接着，利用引擎提供的recastnavigation导航寻路工具集或基于recastnavigation实现的navmesh导航寻路系统，对虚拟场景的mesh数据进行如下处理：a)体素化(voxelization)，即从虚拟场景中标记的虚拟物体的源几何体(如山体、悬崖等的几何体模型)构造一个实心高度场，用来表示虚拟场景中不可行走的空间，通常一些不可行走的表面在这个阶段会被剔除掉(比如坡度过大的面)，其中体素是指空间中的一个有大小的点；b)生成地区(region generation)，即将实心高度场的上表面中连续的区间合并为地区，这一阶段的目标是进一步定义源几何体表面上哪部分是可以行走的，以及将这些可行走的部分划分成连续的地区；c)生成轮廓(contour generation)，即检测地区的轮廓，并构造简单多边形，比如从地区生成非常精细的多边形，再将这些精细多边形进行简化得到简单多边形，简单多边形代表了可行走的表面，这是从体素空间转换回向量空间的第一步处理；d)生成多边形网格(convex polygon generation)，即将轮廓构成的简单多边形分割成一个个凸多边形网格(即poly)，poly代表了可以行走的表面；e)生成高度细节(height detail generation)，即将凸多边形网格poly进行三角化，得到高度细节，例如使用delaunay三角化算法对poly进行三角化，以在poly内部或边缘添加顶点，来确保网格与源几何体表面等价，从而增加高度的细节信息。在经过上述a)至e)的处理后，相当于从虚拟场景烘焙得到的mesh数据，进一步分析得到了由一系列的凸多边形网格poly构成的navmesh导航网格数据，这一navmesh导航网格数据就是上述步骤201涉及的场景导航数据。
118.202、服务器基于该场景导航数据，确定该虚拟场景中的第一目标区域，该第一目标区域用于指示该虚拟场景中该虚拟对象能够到达的单向连通区域。
119.其中，第一目标区域用于指示虚拟场景能够到达的单向连通区域，可选地，第一目标区域是虚拟场景的极大弱连通子图，或者，第一目标区域是虚拟场景的多个弱连通子图的并集，本技术实施例对此不进行具体限定。
120.在一些实施例中，由于场景导航数据是由多个网格所构成的，将每个网格都视为一个图数据中的一个节点，那么根据虚拟对象是否能够从一个网格a移动到达另一个网格b，能够判断在图数据中是否存在网格a对应的节点与网格b对应的节点之间的有向边，在这一基础上，各个网格构成的场景导航数据相当于一张有向图，而每个网格则相当于有向图中的一个顶点。此时，基于场景导航数据确定第一目标区域的过程，相当于从该场景导航数据所对应的有向图中，忽略每条有向边的连接方向，即将有向图的所有的有向边替换为无向边，能够得到有向图的基图。接着，遍历该有向图的基图中的每个顶点(即每个网格)，针对未访问过的每个顶点，均基于广度优先搜索算法，查找到从该顶点出发所能够到达的所有顶点，该顶点和查找到的所有顶点能够构成该有向图的基图中的一个弱连通子图，重复执行上述操作直到每个顶点都被访问过时停止遍历，然后能够得到该有向图的基图中的所有弱连通子图，从各个弱连通子图中能够筛选得到该第一目标区域。可选地，将这些弱连通子图中包含顶点数量最多的弱连通子图作为该第一目标区域，或者，将这些弱连通子图中包含顶点数量最多的n(n≥1)个弱连通子图作为该第一目标区域，本技术实施例不对第一
目标区域的筛选逻辑进行具体限定。
121.示意性地，该场景导航数据是navmesh导航网格数据，navmesh导航网格数据是由多个凸多边形网格poly构成的，在遍历过程中，先查找到首个未访问过的poly，接着按照广度优先搜索算法，查找到与该poly直接或者间接连接的所有poly，此时能够得到包含该poly和查找到的所有poly的一个poly集合，这个poly集合代表了一个弱连通子图，在对navmesh导航网格数据的每个poly都遍历完毕后，能够得到多个poly集合，从该多个poly集合中能够筛选出一个或多个poly集合，将这一个或多个poly集合所构成的区域确定为第一目标区域，比如，仅将包含poly数量最大的poly集合所构成的区域确定为第一目标区域。
122.203、服务器从该第一目标区域中确定第二目标区域，该第二目标区域用于指示该虚拟场景中该虚拟对象能够到达且能够返回的双向连通区域。
123.在一些实施例中，由于步骤202确定出的第一目标区域，忽略了有向图中有向边的连接方向，因此相当于第一目标区域只能排除掉虚拟场景中的虚拟对象不可到达的孤立区域(即完全不相连的网格)，然而第一目标区域仍然存在单向连通的问题，即有可能虚拟对象在第一目标区域内进行活动时，到达了某个网格之后回不到原先的网格了，因此，需要从第一目标区域中再确定出一个第二目标区域，以保证从第二目标区域中每个网格出发均能够返回到本网格。
124.在一些实施例中，由于第一目标区域本身就是虚拟场景的一个弱连通子图，因此代表着在不考虑方向的情况下，第一目标区域中的每个网格都必然与该第一目标区域中的另外的任何一个网格能够直接或间接的相连，因此，可以基于tarjan scc算法，针对第一目标区域(即筛选到的弱连通子图)进行处理，以找到该第一目标区域中包含的至少一个强连通子图。其中，tarjan scc算法是基于对图深度优先搜索的算法，在本技术实施例中，可将tarjan scc算法改为基于对图广度优先搜索的算法，而第一目标区域中的每个强连通子图对应于搜索树中的一颗子树，在搜索时，将当前搜索树中未处理的节点加入到一个堆栈(stack)中，即push未处理节点入栈，从栈顶的节点开始回溯，回溯时判断栈顶到栈中的节点是否为一个强连通子图，在满足强连通子图的判定条件时，能够确定得到一个强连通子图，然后将栈顶的节点退栈，对新的位于栈顶的节点继续回溯。其中，强连通子图的判定条件将在下一实施例中进行详细介绍，这里不再赘述。
125.在获取到第一目标区域的所有强连通子图之后，可以从这些强连通子图中筛选得到第二目标区域，例如，将这些强连通子图中包含顶点数量最多的强连通子图作为该第二目标区域，或者，将这些强连通子图中包含顶点数量最多的m(m≥1)个强连通子图作为该第二目标区域，本技术实施例不对第二目标区域的筛选逻辑进行具体限定。
126.示意性地，在从navmesh导航网格数据中，确定出第一目标区域对应的poly集合之后，对该poly集合，按照tarjan scc算法，查找到该poly集合的所有强连通子图，其中，每个强连通子图能够用一个poly子集来表示，接着，将所有的poly子集中筛选出一个或多个poly子集，将这一个或多个poly子集所构成的区域确定为第二目标区域，比如，仅将包含poly数量最大的poly子集所构成的区域确定为第二目标区域。
127.需要说明的是，上述步骤201-203相当于一个对场景导航数据的后处理过程，后处理结果是划分出了虚拟场景中的第二目标区域，相当于确定出了虚拟场景中的一个极大强连通子图(即强连通分量)，进一步的，服务器能够基于该第二目标区域来指导虚拟场景中
虚拟资源的投放、虚拟对象的刷新以及虚拟对象的路径规划(或称为导航、寻路)，第二目标区域可以称为是navmesh导航网格数据的主区域，通常情况下玩家控制的虚拟对象以及机器控制的游戏机器人的绝大多数活动都位于主区域中，因此，只需要保存第二目标区域的相关数据，就能够提升后续需要访问场景导航数据的各项业务的处理精度。比如，服务器可以控制仅将虚拟资源或游戏机器人投放到第二目标区域中，避免将虚拟资源或游戏机器人投放到一些玩家控制的虚拟对象无法到达的区域，又比如，在对游戏机器人进行路径规划时，尽量控制游戏机器人在第二目标区域中进行移动，同样能够保证游戏机器人能够与玩家控制的虚拟对象进行有效互动。
128.上述所有可选技术方案，能够采用任意结合形成本公开的可选实施例，在此不再一一赘述。
129.本技术实施例提供的方法，通过对虚拟场景的场景导航数据进行后处理，先从虚拟场景中划分出虚拟对象能够到达的第一目标区域，以粗略排除掉一些虚拟对象完全无法行走的孤立区域，接着，在第一目标区域中划分出虚拟对象能够到达且能够返回的第二目标区域，以精细排除掉一些虚拟对象移动过去之后无法返回的区域，这样能够保证后处理得到的第二目标区域具有很高的通达度，通过第二目标区域来指导对虚拟场景中虚拟资源的投放、虚拟对象的刷新以及虚拟对象的路径规划中各类下游业务需求，能够避免虚拟资源或虚拟对象出现到一些玩家无法到达的区域，并且无需进行人工布点，能够节约场景数据处理的人力成本、提高数据处理的准确性。
130.在上一实施例中，简单介绍了针对场景数据的处理流程，而在本技术实施例中，将详细介绍第一目标区域和第二目标区域是如何进行划分得到的，下面进行说明。
131.图3是本技术实施例提供的一种场景数据的处理方法的流程图，如图3所示，该实施例由计算机设备执行，以计算机设备为服务器为例进行说明，该实施例包括：
132.301、服务器获取虚拟场景的场景导航数据，该场景导航数据用于指示该虚拟场景中可供虚拟对象移动的空间。
133.上述步骤301与上述步骤201类似，这里不做赘述。
134.302、服务器基于该场景导航数据，确定该虚拟场景中的多个第一候选区域，每个第一候选区域为该虚拟对象从对应根节点出发所能够到达的单向连通区域。
135.在一些实施例中，由于场景导航数据是由多个网格所构成的，将每个网格都视为一个图数据中的一个节点，那么根据虚拟对象是否能够从一个网格a移动到达另一个网格b，能够判断在图数据中是否存在网格a对应的节点与网格b对应的节点之间的有向边，在这一基础上，各个网格构成的场景导航数据相当于一张有向图，而每个网格则相当于有向图中的一个顶点。
136.在上述基础上，对该场景导航数据中未访问过的任一网格，以该网格为根节点，可以使用广度优先搜索算法，确定得到从该根节点出发所能够到达的各个网格，将该网格和确定得到的各个网格所形成的区域确定为一个第一候选区域，该第一候选区域相当于一个以根节点为中心出发的能够抵达的所有网格构成的可活动空间，重复执行上述操作，直到该场景导航数据中不存在未访问过的网格，代表已经对该场景导航数据中的所有网格遍历完毕，此时能够得到多个第一候选区域。
137.在一些实施例中，针对该场景导航数据所对应的有向图，忽略有向图中每条有向
边的连接方向，即将有向图的所有的有向边替换为无向边，能够得到有向图的基图。接着，遍历该有向图的基图中的每个网格(即每个顶点)，以未访问过的每个网格作为根节点，均基于广度优先搜索算法，查找到从该根节点出发所能够到达的所有网格，换言之，查找到该有向图的基图中与根节点能够直接或间接相连接的所有顶点，这些包括根节点在内的所有顶点构成的顶点集合代表了该有向图的基图中的一个弱连通子图，也代表了任一虚拟对象中虚拟场景中的根节点出发所能够到达的单向连通区域即一个第一候选区域，接着以下一个未访问过的网格作为根节点重复执行上述操作，直到有向图的基图中不存在未访问过的网格，代表已经对该场景导航数据中的所有网格遍历完毕，也已经对该有向图的基图中的所有顶点遍历完毕，此时，能够得到多个根节点各自对应的多个第一候选区域，这些第一候选区域也计算该有向图的基图中的所有弱连通子图。
138.示意性地，该场景导航数据是navmesh导航网格数据，navmesh导航网格数据是由多个凸多边形网格poly构成的，在预处理阶段，对每个poly建立一个能够唯一标识该poly的索引，例如对每个poly均使用一个整数来唯一标识该poly，这个整数称为对应poly的索引，该索引记作polyref，接着，由于对每个poly，都存在与该poly唯一对应的在虚拟场景中的网格坐标和索引polyref，因此针对navmesh导航网格数据的所有poly，能够构建一张哈希表(称为虚拟场景所有polyref的总索引)，哈希表中对每个poly均使用一个key-value(键值对)结构来进行表示，其中，key为对应poly的索引polyref，value为对应poly在虚拟场景中的网格坐标。通过构建哈希表，能够将后续确定第一目标区域和第二目标区域的操作，转换成对哈希表中部分key-value结构所形成集合的交并补操作，能够优化获取第一目标区域、第二目标区域的速度，提示场景数据的处理效率。例如，使用xorshift64随机数生成算法来对每个poly生成对应的索引polyref，以减少索引polyref的数值规律性，在使用xorshift64算法的情况下能够将整体性能提升2.54倍。
139.接着，在本次用于寻找第一候选区域的遍历过程中，访问上述基于navmesh导航网格数据构建的哈希表中的每个key-value结构，相当于访问每个key-value结构对应的poly，找到首个未访问过的poly作为根节点，按照广度优先搜索算法，从根节点出发遍历所有能够直接或间接连接到的poly，得到一个由根节点和查找到的与根节点直接或者间接连接的所有poly共同构成的poly集合，这个poly集合代表了该有向图的基图中的一个弱连通子图，接着查找下一个未访问过的poly作为根节点，重复执行上述操作，直到哈希表中不存在不存在未访问过的key-value结构，代表对navmesh导航网格数据中的所有poly遍历完毕，同时代表对有向图的基图中的所有顶点都遍历完毕，此时能够得到多个poly集合，每个poly集合代表了有向图的基图中的一个弱连通子图，每个poly集合中各个poly在虚拟场景中所形成的单向连通区域也即是一个第一候选区域。
140.需要说明的是，本次遍历中由于将有向图转换成了有向图的基图，即忽略了有向图中所有的有向边的连接方向，因此即使虚拟对象能够从虚拟场景中的网格poly a以跳跃、移动、行走等方式移动到网格poly b，但无法从poly b返回poly a(例如从山坡上跳跃下来之后无法返回)，但由于连接方向被忽略了，因此poly a和poly b也会在无向图中被视为相互连接从而添加到同一个poly集合中。
141.303、服务器从该多个第一候选区域中，筛选得到第一目标区域，该第一目标区域用于指示该虚拟场景中该虚拟对象能够到达的单向连通区域。
142.在一些实施例中，服务器从各个第一候选区域中筛选得到第一目标区域时，可以将该多个第一候选区域中包含的网格数量最大的第一候选区域确定为该第一目标区域。
143.示意性地，上述过程相当于将虚拟场景的所有弱连通子图中包含顶点数量最多的弱连通子图作为该第一目标区域，例如，在将navmesh导航网格数据的所有poly，按照连通性即通达度划分至多个poly集合之后，将包含poly数量最大的poly集合所构成的区域确定为第一目标区域。
144.在一些实施例中，服务器从各个第一候选区域中筛选得到第一目标区域时，还可以按照包含的网格数量从大到小的顺序，对各个第一候选区域进行排序，将排序位于前n(n≥1)位的n个第一候选区域的并集所指示的区域作为该第一目标区域，换言之，将该多个第一候选区域中包含顶点数量最多的n个第一候选区域的并集所指示的区域作为该第一目标区域。
145.示意性地，上述过程相当于将虚拟场景的所有弱连通子图中包含顶点数量最多的n个弱连通子图的并集作为该第一目标区域，例如，在将navmesh导航网格数据的所有poly，按照连通性即通达度划分至多个poly集合之后，按照包含的poly数量从大到小的顺序，对各个poly集合进行排序，将排序位于前n位的n个poly集合的并集所指示的区域作为该第一目标区域。
146.在上述步骤302-303中，提供了服务器基于该场景导航数据，确定该虚拟场景中的第一目标区域的一种可能实施方式，即将场景导航数据中的所有网格，按照连通性即通达度划分至多个第一候选区域，再从该多个第一候选区域中粗略筛选得到第一目标区域，使得在确定第二目标区域时，仅针对第一目标区域中的各个网格进行精细筛选，而位于第一目标区域之外的各个网格都会被排除掉，不参与后续对第二目标区域的计算，能够节约获取第二目标区域的计算量、提示计算效率。
147.在上述步骤302-303中，通过获取第一目标区域，能够粗略地从navmesh导航网格数据的所有poly中，排除掉一些完全不相连的poly，这些被排除掉的poly可以视为是虚拟场景中的一些孤立的poly，在后续确定第二目标区域时，只需要对第一目标区域内剩余的poly处理单向连通问题，就能够实现对虚拟对象所能够到达且能够返回的poly的精细筛选。
148.304、服务器从该第一目标区域中，确定多个第二候选区域，每个第二候选区域为该虚拟对象从对应根节点出发所能够到达且能够返回的双向连通区域。
149.在一些实施例中，针对上述步骤303中确定的第一目标区域包含的所有poly，按照上述步骤302中描述的方式，以每个poly的索引polyref作为key，以对应poly在虚拟场景中的网格坐标作为value，能够创建每个poly的key-value结构，从而第一目标区域包含的所有poly所对应的所有key-value结构能够构成一张新的哈希表，并且哈希表中所有key-value结构所指示的poly在不考虑方向的情况下一定都是互相连接的(因此这些poly属于同一张弱连通子图)。
150.在一些实施例中，服务器基于该第一目标区域，构建搜索树，该搜索树中的每个节点对应于该第一目标区域中的一个网格，例如，针对上述基于第一目标区域构建的哈希表，构建tarjan scc算法的搜索树，其中，搜索树中的每个节点代表了哈希表中的一个key-value结构所对应的poly。
151.接着，从搜索树中首个未访问过的根节点poly出发，基于深度优先搜索算法或广度优先搜索算法进行搜索，找到当前子树上的最后一个poly，将根节点poly和本次搜索到的当前子树上的各个poly(即未处理的各个节点)入栈，从位于栈顶的poly开始回溯，回溯时通过判断位于栈顶的poly是否满足强连通子图的判定条件，如果满足该判定条件，代表栈顶到栈中的poly构成一个强连通子图(构成一个第二候选区域)，然后将位于栈顶的poly退栈，对退栈后新的位于栈顶的poly判断是否满足该判定条件，以此类推。可选地，如果位于栈顶的poly不满足该判定条件，那么需要查看位于栈顶的poly是否还能搜索到下一个相连的poly(即拓展节点)，如果存在拓展节点poly且该拓展节点poly从未入栈过(即未被访问过)那么将该拓展节点poly入栈，由于栈结构具有后进先出的特性，因此新入栈的拓展节点poly会被存储到栈顶，变成新的位于栈顶的poly，从而判断新的位于栈顶的poly(即拓展节点poly)是否满足该判定条件，或者，如果搜索到的拓展节点poly已经在栈中了，那么需要对栈中位于拓展节点poly之后的poly的追溯值进行更新，从而基于更新后的追溯值再次判断是否符合该判定条件，以此类推，直到搜索树中的所有poly都入栈一次且退栈一次了，此时停止遍历，能够得到第一目标区域中的所有强连通子图即所有第二候选区域。
152.可选地，上述强连通子图的判定条件是指：如果搜索树中位于栈顶的节点(poly)i的时间戳dfn[i]和追溯值low[i]相等，即在位于栈顶的poly i存在dfn[i]＝low[i]的情况下，代表搜索树中poly i和poly i的子树能够构成一个强连通子图，那么将以该poly i为根节点的搜索子树上的各个节点poly所形成的区域确定为一个第二候选区域。其中，poly i的时间戳是指在搜索树中poly i被搜索的次数，poly i的追溯值是指poly i或poly i的子树能够追溯到的最早的栈中节点poly的次序。
[0153]
在执行上述tarjan scc算法对搜索树中的所有poly遍历完毕后，能够找到该第一目标区域中包含的所有强连通子图，每个强连通子图都代表了该第一目标区域中的一个第二候选区域。
[0154]
305、服务器从该多个第二候选区域中，筛选得到第二目标区域，该第二目标区域用于指示该虚拟场景中该虚拟对象能够到达且能够返回的双向连通区域。
[0155]
在一些实施例中，服务器从各个第二候选区域中筛选得到第二目标区域时，可以将该多个第二候选区域中包含的网格数量最大的第二候选区域确定为该第二目标区域。
[0156]
示意性地，上述过程相当于将虚拟场景的所有强连通子图中包含顶点数量最多的强连通子图作为该第二目标区域，例如，在将第一目标区域内包含的所有poly构成的poly集合，基于tarjan scc算法划分出多个强连通子图即第二候选区域之后，每个第二候选区域内包含的所有poly均形成了该poly集合的一个poly子集，此时将包含poly数量最大的poly子集所构成的区域确定为第二目标区域。
[0157]
在一些实施例中，服务器从各个第二候选区域中筛选得到第二目标区域时，还可以按照包含的网格数量从大到小的顺序，对各个第二候选区域进行排序，将排序位于前m(m≥1)位的m个第二候选区域的并集所指示的区域作为该第二目标区域，换言之，将该多个第二候选区域中包含顶点数量最多的m个第二候选区域的并集所指示的区域作为该第二目标区域。
[0158]
示意性地，上述过程相当于将虚拟场景的所有强连通子图中包含顶点数量最多的m个强连通子图的并集作为该第二目标区域，例如，在将第一目标区域内包含的所有poly构
成的poly集合，基于tarjan scc算法划分出多个强连通子图即第二候选区域之后，相当于确定了多个第二候选区域各自对应的poly子集，接着，按照包含的poly数量从大到小的顺序，对各个poly子集进行排序，将排序位于前m位的m个poly子集的并集所指示的区域作为该第二目标区域。
[0159]
在上述步骤304-305中，提供了服务器从该第一目标区域中确定第二目标区域的一种可能实施方式，由于第二目标区域内的各个网格均是虚拟对象能够到达且能够返回的可活动空间，因此这些可活动空间所构成的双向连通区域即第二目标区域可视为是虚拟对象在虚拟场景中绝大多数情况下进行活动的主区域，服务器可以保存能够指示该第二目标区域的相关数据，就能够基于该第二目标区域来指导虚拟场景中虚拟资源的投放、虚拟对象的刷新以及虚拟对象的路径规划(或称为导航、寻路)。
[0160]
在一些实施例中，服务器对该场景导航数据中的每个网格，基于该网格所属的区域，确定该网格的区域参数，该区域参数用于指示该虚拟对象在该虚拟场景中的对应网格活动的通达度，每个网格的区域参数能够指示该网格是否属于第一目标区域以及是否属于第二目标区域，从而综合所有网格的区域参数就能够判断出第一目标区域中包含哪些网格、第二目标区域中包含哪些网格。
[0161]
在一些实施例中，对场景导航数据中的每个网格，服务器在该网格位于该第一目标区域之外的情况下，将该网格的区域参数确定为第一数值，换言之，服务器将位于第一目标区域之外的每个网格的区域参数均配置为第一数值，例如，当区域参数是整型数据时，该第一数值为0或者负数，当访问到某一网格的区域参数取值为0或者负数时，代表这一网格位于第一目标区域之外，又例如，当区域参数是字符串时，该第一数值为“孤立(isolated)”，当访问到某一网格的区域参数取值为“孤立”时，代表这一网格位于第一目标区域之外。
[0162]
在一些实施例中，对场景导航数据中的每个网格，服务器在该网格位于该第一目标区域的情况下，将该网格的区域参数确定为第二数值，其中，区域参数为第二数值对应的通达度大于第一数值对应的通达度，换言之，服务器将位于第一目标区域之内的每个网格的区域参数均配置为第二数值，并且定义第二数值具有比第一数值更高的通达度，这里的通达度是指图论中的连通性的衡量指标，通达度越高代表对应网格在整个虚拟场景(有向图)中的连通性越高，通达度越低代表对应网格在整个虚拟场景(有向图)中的连通性越低。例如，当区域参数是整型数据时，该第二数值为正数，当访问到某一网格的区域参数取值为正数时，代表这一网格位于第一目标区域之内，又例如，当区域参数是字符串时，该第二数值为“非孤立”，当访问到某一网格的区域参数取值为“非孤立”时，代表这一网格位于第一目标区域之内。
[0163]
示意性地，针对上述该网格位于该第一目标区域的情况下，基于该网格是否位于第二目标区域内，来对该网格的区域参数进行不同的赋值，比如，当区域参数是整型数据时，将位于第一目标区域之外的各个网格的区域参数配置为0或负数，将位于第一目标区域内但位于第二目标区域外的各个网格的区域参数配置为1，将位于第二目标区域内的各个网格区域参数配置为2，从而能够保证网格的区域参数随着网格的连通性而增大，当然并不一定需要保证网格的区域参数与连通性呈正相关，也可以使得网格的区域参数与连通性呈负相关，或者两者不相关，只要能够通过区域参数区分出来当前网格是否属于第一目标区
域或者是否属于第二目标区域即可。
[0164]
在一些实施例中，服务器针对上述步骤304获取到的该第一目标区域中包含的多个第二候选区域，将该多个第二候选区域按照包含的网格数量从大到小的顺序进行排序，接着，由于在划分第二候选区域时遍历了第一目标区域中的所有网格，并且每个网格都仅入栈一次且退栈一次，代表了对第一目标区域中的每个网格都能够找到一个唯一所属的第二候选区域，那么只需要将每个网格的区域参数确定为该网格所属的第二候选区域在该排序中的序号，就能够标识出每个网格是否属于第二目标区域。例如，如果第二目标区域是指包含的网格数量最大的第二候选区域，代表了第二目标区域在上述多个第二候选区域的排序中必定位于首位，因此只需要找到所有区域参数取值为1的网格，这些网格在虚拟场景中所确定的区域就是第二目标区域。
[0165]
在上述方式中，提供了一种对每个网格均配置一个区域参数，从而以指示第一目标区域包含哪些网格、第二目标区域包含哪些网格的方式，只需要将每个网格poly的区域参数保存到navmesh数据中，就能够提供给后续的虚拟资源的投放、虚拟对象的刷新以及虚拟对象的路径规划(或称为导航、寻路)等业务来查询使用，这样的存储开销较低。
[0166]
在另一些实施例中，服务器还可以针对第一目标区域的各个网格维护一张哈希表，同理针对第二目标区域的各个网格维护另一张哈希表，从而将两张哈希表提供给后续的虚拟资源的投放、虚拟对象的刷新以及虚拟对象的路径规划(或称为导航、寻路)等业务来查询使用，这样的存储开销同样比较低。
[0167]
上述所有可选技术方案，能够采用任意结合形成本公开的可选实施例，在此不再一一赘述。
[0168]
本技术实施例提供的方法，通过对虚拟场景的场景导航数据进行后处理，先从虚拟场景中划分出虚拟对象能够到达的第一目标区域，以粗略排除掉一些虚拟对象完全无法行走的孤立区域，接着，在第一目标区域中划分出虚拟对象能够到达且能够返回的第二目标区域，以精细排除掉一些虚拟对象移动过去之后无法返回的区域，这样能够保证后处理得到的第二目标区域具有很高的通达度，通过第二目标区域来指导对虚拟场景中虚拟资源的投放、虚拟对象的刷新以及虚拟对象的路径规划中各类下游业务需求，能够避免虚拟资源或虚拟对象出现到一些玩家无法到达的区域，并且无需进行人工布点，能够节约场景数据处理的人力成本、提高数据处理的准确性。
[0169]
在上一实施例中，详细介绍了本技术实施例涉及的场景数据的处理方法，在ue或unity等引擎中可视为是对navmesh导航网格数据的后处理方法，在传统的recastnavigation导航方案中，基于能够容纳下虚拟对象行走的空间来对虚拟场景(即游戏地图、场景地图)进行采样，进而生成navmesh导航网格数据，但不会对navmesh导航网格数据进行任何后处理，这导致凡是能够容纳下虚拟对象行走(或站立)的区域内，不论虚拟对象是否能够到达(比如山顶、缝隙中、封闭空间的内部如山内或密闭集装箱内等)，都会生成navmesh导航网格数据，因此如果将未经过后处理的navmesh导航网格数据直接投入到后续对虚拟资源的投放、虚拟对象的刷新或虚拟对象的路径规划等任务中，由于navmesh导航网格数据本身就没有考虑到区域之间的连通性问题，因此navmesh导航网格数据中可能会存在一些彼此不可达的独立区域，此时，虚拟资源如果被投放到玩家不可达的区域，或者虚拟对象刷新在玩家不可达的区域，将导致虚拟资源或虚拟对象无法和玩家产生有效且充分
的游戏互动、人机交互。另外还考虑一种情况，由于在一些游戏规则中，虚拟资源如虚拟宝箱会随机掉落在已经被击败(或淘汰、出局、复活中)的虚拟对象周围，但是，由于虚拟对象被击败的位置具有很高的随机性，这导致在没有充分考虑地形信息的情况下，有可能虚拟宝箱的投放选点会被卡在两个物体模型中间或者地形缝隙中，导致玩家无法正常拾取虚拟宝箱。
[0170]
当使用上述实施例提供的场景数据的处理方法之后，由于能够确定出虚拟场景中的第二目标区域，第二目标区域既保证了虚拟对象可到达也保证了虚拟对象可返回，因此，在应用到虚拟资源或虚拟对象的投放任务中时，只需要控制投放选点始终位于第二目标区域内，比如快速从第二目标区域包含的各个网格中随机选点，就能够避免上述虚拟资源掉落在玩家不可达的区域，从而提到了资源投放准确性，优化了用户体验；在应用到虚拟对象的路径规划任务中时，由于在导航寻路时经常会出现目的地不可达(比如撞墙、碰到障碍物、在山脚无法攀爬)的情况，在传统recastnavigation导航方案中，如果寻路到一个不可达的点，就会导致a*搜索算法发生退化，产生不必要的性能开销，而本技术实施例通过预先划定必定可达的第二目标区域，能够提前排除掉大部分不可达的网格，从而能够避免由于寻路到不可达的网格导致a*搜索算法退化所带来的性能开销。
[0171]
总而言之，上述对navmesh导航网格数据的后处理方法，在划定第一目标区域时，相当于排除了虚拟场景中不可达的网格，即粗略排除一些完全不相连的孤立区域，在划定第二目标区域时，相当于排除了虚拟场景不可返回的网格，即精细排除掉一些去了就无法返回的区域(比如从山坡上跳下来之后无法返回)，这样不管是在控制投放虚拟资源或虚拟对象，还是应对虚拟对象的路径规划，又或者面向虚拟对象的场景查询问题(即在ai控制的虚拟对象进行随机运动时仅选中第二目标区域内的网格，以实现可达网格的高效查询)，均能够大幅提升处理性能和准确性，极大提升游戏体验。
[0172]
在本技术实施例中，将以ue或者unity等支持recastnavigation导航库的游戏引擎为例，介绍针对navmesh导航网格数据的后处理方法，该后处理方法适用于各类复杂地形的fps游戏、第三人称射击游戏、moba游戏、虚拟现实应用程序、三维地图程序、多人器械类生存游戏等，结合游戏引擎的eqs等手段，能够让游戏机器人(指不受玩家控制的虚拟对象，通常由ai行为模型控制)提前知道在虚拟场景中哪些地方无法抵达、哪些地方跳下去了就再也爬不上来等，从而使得游戏机器人在路径规划和移动表现上显示出更高的智能性，并且还能够高效、自动化地随机投放一些虚拟资源或游戏机器人到玩家控制的虚拟对象一定可到达的地方，能够解决在完全随机情况下投放位置刁钻、不可触达的问题，带来更好的玩家体验。
[0173]
图4是本技术实施例提供的一种navmesh导航网格数据的后处理方法的流程图，如图4所示，该实施例由电子设备执行，以电子设备为服务器为例进行说明，该实施例包括下述步骤：
[0174]
401、服务器收集navmesh导航网格数据中所有poly的信息，建立哈希表。
[0175]
其中，navmesh导航网格数据为上述实施例中虚拟场景的场景导航数据的一种示例性说明。
[0176]
可选地，遍历navmesh导航网格数据找到所有poly的索引polyref，使用游戏引擎内建的哈希表建立一个虚拟场景(即全地图)所有polyref的总索引，哈希表的建立过程参
见上述实施例中步骤302的描述，这里不做赘述。
[0177]
图5是本技术实施例提供的一种原始navmesh数据的示意图，如图5所示，在navmesh方案中，将虚拟场景500换分成了一系列的凸多边形网格poly，其中，深色区域501的poly代表了山体内部的不可行走的空间，而浅色区域502和503的poly则代表了可供虚拟对象行走的空间。但是，虽然山体内部能够容纳虚拟对象行走，但是虚拟对象是无法穿山而过的，因此显然浅色区域502是一个可行走但实际不可达的区域。
[0178]
由于ue内建的哈希表实现较为简单，能够针对小型数据进行性能优化。可选地，使用xorshift64算法来处理polyref，以减少其数值的规律性，这样能够将整体性能提升2.54倍。
[0179]
402、服务器寻找哈希表是否存在下一个未访问过的poly？如果存在下一个未访问过的poly，进入步骤403，如果不存在下一个未访问过的poly，进入步骤404。
[0180]
可选地，对步骤401创建的哈希表中所有poly进行遍历，找到当前首个未访问过的poly，进入步骤403，如果没找到未访问过的poly，进入步骤404。
[0181]
403、服务器在不考虑方向的情况下，从找到的该未访问过的poly出发，基于bfs算法访问所有可达的poly，得到一个弱连通分量，返回步骤402。
[0182]
其中，弱连通分量即弱连通子图，也即上述实施例中涉及的第一候选区域。
[0183]
可选地，在本次遍历中忽略poly连接的方向，换言之，即便从poly a能够跳跃到poly b，但无法从poly b返回poly a，也会认为poly a和poly b相互连接来进行遍历。使用上述步骤402中找到的首个未访问过的poly作为根节点，从根节点出发遍历所有与根节点直接或间接连接到的poly，在bfs算法搜索停止时能够得到一个由根节点和bfs算法搜索到的所有poly构成的弱连通分量。
[0184]
重复执行步骤402-403，直到哈希表中所有poly都被访问过，此时哈希表中一定不存在未访问过的poly，进入步骤404。
[0185]
404、服务器将各个弱连通分量按照包含poly的数量从大到小排序。
[0186]
由于已经将navmesh导航网格数据中的全部poly进行了一次划分，形成了多个以根节点为中心可以抵达的poly集合，在所有poly集合中，仅保留包含poly数量最多的poly集合(即极大弱连通子图)，其他所有poly集合中的每个poly都会被排除掉，不参与后续的后处理计算中。
[0187]
405、服务器将除了最大的弱连通分量以外的全部poly均标记为孤立。
[0188]
其中，最大的弱连通分量也即上述实施例涉及的第一目标区域。
[0189]
经过步骤402-404已经粗略地排除掉了完全不相连的poly，这些poly均会被标记为孤立，即，对这些poly的区域参数配置为第一数值，第一数值用于指示这些poly位于第一目标区域之外。
[0190]
图6是本技术实施例提供的一种去除不可达区域后的navmesh数据的示意图，在图5所示的原始navmesh数据的基础上，通过上述步骤402-404识别出来不可达的浅色区域502，将浅色区域502中各个poly标记为孤立，并在后续的后处理计算中排除掉这些已经被标记为孤立的poly。如图5所示，为了对这些标记为孤立的poly构成的不可达的浅色区域502进行可视化表征，将浅色区域502修改成深色区域，代表这一区域虽然可容纳虚拟对象行走，但是虚拟对象实际无法到达。
[0191]
406、服务器使用所有未标记为孤立的poly建立新的哈希表。
[0192]
接下来，需要针对第一目标区域内的poly即所有未标记为孤立的poly，处理单向连通问题，此时使用剩余poly的polyref按照步骤401类似的方式再次建立一张哈希表，可以知晓，这张哈希表中的所有poly在不考虑方向的情况下一定都是互相连接的。
[0193]
407、服务器寻找哈希表是否存在下一个未访问过的poly？如果存在下一个未访问过的poly，进入步骤408，如果不存在下一个未访问过的poly，进入步骤409。
[0194]
可选地，对步骤406创建的哈希表中所有poly进行遍历，找到当前首个未访问过的poly，进入步骤408，如果没找到未访问过的poly，进入步骤409。
[0195]
408、服务器在考虑方向的情况下，运行tarjan scc算法，得到一个强连通分量，返回步骤407。
[0196]
其中，强连通分量即强连通子图，也即上述实施例中涉及的第二候选区域。
[0197]
重复执行步骤407-408，直到哈希表中所有poly都被访问过，此时哈希表中一定不存在未访问过的poly，代表对哈希表中所有poly都运行过tarjan scc算法，这时能够得到若干强连通分量，进入步骤409。
[0198]
409、服务器将各个强连通分量按照包含poly的数量从大到小排序。
[0199]
将tarjan scc算法多次迭代输出的多个强连通分量，按照包含poly的数量从大到小的顺序进行排序，这样能够保证排序位于第1位的强连通分量拥有最多的poly数量，这个排序位于第1位的强连通分量可作为上述实施例中最终的第二目标区域。
[0200]
410、服务器将每个poly标记为所属强连通分量在排序中的序号。
[0201]
换言之，按照从大到小的顺序，对每个强连通分量中的poly从1开始进行编号。比如，将排序位于第1位的强连通分量中的所有poly标记为1，将排序位于第2位的强连通分量中的所有poly标记为2，以此类推，直到对哈希表中所有未标记为孤立的poly均标记完毕。
[0202]
可以知晓，由于排序位于第1位的强连通分量包含的poly数量最多，那么标记为1的poly的数量最多，那么所有标记为1的poly构成的区域称为第二目标区域，即navmesh导航网格数据的主区域，玩家控制的虚拟对象、ai行为模型控制的游戏机器人的大多数活动都位于主区域中。
[0203]
图7是本技术实施例提供的一种navmesh数据中标记为1的poly的示意图，在图6所示的去除不可达区域后的navmesh数据的基础上，通过上述步骤407-409进一步识别出来可到达且可返回(针对山体环境来说特指能够爬上也能够跳下)的强连通分量scc，针对极大强连通分量(即包含poly数量最多的强连通分量，指第二目标区域)中的每个poly，均标记为1。能够看出图7所示的5个索引分别为1f3:0、1a3:0、1e9:0、220:0、243:0的poly 701～705，其区域参数zone均被标记为1，即对poly 701～705均标记zone:1，代表这5个poly均是可以从山体跳下也能够从山脚爬上的区域。
[0204]
图8是本技术实施例提供的一种navmesh数据中标记大于1的poly的示意图，在去除不可达区域后的navmesh数据的基础上，通过上述步骤407-409进一步识别出来可到达且可返回的强连通分量scc，针对极大强连通分量中的每个poly均标记为1，针对其余强连通分量中的每个poly均标记为对应强连通分量在排序中的序号，如图8所示，示出了悬崖环境下的2个索引分别为d1aa:0和d33d:0的poly 801和802，其区域参数zone均被标记为1382，代表poly 801和802均属于在排序中位于第1382位的强连通分量，这代表了虽然虚拟对象
能够在poly 801和802之间互相移动、行走，但是一旦虚拟对象从外部的poly坠落到poly 801或者802，就无法从坠落的poly中爬回到原先的外部poly，即，这些标记大于1的poly与主区域(即第二目标区域，标记为1的poly构成的区域)之间不属于同一个强连通分量。
[0205]
411、结束后处理，服务器保存对每个poly标记的数据。
[0206]
服务器保存对每个poly分配的标记数据，以供后续其他业务的查询使用。
[0207]
应用本技术实施例涉及的场景导航数据的后处理方法，针对2km*2km大小的地图(即虚拟场景)其处理过程只需要8秒左右，各个步骤的运行耗时请参考下述代码结果，并且计算过程是离线进行的，服务器只需要保存已经计算完毕的第二目标区域的相关数据或者整个虚拟场景的连通性信息即可。
[0208]
collectpolys
–
272.273ms
–
total 0.27s/1/272.273ms//收集poly
[0209]
surf
–
536.767ms
–
total 0.54s/1/536.767ms//一次遍历查找弱连通分量
[0210]
markasnull
–
25.430ms
–
total 0.03s/1/25.430ms//除了极大弱连通分量，
[0211]
均标记为孤立即null
[0212]
numpolys 590750,numcomponents 11088,numunreachable 112650//计算各区域包含poly数量
[0213]
recollectpolys
–
179.370ms
–
total 0.18s/1/179.370ms//收集未标记的poly findscc
–
941.055ms
–
total 0.94s/1/941.055ms//二次遍历查找强连通分量
[0214]
markreachabilityzone
–
6161.103ms
–
total 6.16s/1/6161.103ms//标记可到达、可返回的poly，以及可到达、不可返回的poly
[0215]
numrecollected 478100,numscc 16491,numzone1 439890//计算各区域包含poly数量
[0216]
total
–
8124.662ms
–
total 8.12s/1/8124.662ms//总运行耗时
[0217]
在本技术实施例中，通过对原始navmesh数据中的每个poly都进行标记，使得当poly的区域参数取值不同时，能够指示poly所属的区域是否可到达以及是否可返回，比如，poly的区域参数zone取值为孤立(比如定义0或负数为孤立，又比如定义null为孤立)时，poly属于不可达区域；poly的区域参数zone取值为1时，poly属于主区域即第二目标区域(可到达、可返回)；poly的区域参数zone取值大于1时，poly属于第一目标区域内、第二目标区域外的区域(可到达、不可返回)。这样，相当于拿到了虚拟场景的连通性数据，在连通性数据使用时，只需要访问连通性数据中指定poly的区域参数zone，或者比较不同poly的区域参数zone之间的大小，就能够快速给出连通性相关的查询结果。
[0218]
示意性地，在对游戏机器人的随机移动判断过程中，在进行随机移动选点即选取目的地时，取得起点poly和终点poly各自的区域参数zone，如果终点poly的区域参数zone取值为1，或者起点poly和终点poly的区域参数zone相等，则认为本次移动选点合法。
[0219]
示意性地，在控制投放虚拟资源或虚拟对象时，始终控制将虚拟资源或虚拟对象投放到主区域(即仅在区域参数zone取值为1的poly中进行随机选点)，能够保证投放到的poly一定位于玩家控制的虚拟对象可到达的主区域，从而提升了游戏性能、优化了用户体验。
[0220]
在上述各个实施例中，均介绍了场景数据的处理方法的不同实施例，在本技术实施例中，提供一种基于已经处理完毕的场景数据，所提供的对虚拟资源的投放方法，如图9
所示，图9是本技术实施例通过的一种虚拟资源的投放方法的流程图，该实施例由计算机设备执行，以计算机设备为服务器为例进行说明，该实施例包括下述步骤：
[0221]
901、服务器响应于虚拟资源的投放请求，获取虚拟场景的场景导航数据，该场景导航数据用于指示该虚拟场景中可供虚拟对象移动的空间。
[0222]
在一些实施例中，服务器获取虚拟资源的投放请求，该投放请求可以是由终端发起的请求，或者，是由服务器在满足投放条件时自动生成的请求，需要说明的是，在服务器集群架构下，生成投放请求和处理投放请求的服务器可以不是同一物理机，比如游戏服务器来生成投放请求，导航服务器来处理投放请求，本技术实施例不对投放请求的来源进行具体限定。
[0223]
在一些实施例中，服务器响应于该投放请求，对该投放请求进行解析，得到该虚拟资源所欲投放的虚拟场景的场景标识(identification，id)，然后查询与该场景id对应存储的场景导航数据，例如，查询与该场景id对应存储的navmesh导航网格数据。
[0224]
902、服务器获取基于该场景导航数据确定得到的第二目标区域，该第二目标区域用于指示该虚拟场景中该虚拟对象能够到达且能够返回的双向连通区域。
[0225]
在一些实施例中，服务器基于上述各个实施例中涉及的场景数据的处理方法，对虚拟场景能够确定出一个第二目标区域，这时服务器会将第二目标区域的相关数据进行保存，此时只需要访问该第二目标区域的相关数据，即可获取到该虚拟场景中的第二目标区域。
[0226]
比如，第二目标区域的相关数据，是指对场景导航数据中的每个网格都配置的区域参数，例如，访问navmesh导航网格数据中每个poly的区域参数zone，示意性地，将区域参数zone取值为1的所有poly形成的区域确定为第二目标区域。其中该区域参数用于指示该虚拟对象在该虚拟场景中的对应poly活动的通达度。
[0227]
比如，第二目标区域的相关数据，是指包含第二目标区域中所有网格的索引的哈希表，例如，访问第二目标区域对应的哈希表，查询到第二目标区域中所有poly的索引polyref，这些polyref所对应poly形成的区域就是第二目标区域。
[0228]
903、服务器向该虚拟场景中位于该第二目标区域的目标位置投放该虚拟资源。
[0229]
在一些实施例中，服务器从第二目标区域中随机确定一个网格作为目标位置，并控制向目标位置投放虚拟资源，虚拟资源包括虚拟宝箱、虚拟物资、虚拟物品、虚拟道具等，本技术实施例不对虚拟资源的资源类型进行具体限定。
[0230]
比如，服务器从区域参数为1的各个poly中，随机选取该虚拟资源的投放poly，或者，服务器从第二目标区域的哈希表中，随机选取该虚拟资源的投放poly。
[0231]
在本技术实施例中，利用后处理完毕的navmesh数据，来处理对该虚拟场景中虚拟资源的投放请求，响应于该投放请求，能够将该虚拟资源投放至虚拟场景中的第二目标区域中，保证了虚拟资源的投放的目标位置位于玩家控制虚拟对象可到达、可返回的主区域中，极大提升了虚拟资源的投放精度，优化了用户体验。
[0232]
在上述实施例中，详细介绍了如何利用后处理完毕的场景导航数据，来控制向虚拟场景中精准投放虚拟资源，需要说明的是，将上述实施例中的虚拟资源替换为ai行为模型控制的虚拟对象，同样能够实现对虚拟对象(即游戏机器人)的精准投放，这一投放过程也称为虚拟对象的出生或者刷新的过程，这里不做赘述。
[0233]
在本技术实施例中，还提供一种基于后处理完毕的场景导航数据，实现对虚拟对象的路径规划方法，如图10所示，图10是本技术实施例通过的一种虚拟对象的路径规划方法的流程图，该实施例由计算机设备执行，以计算机设备为服务器为例进行说明，该实施例包括下述步骤：
[0234]
1001、服务器响应于对虚拟场景中虚拟对象的路径规划请求，确定该路径规划请求的起点网格和终点网格。
[0235]
在一些实施例中，服务器获取虚拟对象的路径规划请求，该路径规划请求可以是由终端发起的请求，或者，是由服务器在满足路径规划条件(如游戏机器人的随机移动)时自动生成的请求，需要说明的是，在服务器集群架构下，生成路径规划请求和处理路径规划请求的服务器可以不是同一物理机，比如游戏服务器来生成路径规划请求，导航服务器来处理路径规划请求，本技术实施例不对路径规划请求的来源进行具体限定。
[0236]
在一些实施例中，服务器响应于该路径规划请求，对该路径规划请求进行解析，得到本次路径规划的起点网格和终点网格。可选地，在对游戏机器人进行随机移动的合法性判断场景下，路径规划请求中可以仅携带起点网格即起点poly，接着，由服务器随机选取一个与该起点网格相连的终点网格即终点poly。
[0237]
1002、服务器确定该虚拟场景中的第二目标区域，该第二目标区域用于指示该虚拟场景中该虚拟对象能够到达且能够返回的双向连通区域。
[0238]
上述步骤1002与上述步骤902类似，这里不做赘述。
[0239]
1003、服务器在该起点网格和该终点网格位于同一双向连通区域，或者该终点网格位于该第二目标区域时，确定该虚拟对象从该起点网格到该终点网格的移动合法。
[0240]
在一些实施例中，服务器先判断终点网格是否位于第二目标区域内，如果终点网格位于第二目标区域内，那么直接确定移动合法；如果终点网格在第二目标区域外，进一步判断该起点网格和终点网格之间是否虚拟对象可到达且可返回，如果虚拟对象可到达且可返回，说明起点网格和终点网格位于同一双向连通区域，确定移动合法，如果虚拟对象不可到达、或者可到达但不可返回，那么说明起点网格和终点网格之间的移动不合法。
[0241]
示意性地，查询起点poly的区域参数zone和终点poly的区域参数zone，如果终点poly的区域参数zone为1，确定终点poly位于第二目标区域，返回移动合法；如果终点poly的区域参数zone不为1，判断起点poly的区域参数zone和终点poly的区域参数zone是否相等，在起点poly的区域参数zone和终点poly的区域参数zone相等的情况下，确定起点poly和终点poly位于同一双向连通区域，返回移动合法，在起点poly的区域参数zone和终点poly的区域参数zone不相等的情况下，返回移动不合法。
[0242]
在本技术实施例中，针对在两个不可达的poly之间寻路的情况，传统寻路方案会展开a*搜索算法，直到耗尽迭代次数也找不到可行路径，则返回不可达，但本技术实施例只需要判断起点poly和终点poly的区域参数zone是否相等，就能够高效快速判断出两个poly之间是否双向连通，因此所有poly的区域参数zone也称为整个虚拟对象的连通性信息或连通性数据，这时无需展开a*搜索算法，减少了a*搜索算法针对两个不可达的poly的无效遍历次数。
[0243]
进一步地，在游戏引擎eqs选点移动时，同样涉及到判断从路径规划的起点poly到终点poly是否可达，在传统eqs方案中需要指向一次a*搜索算法，同时准备大量的poly来筛
选是否可达，选点效率很低，而本技术实施例仅需要读取起点poly和终点poly各自的区域参数zone，就能够立即判断出从起点poly出发是否能够达到终点poly，而不需要执行原本需要执行的一次a*搜索算法，在单局游戏中整体性能提升了4.97倍，适用于广泛的场景查询eqs任务，优化了eqs的业务表现。
[0244]
图11是本技术实施例提供的一种场景数据的处理装置的结构示意图，如图11所示，该装置包括：
[0245]
获取模块1101，用于获取虚拟场景的场景导航数据，该场景导航数据用于指示该虚拟场景中可供虚拟对象移动的空间；
[0246]
第一确定模块1102，用于基于该场景导航数据，确定该虚拟场景中的第一目标区域，该第一目标区域用于指示该虚拟场景中该虚拟对象能够到达的单向连通区域；
[0247]
第二确定模块1103，用于从该第一目标区域中确定第二目标区域，该第二目标区域用于指示该虚拟场景中该虚拟对象能够到达且能够返回的双向连通区域。
[0248]
本技术实施例提供的装置，通过对虚拟场景的场景导航数据进行后处理，先从虚拟场景中划分出虚拟对象能够到达的第一目标区域，以粗略排除掉一些虚拟对象完全无法行走的孤立区域，接着，在第一目标区域中划分出虚拟对象能够到达且能够返回的第二目标区域，以精细排除掉一些虚拟对象移动过去之后无法返回的区域，这样能够保证后处理得到的第二目标区域具有很高的通达度，通过第二目标区域来指导对虚拟场景中虚拟资源的投放、虚拟对象的刷新以及虚拟对象的路径规划中各类下游业务需求，能够避免虚拟资源或虚拟对象出现到一些玩家无法到达的区域，并且无需进行人工布点，能够节约场景数据处理的人力成本、提高数据处理的准确性。
[0249]
在一种可能实施方式中，基于图11的装置组成，该第一确定模块1102包括：
[0250]
第一确定单元，用于基于该场景导航数据，确定该虚拟场景中的多个第一候选区域，每个第一候选区域为该虚拟对象从对应根节点出发所能够到达的单向连通区域；
[0251]
第一筛选单元，用于从该多个第一候选区域中，筛选得到该第一目标区域。
[0252]
在一种可能实施方式中，该第一确定单元用于：
[0253]
对该场景导航数据中未访问过的任一网格，以该网格为根节点，确定从该根节点出发所能够到达的各个网格，将该网格和确定得到的各个网格所形成的区域确定为一个第一候选区域。
[0254]
在一种可能实施方式中，该第一筛选单元用于：
[0255]
将该多个第一候选区域中包含的网格数量最大的第一候选区域确定为该第一目标区域。
[0256]
在一种可能实施方式中，基于图11的装置组成，该第二确定模块1103包括：
[0257]
第二确定单元，用于从该第一目标区域中，确定多个第二候选区域，每个第二候选区域为该虚拟对象从对应根节点出发所能够到达且能够返回的双向连通区域；
[0258]
第二筛选单元，用于从该多个第二候选区域中，筛选得到该第二目标区域。
[0259]
在一种可能实施方式中，该第二确定单元用于：
[0260]
基于该第一目标区域，构建搜索树，该搜索树中的每个节点对应于该第一目标区域中的一个网格；
[0261]
将该搜索树中未处理的各个节点入栈，对于位于栈顶的节点，在该节点的时间戳
和追溯值相等时，将以该节点为根节点的搜索子树上的各个节点所形成的区域确定为一个第二候选区域。
[0262]
在一种可能实施方式中，该第二筛选单元用于：
[0263]
将该多个第二候选区域中包含的网格数量最大的第二候选区域确定为该第二目标区域。
[0264]
在一种可能实施方式中，基于图11的装置组成，该装置还包括：
[0265]
第三确定模块，用于对该场景导航数据中的每个网格，基于该网格所属的区域，确定该网格的区域参数，该区域参数用于指示该虚拟对象在该虚拟场景中的对应网格活动的通达度。
[0266]
在一种可能实施方式中，基于图11的装置组成，该第三确定模块包括：
[0267]
第三确定单元，用于在该网格位于该第一目标区域之外的情况下，将该网格的区域参数确定为第一数值；
[0268]
该第三确定单元，还用于在该网格位于该第一目标区域的情况下，将该网格的区域参数确定为第二数值，其中，区域参数为第二数值对应的通达度大于第一数值对应的通达度。
[0269]
在一种可能实施方式中，该第三确定单元还用于：
[0270]
对该第一目标区域中包含的多个第二候选区域，按照包含的网格数量从大到小的顺序进行排序，每个第二候选区域为该虚拟对象从对应根节点出发所能够到达且能够返回的双向连通区域；
[0271]
对该第一目标区域中的每个网格，将该网格的区域参数确定为该网格所属的第二候选区域在该排序中的序号。
[0272]
在一种可能实施方式中，基于图11的装置组成，该装置还包括：
[0273]
投放模块，用于响应于对该虚拟场景中虚拟资源的投放请求，将该虚拟资源投放至该虚拟场景中的该第二目标区域。
[0274]
在一种可能实施方式中，基于图11的装置组成，该装置还包括：
[0275]
第四确定模块，用于响应于对该虚拟场景中虚拟对象的路径规划请求，确定该路径规划请求的起点网格和终点网格；
[0276]
第五确定模块，用于在该起点网格和该终点网格位于同一双向连通区域，或者该终点网格位于该第二目标区域时，确定该虚拟对象从该起点网格到该终点网格的移动合法。
[0277]
上述所有可选技术方案，能够采用任意结合形成本公开的可选实施例，在此不再一一赘述。
[0278]
需要说明的是：上述实施例提供的场景数据的处理装置在处理虚拟场景的场景导航数据时，仅以上述各功能模块的划分进行举例说明，实际应用中，能够根据需要而将上述功能分配由不同的功能模块完成，即将计算机设备的内部结构划分成不同的功能模块，以完成以上描述的全部或者部分功能。另外，上述实施例提供的场景数据的处理装置与场景数据的处理方法实施例属于同一构思，其具体实现过程详见场景数据的处理方法实施例，这里不再赘述。
[0279]
图12是本技术实施例通过的一种虚拟资源的投放装置的结构示意图，如图12所
示，该装置包括：
[0280]
获取模块1201，用于响应于虚拟资源的投放请求，获取虚拟场景的场景导航数据，该场景导航数据用于指示该虚拟场景中可供虚拟对象移动的空间；
[0281]
该获取模块1201，还用于获取基于该场景导航数据确定得到的第二目标区域，该第二目标区域用于指示该虚拟场景中该虚拟对象能够到达且能够返回的双向连通区域；
[0282]
投放模块1202，用于向该虚拟场景中位于该第二目标区域的目标位置投放该虚拟资源。
[0283]
本技术实施例提供的装置，通过利用后处理完毕的场景导航数据，来处理对该虚拟场景中虚拟资源的投放请求，响应于该投放请求，将该虚拟资源投放至虚拟场景中的第二目标区域中，保证了虚拟资源的投放的目标位置位于玩家控制虚拟对象可到达、可返回的主区域中，极大提升了虚拟资源的投放精度，优化了用户体验。
[0284]
需要说明的是：上述实施例提供的虚拟资源的投放装置在向虚拟场景中投放虚拟资源时，仅以上述各功能模块的划分进行举例说明，实际应用中，能够根据需要而将上述功能分配由不同的功能模块完成，即将计算机设备的内部结构划分成不同的功能模块，以完成以上描述的全部或者部分功能。另外，上述实施例提供的虚拟资源的投放装置与虚拟资源的投放方法实施例属于同一构思，其具体实现过程详见虚拟资源的投放方法实施例，这里不再赘述。
[0285]
图13是本技术实施例提供的一种计算机设备的结构示意图，如图13所示，以计算机设备为终端1300为例进行说明。可选地，该终端1300的设备类型包括：智能手机、平板电脑、mp3播放器(moving picture experts group audio layer iii，动态影像专家压缩标准音频层面3)、mp4(moving picture experts group audio layer iv，动态影像专家压缩标准音频层面4)播放器、笔记本电脑或台式电脑。终端1300还可能被称为用户设备、便携式终端、膝上型终端、台式终端等其他名称。
[0286]
通常，终端1300包括有：处理器1301和存储器1302。
[0287]
可选地，处理器1301包括一个或多个处理核心，比如4核心处理器、8核心处理器等。可选地，处理器1301采用dsp(digital signal processing，数字信号处理)、fpga(field－programmable gate array，现场可编程门阵列)、pla(programmable logic array，可编程逻辑阵列)中的至少一种硬件形式来实现。在一些实施例中，处理器1301包括主处理器和协处理器，主处理器是用于对在唤醒状态下的数据进行处理的处理器，也称cpu(central processing unit，中央处理器)；协处理器是用于对在待机状态下的数据进行处理的低功耗处理器。在一些实施例中，处理器1301集成有gpu(graphics processing unit，图像处理器)，gpu用于负责显示屏所需要显示的内容的渲染和绘制。一些实施例中，处理器1301还包括ai(artificial intelligence，人工智能)处理器，该ai处理器用于处理有关机器学习的计算操作。
[0288]
在一些实施例中，存储器1302包括一个或多个计算机可读存储介质，可选地，该计算机可读存储介质是非暂态的。可选地，存储器1302还包括高速随机存取存储器，以及非易失性存储器，比如一个或多个磁盘存储设备、闪存存储设备。在一些实施例中，存储器1302中的非暂态的计算机可读存储介质用于存储至少一个程序代码，该至少一个程序代码用于被处理器1301所执行以实现本技术中各个实施例提供的场景数据的处理方法或虚拟资源
的投放方法。
[0289]
在一些实施例中，终端1300还可选包括有：外围设备接口1303和至少一个外围设备。处理器1301、存储器1302和外围设备接口1303之间能够通过总线或信号线相连。各个外围设备能够通过总线、信号线或电路板与外围设备接口1303相连。具体地，外围设备包括：射频电路1304、显示屏1305、摄像头组件1306、音频电路1307和电源1308中的至少一种。
[0290]
外围设备接口1303可被用于将i/o(input/output，输入/输出)相关的至少一个外围设备连接到处理器1301和存储器1302。在一些实施例中，处理器1301、存储器1302和外围设备接口1303被集成在同一芯片或电路板上；在一些其他实施例中，处理器1301、存储器1302和外围设备接口1303中的任意一个或两个在单独的芯片或电路板上实现，本实施例对此不加以限定。
[0291]
射频电路1304用于接收和发射rf(radio frequency，射频)信号，也称电磁信号。射频电路1304通过电磁信号与通信网络以及其他通信设备进行通信。射频电路1304将电信号转换为电磁信号进行发送，或者，将接收到的电磁信号转换为电信号。可选地，射频电路1304包括：天线系统、rf收发器、一个或多个放大器、调谐器、振荡器、数字信号处理器、编解码芯片组、用户身份模块卡等等。可选地，射频电路1304通过至少一种无线通信协议来与其它终端进行通信。该无线通信协议包括但不限于：城域网、各代移动通信网络(2g、3g、4g及5g)、无线局域网和/或wifi(wireless fidelity，无线保真)网络。在一些实施例中，射频电路1304还包括nfc(near field communication，近距离无线通信)有关的电路，本技术对此不加以限定。
[0292]
显示屏1305用于显示ui(user interface，用户界面)。可选地，该ui包括图形、文本、图标、视频及其它们的任意组合。当显示屏1305是触摸显示屏时，显示屏1305还具有采集在显示屏1305的表面或表面上方的触摸信号的能力。该触摸信号能够作为控制信号输入至处理器1301进行处理。可选地，显示屏1305还用于提供虚拟按钮和/或虚拟键盘，也称软按钮和/或软键盘。在一些实施例中，显示屏1305为一个，设置终端1300的前面板；在另一些实施例中，显示屏1305为至少两个，分别设置在终端1300的不同表面或呈折叠设计；在再一些实施例中，显示屏1305是柔性显示屏，设置在终端1300的弯曲表面上或折叠面上。甚至，可选地，显示屏1305设置成非矩形的不规则图形，也即异形屏。可选地，显示屏1305采用lcd(liquid crystal display，液晶显示屏)、oled(organic light-emitting diode，有机发光二极管)等材质制备。
[0293]
摄像头组件1306用于采集图像或视频。可选地，摄像头组件1306包括前置摄像头和后置摄像头。通常，前置摄像头设置在终端的前面板，后置摄像头设置在终端的背面。在一些实施例中，后置摄像头为至少两个，分别为主摄像头、景深摄像头、广角摄像头、长焦摄像头中的任意一种，以实现主摄像头和景深摄像头融合实现背景虚化功能、主摄像头和广角摄像头融合实现全景拍摄以及vr(virtual reality，虚拟现实)拍摄功能或者其它融合拍摄功能。在一些实施例中，摄像头组件1306还包括闪光灯。可选地，闪光灯是单色温闪光灯，或者是双色温闪光灯。双色温闪光灯是指暖光闪光灯和冷光闪光灯的组合，用于不同色温下的光线补偿。
[0294]
在一些实施例中，音频电路1307包括麦克风和扬声器。麦克风用于采集用户及环境的声波，并将声波转换为电信号输入至处理器1301进行处理，或者输入至射频电路1304
以实现语音通信。出于立体声采集或降噪的目的，麦克风为多个，分别设置在终端1300的不同部位。可选地，麦克风是阵列麦克风或全向采集型麦克风。扬声器则用于将来自处理器1301或射频电路1304的电信号转换为声波。可选地，扬声器是传统的薄膜扬声器，或者是压电陶瓷扬声器。当扬声器是压电陶瓷扬声器时，不仅能够将电信号转换为人类可听见的声波，也能够将电信号转换为人类听不见的声波以进行测距等用途。在一些实施例中，音频电路1307还包括耳机插孔。
[0295]
电源1308用于为终端1300中的各个组件进行供电。可选地，电源1308是交流电、直流电、一次性电池或可充电电池。当电源1308包括可充电电池时，该可充电电池支持有线充电或无线充电。该可充电电池还用于支持快充技术。
[0296]
在一些实施例中，终端1300还包括有一个或多个传感器1310。该一个或多个传感器1310包括但不限于：加速度传感器1311、陀螺仪传感器1312、压力传感器1313、光学传感器1314以及接近传感器1315。
[0297]
在一些实施例中，加速度传感器1311检测以终端1300建立的坐标系的三个坐标轴上的加速度大小。比如，加速度传感器1311用于检测重力加速度在三个坐标轴上的分量。可选地，处理器1301根据加速度传感器1311采集的重力加速度信号，控制显示屏1305以横向视图或纵向视图进行用户界面的显示。加速度传感器1311还用于游戏或者用户的运动数据的采集。
[0298]
在一些实施例中，陀螺仪传感器1312检测终端1300的机体方向及转动角度，陀螺仪传感器1312与加速度传感器1311协同采集用户对终端1300的3d动作。处理器1301根据陀螺仪传感器1312采集的数据，实现如下功能：动作感应(比如根据用户的倾斜操作来改变ui)、拍摄时的图像稳定、游戏控制以及惯性导航。
[0299]
可选地，压力传感器1313设置在终端1300的侧边框和/或显示屏1305的下层。当压力传感器1313设置在终端1300的侧边框时，能够检测用户对终端1300的握持信号，由处理器1301根据压力传感器1313采集的握持信号进行左右手识别或快捷操作。当压力传感器1313设置在显示屏1305的下层时，由处理器1301根据用户对显示屏1305的压力操作，实现对ui界面上的可操作性控件进行控制。可操作性控件包括按钮控件、滚动条控件、图标控件、菜单控件中的至少一种。
[0300]
光学传感器1314用于采集环境光强度。在一个实施例中，处理器1301根据光学传感器1314采集的环境光强度，控制显示屏1305的显示亮度。具体地，当环境光强度较高时，调高显示屏1305的显示亮度；当环境光强度较低时，调低显示屏1305的显示亮度。在另一个实施例中，处理器1301还根据光学传感器1314采集的环境光强度，动态调整摄像头组件1306的拍摄参数。
[0301]
接近传感器1315，也称距离传感器，通常设置在终端1300的前面板。接近传感器1315用于采集用户与终端1300的正面之间的距离。在一个实施例中，当接近传感器1315检测到用户与终端1300的正面之间的距离逐渐变小时，由处理器1301控制显示屏1305从亮屏状态切换为息屏状态；当接近传感器1315检测到用户与终端1300的正面之间的距离逐渐变大时，由处理器1301控制显示屏1305从息屏状态切换为亮屏状态。
[0302]
本领域技术人员能够理解，图13中示出的结构并不构成对终端1300的限定，能够包括比图示更多或更少的组件，或者组合某些组件，或者采用不同的组件布置。
[0303]
图14是本技术实施例提供的一种计算机设备的结构示意图，该计算机设备1400可因配置或性能不同而产生比较大的差异，该计算机设备1400包括一个或一个以上处理器(central processing units，cpu)1401和一个或一个以上的存储器1402，其中，该存储器1402中存储有至少一条计算机程序，该至少一条计算机程序由该一个或一个以上处理器1401加载并执行以实现上述各个实施例提供的场景数据的处理方法或虚拟资源的投放方法。可选地，该计算机设备1400还具有有线或无线网络接口、键盘以及输入输出接口等部件，以便进行输入输出，该计算机设备1400还包括其他用于实现设备功能的部件，在此不做赘述。
[0304]
在示例性实施例中，还提供了一种计算机可读存储介质，例如包括至少一条计算机程序的存储器，上述至少一条计算机程序可由终端中的处理器执行以完成上述各个实施例中的场景数据的处理方法或虚拟资源的投放方法。例如，该计算机可读存储介质包括rom(read-only memory，只读存储器)、ram(random-access memory，随机存取存储器)、cd-rom(compact disc read-only memory，只读光盘)、磁带、软盘和光数据存储设备等。
[0305]
在示例性实施例中，还提供了一种计算机程序产品或计算机程序，包括一条或多条程序代码，该一条或多条程序代码存储在计算机可读存储介质中。计算机设备的一个或多个处理器能够从计算机可读存储介质中读取该一条或多条程序代码，该一个或多个处理器执行该一条或多条程序代码，使得计算机设备能够执行以完成上述实施例中的场景数据的处理方法或虚拟资源的投放方法。
[0306]
本领域普通技术人员能够理解实现上述实施例的全部或部分步骤能够通过硬件来完成，也能够通过程序来指令相关的硬件完成，可选地，该程序存储于一种计算机可读存储介质中，可选地，上述提到的存储介质是只读存储器、磁盘或光盘等。
[0307]
以上所述仅为本技术的可选实施例，并不用以限制本技术，凡在本技术的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本技术的保护范围之内。

技术特征：
1.一种场景数据的处理方法，其特征在于，所述方法包括：获取虚拟场景的场景导航数据，所述场景导航数据用于指示所述虚拟场景中可供虚拟对象移动的空间；基于所述场景导航数据，确定所述虚拟场景中的第一目标区域，所述第一目标区域用于指示所述虚拟场景中所述虚拟对象能够到达的单向连通区域；从所述第一目标区域中确定第二目标区域，所述第二目标区域用于指示所述虚拟场景中所述虚拟对象能够到达且能够返回的双向连通区域。2.根据权利要求1所述的方法，其特征在于，所述基于所述场景导航数据，确定所述虚拟场景中的第一目标区域包括：基于所述场景导航数据，确定所述虚拟场景中的多个第一候选区域，每个第一候选区域为所述虚拟对象从对应根节点出发所能够到达的单向连通区域；从所述多个第一候选区域中，筛选得到所述第一目标区域。3.根据权利要求2所述的方法，其特征在于，所述基于所述场景导航数据，确定所述虚拟场景中的多个第一候选区域包括：对所述场景导航数据中未访问过的任一网格，以所述网格为根节点，确定从所述根节点出发所能够到达的各个网格，将所述网格和确定得到的各个网格所形成的区域确定为一个第一候选区域。4.根据权利要求2所述的方法，其特征在于，所述从所述多个第一候选区域中，筛选得到所述第一目标区域包括：将所述多个第一候选区域中包含的网格数量最大的第一候选区域确定为所述第一目标区域。5.根据权利要求1所述的方法，其特征在于，所述从所述第一目标区域中确定第二目标区域包括：从所述第一目标区域中，确定多个第二候选区域，每个第二候选区域为所述虚拟对象从对应根节点出发所能够到达且能够返回的双向连通区域；从所述多个第二候选区域中，筛选得到所述第二目标区域。6.根据权利要求5所述的方法，其特征在于，所述从所述第一目标区域中，确定多个第二候选区域包括：基于所述第一目标区域，构建搜索树，所述搜索树中的每个节点对应于所述第一目标区域中的一个网格；将所述搜索树中未处理的各个节点入栈，对于位于栈顶的节点，在所述节点的时间戳和追溯值相等时，将以所述节点为根节点的搜索子树上的各个节点所形成的区域确定为一个第二候选区域。7.根据权利要求5所述的方法，其特征在于，所述从所述多个第二候选区域中，筛选得到所述第二目标区域包括：将所述多个第二候选区域中包含的网格数量最大的第二候选区域确定为所述第二目标区域。8.根据权利要求1所述的方法，其特征在于，所述方法还包括：对所述场景导航数据中的每个网格，基于所述网格所属的区域，确定所述网格的区域
参数，所述区域参数用于指示所述虚拟对象在所述虚拟场景中的对应网格活动的通达度。9.根据权利要求8所述的方法，其特征在于，所述基于所述网格所属的区域，确定所述网格的区域参数包括：在所述网格位于所述第一目标区域之外的情况下，将所述网格的区域参数确定为第一数值；在所述网格位于所述第一目标区域的情况下，将所述网格的区域参数确定为第二数值，其中，区域参数为第二数值对应的通达度大于第一数值对应的通达度。10.根据权利要求9所述的方法，其特征在于，所述在所述网格位于所述第一目标区域的情况下，将所述网格的区域参数确定为第二数值包括：对所述第一目标区域中包含的多个第二候选区域，按照包含的网格数量从大到小的顺序进行排序，每个第二候选区域为所述虚拟对象从对应根节点出发所能够到达且能够返回的双向连通区域；对所述第一目标区域中的每个网格，将所述网格的区域参数确定为所述网格所属的第二候选区域在所述排序中的序号。11.根据权利要求1所述的方法，其特征在于，所述方法还包括：响应于对所述虚拟场景中虚拟资源的投放请求，将所述虚拟资源投放至所述虚拟场景中的所述第二目标区域。12.根据权利要求1所述的方法，其特征在于，所述方法还包括：响应于对所述虚拟场景中虚拟对象的路径规划请求，确定所述路径规划请求的起点网格和终点网格；在所述起点网格和所述终点网格位于同一双向连通区域，或者所述终点网格位于所述第二目标区域时，确定所述虚拟对象从所述起点网格到所述终点网格的移动合法。13.一种虚拟资源的投放方法，其特征在于，所述方法包括：响应于虚拟资源的投放请求，获取虚拟场景的场景导航数据，所述场景导航数据用于指示所述虚拟场景中可供虚拟对象移动的空间；获取基于所述场景导航数据确定得到的第二目标区域，所述第二目标区域用于指示所述虚拟场景中所述虚拟对象能够到达且能够返回的双向连通区域；向所述虚拟场景中位于所述第二目标区域的目标位置投放所述虚拟资源。14.一种场景数据的处理装置，其特征在于，所述装置包括：获取模块，用于获取虚拟场景的场景导航数据，所述场景导航数据用于指示所述虚拟场景中可供虚拟对象移动的空间；第一确定模块，用于基于所述场景导航数据，确定所述虚拟场景中的第一目标区域，所述第一目标区域用于指示所述虚拟场景中所述虚拟对象能够到达的单向连通区域；第二确定模块，用于从所述第一目标区域中确定第二目标区域，所述第二目标区域用于指示所述虚拟场景中所述虚拟对象能够到达且能够返回的双向连通区域。15.一种虚拟资源的投放装置，其特征在于，所述装置包括：获取模块，用于响应于虚拟资源的投放请求，获取虚拟场景的场景导航数据，所述场景导航数据用于指示所述虚拟场景中可供虚拟对象移动的空间；所述获取模块，还用于获取基于所述场景导航数据确定得到的第二目标区域，所述第
二目标区域用于指示所述虚拟场景中所述虚拟对象能够到达且能够返回的双向连通区域；投放模块，用于向所述虚拟场景中位于所述第二目标区域的目标位置投放所述虚拟资源。16.一种计算机设备，其特征在于，所述计算机设备包括一个或多个处理器和一个或多个存储器，所述一个或多个存储器中存储有至少一条计算机程序，所述至少一条计算机程序由所述一个或多个处理器加载并执行以实现如权利要求1至权利要求12任一项所述的场景数据的处理方法或如权利要求13所述的虚拟资源的投放方法。17.一种存储介质，其特征在于，所述存储介质中存储有至少一条计算机程序，所述至少一条计算机程序由处理器加载并执行以实现如权利要求1至权利要求12任一项所述的场景数据的处理方法或如权利要求13所述的虚拟资源的投放方法。18.一种计算机程序产品，其特征在于，所述计算机程序产品包括至少一条计算机程序，所述至少一条计算机程序由处理器加载并执行以实现如权利要求1至权利要求12任一项所述的场景数据的处理方法或如权利要求13所述的虚拟资源的投放方法。

技术总结
本申请公开了一种场景数据的处理方法、装置、计算机设备及存储介质，属于计算机技术领域。本申请通过对虚拟场景的场景导航数据进行后处理，先从虚拟场景中划分出第一目标区域，以粗略排除掉完全无法行走的孤立区域，接着，在第一目标区域中划分出第二目标区域，以精细排除掉移动过去之后无法返回的区域，这样能够保证后处理得到的第二目标区域具有很高的通达度，并且无需进行人工布点，能够节约场景数据处理的人力成本、提高数据处理的准确性。提高数据处理的准确性。提高数据处理的准确性。


技术研发人员：何弦
受保护的技术使用者：腾讯科技（深圳）有限公司
技术研发日：2022.03.07
技术公布日：2023/9/20