对非玩家角色寻路的方法、装置、存储介质及计算机设备与流程

2021-01-11 15:01:33|

288|

起点商标网

本申请涉及计算机技术领域，尤其涉及电子游戏领域，具体涉及一种对非玩家角色寻路的方法、装置、存储介质及计算机设备。

背景技术：

在大型多场景多人在线游戏中，为了充实丰富游戏的玩法和剧情内容，通常将大量非玩家角色(non-playercharacter，npc)部署于场景中。游戏的玩家可以与npc进行互动，例如，玩家通过点击npc进行玩法的开启或推动任务剧情，因此，npc通常被认为是大型多场景多人在线游戏必不可少的部分。

若玩家要与npc互动，首先要能够找到目标npc，而在游戏场景中，玩家找寻目标npc的过程即为对npc的寻路。目前，对非玩家角色寻路的方法主要是依靠玩家从当前位置开始，在游戏商提供的地图上对位置、角色或/和路径等进行点击，一步一步地接近目标npc，直至找到目标npc。

上述方法虽然最终能够寻找到目标npc，然而，由于大型多场景多人游戏中的npc角色较多，场景复杂，现有对非玩家角色寻路的方法效率非常低，尤其对于一些新手玩家，极其耗费他们的时间。

技术实现要素：

本申请实施例提供一种对非玩家角色寻路的方法、装置、存储介质及计算机设备，可以提升对非玩家角色寻路的效率，节省玩家的时间。

本申请实施例提供了一种对非玩家角色寻路的方法，包括：

接收对目标非玩家角色npc进行寻路的寻路请求，所述寻路请求包括所述目标npc的索引信息；

根据所述目标npc的索引信息，获取所述目标npc在游戏场景中的位置；

根据虚拟角色当前所在游戏场景中的位置与所述目标npc在游戏场景中的位置，选用预先生成的连通图作为对所述目标npc进行寻路的网格化地图；

基于所述网格化地图，对所述目标npc寻路。

可选的，所述目标npc的索引信息包括目标npc的类型，所述方法还包括：创建哈希表，所述哈希表以每个npc的类型为关键码构成一键-值对的键、以所述每个npc在游戏场景中的位置构成所述键-值对的值来存储所述每个npc在游戏场景中的位置。

可选的，所述创建哈希表，包括：基于初始哈希函数对x个所述关键码分别进行哈希运算得到所述x个关键码各个关键码对应的第一哈希值；根据存在冲突的第一哈希值的关键码的数量y和所述关键码的数量x，确定所述关键码的第一哈希值的冲突概率p，所述x和y为正整数；根据所述第一哈希值的冲突概率修改所述初始哈希函数，得到确定哈希函数；基于所述确定哈希函数分别对所述x个关键码进行哈希运算得到所述x个关键码各个关键码对应的第二哈希值；根据所述第二哈希值构建红黑树，并基于所述红黑树构建对应的哈希表。

可选的，所述根据所述目标npc的索引信息，获取所述目标npc在游戏场景中的位置，包括：以所述目标npc的类型为关键码，采用所述第二哈希值在所述哈希表上进行索引；若命中所述哈希表，则从所述第二哈希值对应的存储单元读取所述目标npc在游戏场景中的位置。

可选的，所述创建哈希表包括：从内存划出第一表项存储空间，所述第一表项存储空间包括若干地址空间；构建至少两个哈希函数，并利用所述至少两个哈希函数对所述关键码进行哈希计算，得到每个所述关键码对应的至少两个哈希值；比较所述至少两个哈希值对应的地址空间的空满程度，将待存储信息存储至所述地址空间中存储空间最富余的地址空间；若所述至少两个哈希值对应的地址空间均已存满，则将所述待存储信息存储至第二表项存储空间。

可选的，所述根据所述目标npc的类型，从游戏客户端本地获取所述目标npc在游戏场景中的位置，包括：以所述目标npc的类型为关键码，采用所述至少两个哈希函数对所述关键码并行进行哈希计算得到至少两个哈希值；以所述至少两个哈希值在所述哈希表上进行索引；若命中所述哈希表，则从命中所述哈希表时所采用的哈希值对应的存储单元读取所述目标npc在游戏场景中的位置。

可选的，所述方法还包括：采用主干道配置方式和/或网格导航算法，生成所述连通图。

可选的，所述采用主干道配置方式和/或网格导航算法，生成所述连通图，包括：从所述游戏场景所包含的区域生成多个凸多边形的网格；采用碰撞检测算法检测所述凸多边形的网格中是否存在能够连通的网格；将所述凸多边形的网格中符合预设条件的网格配置为主干道中能够连通的网格；记录所述网格中能够连通的网格的连通信息，形成第一连通图或第二连通图，所述连通信息包括可连通网格中任意一个网格的位置信息、所述可连通网格中任意一个网格所在游戏场景的标识以及所述可连通网格中任意一个网格的邻居网格的标识。

可选的，所述从所述游戏场景所包含的区域生成多个凸多边形的网格，包括：遍历所述区域的轮廓的所有边，以每组三个点为三角形的顶点构成一个有效内部三角形块；将多个所述有效内部三角形块尽可能合并成一个最大面积的凸多边形，直至所有所述有效内部三角形块都合并成多个凸多边形的网格。

可选的，所述采用碰撞检测算法检测所述网格中是否存在能够连通的网格，包括：将碰撞检测模型从当前所在网格的表面抬升，使其距离所述当前网格的表面至预设高度；向所述碰撞检测模型当前所在网格的任意一个邻居网格移动所述已抬升碰撞检测模型；判断所述已抬升碰撞检测模型是否与所述邻居网格发生碰撞；若所述已抬升碰撞检测模型与所述邻居网格发生碰撞，则确定所述碰撞检测模型当前所在网格与所述邻居网格不连通，否则，确定所述碰撞检测模型当前所在网格与所述邻居网格连通。

可选的，所述判断所述已抬升碰撞检测模型是否与所述邻居网格发生碰撞，包括：获取所述碰撞检测模型当前所在网格的高度hc和所述邻居网格的高度hn；比较所述hn与hc-hs以及所述hn与hc+hs的大小，所述hs为所述预设高度；若所述hn在[hc-hs，hc+hs]，则确定所述已抬升碰撞检测模型不会与所述邻居网格发生碰撞，否则，确定所述已抬升碰撞检测模型会与所述邻居网格发生碰撞。

可选的，所述判断所述已抬升碰撞检测模型是否与所述邻居网格发生碰撞，包括：若所述邻居网格包含一孔状空间，则比较所述孔状空间最大位置的尺寸hmax与hm+hs的大小，所述hm为所述碰撞检测模型的高度，所述hs为所述预设高度；若所述hmax不小于所述hm+hs，则确定所述已抬升碰撞检测模型不会与所述邻居网格发生碰撞，否则，确定所述已抬升碰撞检测模型会与所述邻居网格发生碰撞。

可选的，所述虚拟角色的属性包括所述虚拟角色当前所在游戏场景的标识，所述方法还包括：根据所述目标npc的类型，获取所述目标npc所在游戏场景的标识；在查询起点集合和终点集合之前，根据所述虚拟角色当前所在游戏场景的标识和所述目标npc所在游戏场景的标识，确定所述虚拟角色与所述目标npc是否处于同一场景；若所述虚拟角色与所述目标npc不是处于同一场景，则判断是否能够对所述目标npc进行跨场景寻路。

可选的，所述判断是否能够对所述目标npc进行跨场景寻路，包括：根据所述虚拟角色当前所在游戏场景中的位置与所述目标npc在游戏场景中的位置，查询所述虚拟角色和/或所述目标npc附近的跳转点；若所述虚拟角色和/或所述目标npc附近的跳转点的属性信息表明所述虚拟角色和/或所述目标npc附近存在能够实现场景连通的跳转点，则确定能够对所述目标npc进行跨场景寻路。

可选的，所述连通图包括第一连通图和第二连通图，所述第一连通图包括对所述游戏场景中的网格进行主干道配置后所得游戏场景中网格之间的连通信息，所述第二连通图包括采用网格导航算法计算所得游戏场景中网格之间的连通信息，所述根据虚拟角色当前所在游戏场景中的位置与所述目标npc在游戏场景中的位置，选用预先生成的连通图作为对所述目标npc进行寻路的网格化地图，包括：在确定能够对所述目标npc进行同一场景寻路或跨场景寻路后，查询所述起点集合和所述终点集合，所述起点集合包括所述第一连通图中距离所述虚拟角色当前所在游戏中的位置最近的网格中心点，所述终点集合包括所述第一连通图中距离所述目标npc在游戏场景中的位置最近的网格中心点；若所述起点集合存在能够与所述终点集合中网格中心点连通的网格中心点，则选用所述第一连通图作为对所述目标npc进行寻路的网格化地图；若所述起点集合不存在能够与所述终点集合中网格中心点连通的网格中心点，则选用所述第二连通图作为对所述目标npc进行寻路的网格化地图。

可选的，所述第一连通图中每个网格中心点的位置以及所述每个网格中心点与其他网格中心点的连通关系采用四叉树的数据结构存储。

本申请实施例还提供一种对非玩家角色寻路的装置，包括：

接收模块，用于接收对目标非玩家角色npc进行寻路的寻路请求，所述寻路请求包括所述目标npc的索引信息；

获取模块，用于根据所述目标npc的索引信息，获取所述目标npc在游戏场景中的位置；

生成模块，用于根据虚拟角色当前所在游戏场景中的位置与所述目标npc在游戏场景中的位置，选用预先生成的连通图作为对所述目标npc进行寻路的网格化地图；

寻路模块，用于基于所述预先生成的连通图，对所述目标npc寻路。

本申请实施例还提供一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序适于处理器进行加载，以执行如上任一实施例所述的对非玩家角色寻路的方法中的步骤。

本申请实施例还提供一种计算机设备，所述计算机设备包括存储器和处理器，所述存储器中存储有计算机程序，所述处理器通过调用所述存储器中存储的所述计算机程序，执行如上任一实施例所述的对非玩家角色寻路的方法中的步骤。

从上述本申请实施例提供的技术方案可知，由于只需要触发一次对目标非玩家角色npc进行寻路的寻路请求，即可开启后续的获取目标npc在游戏场景中的位置、选用预先生成的连通图作为对目标npc进行寻路的网格化地图以及基于预先生成的连通图，采用最短路径算法对目标npc寻路，无需玩家手动一步一步寻路亦可以找到目标npc，因此，相对于现有技术，本申请实施例提供的技术方案对非玩家角色寻路的方法效率高，尤其是场景复杂的游戏，能够明显节省新手玩家的时间成本。

附图说明

为了更清楚地说明本申请实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本申请的一些实施例，对于本领域技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本申请实施例提供的对非玩家角色寻路的装置的系统示意图。

图2为本申请实施例提供的对非玩家角色寻路的方法的流程示意图。

图3为本申请实施例提供的创建哈希表的流程示意图。

图4为本申请另一实施例提供的创建哈希表的流程示意图。

图5为本申请实施例提供的采用主干道配置方式和/或网格导航算法生成连通图的流程示意图。

图6为本申请实施例提供的将游戏场景所包含的区域划分为多个凸多边形网格后连通各个网格的中心点时的寻路示意图。

图7a为本申请实施例提供的分割出有效内部三角形块的示意图。

图7b为本申请实施例提供的分割出无效三角形块的示意图。

图8a为本申请实施例提供的游戏场景中一些相对网格比较低矮的凸起或比较浅显的凹陷示意图。

图8b为本申请实施例提供的将碰撞检测模型从当前所在网格的表面抬升预设高度的示意图。

图9为本申请实施例提供的判断已抬升碰撞检测模型是否会与邻居网格发生碰撞示意图。

图10a为本申请实施例提供的已抬升碰撞检测模型从当前所在网格移动至邻居网格移动后不与邻居网格发生碰撞的示意图。

图10b为本申请实施例提供的已抬升碰撞检测模型从当前所在网格移动至邻居网格移动后会与邻居网格发生碰撞的示意图。

图11为本申请实施例提供的选用预先生成的连通图作为对目标npc进行寻路的网格化地图的流程示意图。

图12为本申请实施例提供的对非玩家角色寻路的装置的结构示意图。

图13为本申请另一实施例提供的对非玩家角色寻路的装置的结构示意图。

图14为本申请另一实施例提供的对非玩家角色寻路的装置的结构示意图。

图15为本申请另一实施例提供的对非玩家角色寻路的装置的结构示意图。

图16为本申请实施例提供的计算机设备的结构示意图。

具体实施方式

下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。

本申请实施例提供一种对非玩家角色寻路的方法、装置、存储介质及计算机设备。具体地，本申请实施例的对非玩家角色寻路的方法可以由计算机设备执行，其中，该计算机设备可以为终端或者服务器等设备。该终端可以为智能手机、平板电脑、笔记本电脑、触控屏幕、游戏机、个人计算机(pc，personalcomputer)、个人数字助理(personaldigitalassistant，pda)等终端设备，终端还可以包括客户端，该客户端可以是游戏应用客户端、携带有游戏程序的浏览器客户端或即时通信客户端等。服务器可以是独立的物理服务器，也可以是多个物理服务器构成的服务器集群或者分布式系统，还可以是提供云服务、云数据库、云计算、云函数、云存储、网络服务、云通信、中间件服务、域名服务、安全服务、cdn、以及大数据和人工智能平台等基础云计算服务的云服务器。

例如，当该对非玩家角色寻路的方法运行于终端时，终端设备存储有游戏应用程序并用于呈现游戏画面中的虚拟场景。终端设备用于通过图形用户界面与用户进行交互，例如通过终端设备下载安装游戏应用程序并运行。该终端设备将图形用户界面提供给用户的方式可以包括多种，例如，可以渲染显示在终端设备的显示屏上，或者，通过全息投影呈现图形用户界面。例如，终端设备可以包括触控显示屏和处理器，该触控显示屏用于呈现图形用户界面以及接收用户作用于图形用户界面产生的操作指令，该图形用户界面包括游戏画面，该处理器用于运行该游戏、生成图形用户界面、响应操作指令以及控制图形用户界面在触控显示屏上的显示。

例如，当该对非玩家角色寻路的方法运行于服务器时，可以为云游戏。云游戏是指以云计算为基础的游戏方式。在云游戏的运行模式下，游戏应用程序的运行主体和游戏画面呈现主体是分离的，对非玩家角色寻路的方法的储存与运行是在云游戏服务器上完成的。而游戏画面呈现是在云游戏的客户端完成的，云游戏客户端主要用于游戏数据的接收、发送以及游戏画面的呈现，例如，云游戏客户端可以是靠近用户侧的具有数据传输功能的显示设备，如，移动终端、电视机、计算机、掌上电脑、个人数字助理等，但是进行游戏数据处理的终端设备为云端的云游戏服务器。在进行游戏时，用户操作云游戏客户端向云游戏服务器发送操作指令，云游戏服务器根据操作指令运行游戏，将游戏画面等数据进行编码压缩，通过网络返回云游戏客户端，最后，通过云游戏客户端进行解码并输出游戏画面。

请参阅图1，图1为本申请实施例提供的对非玩家角色寻路的装置的系统示意图。该系统可以包括至少一个终端1000，至少一个服务器2000，至少一个数据库3000，以及网络4000。用户持有的终端1000可以通过网络4000连接到不同游戏的服务器。终端1000是具有计算硬件的任何设备，该计算硬件能够支持和执行与游戏对应的软件产品。另外，终端1000具有用于感测和获得用户通过在一个或者多个触控显示屏的多个点执行的触摸或者滑动操作的输入的一个或者多个多触敏屏幕。另外，当系统包括多个终端1000、多个服务器2000、多个网络4000时，不同的终端1000可以通过不同的网络4000、通过不同的服务器2000相互连接。网络4000可以是无线网络或者有线网络，比如无线网络为无线局域网(wlan)、局域网(lan)、蜂窝网络、2g网络、3g网络、4g网络、5g网络等。另外，不同的终端1000之间也可以使用自身的蓝牙网络或者热点网络连接到其他终端或者连接到服务器等。例如，多个用户可以通过不同的终端1000在线从而通过适当网络连接并且相互同步，以支持多玩家游戏。另外，该系统可以包括多个数据库3000，多个数据库3000耦合到不同的服务器2000，并且可以将与游戏环境有关的信息在不同用户在线进行多玩家游戏时连续地存储于数据库3000中。

本申请实施例提供了一种对非玩家角色寻路的方法，该方法可以由终端或服务器执行。本申请实施例以对非玩家角色寻路的方法由终端执行为例来进行说明。其中，该终端包括触控显示屏和处理器，该触控显示屏用于呈现图形用户界面以及接收用户作用于图形用户界面产生的操作指令。用户通过触控显示屏对图形用户界面进行操作时，该图形用户界面可以通过响应于接收到的操作指令控制终端本地的内容，也可以通过响应于接收到的操作指令控制对端服务器的内容。例如，用户作用于图形用户界面产生的操作指令包括用于启动游戏应用程序的指令，处理器被配置为在接收到用户提供的启动游戏应用程序的指令之后启动游戏应用程序。此外，处理器被配置为在触控显示屏上渲染和绘制与游戏相关联的图形用户界面。触控显示屏是能够感测屏幕上的多个点同时执行的触摸或者滑动操作的多触敏屏幕。用户在使用手指在图形用户界面上执行触控操作，图形用户界面在检测到触控操作时，控制游戏的图形用户界面中的不同虚拟对象执行与触控操作对应的动作。例如，该游戏可以为休闲游戏、动作游戏、角色扮演游戏、策略游戏、体育游戏、益智游戏等游戏中的任一种。其中，游戏可以包括在图形用户界面上绘制的游戏的虚拟场景。此外，游戏的虚拟场景中可以包括由用户(或玩家)控制的一个或多个虚拟对象，诸如虚拟角色。另外，游戏的虚拟场景中还可以包括一个或多个障碍物，诸如栏杆、沟壑、墙壁等，以限制虚拟对象的移动，例如将一个或多个对象的移动限制到虚拟场景内的特定区域。可选地，游戏的虚拟场景还包括一个或多个元素，诸如技能、分值、角色健康状态、能量等，以向玩家提供帮助、提供虚拟服务、增加与玩家表现相关的分值等。此外，图形用户界面还可以呈现一个或多个指示器，以向玩家提供指示信息。例如，游戏可以包括玩家控制的虚拟对象和一个或多个其他虚拟对象(诸如敌人角色)。在一个实施例中，一个或多个其他虚拟对象由游戏的其他玩家控制。例如，一个或多个其他虚拟对象可以由计算机控制，诸如使用人工智能(ai)算法的机器人，实现人机对战模式。例如，虚拟对象拥有游戏玩家用来实现目标的各种技能或能力。例如虚拟对象拥有可用于从游戏中消除其他对象的一种或多种武器、道具、工具等。这样的技能或能力可由游戏的玩家使用与终端的触控显示屏的多个预设触控操作之一来激活。处理器可以被配置为响应于用户的触控操作产生的操作指令来呈现对应的游戏画面。

请参阅图2，为本申请实施例提供的对非玩家角色寻路的方法的流程示意图，主要包括步骤s201至步骤s204，详细说明如下：

步骤s201，接收对目标非玩家角色npc进行寻路的寻路请求，其中，寻路请求包括目标npc的索引信息。

在本申请实施例中，对目标npc进行寻路的寻路请求为某个事件发生或某个操作出现时触发，例如，在成功完成一个任务之后，需要找寻一个去交付任务成果的npc，此时会触发对该npc寻路的寻路请求；又如，玩家在游戏界面点击了一个玩法的入口，也会触发寻路一个该玩法对应的npc，等等；客户端后台每触发一次对目标npc进行寻路的寻路请求，前台即接收对该目标npc进行寻路的寻路请求。需要说明的是，在一次寻路过程中，对目标npc进行寻路的寻路请求仅仅需要触发一次，即寻路请求为对目标npc进行寻路时被触发的仅有一次请求行为，中途无需再次触发，这对玩家、尤其是新手玩家而言，游戏的体验比较友好。

后台触发的对目标npc进行寻路的寻路请求主要包括该目标npc的索引信息，其包括该目标npc的类型；npc的类型标识了该npc的作用，例如，任务npc、节日活动npc和领奖npc分别标识该npc是某项任务中的角色、承担某个节日活动的某个角色和关于领奖活动的角色，等等。对于一些npc非常多且场景非常复杂的游戏，为了分类更加精确，还可以对npc进行子类型的标识，即一个npc同时采用类型以及该类型下的子类型来标识。

步骤s202，根据目标npc的索引信息，获取目标npc在游戏场景中的位置。

游戏策划师在策划某款游戏时，认为游戏场景中的某个位置适合安放npc就在该位置安放一个npc，npc的这个位置信息是在服务器端保存的。虽然游戏策划师知晓npc的位置，但这个位置对程序开发者或对客户端程序而言还是未知的。为了后续客户端程序能够获取到npc在游戏场景中的位置，需要对npc在游戏场景中的位置做一些预处理工作，具体是从服务器端读取npc在游戏场景中的位置，然后，按照某种映射关系，将npc的类型和该npc在游戏场景中的位置保存于游戏客户端，如此，后续可以根据某个npc的类型，从服务器端或游戏客户端本地获取该npc在游戏场景中的位置。在本申请实施例中，一个npc在游戏场景中的位置由一个四元数表示，即(x，y，z，w)，其中，(x，y，z)是该npc在游戏场景中相对于三维坐标系中原点o(0，0，0)的坐标，w为该npc所在游戏场景的场景编号或标识。

考虑到哈希表在查找方面具有速度快的优势，在本申请实施例中，可以创建哈希表，其中，哈希表以每个npc的类型为关键码构成一键-值(key-value)对的键(key)、以每个npc在游戏场景中的位置构成键-值对的值(value)来存储每个npc在游戏场景中的位置。后续查询时，只要以npc的类型为关键码，即可查询到哈希值对应的存储单元中的值即该npc在游戏场景中的位置。

虽然哈希表具有查询速度快的优势，然而，哈希表也存在哈希冲突，即不同的关键码经哈希运算得到同一哈希值这一天然缺陷，因此，为了减少这种哈希冲突的概率，作为本申请一个实施例，前述创建哈希表可通过如附图3示例的步骤s301至步骤s305实现，说明如下：

步骤s301：基于初始哈希函数对x个关键码分别进行哈希运算得到x个关键码各个关键码对应的第一哈希值。

在本申请实施例中，基于初始哈希函数，对x个关键码分别进行哈希运算，得到x个关键码各个关键码对应的第一哈希值，此处，关键码是npc的类型或者该npc的类型转换而来所对应的一串字符。

步骤s302：根据存在冲突的第一哈希值的关键码的数量y和关键码的数量x，确定关键码的第一哈希值的冲突概率p，其中，x和y为正整数。

哈希值冲突或哈希冲突的概念如前所述，在本申请实施例中，记关键码的数量为x、存在冲突的第一哈希值的关键码数量为y，则关键码的第一哈希值的冲突概率p＝y/x。例如，若所有关键码数量为15000，仅有关键码“edsxu”、“fexyz”和“byduk”(“edsxu”、“fexyz”和“byduk”可认为是某三个npc的类型对应的三串字符)的第一哈希值相同，存在冲突，则这组关键码的第一哈希值的冲突概率p＝3/15000＝0.02％。

步骤s303：根据第一哈希值的冲突概率修改初始哈希函数，得到确定哈希函数。

作为本申请一个实施例，根据关键码的第一哈希值的冲突概率修改初始哈希函数，得到确定哈希函数可以是：1)设置哈希值冲突概率的最大允许值pm；2)根据哈希值冲突概率的最大允许值pm和关键码的第一哈希值的冲突概率p，不断调整初始哈希函数的参数，用这些不同参数的哈希函数计算哈希值的冲突概率；3)当哈希值的冲突概率p降低为小于哈希值冲突概率的最大允许值pm时，将此时的参数作为确定哈希函数的参数，得到确定哈希函数。

步骤s304：基于确定哈希函数分别对x个关键码进行哈希运算，得到x个关键码各个关键码对应的第二哈希值。

当经步骤s303得到确定哈希函数后，采用确定哈希函数分别对x个关键码进行哈希运算得到x个关键码各个关键码对应的第二哈希值。

步骤s305：根据第二哈希值构建红黑树，并基于红黑树构建对应的哈希表。

本申请一个或多个实施例中,红黑树是一个自平衡二叉查找树，平衡二叉树的最小高度和最大高度的差值的绝对值不超过1。红黑树处于空状态时，树中的根节点和根节点的子节点均为空节点。将x个关键码作为键(key)，x个关键码的第二哈希值作为值(value)的存储地址构建红黑树，在红黑树构建过程中，为了维护红黑树的平衡性，会对树的节点进行颜色变换和旋转操作。当红黑树表示构建完成后，完成一次红黑树表示的遍历，根据遍历得到的红黑树表示中各节点的信息创建哈希表。

相应于经上述步骤s301至步骤s305创建的哈希表，作为本申请一个实施例，步骤s202即根据目标npc的索引信息，获取目标npc在游戏场景中的位置可以是：以目标npc的类型为关键码，采用第二哈希值在哈希表上进行索引；若命中哈希表，则从第二哈希值对应的存储单元读取目标npc在游戏场景中的位置。此处需要说明的是，本实施例中“以目标npc的类型为关键码，采用第二哈希值在哈希表上进行索引”，其第二哈希值是以目标npc的类型为关键码，经前述实施例中创建哈希表时所用的确定哈希函数进行哈希运算后得到。

作为本申请另一实施例，前述创建哈希表可通过如附图4示例的步骤s401至步骤s404实现，说明如下：

步骤s401：从内存划出第一表项存储空间，其中，第一表项存储空间包括若干地址空间。

在本申请实施例中，第一表项存储空间的每个地址空间设置并维护一指示该地址空间空满程度的空满标识，例如，为每个地址空间设置一个变量作为空满标识，每当该地址空间存储一个信息后，变量即增1，因此，一个地址空间的空满标识的值越小，表示该地址空间的存储空间越富余。

步骤s402：构建至少两个哈希函数，并利用至少两个哈希函数对关键码进行哈希计算，得到每个关键码对应的至少两个哈希值。

如前所述，关键码即npc的类型或者该npc的类型转换而来所对应的一串字符。在本实施例中，对于每个关键码，使用至少两个哈希函数对其进行哈希计算，计算所得至少两个哈希值，该至少两个哈希值又至少对应两个不同的地址空间。

步骤s403：比较至少两个哈希值对应的地址空间的空满程度，将待存储信息存储至第一表项存储空间中地址空间中存储空间最富余的地址空间。

如前所述，一个地址空间的空满标识的值越小，表示该地址空间的存储空间越富余，因此，比较至少两个哈希值对应的地址空间的空满程度，可以比较该至少两个哈希值对应的地址空间的空满标识的值大小，若某个地址空间的空满标识的值较小，则应该将待存储信息存储至该地址空间。

步骤s404：若至少两个哈希值对应的地址空间的均已存满，则将待存储信息存储至第二表项存储空间。

如前所述，第一表项存储空间的每个地址空间维护了一个指示该地址空间空满程度的空满标识，因此，在比较至少两个哈希值对应的地址空间的空满程度时，可以查看该至少两个地址空间的空满标识。若该至少两个地址空间均未存满，则将待存储信息存储至第一表项存储空间中地址空间中存储空间最富余的地址空间。若至少两个哈希值对应的地址空间的均已存满，则将待存储信息存储至第二表项存储空间。在本申请实施例中，可以根据需要，第二表项存储空间也可以包含若干地址空间。

显然，在将待存储信息存储至第一表项存储空间中地址空间中存储空间最富余的地址空间，可以减小哈希冲突的概率，而采取至少两种哈希函数来计算存储地址，可以节省存储资源。

相应于经上述步骤s401至步骤s404创建的哈希表，作为本申请一个实施例，步骤s202即根据目标npc的索引信息，获取目标npc在游戏场景中的位置可以是：以目标npc的类型为关键码，采用至少两个哈希函数对关键码并行进行哈希计算得到至少两个哈希值；以至少两个哈希值在哈希表上进行索引；若命中哈希表，则从命中哈希表时所采用的哈希值对应的存储单元读取目标npc在游戏场景中的位置。需要说明的是，本实施例的“采用至少两个哈希函数对关键码并行进行哈希计算得到至少两个哈希值”，其中的至少两个哈希函数是分别与前述实施例步骤s402中构建的至少两个哈希函数相同的哈希函数。

步骤s203，根据虚拟角色当前所在游戏场景中的位置与目标npc在游戏场景中的位置，选用预先生成的连通图作为对目标npc进行寻路的网格化地图。

在本申请实施例中，虚拟角色为游戏玩家通过客户端进行控制的游戏角色，其能够反映游戏玩家的意志，例如，对目标npc进行寻路、与目标npc交互，等等，而连通图作为对目标npc进行寻路的网格化地图，可以预先生成，方法是采用主干道配置方式和/或网格导航算法实现，即附图2示例的方法还包括：采用主干道配置方式和/或网格导航算法，生成连通图，具体而言，可通过附图5示例的步骤s501至s504实现，说明如下：

步骤s501：从游戏场景所包含的区域生成多个凸多边形的网格。

寻路，本质是从区域的一个“地块”寻到另一个与该“地块”连通的“地块”的过程，最简单的寻路过程就是假设从“地块”的中心点出发，按照网格导航算法计算出来的路线，走到另一个连通“地块”的中心点，而这些“地块”在游戏场景中可以视为网格。为了简化路径算法，一般是将游戏场景所包含的区域按照凸多边形来划分“地块”，即，将游戏场景所包含的区域划分为多个凸多边形网格。如附图6所示，是将游戏场景所包含的区域划分为多个凸多边形网格后，连通各个网格的中心点时的寻路示意图。

考虑到本申请实施例的网格导航算法，其网格模型为三角形，并且，三角形为最简单的凸多边形，本申请在实现从游戏场景所包含的区域生成多个凸多边形的网格时，具体是：遍历区域的轮廓的所有边，以每组三个点为三角形的顶点构成一个有效内部三角形块，然后，再将多个有效内部三角形块尽可能合并成一个最大面积的凸多边形，直至所有有效内部三角形块都合并成多个凸多边形的网格。在本申请实施例中，上述遍历区域的轮廓的所有边，以每组三个点为三角形的顶点构成一个有效内部三角形块，实际是对区域进行三角形网格的划分，而一个三角形网格或三角形块是否是有效的内部三角形块，一个基本判断方法是以其中一个顶点为端点，顺着区域的相邻边界发出两条射线，若分割的终点位于区域的内部角中，则此时可以分割出一个有效内部三角形块，否则，就不是有效内部三角形块。如附图7a所示，是从顶点a发出的射线ac，交区域的边界于终点c，且终点c位于区域的内部角，因此，分割出来一个有效内部三角形块，而附图7b则是一个无效分割的示意图。

需要说明的是，在上述实施例中，之所以要将多个有效内部三角形块尽可能合并成一个最大面积的凸多边形，是考虑到一方面，对区域做过多的分割有时并无必要，另一方面，在寻路的精度能够达到预设阈值的前提下，需要考虑算法的效率问题，而将多个有效内部三角形块尽可能合并成一个最大面积的凸多边形，可以减少区域内凸多边形的数量，从而减少后续寻路时的计算量。至于合并的具体方法，可以是先找到所有能够被合并的有效内部三角形块，然后从中选取两个有最长公共边的有效内部三角形块合并，重复上述步骤，直至再没有可合并的多边形。此处需要说明的是，合并后的图形要求仍然是一个凸多边形，其判断方法是共享顶点的两个三角形在合并后，若能形成内部锐角，则合并后的多边形仍然会是凸多边形。

步骤s502：采用碰撞检测算法检测凸多边形的网格中是否存在能够连通的网格。

具体地，采用碰撞检测算法检测凸多边形的网格中是否存在能够连通的网格可通过如下步骤s5021至步骤s5024实现：

步骤s5021：将碰撞检测模型从当前所在网格的表面抬升，使其距离当前网格的表面至预设高度。

在本申请实施例中，碰撞检测模型是碰撞检测算法中用于检测两个网格是否连通的模型。为了与游戏场景中的“人”这一常见角色最大程度地相似，可以将该模型拟合为一个上窄下宽的形状，例如，三角形，即，在本申请实施例中，碰撞检测模型可以是一个三角形。另一方面，考虑到游戏场景中一些相对网格比较低矮的凸起或比较浅显的凹陷(如附图8a)，在实际寻路时角色是可以跨越过去的，不应该成为两个网格不连通的障碍，因此，在碰撞检测算法中，可以将碰撞检测模型从当前所在网格的表面抬升，使其距离当前网格的表面至预设高度，以避免将实际可以连通的网格误判为不连通。如附图8b所示，是将碰撞检测模型从当前所在网格的表面抬升预设高度的示意图，图中标识hs的部分就是预设高度，也是碰撞检测算法为当前游戏场景设置的所谓最大爬坡高度scrambleheight。

步骤s5022：向碰撞检测模型当前所在网格的任意一个邻居网格移动已抬升碰撞检测模型。

步骤s5023：判断已抬升碰撞检测模型是否与邻居网格发生碰撞。

如附图9所示，当邻居网格的高度不高于碰撞检测模型当前所在网格的高度加上预设高度，已抬升碰撞检测模型从当前所在网格移动至邻居网格时才可能翻越过去而不发生碰撞，与此同时，当邻居网格的高度不低于碰撞检测模型当前所在网格的高度减去预设高度，才不至于已抬升碰撞检测模型所处高度与邻居网格的高度相差太大，导致已抬升碰撞检测模型也不能跨越过去。因此，作为本申请一个实施例，判断已抬升碰撞检测模型是否与邻居网格发生碰撞可以是：获取碰撞检测模型当前所在网格的高度hc和邻居网格的高度hn；比较hn与hc-hs以及hn与hc+hs的大小；若hn在[hc-hs，hc+hs]，则确定已抬升碰撞检测模型不会与邻居网格发生碰撞，否则，确定已抬升碰撞检测模型会与邻居网格发生碰撞，此处，hs为前述实施例提及的预设高度，即碰撞检测算法为当前游戏场景设置的最大爬坡高度。

上述实施例中，假设邻居网格是没有孔的，然而，在实际游戏场景中网格可能带有孔，在这种情况下，作为本申请另一实施例，判断已抬升碰撞检测模型是否与邻居网格发生碰撞可以是：若邻居网格包含一孔状空间，则比较孔状空间最大位置的尺寸hmax与hm+hs的大小；若hmax不小于hm+hs，则确定已抬升碰撞检测模型不会与邻居网格发生碰撞，否则，确定已抬升碰撞检测模型会与邻居网格发生碰撞，此处，hm为碰撞检测模型的高度，hs为前述实施例提及的预设高度，即碰撞检测算法为当前游戏场景设置的最大爬坡高度。如附图10a所示，是hmax不小于hm+hs时，已抬升碰撞检测模型从当前所在网格移动至邻居网格移动后不与邻居网格发生碰撞的示意图，而附图10b是hmax小于hm+hs时，已抬升碰撞检测模型从当前所在网格移动至邻居网格移动后将与邻居网格发生碰撞的示意图。

步骤s5024：若已抬升碰撞检测模型与邻居网格发生碰撞，则确定碰撞检测模型当前所在网格与邻居网格不连通，否则，确定碰撞检测模型当前所在网格与邻居网格连通。

步骤s503：将凸多边形的网格中符合预设条件的网格配置为主干道中能够连通的网格。

考虑到一些游戏场景中，虚拟角色在寻路时是可以跨越某些凸起或凹陷等特殊地形的，但在碰撞检测时却将其确定为障碍物而不能跨越，此外，网格导航算法的最短路径特性，导致一些玩家寻路时能够“抄近道”。为了防止上述情形，可以将凸多边形的网格中符合预设条件的网格配置为主干道中能够连通的网格，其中，符合预设条件的网格包括游戏场景中实际可通达但碰撞检测确定为不可通达的网格以及策划师策划好、并且有利于提升玩家游戏体验的路径所包含的网格，等等，这些符合预设条件的网格可配置成可连通的网格，这些网格连通后即成为主干道。

步骤s504：记录网格中能够连通的网格的连通信息，形成第一连通图或第二连通图，其中，连通信息包括可连通网格中任意一个网格的位置信息、可连通网格中任意一个网格所在游戏场景的标识以及可连通网格中任意一个网格的邻居网格的标识。

上述记录网格中能够连通的网格的连通信息，形成第一连通图或第二连通图包括将经步骤s503配置为主干道中能够连通的网格的连通信息记录下来，形成第一连通图，以及将经步骤s502检测能够连通的网格的连通信息记录下来，形成第二连通图。这些连通信息包括可连通网格中任意一个网格的位置信息、可连通网格中任意一个网格所在游戏场景的标识以及可连通网格中任意一个网格的邻居网格的标识，等等，其中，可连通网格中任意一个网格所在游戏场景的标识以及可连通网格中任意一个网格的邻居网格的标识，在网格导航算法中也被称为路点信息。路点信息在网格导航算法中是一个数据结构，其包含edge、waypoint、waypointset、connect和chunk等成员，其中，edge为基本凸多边形网格，可能是一个三角形，等等，waypoint即由基本凸多边形网格合并后的凸多边形，由此说明，一个edge必然属于某个waypoint，而该edge的外侧可能具有其他的waypoint作为该edge所属waypoint的邻居waypoint，每个waypoint都有各自的标识(id)，因此，某个waypoint的邻居waypoint可通过该邻居waypoint的标识予以记录，waypointset是相互连通的waypoint组成的集合，connect是与当前waypointset连通的其他waypointset，而chunk是waypointset的集合，chunk是一个容器，一个chunk内的waypointset可能是连通的或不连通的，某个waypointset只属于一个chunk，因此，若生成的waypointset刚好跨过多个chunk，该waypointset可能被拆分，并标明某个边临近chunk；若两个chunk真的连通，则意味着可以从一个chunk包含的waypoint，寻路到与之连通的chunk包含waypoint。当生成连通图，意味着路点信息随之生成，虚拟角色当前所在游戏场景中的位置也能够根据这些路点信息确定。

需要说明的是，与第二连通图是通过网格导航算法生成不同，由于第一连通图是采用主干道配置方式生成，随时都有增加主干道或者查询主干道上的网格的操作，为了提高这些操作的效率，在本申请实施例中，第一连通图中每个网格中心点的位置以及每个网格中心点与其他网格中心点的连通关系采用四叉树的数据结构存储。

在采用主干道配置方式和/或网格导航算法，生成连通图以及获取了目标npc在游戏场景中的位置后，根据虚拟角色当前所在游戏场景中的位置与目标npc在游戏场景中的位置，选用预先生成的连通图作为对目标npc进行寻路的网格化地图可通过如下步骤s1至s3进行：

步骤s1：在确定能够对目标npc进行同一场景寻路或跨场景寻路后，查询起点集合和终点集合，其中，起点集合包括第一连通图中距离虚拟角色当前所在游戏中的位置最近的网格中心点，终点集合包括第一连通图中距离目标npc在游戏场景中的位置最近的网格中心点。

如前所述，一个npc的类型与该npc所在游戏场景的标识存在映射关系，因此，可以根据目标npc的类型，获取目标npc所在游戏场景的标识，而虚拟角色的属性本身包括虚拟角色当前所在游戏场景的标识。因此，如何确定能够对目标npc进行同一场景寻路或跨场景寻路的具体技术方案可以是：在查询起点集合和终点集合之前，根据虚拟角色当前所在游戏场景的标识和目标npc所在游戏场景的标识，确定虚拟角色与目标npc是否处于同一场景；若虚拟角色与目标npc不是处于同一场景，则判断是否能够对目标npc进行跨场景寻路。

上述判断是否能够对目标npc进行跨场景寻路，具体而言可以是：根据虚拟角色当前所在游戏场景中的位置与目标npc在游戏场景中的位置，查询虚拟角色和/或目标npc附近的跳转点；若虚拟角色和/或目标npc附近的跳转点的属性信息表明虚拟角色和/或目标npc附近存在能够实现场景连通的跳转点，则确定能够对目标npc进行跨场景寻路。

在上述本申请实施例中，跳转点是为虚拟角色能够跨场景寻路而设置，一个跳转点主要包含如下三个属性：id、pos、des，其中，id是跳转点所在游戏场景的唯一标识，pos为跳转点位于id1标识的游戏场景中的位置，des为跳转的目标地点，而des又包含id-i和pos-i两个子属性，其中，id-i是跳转点的目标地点所属游戏场景的唯一标识，pos-i是目标地点在id-i标识的游戏场景中的位置。需要说明的是，一个跳转点可以具有多个不同的目标地点，表明虚拟角色在寻路时可以从当前位置跳转到不同的游戏场景的不同位置。在上述判断是否能够对目标npc进行跨场景寻路的实施例中，若虚拟角色附近的跳转点，其目标地点的id-i表明目标地点所属游戏场景与目标npc所在游戏场景是同一游戏场景，目标地点的pos-i表明目标地点在id-i标识的游戏场景中的位置与目标npc在其所属游戏场景中的位置是同一位置，则确定能够对目标npc进行跨场景寻路。

步骤s2：若起点集合存在能够与终点集合中网格中心点连通的网格中心点，则选用第一连通图作为对目标npc进行寻路的网格化地图。

由于起点集合包括第一连通图中距离虚拟角色当前所在游戏中的位置最近的网格中心点，终点集合包括第一连通图中距离目标npc在游戏场景中的位置最近的网格中心点，因此，若起点集合存在能够与终点集合中网格中心点连通的网格中心点，则虚拟角色可以先寻路到距离虚拟角色当前所在游戏中的位置最近的网格中心点，再根据起点集合中网格中心点与终点集合中网格中心点的连通关系，寻路到目标npc。需要说明的是，此处的第一连通图是前述实施例中采用主干道配置方式生成的连通图，包括对游戏场景中的网格进行主干道配置后所得游戏场景中网格之间的连通信息。在起点集合存在能够与终点集合中网格中心点连通的网格中心点时，选用第一连通图作为对目标npc进行寻路的网格化地图，表明优先使用配置的主干道对目标npc进行寻路。

步骤s3：若起点集合不存在能够与终点集合中网格中心点连通的网格中心点，则选用第二连通图作为对目标npc进行寻路的网格化地图。

此处的第二连通图是前述实施例中采用网格导航算法生成的连通图，包括采用网格导航算法计算所得游戏场景中网格之间的连通信息。

附图11给出了根据虚拟角色当前所在游戏场景中的位置与目标npc在游戏场景中的位置，选用预先生成的连通图作为对目标npc进行寻路的网格化地图的完整流程。

步骤s204，基于经步骤s203选用的网格化地图，对目标npc寻路。

在本申请实施例中，对目标npc寻路可以是采用最短路径算法对目标npc寻路，而最短路径算法可以是dijkstra算法、floyd算法和启发式搜索算法等算法中的一种或几种的结合，例如，可以使用启发式搜索算法中的a*算法对目标npc进行寻路。作为本申请一个实施例，基于经步骤s203选用的网格化地图，采用最短路径算法对目标npc寻路可以通过如下步骤s2041至步骤s2046实现：

s2041：初始化目标节点即目标npc所在网格中心点、a*算法的开放表和闭合表，将起始节点即虚拟角色当前所在网格中心点放入开放表，将闭合表置空，在本申请实施例中，开放表可用于存储遍历的所有节点，闭合表可用于存储已经找到的目标节点，节点也即网格化地图的网格中心点；

s2042：判断开放表是否为空，若开放表为空，则结束算法，否则，从开放表的表头取一个节点n；

s2043：判断节点n是否为目标节点，若是，则进入步骤s2044，否则，结束算法；

s2044：将节点n的所有后续节点展开以形成直相关子节点，判断这些直相关子节点是否在闭合表中，若是，则进入步骤s2045，否则，将直相关子节点放入开放表中；

s2045：将节点n放入闭合表中，同时采用a*算法的代价估计函数f(n)计算节点n的每一个后续节点的代价估计值f’(n)；

s2046：将开放表中的代价估计值f’(n)进行最小堆排序，例如最小二叉堆排序，将代价估计值f’(n)最小的节点放在开放表的表头，返回步骤s2042循环上述步骤，直至目标节点出现在闭合表中或开放表为空。

上述本申请实施例提供的对非玩家角色寻路的方法，由于只需要触发一次对目标非玩家角色npc进行寻路的寻路请求，即可开启后续的获取目标npc在游戏场景中的位置、选用预先生成的连通图作为对目标npc进行寻路的网格化地图以及基于预先生成的连通图，对目标npc寻路，无需玩家手动一步一步寻路亦可以找到目标npc，因此，相对于现有技术，本申请实施例提供的技术方案对非玩家角色寻路的方法效率高，尤其是场景复杂的游戏，能够明显节省新手玩家的时间成本。

为便于更好的实施本申请实施例的对非玩家角色寻路的方法，本申请实施例还提供一种对非玩家角色寻路的装置。请参阅12，为本申请实施例提供的对非玩家角色寻路的装置的结构示意图。该对非玩家角色寻路的装置可以包括接收模块1201、获取模块1202、选用模块1203和寻路模块1204，其中：

接收模块1201，用于接收对目标非玩家角色npc进行寻路的寻路请求，其中，寻路请求包括目标npc的索引信息；

获取模块1202，用于根据目标npc的索引信息，获取目标npc在游戏场景中的位置；

选用模块1203，用于根据虚拟角色当前所在游戏场景中的位置与目标npc在游戏场景中的位置，选用预先生成的连通图作为对目标npc进行寻路的网格化地图；

寻路模块1204，用于基于网格化地图，对目标npc寻路。

请参阅13，为本申请实施例提供的对非玩家角色寻路的装置的另一结构示意图。图13与图12在区别在于：目标npc的索引信息包括目标npc的类型，该对非玩家角色寻路的装置还包括创建模块1301，用于创建哈希表，其中，哈希表以每个npc的类型为关键码构成一键-值对的键、以每个npc在游戏场景中的位置构成键-值对的值来存储每个npc在游戏场景中的位置。

可选的，创建模块1301具体用于基于初始哈希函数对x个关键码分别进行哈希运算得到x个关键码各个关键码对应的第一哈希值，根据存在冲突的第一哈希值的关键码的数量y和关键码的数量x，确定关键码的第一哈希值的冲突概率p，根据第一哈希值的冲突概率修改初始哈希函数，得到确定哈希函数，基于确定哈希函数分别对x个关键码进行哈希运算得到x个关键码各个关键码对应的第二哈希值，根据第二哈希值构建红黑树，并基于红黑树构建对应的哈希表，其中，x和y为正整数；相应地，获取模块1202具体用于以目标npc的类型为关键码，采用第二哈希值在创建模块1301创建的哈希表上进行索引，若命中哈希表，则从第二哈希值对应的存储单元读取目标npc在游戏场景中的位置。

可选的，创建模块1301具体用于从内存划出第一表项存储空间构建至少两个哈希函数，并利用至少两个哈希函数对关键码进行哈希计算，得到每个关键码对应的至少两个哈希值，比较至少两个哈希值对应的地址空间的空满程度，将待存储信息存储至地址空间中存储空间最富余的地址空间，若至少两个哈希值对应的地址空间均已存满，则将待存储信息存储至第二表项存储空间，其中，第一表项存储空间包括若干地址空间；相应地，获取模块1202具体用于以目标npc的类型为关键码，采用至少两个哈希函数对关键码并行进行哈希计算得到至少两个哈希值，以至少两个哈希值在创建模块1301创建的哈希表上进行索引，若命中哈希表，则从命中哈希表时所采用的哈希值对应的存储单元读取目标npc在游戏场景中的位置。

请参阅14，为本申请实施例提供的对非玩家角色寻路的装置的另一结构示意图。图14与图12在区别在于：该对非玩家角色寻路的装置还包括连通图生成模块1401，用于采用主干道配置方式和/或网格导航算法，生成连通图。

可选的，连通图生成模块1401具体用于从游戏场景所包含的区域生成多个凸多边形的网格，采用碰撞检测算法检测凸多边形的网格中是否存在能够连通的网格，将凸多边形的网格中符合预设条件的网格配置为主干道中能够连通的网格，记录网格中能够连通的网格的连通信息，形成第一连通图或第二连通图，其中，连通信息包括可连通网格中任意一个网格的位置信息、可连通网格中任意一个网格所在游戏场景的标识以及可连通网格中任意一个网格的邻居网格的标识。

可选的，上述从游戏场景所包含的区域生成多个凸多边形的网格可以是：遍历区域的轮廓的所有边，以每组三个点为三角形的顶点构成一个有效内部三角形块，将多个有效内部三角形块尽可能合并成一个最大面积的凸多边形，直至所有的有效内部三角形块都合并成多个凸多边形的网格。

可选的，上述采用碰撞检测算法检测网格中是否存在能够连通的网格可以是：将碰撞检测模型从当前所在网格的表面抬升，使其距离当前网格的表面至预设高度，向碰撞检测模型当前所在网格的任意一个邻居网格移动已抬升碰撞检测模型，判断已抬升碰撞检测模型是否与邻居网格发生碰撞，若已抬升碰撞检测模型与邻居网格发生碰撞，则确定碰撞检测模型当前所在网格与邻居网格不连通，否则，确定碰撞检测模型当前所在网格与邻居网格连通。

可选的，上述判断已抬升碰撞检测模型是否与邻居网格发生碰撞可以是：获取碰撞检测模型当前所在网格的高度hc和邻居网格的高度hn；比较hn与hc-hs以及hn与hc+hs的大小，若hn在[hc-hs，hc+hs]，则确定已抬升碰撞检测模型不会与邻居网格发生碰撞，否则，确定已抬升碰撞检测模型会与邻居网格发生碰撞，其中，hs为预设高度。

可选的，上述判断已抬升碰撞检测模型是否与邻居网格发生碰撞可以是：若邻居网格包含一孔状空间，则比较孔状空间最大位置的尺寸hmax与hm+hs的大小，若hmax不小于hm+hs，则确定已抬升碰撞检测模型不会与邻居网格发生碰撞，否则，确定已抬升碰撞检测模型会与邻居网格发生碰撞，其中，hm为碰撞检测模型的高度，hs为预设高度。

请参阅15，为本申请实施例提供的对非玩家角色寻路的装置的另一结构示意图。图15与图12在区别在于：该对非玩家角色寻路的装置还包括标识获取模块1501、确定模块1502和判断模块1503，其中：

标识获取模块1501，用于根据目标npc的类型，获取目标npc所在游戏场景的标识；

确定模块1502，用于在查询起点集合和终点集合之前，根据虚拟角色当前所在游戏场景的标识和目标npc所在游戏场景的标识，确定虚拟角色与目标npc是否处于同一场景；

判断模块1503，用于若虚拟角色与目标npc不是处于同一场景，则判断是否能够对目标npc进行跨场景寻路。

可选的，上述判断模块1503具体用于根据虚拟角色当前所在游戏场景中的位置与目标npc在游戏场景中的位置，查询虚拟角色和/或目标npc附近的跳转点，若虚拟角色和/或目标npc附近的跳转点的属性信息表明玩家和/或目标npc附近存在能够实现场景连通的跳转点，则确定能够对目标npc进行跨场景寻路。

可选的，上述连通图包括第一连通图和第二连通图，第一连通图包括对游戏场景中的网格进行主干道配置后所得游戏场景中网格之间的连通信息，第二连通图包括采用网格导航算法计算所得游戏场景中网格之间的连通信息，选用模块1203具体用于在确定能够对目标npc进行同一场景寻路或跨场景寻路后，查询起点集合和所述终点集合，若起点集合存在能够与终点集合中网格中心点连通的网格中心点，则选用第一连通图作为对目标npc进行寻路的网格化地图，若起点集合不存在能够与终点集合中网格中心点连通的网格中心点，则选用第二连通图作为对目标npc进行寻路的网格化地图，其中，起点集合包括第一连通图中距离玩家当前所在游戏中的位置最近的网格中心点，终点集合包括第一连通图中距离目标npc在游戏场景中的位置最近的网格中心点。

可选的，上述第一连通图中每个网格中心点的位置以及每个网格中心点与其他网格中心点的连通关系采用四叉树的数据结构存储。

上述所有的技术方案，可以采用任意结合形成本申请的可选实施例，在此不再一一赘述。

本申请实施例提供的对非玩家角色寻路的装置，由于只需要触发一次对目标非玩家角色npc进行寻路的寻路请求，即可开启后续的获取目标npc在游戏场景中的位置、选用预先生成的连通图作为对目标npc进行寻路的网格化地图以及基于预先生成的连通图，对目标npc寻路，无需玩家手动一步一步寻路亦可以找到目标npc，因此，相对于现有技术，本申请实施例提供的技术方案对非玩家角色寻路的方法效率高，尤其是场景复杂的游戏，能够明显节省新手玩家的时间成本。

相应的，本申请实施例还提供一种计算机设备，该计算机设备可以为终端或者服务器，该终端可以为智能手机、平板电脑、笔记本电脑、触控屏幕、游戏机、个人计算机(pc，personalcomputer)、个人数字助理(personaldigitalassistant，pda)等终端设备。如图16所示，图16为本申请实施例提供的计算机设备的结构示意图。该计算机设备400包括有一个或者一个以上处理核心的处理器401、有一个或一个以上计算机可读存储介质的存储器402及存储在存储器402上并可在处理器上运行的计算机程序。其中，处理器401与存储器402电性连接。本领域技术人员可以理解，图中示出的计算机设备结构并不构成对计算机设备的限定，可以包括比图示更多或更少的部件，或者组合某些部件，或者不同的部件布置。

处理器401是计算机设备400的控制中心，利用各种接口和线路连接整个计算机设备400的各个部分，通过运行或加载存储在存储器402内的软件程序和/或模块，以及调用存储在存储器402内的数据，执行计算机设备400的各种功能和处理数据，从而对计算机设备400进行整体监控。

在本申请实施例中，计算机设备400中的处理器401会按照如下的步骤，将一个或一个以上的应用程序的进程对应的指令加载到存储器402中，并由处理器401来运行存储在存储器402中的应用程序，从而实现各种功能：

接收对目标非玩家角色npc进行寻路的寻路请求，其中，寻路请求包括目标npc的索引信息；根据目标npc的索引信息，获取目标npc在游戏场景中的位置；根据虚拟角色当前所在游戏场景中的位置与目标npc在游戏场景中的位置，选用预先生成的连通图作为对目标npc进行寻路的网格化地图；基于网格化地图，对目标npc寻路。

以上各个操作的具体实施可参见前面的实施例，在此不再赘述。

可选的，如图16所示，计算机设备400还包括：触控显示屏403、射频电路404、音频电路405、输入单元406以及电源407。其中，处理器401分别与触控显示屏403、射频电路404、音频电路405、输入单元406以及电源407电性连接。本领域技术人员可以理解，图16中示出的计算机设备结构并不构成对计算机设备的限定，可以包括比图示更多或更少的部件，或者组合某些部件，或者不同的部件布置。

触控显示屏403可用于显示图形用户界面以及接收用户作用于图形用户界面产生的操作指令。触控显示屏403可以包括显示面板和触控面板。其中，显示面板可用于显示由用户输入的信息或提供给用户的信息以及计算机设备的各种图形用户接口，这些图形用户接口可以由图形、文本、图标、视频和其任意组合来构成。可选的，可以采用液晶显示器(lcd，liquidcrystaldisplay)、有机发光二极管(oled，organiclight-emittingdiode)等形式来配置显示面板。触控面板可用于收集用户在其上或附近的触摸操作(比如用户使用手指、触笔等任何适合的物体或附件在触控面板上或在触控面板附近的操作)，并生成相应的操作指令，且操作指令执行对应程序。可选的，触控面板可包括触摸检测装置和触摸控制器两个部分。其中，触摸检测装置检测用户的触摸方位，并检测触摸操作带来的信号，将信号传送给触摸控制器；触摸控制器从触摸检测装置上接收触摸信息，并将它转换成触点坐标，再送给处理器401，并能接收处理器401发来的命令并加以执行。触控面板可覆盖显示面板，当触控面板检测到在其上或附近的触摸操作后，传送给处理器401以确定触摸事件的类型，随后处理器401根据触摸事件的类型在显示面板上提供相应的视觉输出。在本申请实施例中，可以将触控面板与显示面板集成到触控显示屏403而实现输入和输出功能。但是在某些实施例中，触控面板与触控面板可以作为两个独立的部件来实现输入和输出功能。即触控显示屏403也可以作为输入单元406的一部分实现输入功能。

在本申请实施例中，通过处理器401执行游戏应用程序在触控显示屏403上生成图形用户界面，图形用户界面上的虚拟场景中包含至少一个技能控制区域，技能控制区域中包含至少一个技能控件。该触控显示屏403用于呈现图形用户界面以及接收用户作用于图形用户界面产生的操作指令。

射频电路404可用于收发射频信号，以通过无线通信与网络设备或其他计算机设备建立无线通讯，与网络设备或其他计算机设备之间收发信号。

音频电路405可以用于通过扬声器、传声器提供用户与计算机设备之间的音频接口。音频电路405可将接收到的音频数据转换后的电信号，传输到扬声器，由扬声器转换为声音信号输出；另一方面，传声器将收集的声音信号转换为电信号，由音频电路405接收后转换为音频数据，再将音频数据输出处理器401处理后，经射频电路404以发送给比如另一计算机设备，或者将音频数据输出至存储器402以便进一步处理。音频电路405还可能包括耳塞插孔，以提供外设耳机与计算机设备的通信。

输入单元406可用于接收输入的数字、字符信息或用户特征信息(例如指纹、虹膜、面部信息等)，以及产生与用户设置以及功能控制有关的键盘、鼠标、操作杆、光学或者轨迹球信号输入。

电源407用于给计算机设备400的各个部件供电。可选的，电源407可以通过电源管理系统与处理器401逻辑相连，从而通过电源管理系统实现管理充电、放电、以及功耗管理等功能。电源407还可以包括一个或一个以上的直流或交流电源、再充电系统、电源故障检测电路、电源转换器或者逆变器、电源状态指示器等任意组件。

尽管图16中未示出，计算机设备400还可以包括摄像头、传感器、无线保真模块、蓝牙模块等，在此不再赘述。

在上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述的部分，可以参见其他实施例的相关描述。

由上可知，本实施例提供的计算机设备，由于只需要触发一次对目标非玩家角色npc进行寻路的寻路请求，即可开启后续的获取目标npc在游戏场景中的位置、选用预先生成的连通图作为对目标npc进行寻路的网格化地图以及基于预先生成的连通图，对目标npc寻路，无需玩家手动一步一步寻路亦可以找到目标npc，因此，相对于现有技术，本申请实施例提供的技术方案对非玩家角色寻路的方法效率高，尤其是场景复杂的游戏，能够明显节省新手玩家的时间成本。

本领域普通技术人员可以理解，上述实施例的各种方法中的全部或部分步骤可以通过指令来完成，或通过指令控制相关的硬件来完成，该指令可以存储于一计算机可读存储介质中，并由处理器进行加载和执行。

为此，本申请实施例提供一种计算机可读存储介质，其中存储有多条计算机程序，该计算机程序能够被处理器进行加载，以执行本申请实施例所提供的任一种对非玩家角色寻路的方法中的步骤。例如，该计算机程序可以执行如下步骤：

以上各个操作的具体实施可参见前面的实施例，在此不再赘述。

其中，该存储介质可以包括：只读存储器(rom，readonlymemory)、随机存取记忆体(ram，randomaccessmemory)、磁盘或光盘等。

由于该存储介质中所存储的计算机程序，可以执行本申请实施例所提供的任一种对非玩家角色寻路的方法中的步骤，因此，可以实现本申请实施例所提供的任一种对非玩家角色寻路的方法所能实现的有益效果，详见前面的实施例，在此不再赘述。

以上对本申请实施例所提供的一种对非玩家角色寻路的方法、装置、存储介质及计算机设备进行了详细介绍，本文中应用了具体个例对本申请的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本申请的方法及其核心思想；同时，对于本领域的技术人员，依据本申请的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本申请的限制。

起点商标作为专业知识产权交易平台，可以帮助大家解决很多问题，如果大家想要了解更多知产交易信息请点击【在线咨询】或添加微信【19522093243】与客服一对一沟通，为大家解决相关问题。