游戏中虚拟对象的导航方法及电子设备

摘要

本发明提供了一种游戏中虚拟对象的导航方法及电子设备，该方法包括：响应针对于游戏场景中一虚拟对象的目标点设置操作，确定虚拟对象对应的起点和终点；从起点所在的节点开始，对游戏场景中可行走区域的网格节点执行寻路算法，得到起点至终点的目标节点组；基于目标节点组确定导航路径；控制虚拟对象按照导航路径移动至终点。该方式中，可行走区域的叶子节点的网格尺寸大，有效缓解了广阔的可行走区域对应的网格存储空间消耗较大的问题，障碍物区域的叶子节点的网格尺寸小，保证了障碍物区域的精确定位，通过搜路操作确定路径点的方式，能够保证搜索出的导航路径更优选，有效提升了虚拟对象的导航效果。

说明书

技术领域

本发明涉及游戏技术领域，尤其是涉及游戏中虚拟对象的导航方法及电子设备。

背景技术

游戏中的寻路是指让某个角色从场景中的某个位置按照适当的路径自主移动到另一位置。通常，寻路算法可以分为两个步骤：场景地图表示和路径搜索。场景地图表示是把实际的游戏场景抽象成特定的数学模型，用于表征场景结构、障碍物信息和可行区域信息；路径搜索是在此数学模型上执行搜索算法，得到最终的寻路路径。

场景地图表示的方法多种多样，有二维网格法、路径点法、导航网格法等。二维网格法是把场景划分成大小相等的二维网格，每个网格可以被标注为是否是障碍物，寻路路径以网格为单位，绕过被标注为障碍物的网格。路径点法是把场景抽象成一系列的路径点，这些路径点的位置和连通关系可以人为设计，角色寻路时可以按照设计者的想法去移动。导航网格法(Navmesh)用形状大小不一的凸多边形集合表示整个场景，用多边形覆盖场景中的可行走区域，与前两种方法相比，导航网格法更加灵活，对于复杂场景中的寻路，导航网格法往往是首选。

路径搜索算法是基于场景地图的搜索算法，常见的算法有深度优先搜索、广度优先搜索、Dijkstra算法和A*算法等。

游戏场景中有一类空旷的游戏场景，该游戏场景中的可行走区域比障碍物区域广阔的多，并且障碍物区域是动态变化的，即障碍物在游戏场景创建时位置随机。以海域游戏场景为例，该场景为有若干海岛的广阔海域，海域面积宽阔，且岛屿位置随机。

对于这类空旷游戏场景中的寻路，由于障碍物的随机性，无法基于导航网格法预先准备导航网格，并且由于空旷游戏场景中的可行走区域非常广阔，导致计算导航网格的内存开销较大，影响了寻路的计算效率。

发明内容

有鉴于此，本发明的目的在于提供游戏中虚拟对象的导航方法及电子设备，以缓解上述问题。

第一方面，本发明实施例提供了一种游戏中虚拟对象的导航方法，通过电子设备显示游戏场景，该方法包括：响应针对于上述游戏场景中一虚拟对象的目标点设置操作，确定虚拟对象对应的起点和终点；从起点所在的节点开始，对游戏场景中可行走区域的网格节点执行寻路算法，得到起点至终点的目标节点组，其中，所述网格节点为根据所述游戏场景中的障碍物的参数信息对所述游戏场景进行划分以形成的四叉树中的节点，所述游戏场景中障碍物区域的叶子节点的网格尺寸小于可行走区域的部分叶子节点的网格尺寸；基于目标节点组确定起点至终点的导航路径；其中，导航路径由目标节点组中的目标节点对应的路径点组成；控制虚拟对象按照导航路径移动至终点。

其中，上述网格节点为根据所述游戏场景中的障碍物的参数信息对所述游戏场景进行划分以形成的四叉树中的节点，通过如下步骤进行：响应针对于所述游戏场景的网格创建操作，以预设最大网格尺寸为根节点的边长，对所述游戏场景中障碍物的障碍物区域进行四叉树网格划分，直至将所述障碍物区域划分至叶子节点的边长等于预设最小网格尺寸。

进一步的，响应针对于所述游戏场景的网格创建操作，以预设最大网格尺寸为根节点的边长，对所述游戏场景中障碍物的障碍物区域进行四叉树网格划分，直至将所述障碍物区域划分至叶子节点的边长等于预设最小网格尺寸包括：响应针对于初始状态的所述游戏场景的网格创建操作，以预设最大网格尺寸为根节点的边长，对所述游戏场景进行四叉树网格划分，直至划分至四叉树的基准网格；其中，初始状态的所述游戏场景均为可行走区域；响应针对于所述游戏场景的障碍物创建操作，在所述游戏场景中创建障碍物，对所述障碍物的障碍物区域的基准网格进行四叉树网格划分，直至划分至叶子节点的边长等于预设最小网格尺寸；其中，所述基准网格的尺寸介于所述预设最大网格尺寸与所述预设最小网格尺寸之间。

进一步的，该方法还包括：检查边长等于预设最小网格尺寸的叶子节点是否处于障碍物区域内；如果是，标注叶子节点为障碍物区域的叶子节点；如果否，且叶子节点的兄弟节点均不在障碍物区域内，删除叶子节点和叶子节点的兄弟节点。

进一步的，检查边长等于预设最小网格尺寸的叶子节点是否处于障碍物区域内的步骤，包括：检查预设最小网格尺寸的叶子节点的中心点是否在障碍物区域内；如果是，确定叶子节点在障碍物区域内；如果否，对叶子节点进行四叉树划分得到该叶子节点的子节点，如果该叶子节点的子节点的中心点均不在障碍物区域内，确定该叶子节点不在障碍物区域内；如果该叶子节点至少一个子节点的中心点在障碍物区域内，确定该叶子节点在障碍物区域内。

进一步的，上述确定虚拟对象对应的起点和终点的步骤，包括：将虚拟对象当前所在位置的节点和目标点设置操作设置的目标点所在位置的节点，分别划分至最小网格尺寸；将包含虚拟对象的中心点的叶子节点确定为虚拟对象对应的起点；将包含目标点的中心点的叶子节点确定为虚拟对象对应的终点；该方法还包括：当确定出导航路径时，还原虚拟对象当前所在位置的节点为划分至最小网格尺寸前的网格节点，还原目标点所在位置的节点为划分至最小网格尺寸前的网格节点。

进一步的，上述寻路算法为A*搜索算法，所述A*搜索算法通过以下方式确定当前节点的相邻节点：基于游戏场景中可行走区域的四叉树网格节点，在当前节点的邻位方向查找网格尺寸大于或等于当前节点的网格尺寸的节点，得到待定节点组；将待定节点组中的非叶子节点作为中间节点，从中间节点中搜索与当前节点相邻的叶子节点；将搜索到的叶子节点和待定节点组中除中间节点之外的节点作为当前节点的相邻节点。

进一步的，电子设备保存有各个节点的父子关系；上述在当前节点的邻位方向查找网格尺寸大于或等于当前节点的网格尺寸的节点，得到待定节点组的步骤，包括：获取当前节点的父节点和当前节点在父节点中的方位信息；对于每个预先指定的邻位方向，均执行以下操作确定待定节点：如果方位信息对应的方向和邻位方向相反，从当前节点的兄弟节点中确定待定节点；兄弟节点的网格尺寸和当前节点的网格尺寸相等；如果方位信息对应的方向和邻位方向相同，将位于父节点邻位方向的相邻节点作为当前节点的待定节点；相邻节点的网格尺寸大于当前节点的网格尺寸；将各个邻位方向对应的待定节点组成当前节点的待定节点组。

进一步的，上述从中间节点中搜索与当前节点相邻的叶子节点的步骤，包括：在每个预先指定的邻位方向，按照预设的深度优先遍历原则，递归遍历中间节点中与邻位方向反方向的子节点，直到遍历完与邻位方向反方向的叶子节点；从遍历到的叶子节点中确定当前节点相邻的叶子节点。

进一步的，控制虚拟对象按照导航路径移动至终点的步骤，包括：响应于虚拟对象到达导航路径上的路径点事件，从导航路径上读取下一个路径点，将读取到的路径点作为当前路径点，执行以下操作：确定当前路径点与虚拟对象当前位置的相对关系；根据相对关系调整虚拟对象的前进方向和前进速度，以使虚拟对象朝着当前路径点前进。

进一步的，确定当前路径点与虚拟对象当前位置的相对关系的步骤，包括：按照虚拟对象的前进速度确定间隔帧数；按照确定的间隔帧数修正当前路径点与虚拟对象当前位置的相对关系；根据相对关系调整虚拟对象的前进方向和前进速度的步骤，包括：按照修正后的相对关系调整虚拟对象的前进方向和前进速度。

进一步的，该方法还包括：基于虚拟对象的前进速度确定路径点半径；如果虚拟对象当前所在位置与当前路径点的距离小于或等于路径点半径，确定虚拟对象到达当前路径点。

进一步的，基于虚拟对象的前进速度确定路径点半径的步骤，包括：计算路径点半径R＝r+k×s，其中，r为预设基础半径，k为预设修正系数，s为虚拟对象的前进速度。

进一步的，上述游戏场景为海洋场景，虚拟对象为虚拟船只；各个节点的网格尺寸均为2的整数次幂。

第二方面，本发明实施例还提供一种电子设备，包括处理器和存储器，存储器存储有能够被处理器执行的计算机可执行指令，处理器执行计算机可执行指令以实现第一方面任一项的游戏中虚拟对象的导航方法。

第三方面，本发明实施例还提供一种计算机可读存储介质，计算机可读存储介质存储有计算机可执行指令，计算机可执行指令在被处理器调用和执行时，计算机可执行指令促使处理器实现第一方面任一项的游戏中虚拟对象的导航方法。

本发明实施例带来了以下有益效果：

本发明实施例提供了一种游戏中虚拟对象的导航方法及电子设备，响应针对于游戏场景中一虚拟对象的目标点设置操作，确定虚拟对象对应的起点和终点；从起点所在的节点开始，对游戏场景中可行走区域的网格节点执行寻路算法，得到起点至终点的目标节点组；基于目标节点组确定起点至终点的导航路径；其中，导航路径由目标节点组中的目标节点对应的路径点组成；控制虚拟对象按照导航路径移动至终点。该方式中，网格节点为根据游戏场景中的障碍物的参数信息对游戏场景进行划分以形成的四叉树中的节点，而游戏场景中障碍物区域的叶子节点的网格尺寸小于可行走区域的部分叶子节点的网格尺寸，这种可行走区域的叶子节点的网格尺寸较大的划分方式，可以有效缓解广阔的可行走区域对应的网格存储空间消耗较大的问题，同时，障碍物区域的叶子节点的网格尺寸较小的划分方式，还可以保证障碍物区域的精确定位，为搜路操作提供可靠的数据基础；以及，在搜路操作过程中，通过对游戏场景中可行走区域的四叉树网格节点执行寻路算法，得到起点至终点的目标节点组；基于目标节点组确定出导航路径的方式，能够保证搜索出的导航路径更优选，有效提升了虚拟对象的导航效果。

本发明的其他特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。本发明的目的和其他优点在说明书以及附图中所特别指出的结构来实现和获得。

为使本发明的上述目的、特征和优点能更明显易懂，下文特举较佳实施例，并配合所附附图，作详细说明如下。

附图说明

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

图1为本发明实施例提供的一种四叉树示意图；

图2为本发明实施例提供的一种四叉树逻辑图；

图3为本发明实施例提供的一种游戏中虚拟对象的导航方法的流程图；

图4为本发明实施例提供的一种相邻节点的示意图；

图5为本发明实施例提供的另一种相邻节点的示意图；

图6为本发明实施例提供的一种父节点的示意图；

图7为本发明实施例提供的一种节点网格尺寸的示意图；

图8为本发明实施例提供的一种基准网格划分的效果示意图；

图9为本发明实施例提供的一种初始的游戏场景划分至基准网格的示意图；

图10为本发明实施例提供的一种节点的结构示意图；

图11为本发明实施例提供的一种创建障碍物的划分结果示意图；

图12为本发明实施例提供的另一种游戏中虚拟对象的导航方法的流程图；

图13为本发明实施例提供的一种虚拟对象的起点和终点划分至最小层级的示意图；

图14为本发明实施例提供的一种查找北侧相邻节点的流程图；

图15为本发明实施例提供的一种node节点的示意图；

图16为本发明实施例提供的另一种node节点的示意图；

图17为本发明实施例提供的另一种游戏中虚拟对象的导航方法的流程图；

图18为本发明实施例提供的一种修正机制示意图；

图19为本发明实施例提供的一种控制虚拟对象移动的结果示意图；

图20为本发明实施例提供的一种海洋场景示意图；

图21为本发明实施例提供的一种海洋场景中虚拟船只的导航方法的流程图；

图22为本发明实施例提供的一种游戏中虚拟对象的导航装置的示意图；

图23为本发明实施例提供的一种电子设备的示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合附图对本发明的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

寻路是游戏行业中的常见需求，在诸多游戏中都有广泛的应用，如怪物AI(Artificial Intelligence，人工智能)、玩家自动模式、过场动画剧情等。但随着开放世界游戏的发展以及玩家对游戏内容要求的提高，现有的寻路方法无法对大世界、随机生成地形场景给予高效的支持。如何找到一种高效的方法组织场景信息，并给出寻路结果，是游戏业界所关注的问题。

例如，对于游戏场景是一个有若干海岛的广阔海域，海域面积宽阔，且，岛屿位置随机，该场景具有以下特性：一是可行走区域比障碍物区域广阔的多；二是障碍物区域是动态变化的，即障碍物在游戏场景创建时位置随机，因此，现有的寻路方法对于该游戏场景还存在一些问题，如场景地图表示效率低下和不够灵活。

具体地，对于上述游戏场景，如果使用导航网格法，由于岛屿位置的随机性，所以提前准备整个场景的导航网格不可行；虽然采用基于磁贴Tile的导航网格(Tile-NavMesh)可以解决障碍物随机性问题，但是，寻路网格铺满整个场景将导致严重的内存浪费，且，由于障碍物稀疏，很多导航网格并未对规避障碍物做出贡献，进而意味着计算资源的浪费。如果使用二维网格法，则二维网格的大小很难把握，网格尺寸越小，寻路越精准，但是计算开销越大；网格尺寸越大，可以节省资源，但寻路精度将大大降低，导致二维网格法的可行性较低。如果使用路径点法，由于人为布置的路径点难以完全涵盖广阔海面上所有寻路的可能性，因此，路径点法的可行性极低。

因此，对于空旷游戏场景中的寻路，现有的寻路方法大多具有对随机障碍物支持不足、计算效率不高、资源占用较大的缺点，从而降低了用户的游戏体验度。基于此，本发明实施例提供了一种游戏中虚拟对象的导航方法、装置及电子设备，该技术可以应用于多种游戏场景中，尤其可以应用于可行走区域比障碍物区域广阔的多，且障碍物区域是动态变化的空旷游戏场景中。

为便于对本实施例进行理解，下面首先对本发明实施例提供的一种游戏中虚拟对象的导航方法进行详细介绍，该方法可以应用于电子设备，通过电子设备提供图形用户界面，该图形用户界面至少包括游戏场景以及虚拟对象；其中，虚拟对象也可以称为虚拟角色或者游戏角色；游戏场景为空旷游戏场景，如区域广阔、障碍物位置随机且密度稀疏的海洋场景，树木密度稀疏的草原场景，以及存在其它战机障碍的空中场景等。

电子设备控制虚拟对象在空旷游戏场景中移动；其中，电子设备可以是手机、电脑、笔记本和平板电脑等设备；图形用户界面为游戏中当前正展示的场景，包括空旷游戏场景、虚拟对象和各种障碍物等，其中，各种障碍物可以为静态障碍物，即在游戏场景创建时建立的密度稀疏的岛屿障碍物，也可以为动态障碍物，即虚拟对象虚拟场景中移动时，遇到的需要避免碰撞的其余虚拟对象。在实际应用中，电子设备可以通过电子设备中的处理器控制虚拟对象在游戏场景中移动，也可以通过图形用户界面中的移动控件，控制虚拟对象在游戏场景中移动。

此外，电子设备显示的游戏场景以四叉树网格划分方式进行网格划分，其中，四叉树是一种常用于二维空间划分的树状数据结构，其表现上是网格的形式，无论尺寸大小，每个网格都是一个节点，如图1所示，四叉树的每个节点都是正方形，尺寸最大的节点即外面最大的网格称为根节点，如图1中的根节点A，将节点继续划分，可以得到多个子节点，当某个节点细分至没有子节点时，该节点称为叶子节点，即叶子节点对应的正方形里没有其他正方形，如图1中的叶子节点A1。此外，为了便于理解，如图2所示的逻辑图，其中根节点A为逻辑图中最高出的节点，叶子节点A1为逻辑图中下面没有箭头的节点。显然，如果一个大正方形划分出了四个小正方形，那么小正方形的边长一定是大正方形的一半。对应到逻辑图，就是每深一层，边长除以2。

为了便于阐述，将上述游戏场景分为障碍物区域和可行走区域，其中，可行走区域为电子设备控制虚拟对象可以移动的区域，例如，对于海洋场景，障碍物区域包括海洋场景中所有随机位置的岛屿障碍物，可行走区域则为虚拟船只(虚拟对象)避开岛屿障碍物可以移动的区域。通过四叉树网格划分方式分别对障碍物区域和可行走区域进行网格划分，直至得到障碍物区域的叶子节点和可行走区域的叶子节点，且，可行走区域的叶子节点除虚拟对象起点和终点所在的叶子节点之外，其余的叶子节点的网格尺寸大于或等于障碍物区域的叶子节点的网格尺寸，从而通过可行走区域的叶子节点的网格尺寸大的方式，可以有效缓解广阔的可行走区域对应的网格存储空间消耗较大的问题，同时，障碍物区域的叶子节点的网格尺寸小的方式，还可以保证障碍物区域的精确定位，为搜路操作提供可靠的数据基础。此外，四叉树由于划分灵活，因此，可以很好地支持随机生成的障碍物即动态障碍物。

如图3所示的游戏中虚拟对象的导航方法的流程图，该方法的执行主体为电子设备，通过电子设备显示游戏场景，该方法包括以下步骤：

步骤S302，响应针对于游戏场景中一虚拟对象的目标点设置操作，确定虚拟对象对应的起点和终点。

在实际应用中，用户可以在电子设备提供的图形用户界面中，设置虚拟对象的目标点，如果界面是触摸屏，则用户可以通过按压操作完成目标点设置；如果界面是不可触摸的屏幕，则用户还可以通过鼠标和/或键盘的点击操作完成目标点设置。此时，根据虚拟对象当前所在的位置和设置的目标点可以确定虚拟对象的起点和终点。为了便于理解，这里举例说明，对于海洋场景中，玩家控制虚拟船只进入游戏场景后，此时，玩家通过按压或点选海洋场景中的某个位置，即目标点，即可根据虚拟船只的当前位置和目标点，确定该虚拟船只的起点和终点。

步骤S304，从起点所在的节点开始，对游戏场景中可行走区域的网格节点执行寻路算法，得到起点至终点的目标节点组。

其中，本申请实施例中的网格节点为根据游戏场景中的障碍物的参数信息对游戏场景进行划分以形成的四叉树中的节点，该游戏场景中障碍物区域的叶子节点的网格尺寸小于可行走区域的部分叶子节点的网格尺寸。

对于四叉树划分后的游戏场景，上述确定虚拟对象的起点和终点之后，还通过预设的寻路算法执行搜路操作，其中，该寻路算法可以是基于四叉树网格的k近邻算法、A*算法或广度优先搜索算法等，或者是相应算法改进后的算法。其中，以A*算法为例，常规的A*算法主要是将待搜索的区域简化成一个个小方格，如在常规二维网格中，网格大小一致，常常以二维数组进行组织，通过查找当前网格(当前节点)的所有相邻网格，得到当前节点的所有可到达节点，生成一组子节点，直至查找到终点，得到从起点至终点的节点组，如图4所示的相邻节点的示意图，其中，网格A所有相邻的网格包括：网格A相邻的东(East，简称E)、西(West，简称W)、南(South，简称S)、北(North，简称N)、东南(Southeast，简称SE)、东北(Northeast，简称NE)、西南(Southwest，简称SW)和西北(Northwest，简称NW)八个方向的网格，每个网格的尺寸与网格A的尺寸相同。

本发明实施例中，由于采用的是四叉树划分后的游戏场景，因此，当前节点相邻的节点的网格尺寸可能相同，也可能不同，如图5所示，对于节点A所有相邻的节点，其中，北方向的N节点和东方向的E节点的网格尺寸明显大于节点A的网格尺寸，本实施例在常规的A*算法的基础上，对当前节点的可达邻居节点的确定方式进行了修改，以适应四叉树划分后的游戏场景。作为一种可能的实施方式，上述寻路算法在确定当前节点的相邻节点过程中，基于游戏场景中可行走区域的网格节点间的父子关系，确定当前节点的相邻节点，以实现确定出的相邻节点尽可能的为叶子节点，使得目标节点组占用的存储空间较小且基于此目标节点组确定的导航路径更合理。

步骤S306，基于目标节点组确定起点至终点的导航路径；其中，导航路径由目标节点组中的目标节点对应的路径点组成。

上述目标节点组为目标节点组成的一个具有顺序的节点列表，考虑到每个节点均对应于网格区域，面积比较大，因此在确定导航路径过程中，将每个目标节点转换为一个点位置，即路径点，会更利于准确表示导航路径。作为一种可能的实现方式，可以将目标节点的中心点作为该目标节点对应的路径点。当然，也可以将目标节点中的其他点作为该目标节点对应的路径点，本发明实施例对此不进行限制。

上述路径点对应的导航路径为这些路径点的有序连线，该连线的具体方式可以是直线连接或者曲线拟合等方式。

步骤S308，控制虚拟对象按照导航路径移动至终点。

在实际应用中，虚拟对象如虚拟船只的移动过程与人物移动过程并不相同，由于水的阻力、风速和风力等，虚拟船只无法急停、急走或快速转向。因此，在控制虚拟船只按照导航路径移动时，可以不直接设置其位置和速度，而是模拟玩家或用户操作。基于此，可以在图形用户界面中显示针对虚拟对象的指令控件，例如，当用户触发转向指令时，此时通过服务器或电子设备中的处理器控制虚拟对象进行转向操作；当用户触发启动指令或停止指令时，控制虚拟对象进行启动操作或停止操作，从而保证了虚拟对象沿着导航路径移动时自然和不生硬，提高了用户的游戏体验度。

本发明实施例提供了一种游戏中虚拟对象的导航方法，响应针对于游戏场景中一虚拟对象的目标点设置操作，确定虚拟对象对应的起点和终点；从起点所在的节点开始，对游戏场景中可行走区域的网格节点执行寻路算法，得到起点至终点的目标节点组；基于目标节点组确定起点至终点的导航路径；控制虚拟对象按照导航路径移动至终点。该方式中，网格节点为根据游戏场景中的障碍物的参数信息对游戏场景进行划分以形成的四叉树中的节点，而游戏场景中障碍物区域的叶子节点的网格尺寸小于可行走区域的部分叶子节点的网格尺寸，这种可行走区域的叶子节点的网格尺寸较大的划分方式，可以有效缓解广阔的可行走区域对应的网格存储空间消耗较大的问题，同时，障碍物区域的叶子节点的网格尺寸较小的划分方式，还可以保证障碍物区域的精确定位，为搜路操作提供可靠的数据基础；以及，在搜路操作过程中，通过对游戏场景中可行走区域的四叉树网格节点执行寻路算法，得到起点至终点的目标节点组；基于目标节点组确定出导航路径的方式，能够保证搜索出的导航路径更优选，有效提升了虚拟对象的导航效果。

在其中一种可能的实施例中，上述方法还包括游戏场景的划分过程，即上述网格节点为根据游戏场景中的障碍物的参数信息对游戏场景进行划分以形成的四叉树中的节点，通过如下步骤进行：响应针对于所述游戏场景的网格创建操作，以预设最大网格尺寸为根节点的边长，对所述游戏场景中障碍物的障碍物区域进行四叉树网格划分，直至将所述障碍物区域划分至叶子节点的边长等于预设最小网格尺寸。通过这种方式可以保证障碍物区域的网格尺寸比较小，进而使后续确定的障碍物区域更准确。

上述游戏场景的划分过程还可以包括：(1)响应针对于初始状态的游戏场景的网格创建操作，以预设最大网格尺寸为根节点的边长，对游戏场景进行四叉树网格划分，直至划分至四叉树的基准网格；其中，初始状态的游戏场景均为可行走区域；(2)响应针对于游戏场景的障碍物创建操作，在游戏场景中创建障碍物，对障碍物的障碍物区域的基准网格进行四叉树网格划分，直至划分至叶子节点的边长等于预设最小网格尺寸；其中，上述基准网格的尺寸介于预设最大网格尺寸与预设最小网格尺寸之间。

上述网格创建过程分了两步进行，首先对于没有创建障碍物的游戏场景，即初始状态的游戏场景进行网格划分，此时初始状态的游戏场景中所有区域均为可行走区域，因此该阶段的网格划分采用以预设最大网格尺寸为根节点的边长，对游戏场景进行四叉树网格划分，直至划分至四叉树的基准网格。而最大网格至基准网格间的层级数可以视游戏场景的大小而定。

完成上述初始状态的游戏场景中的网格划分之后，如果该游戏场景创建了障碍物，例如在海洋游戏场景中创建了一个或多个岛屿作为障碍物。则继续对障碍物所在位置的障碍物区域进行四叉树网格划分，即对障碍物区域中的基准网格进行四叉树网格划分，直至划分至叶子节点的边长等于预设最小网格尺寸。基准网格至预设最小网格间的层级数可以视障碍物区域大小而定。

上述网格间的层级数用于表征网格的划分次数，划分次数越多，两类网格间的层级数差的越多。比如，最大网格的边长是a，那么次一级网格的边长就是a/2，次次一级网格的边长就是a/2/2，对应到逻辑图就是越往下一层，就再除一个2。那么为了计算方便(为了无论怎么除以2都希望仍然是整数)，就设定a是2的幂次，基于此，本实施例中的预设最大网格尺寸定为2

理论上四叉树是可以无限向下划分的，越划分，最下面的正方形边长就越小。为了控制这个最小边长，引入了最小层级minLevel。对于允许划分到的最小的正方形，m＝minLevel。而上述最小网格尺寸可以是最小层级minLevel对应的尺寸，也可以大于最小层级minLevel对应的尺寸。

上述基准网格对应基准层级baseLevel，所谓基准网格，就是在对障碍物划分之前，预先把所有的正方形都划分到baseLevel，得到一个二维均匀网格，但实际结构是四叉树的网格。换句话说，就是在对障碍物划分之前，先递归划分所有的小正方形，直到所有的叶节点的边长都等于2

由于四叉树的每个节点都是正方形，为了叙述方便，如图6所示，一个父节点的四个子节点根据其空间划分区域，可以分为东北、东南、西北和西南四个节点，其中，东北、东南、西北和西南四个节点称为兄弟节点，即父节点相同的子节点彼此称为兄弟节点。因此，四叉树节点的划分是一个节点生成子节点的过程，四个子节点将父节点所含的二维空间分成四个部分，显然子节点的正方形边长为父节点正方形边长的一半，如图7中根节点A的边长为L，则划分一次之后，得到的子节点A2和叶子节点A1的边长均为L/2，当对子节点A2继续划分后，得到的子节点A21的边长为L/2/2即L/2

例如，对于某个大小为16384×16384的游戏场景，由于16384＝2

为了便于理解，这里举例说明。如图8所示，其中斜线覆盖的网格表示障碍物H。其中，图8中8-a，B和C点所在网格的尺寸较大，如果导航路径为A-C-B，可以看出，导航路径的连线在C点比较陡，转弯角度较大。若沿着此导航路径行驶，虚拟对象的行走过程显然不太自然，较为生硬。图8中8-b则为在8-a基础上进一步划分网格后的结果，同样的障碍物H，基于8-b的网格划分方式此得到的导航路径A-C-B中的C点更靠近障碍物侧了，使得8-b的导航路径A-C-B相较于8-a中的导航路径更平缓，距离更短了。因此，与8-a相比，8-b中虚拟对象的路径明显自然一些。此外，图8中8-c则是在8-b的基础上又进一步进行了网格划分，可行走区域叶子节点的尺寸与障碍物H所在区域的叶子节点的网格尺寸一样，该基于四叉树网格划分方式得到的网格退化为常规的二维网格，此时，通过预设的A*搜路算法对节点进行搜路操作，得到虚拟对象的导航路径为A-C13-C2-C3-B，与8-b相比，8-c虽然提高了网格的划分精度，但是增大了计算量。因此，在网格划分上面，需要根据实际应用的精度需要，合理地划分网格。如图9所示，可行走区域由最初网格尺寸为2

如果障碍物为动态障碍物，则需要基于动态障碍物改变位置后进行网格的划分与恢复，具体包括：将动态障碍物当前位置所在网格划分至最小网格尺寸，将动态障碍物位置改变前所在位置的网格恢复为划分前的尺寸，如恢复至基准网格尺寸。

上述游戏场景中四叉树网格的划分方式，能够在游戏场景中创建障碍物之后，根据创建的障碍物的位置和形状，对障碍物区域的基准网格进行进一步地四叉树网格划分，即以递归的方式将障碍物区域中的基准网格划分至叶子节点，且叶子节点的边长为预设最小网格尺寸即2

在对障碍物区域进行划分后，为了尽可能地保证障碍物区域中网格划分的准确性，上述(2)执行之后，还可以检查障碍物区域对应的网格节点，检查这些网格节点是否确实在障碍物区域中，基于此，上述方法还包括：检查预设最小网格尺寸的叶子节点是否处于障碍物区域内；如果是，则标注该叶子节点为障碍物区域的叶子节点；如果否，且该叶子节点的兄弟节点也均不在障碍物区域内，则删除该叶子节点和叶子节点的兄弟节点，仅保留至该叶子节点的父节点。

作为一种可能的实施方式，检查预设最小网格尺寸的叶子节点是否处于障碍物区域内的步骤，包括：检查预设最小网格尺寸的叶子节点的中心点是否在障碍物区域内；如果是，确定该叶子节点在障碍物区域内；如果否，对该叶子节点进行四叉树划分得到该叶子节点的子节点，如果该叶子节点的子节点的中心点均不在障碍物区域内，确定该叶子节点不在障碍物区域内；如果该叶子节点至少一个子节点的中心点在障碍物区域内，确定该叶子节点在障碍物区域内。

如图10所示，以某一个叶子节点为例，如果叶子节点的中心点O在障碍物区域内，则标注该叶子节点为障碍物区域的叶子节点，默认该叶子节点覆盖障碍物区域中的障碍物；如果该叶子节点的中心点O不在障碍物区域内，则此时还可以进一步对该叶子节点进行四叉树划分，得到该叶子节点的四个子节点，判断该四个子节点的四个中心点X1、X2、X3和X4是否在障碍物区域内，如果X1、X2、X3和X4不在障碍物区域内，即该叶子节点的中心点O和四个子节点的中心点点X1、X2、X3和X4均不在障碍物区域内，则认为该叶子节点未在障碍物区域内，即没有覆盖障碍物；反之，如果X1、X2、X3和X4中有一个点在障碍物区域内，例如点X1在障碍物区域内，中心点O、点X2、X3和X4均不在障碍物区域内，此时，仍判定该叶子节点在障碍物区域内，即该叶子节点覆盖障碍物。如图11所示的为障碍物区域的基准网格进行四叉树网格划分的过程示意图，通过对障碍物区域进行划分，使得障碍物区域中的网格尺寸更小，可以更加精确地定位障碍物的位置，为搜路操作提供可靠的数据基础。

在图3的基础上，本发明实施例还提供了另一种游戏中虚拟对象的导航方法，该方法执行主体为电子设备，重点描述了确定虚拟对象的起点和终点的过程，本实施例以寻路算法为A*搜索算法为例进行说明。如图12所示，该方法包括以下步骤：

步骤S1202，响应针对于游戏场景中一虚拟对象的目标点设置操作，将虚拟对象当前所在位置的节点和目标点设置操作设置的目标点所在位置的节点，分别划分至最小网格尺寸。该最小网格尺寸为预设尺寸，可以是小于基准网格尺寸且大于最小层级对应尺寸间的任意一个值，当然作为一种特例，该最小网格尺寸也可以等于最小层级对应的尺寸。

具体地，如果虚拟对象当前所在位置的节点为一个网格尺寸较大的节点，当进行搜路操作时，以虚拟对象当前所在位置的节点的中心为第一个路径点，此时，第一个路径点(起点)可能距离虚拟对象的实际位置误差较大；同样的，对于上述目标点(也即目标点设置操作设置的终点)，如果目标点所在位置的节点的网格尺寸较大，若以该节点的中心作为终点也可能与目标点设置操作存在一定的误差，从而导致搜路操作得到的导航路径准确性降低，当控制虚拟对象沿着导航路径移动时，可能会出现虚拟对象移动不自然，影响用户体验度。

因此，上述步骤S1202将虚拟对象当前所在位置的节点和目标点设置操作设置的目标点所在位置的节点，分别划分至最小网格尺寸，以提高起点和终点的精度。例如：对于一个大小为1024x1024的节点，无论虚拟船只在该当前所在位置的节点的哪个位置，第一个路径点均为该节点的中心，则可能虚拟船只的实际位置距离该节点的中心很远，导致第一个路径点与虚拟船只所在位置的误差较大，当将该1024x1024的节点划分至预设最小网格尺寸时，如此时节点大小为8x8，显然第一个路径点为该节点的中心与虚拟船只所在位置的误差明显减少了，上述步骤将虚拟对象当前所在位置的叶子节点和目标点所在位置的叶子节点分别划分至预设最小网格尺寸的节点。

为了便于理解，这里举例说明。如图13所示，其中，图13中箭头左边图中虚拟对象当前所在位置为A点，目标点设置操作设置的目标点为B点，其中，A点和B点所在的位置均为一个网格尺寸较大的节点。当进行搜路操作时，第一个路径点为A点所在位置的节点的中心O

步骤S1204，将包含虚拟对象的中心点的叶子节点确定为虚拟对象对应的起点；将包含目标点的中心点的叶子节点确定为虚拟对象对应的终点。

步骤S1206，从起点所在的节点开始，对游戏场景中可行走区域的四叉树网格节点执行预设的A*搜路算法，得到起点至终点的目标节点组。

其中，预设的A*搜路算法通过以下方式确定当前节点的相邻节点：(1)基于游戏场景中可行走区域的四叉树网格节点，在当前节点的邻位方向(可以包括图4所示的八个方向)查找网格尺寸大于或等于当前节点的网格尺寸的节点，得到待定节点组；(2)将待定节点组中的非叶子节点作为中间节点，从中间节点中搜索与当前节点相邻的叶子节点；(3)将搜索到的叶子节点和待定节点组中除中间节点之外的节点作为当前节点的相邻节点.在每个邻位方向重复上述(1)-(3)，从而得到当前节点的所有相邻节点。

需要说明的是，这里预设的A*搜路算法通过在当前节点的邻位查找网格尺寸大于或等于当前节点的网格尺寸的节点，以得到当前节点进行的相邻所有叶子节点，因此，预设的A*搜路算法与常规的A*算法不同，与常规的A*算法相比，预设的A*搜路算法查找到的相邻节点更加精准，从而基于目标节点组确定的导航路径更加精准，提高了虚拟对象躲避障碍物的精度，因此，当控制虚拟对象沿着导航路径移动时，保证了虚拟对象移动方向的正确性，避免了虚拟对象移动至终点之外的位置，给用户造成较差的游戏体验。

在实际应用中，电子设备中保存有各个节点的父子关系，对于当前路径点所在的当前节点，电子设备可以获取当前节点的父节点，由于父节点的四个子节点分别处于不同的方向，因此，当前节点在父节点中的方位信息是固定不变的。基于此，上述在当前节点的邻位方向查找网格尺寸大于或等于当前节点的网格尺寸的节点，得到待定节点组的步骤包括：获取当前节点的父节点和当前节点在父节点中的方位信息；对于当前节点的每个预先指定的邻位方向，均执行以下操作确定待定节点：如果当前节点的方位信息对应的方向与邻位方向相反，则从当前节点的兄弟节点中确定待定节点，由于同一个父节点，因此，此时兄弟节点的网格尺寸和当前节点的网格尺寸相等；如果当前节点的方位信息对应的方向与邻位方向相同，则此时从当前节点的父节点邻位方向的相邻节点作为当前节点的待定节点，由于该相邻节点为父节点的邻居节点，因此，此时邻居节点的网格尺寸大于当前节点的网格尺寸，对于每一个邻位方向，均重复上述过程。最后将各个邻位方向对应的待定节点组成当前节点的待定节点组。为了便于理解，这里以查找尺寸大于或等于当前节点的北侧相邻节点为例说明。如图14所示，该查找过程如下：

步骤S142，判断当前节点是否有父节点，如果没有父节点，那么当前节点是根节点，此时当前节点不存在北侧的相邻节点，则结束查找过程；如果当前节点有父节点，则执行步骤S144。

步骤S144，判断当前节点是否是父节点的西南方向或者东南方向子节点，如果否，则执行步骤S146；如果是，则当前节点北侧相邻节点就是其兄弟节点，根据对应关系分别得到父节点的西北方向或者东北方向子节点即可，并结束查找过程。例如，如图6所示，如果当前节点为父节点的东南方向子节点，则其北侧相邻节点即为东北方向子节点，通过同一个父节点的兄弟关系即可直接获得。

步骤S146，采用递归方法，获得当前节点的父节点的北侧相邻node节点。

步骤S148，判断node节点是否不存在或node节点是否没有子节点，如果node节点存在，且有子节点，则执行步骤S1410；如果node节点不存在，则此时当前节点不存在北侧相邻节点，查找到的node节点即为空，如果node节点存在，且，没有子节点，则node节点即为当前节点的相邻节点，即查找得到node节点，并结束查找过程。如图15所示，当前节点N为其父节点的东北方向子节点，此时，首先通过向上一级获取当前节点N的父节点，然后查找获取父节点的北侧相邻node节点，且，该node节点没有子节点，则该node节点即为当前节点N的北侧相邻节点。

步骤S1410，判断当前节点是否是父节点的西北方向或者东北方向子节点，如果否，则所求的北侧相邻节点不存在，并结束查找过程；如果是，则执行步骤S1412。

步骤S1412，获取node节点的西南方向或者东南方向子节点。具体地，如果当前节点是否是父节点的西北方向或者东北方向子节点，则如图6所示，node节点的西南方向或者东南方向子节点即为所求的当前节点的北侧相邻节点。为了便于理解，这里举例说明。如图16所示，其中，图16中16-a中node节点存在子节点，则当前节点的北侧相邻节点并非是node节点，但一定在node节点范围内，由于当前节点是其父节点的东北方向子节点，则查找该node节点的东南方向子节点M，因此，这里通过当前节点N查找其父节点是一次向上一级的查找，node节点查找其东南方向子节点M则是一次向下一级的查找，因此，本发明实施例中递归方法的思想即为：如果查找父节点向上查找了n次，则其北侧相邻节点向下n次查找子节点，如果子节点的深度不够n，则将最后一次查找到的北侧相邻节点的子节点作为当前节点的北侧相邻节点，如果子节点的深度超过n，则此时也只向下查找n次，从而确保得到的相邻节点的尺寸大于或等于当前节点的尺寸。如图16中16-b所示，虽然节点M还可以划分为四个子节点，但当前节点的北侧相邻节点应为node节点的东南方向子节点M，又由于此时查找的是当前节点N的北侧相邻节点，因此，此时应找出节点M的子节点中南侧所有南侧的子节点，即最后的结果应该如图16中16-c所示。

对于所述待定节点组中的非叶子节点，即上述中间节点，这类中间节点内部还有子节点，需要在该中间节点中继续查找当前节点的相邻节点。具体查找方式包括：在每个预先指定的邻位方向，按照预设的深度优先遍历原则，递归遍历中间节点中与该邻位方向反方向的子节点，直到遍历完与邻位方向反方向的叶子节点，从遍历到的叶子节点中确定当前节点相邻的叶子节点。例如，对于上述查找到的当前节点北侧的相邻节点，分别对每个相邻节点进行深度优先遍历，递归访问每个相邻节点的西南和东南方向的子节点，直到访问至叶子节点。由于节点尺寸可能不同，所以在遍历过程中可能访问到多个满足条件的叶子节点，这些叶子节点都是给定节点的北侧相邻节点，并从满足条件的多个叶子节点中确定当前节点在邻位方向对应的下一个路径点即目标节点。

步骤S1208，基于目标节点组确定起点至终点的导航路径；其中，导航路径由目标节点组中的目标节点对应的路径点组成。

步骤S1210，还原虚拟对象当前所在位置的节点为划分至最小网格尺寸前的网格节点，还原目标点所在位置的节点为划分至最小网格尺寸前的网格节点。

具体地，当确定导航路径后，将虚拟对象的中心点所在的节点和目标点的中心点所在的节点分别进行还原处理，得到虚拟对象当前所在位置的节点为划分至最小网格尺寸前的网格节点和目标点位置的叶子节点为划分至最小网格尺寸前的网格节点，通过该还原操作，有效缓解因为每次搜路操作导致起点和终点的网格划分带来的存储空间不断消耗的问题。

步骤S1212，控制虚拟对象按照导航路径移动至终点。上述游戏中虚拟对象的导航方法，通过将虚拟对象当前所在位置的节点和目标点设置操作设置的目标点所在位置的节点分别划分至最小网格尺寸，减少了虚拟对象对应的起点和终点的误差，提高了对虚拟对象的起点和终点的精确定位；当搜路操作结束得到导航路径后，再将虚拟对象当前所在位置的节点和目标点所在位置的节点分别还原为最小网格尺寸前的网格节点，从而避免了搜路操作对网格结构产生以影响，通过可行走区域的叶子节点的网格尺寸大的方式，有效缓解了广阔的可行走区域对应的网格存储空间消耗较大的问题。

在图3的基础上，本发明实施例还提供了另一种游戏中虚拟对象的导航方法，该方法重点描述了控制虚拟对象按照导航路径移动至终点的过程。如图17所示，该方法包括以下步骤：

步骤S1702，响应针对于游戏场景中一虚拟对象的目标点设置操作，确定虚拟对象对应的起点和终点。

步骤S1704，从起点所在的节点开始，对游戏场景中可行走区域的网格节点执行寻路算法，得到起点至终点的目标节点组。

步骤S1706，基于目标节点组确定起点至终点的导航路径；其中，导航路径由目标节点组中的目标节点对应的路径点组成。

上述步骤S1702～S1706，可以参考前述方法实施例，本发明实施例在此不再详细赘述。

步骤S1708，响应于虚拟对象到达导航路径上的路径点事件，从导航路径上读取下一个路径点，将读取到的路径点作为当前路径点，执行步骤S1710～S1712。

通过前述搜路操作，可以得到虚拟对象从起点至终点的导航路径，该导航路径由一系列路径点(即目标节点)组成。在控制虚拟对象按照导航路径移动时，由于每个路径点与虚拟对象的相对位置均不相同，因此，当虚拟对象向每个路径点移动时，需要生成该路径点对应的路径点事件，以便虚拟对象到达该路径点时，实际位置与路径点的位置尽量贴合，从而确保虚拟对象移动过程中自然和不生硬。

其中，路径点事件和常规的设置位置和速度参数并不相同，这里路径点事件为模拟玩家(用户)操作，例如，对于第一个路径点，此时需要控制虚拟对象按照预设方向启动，因此，第一个路径点事件需包括启动指令和第一个路径点指向第二路径点的预设方向，在移动过程中，将读取的第二个路径点作为当前路径点，此时，当前路径点事件包括：加速指令，用于控制虚拟对象加速移动至当前路径点；减速指令，用于虚拟对象距离当前路径点很近时减速移动；转向指令，用于当虚拟对象的移动方向偏离当前路径点，控制虚拟对象的转动移动方向，以使虚拟对象朝着当前路径点移动。如果虚拟对象为虚拟船只，则移动方向为船头方向，即以船只当前实际位置为起点，按照虚拟船只的前进方向作射线，并通过判断当前路径点是否在射线上衡量虚拟船只的移动方向是否朝向当前路径点，从而确保虚拟船只到达当前路径点的时候，实际位置尽可能贴合当前路径点。

步骤S1710，确定当前路径点与虚拟对象当前位置的相对关系。

在实际应用中，虚拟对象的实际位置可能和读取的当前路径点(即下一个路径点)较远，则此时虚拟对象和当前路径点的误差距离会比较大，导致虚拟对象无法真正移动至当前路径点，因此，在移动过程中，需要确定读取的当前路径点与虚拟对象当前位置的相对关系，以便根据相对关系对虚拟对象的前进方向和前进速度进行修正，从而确保虚拟对象到达当前路径点时，实际位置尽可能贴合当前路径点。

具体地，在虚拟对象朝着当前路径点移动的过程中，按照虚拟对象的前进速度确定间隔帧数；按照确定的间隔帧数修正当前路径点与虚拟对象当前位置的相对关系。其中，根据下式确定虚拟对象的间隔帧数：

其中，N表示间隔帧数，speed表示虚拟对象的前进速度。因此，虚拟对象的前进速度越快，则间隔帧数越少，则修正越频繁，从而虚拟对象的移动方向越正确。如图18所示，如果不进行修正，则虚拟对象的实际位置与路径点位置即目标位置存在较大的误差距离；当通过多次修正后，虚拟对象的实际位置尽可能贴合目标位置即路径点处，从而确保了虚拟对象移动过程中自然和不生硬，提高了导航精度，提高了用户的游戏体验度。

步骤S1712，根据相对关系调整虚拟对象的前进方向和前进速度，以使虚拟对象朝着当前路径点前进。

具体地，通过上述间隔帧数对相对关系进行修正，并基于修正后的相对关系调整虚拟对象的前进方向和前进速度，从而以使虚拟对象的前进方向始终朝着当前路径点，前进速度控制在较佳的速度范围内，避免虚拟对象因前进速度出现事故，如对于虚拟对象转弯的情况，如果不修正前进速度和前进方向，则虚拟对象可能会因前进方向和前进速度出现转弯效果不理想的情况，即便可以改变前进方向，但也可能由于前进速度太快出现转弯不理想的情况，因此，需要通过修正后的相对关系调整虚拟对象的前进方向和前进速度，从而保证虚拟对象以自然和不生硬的状态到达每个路径点，且，到达的实际位置与对应的路径点尽可能贴合，进而提高了虚拟对象的导航精度。

在一种可能的实施例中，上述方法还包括：基于虚拟对象的前进速度确定路径点半径；如果虚拟对象当前所在位置与当前路径点的距离小于或等于路径点半径，确定虚拟对象到达当前路径点。

具体地，考虑到虚拟对象如虚拟船只无法原地改变前进方向，即在转向过程中仍会前进一段距离，以及虚拟船只在海面上的导航精度无需十分精确，所以虚拟对象的实际位置尽可能贴合路径点位置即可，无需完全重合，因此，根据虚拟对象的前进速度可以确定当前路径点半径，当虚拟对象实际位置与当前路径点的距离小于或等于该路径点半径，即默认虚拟对象到达当前路径点，即虚拟对象的实际位置十分贴合当前路径点的位置。

其中，根据下式计算路径点半径：

R＝r+k×s (2)

其中，r为预设基础半径(例如当前节点边长的一半)，k为预设修正系数，s为虚拟对象的前进速度。需要说明的是，这里路径点半径R即为虚拟对象转向的预留距离，以使实际位置与路径点位置尽可能贴合，故路径点半径R最小大于0，s可以为虚拟对象的前进速度speed的一半，因此，虚拟对象的前进速度越大，则路径点半径越大，从而虚拟对象转弯的预留距离越大，如图19所示，左图为基于预设基础半径r控制虚拟对象的行驶示意图，右图为基于上述路径点半径R控制虚拟对象的行驶示意图，右图中，虚拟对象在行驶过程中，与路径点的距离只要在R以内，即虚拟对象的中心在虚线圆所在区域内，即认为虚拟对象通过该路径点，可以向下一个路径点继续行驶，这种方式能够确保虚拟对象以较佳状态转弯，且，到达的实际位置尽可能贴合路径点的位置。

为了便于理解，这里以虚拟船只为例进行说明。如图20所示，对于一个海洋场景中的某部分海域，通过四叉树划分为网格，其中，斜线覆盖区域为岛屿所在区域，基于岛屿所在区域的边缘位置涉及到的叶子节点以点图填充，这些点图填充的节点和岛屿所在区域构成了障碍物区域，这些区域均不可以行走，障碍物区域之外的区域为可行走区域。虚拟船只的导航路径由起点至终点的一系列路径点组成，包含路径点的网格为导航路径中的目标节点，这里路径点采用可行走区域中的网状圆表示，在控制虚拟船只移动过程中，使虚拟船只贴合每个路径点移动即可，从而实现虚拟船只在航行移动过程中自然不生硬，提高用户的游戏体验度，其中，如图21所示，该虚拟船只的具体控移动过程如下：

步骤S2102，通过搜路操作获得虚拟船只的导航路径，其中，导航路径为路径点列表，该路径点列表存储有从虚拟船只起点至终点的一系列路径点。

在移动过程中，通过读取路径点列表中每个路径点，并执行对应的路径点事件，以控制虚拟船只以自然的行驶状态移动至路径点，因此，在行驶过程中，当虚拟船只到达当前路径点之后，需要读取路径列表中的下一个路径点，直至读取到最后一个路径点即终点，控制虚拟船只停船结束该导航过程。

步骤S2104，判断导航路径中是否还有下一个路径点；如果有，则执行步骤S2106；如果没有，则认为虚拟船只到达终点，此时虚拟船只按照终点的路径点事件执行停止操作。

步骤S2106，从导航路径上读取下一个路径点，将读取到的路径点作为当前路径点，并执行当前路径点对应的路径点事件，控制虚拟船只转弯，以使虚拟船只前进方向对准当前路径点。

步骤S2108，虚拟船只转弯完成后，停止转弯，并控制虚拟船只按照前进方向和前进速度向当前路径点移动。

在此过程中，按照虚拟船只的前进速度确定间隔帧数，并根据确定的间隔帧数修正当前路径点与虚拟对象当前位置的相对关系，即修正虚拟船只的前进方向，以使虚拟船只正确行驶至当前路径点，且，到达的实际位置尽可能贴近当前路径点的位置，提高虚拟船只的导航精度。

此外，还根据虚拟船只的前进速度确定路径点半径；当虚拟船只的实际位置与当前路径点的距离小于或等于该路径点半径时，即判定此时虚拟船只到达当前路径点，并读取路径点列表中当前路径点的下一个路径点，重复上述控制过程，直至虚拟船只到达最后一个路径点即终点。

步骤S2110，虚拟船只到达当前路径点之后，从导航路径的路径点列表中删除当前路径点，并重复上述步骤S2104～S2110，直至虚拟船只到达最后一个路径点，控制虚拟船只停船结束该导航过程。

因此，上述游戏中虚拟对象的导航方法，通过在虚拟对象移动过程中加入方向修正机制，在保证虚拟对象贴着导航路径移动的同时，减少移动误差，保证虚拟对象移动过程中自然不生硬，从而提高了用户的游戏体验度。此外，上述方法中由于四叉树是用于场景管理的常见数据结构，因此，还可以进一步扩展出AOI(Area of Interest，感兴趣区域)功能，省去了重新开发功能的成本，便于在实际应用中推广实施。

对应于上述的方法实施例，本发明实施例还提供了一种游戏中虚拟对象的导航装置，通过电子设备显示游戏场景。如图22所示，该装置包括依次连接的：起点终点确定模块221、目标节点组确定模块222、导航路径确定模块223和移动模块224，其中，各个模块的功能如下：

起点终点确定模块221，用于响应针对于游戏场景中一虚拟对象的目标点设置操作，确定虚拟对象对应的起点和终点；其中，上述网格节点为根据所述游戏场景中的障碍物的参数信息对所述游戏场景进行划分以形成的四叉树中的节点，所述游戏场景中障碍物区域的叶子节点的网格尺寸小于可行走区域的部分叶子节点的网格尺寸。

目标节点组确定模块222，用于从起点所在的节点开始，对游戏场景中可行走区域的四叉树网格节点执行寻路算法，得到起点至终点的目标节点组；

导航路径确定模块223，用于基于目标节点组确定起点至终点的导航路径；其中，导航路径由目标节点组中的目标节点对应的路径点组成；

移动模块224，用于控制虚拟对象按照导航路径移动至终点。

本发明实施例提供了一种游戏中虚拟对象的导航装置，响应针对于游戏场景中一虚拟对象的目标点设置操作，确定虚拟对象对应的起点和终点；从起点所在的节点开始，对游戏场景中可行走区域的四叉树网格节点执行寻路算法，得到起点至终点的目标节点组；基于目标节点组确定起点至终点的导航路径；控制虚拟对象按照导航路径移动至终点。该方式中，网格节点为根据游戏场景中的障碍物的参数信息对游戏场景进行划分以形成的四叉树中的节点，而游戏场景中障碍物区域的叶子节点的网格尺寸小于可行走区域的部分叶子节点的网格尺寸，这种可行走区域的叶子节点的网格尺寸较大的划分方式，可以有效缓解广阔的可行走区域对应的网格存储空间消耗较大的问题，同时，障碍物区域的叶子节点的网格尺寸较小的划分方式，还可以保证障碍物区域的精确定位，为搜路操作提供可靠的数据基础；以及，在搜路操作过程中，由于叶子节点的网格尺寸小于其父节点的网格尺寸，通过在邻居方向上查找叶子节点，进而确定出的路径点的方式，能够保证搜索出的导航路径更优选，有效提升了虚拟对象的导航效果。

进一步的，上述起点终点确定模块221还用于：将虚拟对象当前所在位置的节点和目标点设置操作设置的目标点所在位置的节点，分别划分至最小网格尺寸；将包含虚拟对象的中心点的叶子节点确定为虚拟对象对应的起点；将包含目标点的中心点的叶子节点确定为虚拟对象对应的终点；该装置还用于：当确定出导航路径时，还原虚拟对象当前所在位置的节点为划分至最小网格尺寸前的网格节点，还原目标点所在位置的节点为划分至最小网格尺寸前的网格节点。

进一步的，以寻路算法为A*搜索算法为例，A*搜路算法通过以下方式确定当前节点的相邻节点：基于游戏场景中可行走区域的四叉树网格节点，在当前节点的邻位方向查找网格尺寸大于或等于当前节点的网格尺寸的节点，得到待定节点组；将待定节点组中的非叶子节点作为中间节点，从中间节点中搜索与当前节点相邻的叶子节点；将搜索到的叶子节点和待定节点组中除中间节点之外的节点作为当前节点的相邻节点。

进一步的，电子设备保存有各个节点的父子关系，上述在当前节点的邻位方向查找网格尺寸大于或等于当前节点的网格尺寸的节点，得到待定节点组包括：获取当前节点的父节点和当前节点在父节点中的方位信息；对于每个预先指定的邻位方向，均执行以下操作确定待定节点：如果方位信息对应的方向和邻位方向相反，从当前节点的兄弟节点中确定待定节点；兄弟节点的网格尺寸和当前节点的网格尺寸相等；如果方位信息对应的方向和邻位方向相同，将位于父节点邻位方向的相邻节点作为当前节点的待定节点；相邻节点的网格尺寸大于当前节点的网格尺寸；将各个邻位方向对应的待定节点组成当前节点的待定节点组。

进一步的，上述从中间节点中搜索与当前节点相邻的叶子节点包括：在每个预先指定的邻位方向，按照预设的深度优先遍历原则，递归遍历中间节点中与邻位方向反方向的子节点，直到遍历完与邻位方向反方向的叶子节点；从遍历到的叶子节点中确定当前节点相邻的叶子节点。

进一步的，上述装置还包括网格划分模块，与起点终点确定模块221连接，用于：响应针对于所述游戏场景的网格创建操作，以预设最大网格尺寸为根节点的边长，对所述游戏场景中障碍物的障碍物区域进行四叉树网格划分，直至将所述障碍物区域划分至叶子节点的边长等于预设最小网格尺寸。进一步地，该网格划分模块还用于响应针对于初始状态的游戏场景的网格创建操作，以预设最大网格尺寸为根节点的边长，对游戏场景进行四叉树网格划分，直至划分至四叉树的基准网格；其中，初始状态的游戏场景均为可行走区域；响应针对于游戏场景的障碍物创建操作，在游戏场景中创建障碍物，对障碍物的障碍物区域的基准网格进行四叉树网格划分，直至划分至叶子节点的边长等于预设最小网格尺寸；其中，基准网格的尺寸介于预设最大网格尺寸与预设最小网格尺寸之间。

进一步的，上述网格划分模块还用于：检查预设最小网格尺寸的叶子节点是否处于障碍物区域内；如果是，标注叶子节点为障碍物区域的叶子节点；如果否，且叶子节点的兄弟节点均不在障碍物区域内，删除叶子节点和叶子节点的兄弟节点。

进一步的，上述网格划分模块还用于：检查预设最小网格尺寸的叶子节点的中心点是否在障碍物区域内；如果是，确定该叶子节点在障碍物区域内；如果否，对该叶子节点进行四叉树划分得到该叶子节点的子节点，如果该叶子节点的子节点的中心点均不在障碍物区域内，确定该叶子节点不在障碍物区域内；如果该叶子节点至少一个子节点的中心点在障碍物区域内，确定该叶子节点在障碍物区域内。

进一步的，上述移动模块224还用于：响应于虚拟对象到达导航路径上的路径点事件，从导航路径上读取下一个路径点，将读取到的路径点作为当前路径点，执行以下操作：确定当前路径点与虚拟对象当前位置的相对关系；根据相对关系调整虚拟对象的前进方向和前进速度，以使虚拟对象朝着当前路径点前进。

进一步的，上述移动模块224还用于：按照虚拟对象的前进速度确定间隔帧数；按照确定的间隔帧数修正当前路径点与虚拟对象当前位置的相对关系；按照修正后的相对关系调整虚拟对象的前进方向和前进速度。

进一步的，上述装置还用于：基于虚拟对象的前进速度确定路径点半径；如果虚拟对象当前所在位置与当前路径点的距离小于或等于路径点半径，确定虚拟对象到达当前路径点。

进一步的，上述装置还用于：计算路径点半径R＝r+k×s，其中，r为预设基础半径，k为预设修正系数，s为虚拟对象的前进速度。

进一步的，上述游戏场景为海洋场景，上述虚拟对象为虚拟船只；各个节点的网格尺寸均为2的整数次幂。

本发明实施例提供的游戏中虚拟对象的导航装置，与上述实施例提供的游戏中虚拟对象的导航方法具有相同的技术特征，所以也能解决相同的技术问题，达到相同的技术效果。

本发明实施例还提供一种电子设备，包括处理器和存储器，存储器存储有能够被处理器执行的机器可执行指令，处理器执行机器可执行指令以实现上述游戏中虚拟对象的导航方法。

参见图23所示，该电子设备包括处理器230和存储器231，该存储器231存储有能够被处理器230执行的机器可执行指令，该处理器230执行机器可执行指令以实现上述游戏中虚拟对象的导航方法。

进一步地，图23所示的电子设备还包括总线232和通信接口233，处理器230、通信接口233和存储器231通过总线232连接。

其中，存储器231可能包含高速随机存取存储器(RAM，Random Access Memory)，也可能还包括非不稳定的存储器(non-volatile memory)，例如至少一个磁盘存储器。通过至少一个通信接口233(可以是有线或者无线)实现该系统网元与至少一个其他网元之间的通信连接，可以使用互联网，广域网，本地网，城域网等。总线232可以是ISA(IndustrialStandard Architecture，工业标准结构总线)总线、PCI(Peripheral ComponentInterconnect，外设部件互连标准)总线或EISA(Enhanced Industry StandardArchitecture，扩展工业标准结构)总线等。所述总线可以分为地址总线、数据总线、控制总线等。为便于表示，图23中仅用一个双向箭头表示，但并不表示仅有一根总线或一种类型的总线。

处理器230可能是一种集成电路芯片，具有信号的处理能力。在实现过程中，上述方法的各步骤可以通过处理器230中的硬件的集成逻辑电路或者软件形式的指令完成。上述的处理器230可以是通用处理器，包括中央处理器(Central Processing Unit，简称CPU)、网络处理器(Network Processor，简称NP)等；还可以是数字信号处理器(DigitalSignal Processor，简称DSP)、专用集成电路(Application Specific IntegratedCircuit，简称ASIC)、现场可编程门阵列(Field-Programmable Gate Array，简称FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件。可以实现或者执行本发明实施例中的公开的各方法、步骤及逻辑框图。通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等。结合本发明实施例所公开的方法的步骤可以直接体现为硬件译码处理器执行完成，或者用译码处理器中的硬件及软件模块组合执行完成。软件模块可以位于随机存储器，闪存、只读存储器，可编程只读存储器或者电可擦写可编程存储器、寄存器等本领域成熟的存储介质中。该存储介质位于存储器231，处理器230读取存储器231中的信息，结合其硬件完成前述实施例的方法的步骤。

本实施例还提供一种机器可读存储介质，机器可读存储介质存储有机器可执行指令，机器可执行指令在被处理器调用和执行时，机器可执行指令促使处理器实现上述游戏中虚拟对象的导航方法。

本发明实施例所提供的游戏中虚拟对象的导航方法、装置和电子设备的计算机程序产品，包括存储了程序代码的计算机可读存储介质，所述程序代码包括的指令可用于执行前面方法实施例中所述的方法，具体实现可参见方法实施例，在此不再赘述。上述技术中涉及到“到达”、“方向对准某点”等概念。转换成数学模型，到达指两个点重合(位置完全相同)、方向对准某点指该点在射线上。但是在计算机实践中，这些数学模型过于理想，比如两点位置完全相同，由于位置用浮点数保存，那么A(0,0.00001)和B(0,0.0000002)的位置就不相同。但如此小的差距其实可以认为相同。所以为了避免这种情况，A与B重合往往看作A在以B为圆心，半径为r的圆内。

所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的系统和装置的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。

另外，在本发明实施例的描述中，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以具体情况理解上述术语在本发明中的具体含义。

所述功能如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个处理器可执行的非易失的计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等各种可以存储程序代码的介质。

在本发明的描述中，需要说明的是，术语“中心”、“上”、“下”、“左”、“右”、“竖直”、“水平”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。此外，术语“第一”、“第二”、“第三”仅用于描述目的，而不能理解为指示或暗示相对重要性。

最后应说明的是：以上所述实施例，仅为本发明的具体实施方式，用以说明本发明的技术方案，而非对其限制，本发明的保护范围并不局限于此，尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，其依然可以对前述实施例所记载的技术方案进行修改或可轻易想到变化，或者对其中部分技术特征进行等同替换；而这些修改、变化或者替换，并不使相应技术方案的本质脱离本发明实施例技术方案的精神和范围，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应所述以权利要求的保护范围为准。