地图寻路方法、装置、设备及介质

摘要

本申请公开了一种地图寻路方法、装置、设备及介质，涉及寻路技术领域。所述方法包括：确定地图中待搜索的当前节点；沿当前节点的候选搜索方向进行搜索，得到候选搜索方向上的跳点，跳点是寻路路径中候选的转角节点，转角节点是路径前进方向发生改变的节点；确定跳点的父节点，父节点包括寻路路径中到达所述跳点的前一个转角节点；在搜索到寻路路径的终止节点后，从终止节点开始逐跳回溯父节点以生成寻路路径。本申请可以提高寻路搜索的速度，确定最优的寻路路径。

权利要求

1.一种地图寻路方法，其特征在于，所述方法应用于正六边形网格地图中，所述正六边形网格地图中的运动物体沿正六边形的轴方向进行移动，所述方法包括：确定地图中的待搜索的当前节点；

沿所述当前节点的候选搜索方向进行搜索，得到所述候选搜索方向上的跳点，所述跳点是寻路路径中候选的转角节点，所述转角节点是路径前进方向发生改变的节点；

确定所述跳点的父节点，所述父节点包括所述寻路路径中到达所述跳点的前一个转角节点；

在搜索到所述寻路路径的终止节点后，从所述终止节点开始逐跳回溯所述父节点以生成所述寻路路径；

所述沿所述当前节点的候选搜索方向进行搜索，得到所述候选搜索方向上的跳点，包括：沿所述当前节点的对角方向进行搜索，得到第二跳点，所述第二跳点是具有中间跳点的节点，所述中间跳点是在所述第二跳点的对角方向相邻的两个轴方向中的任一方向上搜索到的具有强迫邻居的节点，所述强迫邻居是所述中间跳点和阻挡节点共同相邻的节点，所述强迫邻居位于当前搜索方向的前方，所述阻挡节点是障碍物所在的节点；

所述方法还包括：在相邻的两个父节点是对角节点的情况下，增加中间点以形成所述两个父节点的路径，所述中间点是与所述两个父节点均相邻的邻居节点，所述对角节点用于指示一个节点在对角方向上移动一格的节点，所述邻居节点用于指示与一个节点共用一条边的节点。

2.根据权利要求1所述的方法，其特征在于，所述沿所述当前节点的候选搜索方向进行搜索，得到所述候选搜索方向上的跳点，包括：

沿所述当前节点的轴方向进行搜索，得到第一跳点；

其中，所述第一跳点是具有强迫邻居的节点，所述强迫邻居是所述第一跳点和阻挡节点共同相邻的节点，所述强迫邻居位于所述轴方向的前方，所述阻挡节点是障碍物所在的节点。

3.根据权利要求2所述的方法，其特征在于，所述确定所述跳点的父节点，包括：响应于所述第一跳点不是待搜索的节点中的一个，将所述当前节点确定为所述第一跳点的父节点。

4.根据权利要求2所述的方法，其特征在于，所述确定所述跳点的父节点，包括：响应于所述第一跳点是待搜索的节点中的一个，根据第一路径和第二路径确定所述第一跳点的父节点；

其中，所述第一路径是所述寻路路径的起始节点经过所述当前节点到达所述第一跳点的路径，所述第二路径是所述起始节点不经过所述当前节点到达所述第一跳点的路径。

5.根据权利要求2所述的方法，其特征在于，所述方法还包括：在未搜索到所述第一跳点的情况下，获取另一个待搜索的节点作为所述当前节点，重新从所述沿所述当前节点的候选搜索方向进行搜索，得到所述候选搜索方向上的跳点的步骤开始执行。

6.根据权利要求1所述的方法，其特征在于，所述确定所述跳点的父节点，包括：响应于所述第二跳点不是待搜索的节点中的一个，将所述当前节点确定为所述第二跳点的父节点。

7.根据权利要求1所述的方法，其特征在于，所述确定所述跳点的父节点，包括：响应于所述第二跳点是待搜索的节点中的一个，根据第三路径和第四路径确定所述第二跳点的父节点；

其中，所述第三路径是所述寻路路径的起始节点经过所述当前节点到达所述第二跳点的路径，所述第四路径是所述起始节点不经过所述当前节点到达所述第二跳点的路径。

8.根据权利要求1所述的方法，其特征在于，所述方法还包括：在未搜索到所述第二跳点的情况下，将所述当前节点的对角节点更新为新的当前节点，重新从所述沿所述当前节点的对角方向进行搜索，得到第二跳点的步骤开始执行，所述对角节点是所述当前节点在对角方向上移动一格的节点。

9.根据权利要求1所述的方法，其特征在于，所述方法还包括：在未搜索到所述第二跳点的情况下，获取另一个待搜索的节点作为所述当前节点，重新从所述沿所述当前节点的候选搜索方向进行搜索，得到所述候选搜索方向上的跳点的步骤开始执行。

10.根据权利要求1至9任一所述的方法，其特征在于，所述确定地图中的待搜索的当前节点，包括：

根据所述待搜索的节点的权重值确定当前节点，所述待搜索的节点的权重值是起始节点到达所述待搜索的节点的路径的长度和所述待搜索的节点到达终止节点的预估路径的长度之和。

11.一种地图寻路装置，其特征在于，所述装置应用于正六边形网格地图中，所述正六边形网格地图中的运动物体沿正六边形的轴方向进行移动，所述装置包括：确定模块，用于确定地图中的待搜索的当前节点；

搜索模块，用于沿所述当前节点的候选搜索方向进行搜索，得到所述候选搜索方向上的跳点，所述跳点是寻路路径中候选的转角节点，所述转角节点是路径前进方向发生改变的节点；

所述确定模块，还用于确定所述跳点的父节点，所述父节点包括所述寻路路径中到达所述跳点的前一个转角节点；

生成模块，用于在搜索到所述寻路路径的终止节点后，从所述终止节点开始逐跳回溯所述父节点以生成所述寻路路径；

所述搜索模块，用于沿所述当前节点的对角方向进行搜索，得到第二跳点，所述第二跳点是具有中间跳点的节点，所述中间跳点是在所述第二跳点的对角方向相邻的两个轴方向中的任一方向上搜索到的具有强迫邻居的节点，所述强迫邻居是所述中间跳点和阻挡节点共同相邻的节点，所述强迫邻居位于当前搜索方向的前方，所述阻挡节点是障碍物所在的节点；

所述生成模块，用于在相邻的两个父节点是对角节点的情况下，增加中间点以形成所述两个父节点的路径，所述中间点是与所述两个父节点均相邻的邻居节点，所述对角节点用于指示一个节点在对角方向上移动一格的节点，所述邻居节点用于指示与一个节点共用一条边的节点。

12.一种计算机设备，其特征在于，所述计算机设备包括处理器和存储器，所述存储器中存储有至少一条程序代码，所述程序代码由所述处理器加载并执行以实现如权利要求1至10中任一项所述的地图寻路方法。

13.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质中存储有至少一条程序代码，所述程序代码由处理器加载并执行以实现如权利要求1至10中任一项所述的地图寻路方法。

说明书

地图寻路方法、装置、设备及介质

技术领域

[0001] 本申请涉及寻路技术领域，特别涉及一种地图寻路方法、装置、设备及介质。

背景技术

[0002] 地图中通常存在有障碍物，比如游戏地图中出现的敌方堡垒，又如扫地机器人行走时遇到的桌椅。

[0003] 为使得网格地图上的运动物体能够避开障碍物到达指定位置，需要在网格地图上进行寻路搜索。以游戏中网格地图上出现的敌方堡垒为例，玩家控制的角色需要绕过敌方
堡垒到达目标位置，此时，需要为玩家提供一条绕开敌方堡垒所在的节点的寻路路径。以采
用正六边形构建的网格地图为例，相关技术将起始节点作为最开始的当前节点，通过对当
前节点相邻的所有节点均进行寻路搜索，最终确定寻路路径。该寻路路径是使得运动物体
从起始节点避开障碍物到达终止节点的移动路径。

[0004] 在网格地图中的节点数量较多的情况下，服务器需要对数量较大的节点进行搜索，使得寻路的速度降低，导致最终确定的寻路路径非最优路径，容易出现绕路的情况。

发明内容

[0005] 本申请实施例提供了一种地图寻路方法、装置、设备及介质，可以基于跳点来进行寻路搜索，避免对所有节点均进行寻路搜索，从而提高寻路速度。所述技术方案如下。

[0006] 根据本申请的一个方面，提供了一种地图寻路方法，该方法包括：

[0007] 确定地图中的待搜索的当前节点；

[0008] 沿当前节点的候选搜索方向进行搜索，得到候选搜索方向上的跳点，跳点是寻路路径中候选的转角节点，转角节点是路径前进方向发生改变的节点；

[0009] 确定跳点的父节点，父节点包括寻路路径中到达跳点的前一个转角节点；

[0010] 在搜索到寻路路径的终止节点后，从终止节点开始逐跳回溯父节点以生成寻路路径。

[0011] 根据本申请的一个方面，提供了一种地图寻路装置，该装置包括：

[0012] 确定模块，用于地图中的待搜索的当前节点；

[0013] 搜索模块，用于沿当前节点的候选搜索方向进行搜索，得到候选搜索方向上的跳点，跳点是寻路路径中候选的转角节点，转角节点是路径前进方向发生改变的节点；

[0014] 确定模块，还用于确定跳点的父节点，父节点包括寻路路径中到达跳点的前一个转角节点；

[0015] 生成模块，用于在搜索到寻路路径的终止节点后，从终止节点开始逐跳回溯父节点以生成寻路路径。

[0016] 根据本申请的一个方面，提供了一种计算机设备，该计算机设备包括处理器和存储器，存储器中存储有至少一条程序代码，程序代码由处理器加载并执行如上所述的地图
寻路方法。

[0017] 根据本申请的一个方面，提供了一种计算机可读存储介质，该计算机可读存储介质中存储有至少一条程序代码，程序代码由处理器加载并执行以实现如上所述的地图寻路
方法。

[0018] 本申请实施例提供的技术方案带来的有益效果至少包括：

[0019] 通过沿当前节点的候选搜索方向搜索跳点，基于搜索到的跳点和当前节点确定每个跳点的父节点进行记录。在搜寻到终止节点后，从终止节点逐跳回溯一个或多个父节点
以生成寻路路径。使得通过确定寻路路径中的转角节点即可生成最优的寻路路径，减少了
寻路搜索过程所需要搜索的节点数量，无需对所有节点进行寻路搜索，从而提高寻路搜索
的速度；通过转角节点生成的最优的寻路路径，有助于避免出现绕路的情况。

附图说明

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

[0021] 图1是本申请一个示例性实施例提供的终端的结构示意图；

[0022] 图2是本申请一个示例性实施例提供的计算机系统的结构框图；

[0023] 图3是本申请一个示例性实施例提供的地图寻路方法的流程图；

[0024] 图4是本申请一个示例性实施例提供的正六边形网格地图的坐标系；

[0025] 图5是本申请一个示例性实施例提供的正六边形网格地图的坐标系；

[0026] 图6是本申请一个示例性实施例提供的正六边形网格地图的坐标系；

[0027] 图7是本申请一个示例性实施例提供的正六边形网格地图的坐标系；

[0028] 图8是本申请一个示例性实施例提供的正六边形网格地图的坐标系；

[0029] 图9是本申请一个示例性实施例提供的正六边形网格地图的坐标系；

[0030] 图10是本申请一个示例性实施例提供的正六边形网格地图的坐标系；

[0031] 图11是本申请一个示例性实施例提供的正六边形网格地图的坐标系；

[0032] 图12是本申请一个示例性实施例提供的地图寻路方法的流程图；

[0033] 图13是本申请一个示例性实施例提供的地图寻路方法的流程图；

[0034] 图14是本申请一个示例性实施例提供的地图寻路方法的流程图；

[0035] 图15是本申请一个示例性实施例提供的寻路路径的示意图；

[0036] 图16是本申请一个示例性实施例提供的地图寻路装置的框图；

[0037] 图17是本申请一个示例性实施例提供的终端的框图。

具体实施方式

[0038] 为使本申请的目的、技术方案和优点更加清楚，下面将结合附图对本申请实施方式作进一步地详细描述。

[0039] 首先对本申请实施例中涉及的名词进行介绍。

[0040] 正六边形的网格地图：是指由多个正六边形构成的网格地图。示意性的，在正六边形的网格地图中，一个节点向轴方向上相邻的节点移动一格的代价为1，向对角方向上移动
一格的代价为2。

[0041] 寻路：通常表示在网格地图中根据规则为运动物体寻找一条可移动的路径。其中，网格地图可以是基于正四边形构建的网格地图，也可以是基于正六边形构建的网格地图，
还可以是其他类型的网格地图。

[0042] 第一节点集合（OpenList）：寻路过程中待搜索的节点组成的节点集合，也可以称之为开启列表。

[0043] 第二节点集合（CloseList）：寻路过程中已经搜索过的节点组成的节点集合，也可以称之为关闭列表。

[0044] 节点：是指网格地图上的格子，是寻路搜索的最小单位。本申请中涉及的当前节点、邻居节点、对角节点、阻挡节点、跳点、强制邻居、中间跳点、父节点等均为节点的一种。
以基于正六边形构建的网格地图为例，每个节点均为一个正六边形的节点。上述节点的具
体含义将在下文中展开具体阐述。

[0045] 人工智能(Artificial Intelligence, AI)：是利用数字计算机或者数字计算机控制的机器模拟、延伸和扩展人的智能，感知环境、获取知识并使用知识获得最佳结果的理
论、方法、技术及应用系统。换句话说，人工智能是计算机科学的一个综合技术，它企图了解
智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器。人工智能
也就是研究各种智能机器的设计原理与实现方法，使机器具有感知、推理与决策的功能。

[0046] 人工智能技术是一门综合学科，涉及领域广泛，既有硬件层面的技术也有软件层面的技术。人工智能基础技术一般包括如传感器、专用人工智能芯片、云计算、分布式存储、
大数据处理技术、操作/交互系统、机电一体化等技术。人工智能软件技术主要包括计算机
视觉技术、语音处理技术、自然语言处理技术以及机器学习/深度学习等几大方向。

[0047] 本申请实施例提供的地图寻路方法，可用于智能机器行进路径的确定过程中，或者驾驶路径的确定过程中，或者其他基于正六边形网格地图进行的路径的确定过程中。示
意性的，本申请实施例提供的地图寻路方法，还可以放置于区块链上加以使用。

[0048] 本申请中提供的方法可以应用于具有虚拟环境和虚拟角色的应用程序中。示例性的，支持虚拟环境的应用程序是用户可以控制虚拟角色在虚拟环境内移动的应用程序。示
例性的，本申请中提供的方法可以应用于：虚拟现实（Virtual Reality，VR）应用程序、增强
现实(Augmented Reality，AR)程序、三维地图程序、军事仿真程序、虚拟现实游戏、增强现
实游戏、第一人称射击游戏（First‑Person Shooting Game，FPS）、第三人称射击游戏
（Third‑Person Shooting Game，TPS）、多人在线战术竞技游戏（Multiplayer Online 
Battle Arena Games，MOBA）、策略游戏（Simulation Game，SLG）中的任意一种程序。

[0049] 示例性的，虚拟环境中的游戏由一个或多个游戏世界的地图构成，游戏中的虚拟环境模拟现实世界的场景，用户可以操控游戏中的虚拟角色在虚拟环境中进行行走、跑步、
跳跃、射击、格斗、驾驶、使用虚拟武器攻击其他虚拟角色、使用虚拟武器蓄力攻击其他虚拟
角色等动作，交互性较强，并且多个用户可以在线组队进行竞技游戏。

[0050] 在一些实施例中，上述应用程序可以是射击类游戏、竞速类游戏、角色扮演类游戏、冒险类游戏、沙盒游戏、战术竞技游戏、军事仿真程序等程序。该客户端可以支持
Windows操作系统、苹果操作系统、安卓操作系统、IOS操作系统和LINUX操作系统中的至少
一种操作系统，并且不同操作系统的客户端可以互联互通。在一些实施例中，上述客户端是
适用于具有触摸屏的移动终端上的程序。

[0051] 在一些实施例中，上述客户端是基于三维引擎开发的应用程序，比如三维引擎是Unity引擎。

[0052] 本申请中的终端可以是台式计算机、膝上型便携计算机、手机、平板电脑、电子书阅读器、MP3（Moving Picture Experts Group Audio Layer III，动态影像专家压缩标准
音频层面3）播放器、MP4（Moving Picture Experts Group Audio Layer IV，动态影像专家
压缩标准音频层面4）播放器等等。该终端中安装和运行有支持虚拟环境的客户端，比如支
持三维虚拟环境的应用程序的客户端。该应用程序可以是战术竞技生存（Battle Royale，
BR）游戏、虚拟现实应用程序、增强现实程序、三维地图程序、军事仿真程序、第三人称射击
游戏、第一人称射击游戏、多人在线战术竞技游戏中的任意一种。可选地，该应用程序可以
是单机版的应用程序，比如单机版的3D游戏程序，也可以是网络联机版的应用程序。

[0053] 图1是本申请一个示例性实施例提供的终端的结构示意图，该终端包括处理器101、触摸屏102以及存储器103。

[0054] 处理器101可以是单核处理器、多核处理器、嵌入式芯片以及具有指令运行能力的处理器中的至少一种。

[0055] 触摸屏102包括普通触摸屏或压力感应触摸屏。普通触摸屏可以对施加在触摸屏102上的按压操作或滑动操作进行测量；压力感应触摸屏可以对施加在触摸屏102上的按压
力度进行测量。

[0056] 存储器103存储有处理器101的可执行程序。示意性的，存储器103中存储有虚拟环境程序A、应用程序B、应用程序C、触摸（以及压力）感应模块18、操作系统的内核层19。其中，
虚拟环境程序A为基于三维虚拟环境模块17开发的应用程序。可选地，虚拟环境程序A包括
但不限于由三维虚拟环境模块（也称虚拟环境模块）17开发的游戏程序、虚拟现实程序、三
维地图程序、三维演示程序中的至少一种。比如，终端的操作系统采用安卓操作系统时，虚
拟环境程序A采用Java编程语言以及C#语言进行开发；又比如，终端的操作系统采用IOS操
作系统时，虚拟环境程序A采用Object‑C编程语言以及C#语言进行开发。

[0057] 三维虚拟环境模块17是一款支持多种操作系统平台的模块，示意性的，三维虚拟环境模块可用于游戏开发领域、虚拟现实（Virtual Reality，VR）领域以及三维地图领域等
多领域的程序开发，本申请实施例对三维虚拟环境模块17的具体类型不限，在下文实施例
中以三维虚拟环境模块17是使用Unity引擎开发的模块为例来举例说明。

[0058] 触摸（以及压力）感应模块18是用于接收触摸屏驱动程序191所上报的触摸事件（以及压力触控事件）的模块，可选地，触摸感应模块可以不具有压力感应功能，不接收压力
触控事件。触摸事件包括：触摸事件的类型和坐标值，触摸事件的类型包括但不限于：触摸
开始事件、触摸移动事件和触摸落下事件。压力触控事件中包括：压力触控事件的压力值以
及坐标值。该坐标值用于指示压力触控操作在显示屏上的触控位置。可选地，以显示屏的水
平方向建立横坐标轴，显示屏的竖直方向建立竖坐标轴得到一个二维坐标系。

[0059] 示意性的，内核层19包括了触摸屏驱动程序191以及其它驱动程序192。触摸屏驱动程序191是用于检测压力触控事件的模块，当触摸屏驱动程序191检测到压力触控事件
后，将压力触控事件传递给触摸（以及压力）感应模块18。

[0060] 其它驱动程序192可以是与处理器101有关的驱动程序、与存储器103有关的驱动程序、与网络组件有关的驱动程序、与声音组件有关的驱动程序等。

[0061] 可选的，终端也可以通过游戏控制器来控制虚拟角色在虚拟环境中的移动，不需要设置触摸屏102记忆存储器103中包括的与触摸屏相应的处理模块。本领域技术人员可以
知晓，上述仅为对终端的结构的概括性示意。在不同的实施例中，终端可以具有更多或更少
的组件。比如，终端还可以包括重力加速度传感器、陀螺仪传感器、电源等。

[0062] 图2示出了本申请一个示例性实施例提供的计算机系统的结构框图，该计算机系统200包括：终端210、服务器集群220。

[0063] 终端210安装和运行有支持虚拟环境的客户端211，该客户端211可以是支持虚拟环境的应用程序。比如，客户端211是运行有支持正六边形网格地图的游戏应用程序。当终
端运行客户端211时，终端210的屏幕上显示客户端211的用户界面。该客户端可以是FPS游
戏、TPS游戏、军事仿真程序、MOBA游戏、战术竞技游戏、SLG游戏的任意一种。终端210是第一
用户212使用的终端，第一用户212使用终端210控制位于虚拟环境中的第一虚拟角色进行
活动，第一虚拟角色可以称为第一用户212的第一虚拟角色。第一虚拟角色的活动包括但不
限于：调整身体姿态、爬行、步行、奔跑、骑行、飞行、跳跃、驾驶、拾取、射击、攻击、投掷中的
至少一种。示意性的，第一虚拟角色是第一虚拟角色，比如仿真人物角色或动漫人物角色。

[0064] 终端210的设备类型包括：智能手机、平板电脑、电子书阅读器、MP3播放器、MP4播放器、膝上型便携计算机和台式计算机中的至少一种。

[0065] 图2中仅示出了一个终端，但在不同实施例中存在多个其它终端240。在一些实施例中，还存在至少一个其它终端240是开发者对应的终端，在其它终端240上安装有虚拟环
境的客户端的开发和编辑平台，开发者可在其它终端240上对客户端进行编辑和更新，并将
更新后的客户端安装包通过有线或无线网络传输至服务器集群220，终端210可从服务器集
群220下载客户端安装包实现对客户端的更新。

[0066] 终端210和其它终端240通过无线网络或有线网络与服务器集群220相连。

[0067] 服务器集群220包括一台服务器、多台服务器、云计算平台和虚拟化中心中的至少一种。服务器集群220用于为支持三维虚拟环境的客户端提供后台服务。可选地，服务器集
群220承担主要计算工作，终端承担次要计算工作；或者，服务器集群220承担次要计算工
作，终端承担主要计算工作；或者，服务器集群220和终端之间采用分布式计算架构进行协
同计算。

[0068] 可选地，上述终端和服务器均为计算机设备。

[0069] 在一个示意性的例子中，服务器集群220包括服务器221和服务器226，服务器221包括处理器222、用户帐号数据库223、对战服务模块224、面向用户的输入/输出接口
（Input/Output Interface，I/O接口）225。其中，处理器222用于加载服务器221中存储的指
令，处理用户帐号数据库223和对战服务模块224中的数据；用户帐号数据库223用于存储终
端210以及其它终端240所使用的用户帐号的数据，比如用户帐号的头像、用户帐号的昵称、
用户帐号的战斗力指数，用户帐号所在的服务区；对战服务模块224用于提供多个对战房间
供用户进行对战；面向用户的I/O接口225用于通过无线网络或有线网络和终端210建立通
信交换数据。

[0070] 结合上述对虚拟环境的介绍以及实施环境说明，示意性的如图3所示，本申请实施例提供了一种地图寻路方法，该方法应用于服务器中。本申请实施例提供的寻路方法包括
如下步骤。

[0071] 步骤302：确定地图中的待搜索的当前节点。

[0072] 示意性的，第一节点集合中包括至少一个待搜索的节点。

[0073] 其中，当前节点，是指正在进行寻路搜索的节点。示意性的，当前节点是地图中的待搜索的节点中的一个，由待搜索的节点构成的节点集合称之为第一节点集合。相应的，由
已搜索的节点构成的节点集合称之为第二节点集合。

[0074] 以下将以当前节点包括于第一节点集合为例展开阐述。

[0075] 示意性的，在当前节点的寻路搜索结束后，将该节点从第一节点集合中取出，放入第二节点集合中。另外，第一节点集合为空时，即没有待搜索的节点时，结束寻路。相当于，
在进行寻路搜索的正六边形网格地图中，从起始节点无法找到一个路径可以到达终止节
点，其中，起始节点是路径起点所在的节点，终止节点是路径终点所在的节点。

[0076] 在寻路搜索的过程中，通常是从起始节点开始的。因此，在执行步骤302之前，需要先将起始节点放入第一节点集合中。

[0077] 步骤304：沿当前节点的候选搜索方向进行搜索，得到候选搜索方向上的跳点。

[0078] 示意性的，跳点是寻路路径的候选的转角节点，转角节点是路径前进方向发生改变的节点。

[0079] 示意性的，以本申请实施例提供的地图寻路方法应用于正六边形网格地图中为例，候选搜索方向是指正六边形的轴方向和对角方向中的至少一个。其中，正六边形的轴方
向是指正六边形的中心与六条边中的一个的中点构成的直线方向，对角方向是指正六边形
的中心与六个对角中的一个构成的直线方向。示意性的，正六边形包括六个轴方向和六个
对角方向。

[0080] 其中，寻路路径是指寻路搜索得到的从起始节点到终止节点的路线，跳点是寻路路径中可能存在的候选的转角节点。

[0081] 比如，寻路路径依次经过节点a、节点b、节点c、节点d上，上述四个节点均不是起始节点和终止节点中的一个。节点a到达节点b的方向为向右的水平方向，节点b向下一个节点
c的前进方向为向上的垂直方向，节点c向下一个节点d的前进方向为向右上的对角方向。其
中，节点b和节点c是跳点。可见，跳点在寻路路径中具有较为重要的意义，在跳点不包括于
第一节点集合时，需要将跳点加入到第一节点集合中成为待搜索的节点之一。

[0082] 示意性的，跳点包括如下节点中的至少一种：起始节点、终止节点、具有强迫邻居的节点、具有中间跳点的节点。将具有强迫邻居的节点视为第一跳点，将具有中间跳点的节
点视为第二跳点，以下结合正六边形网格地图对第一跳点和第二跳点进行解释。

[0083] 首先，图4至图6示出了正六边形网格地图的部分坐标系。根据正六边形的不同排布方式，可以采用不同的坐标系系统。本申请实施例以坐标系系统为立方体坐标系（Cube 
coordinates）为例。示意性的，坐标轴x、y、z呈60°夹角。其中，坐标系中的一个格子相当于
网格地图中的一个节点，每个格子的坐标为（x，y，z），其中每个格子的坐标均满足x+y+z=0，
图4中标有（x，y，z）坐标的节点为坐标系的原点。另外，坐标系中，坐标轴的方向是轴方向，
两个坐标轴之间形成对角方向。也即，相对于正六边形而言，每个边对应一个轴方向，每个
对角对应一个对角方向。

[0084] 邻居节点是指与某一节点相邻的节点。也即，当两个节点共用一条边时，两个节点互为对方的邻居节点。示意性的如图5所示，节点A具有六个相邻的节点，六个相邻的节点均
为节点A的邻居节点，节点A也是该六个节点的邻居节点。对角节点是指某一节点在对角方
向上移动一格的节点。示意性的如图6所示，节点A向右上的对角方向上移动一格可得到节
点B。可以认为，节点B和节点A互为对角节点。示意性的，图中节点C、D、E、F、G均与节点A互为
对角节点。

[0085] 1、第一跳点：具有强迫邻居的节点。

[0086] 强迫邻居是指与跳点和阻挡节点共同相邻的节点，也即，跳点、阻挡节点、强迫邻居同时出现，且互为邻居节点。强迫邻居位于搜索方向的前方或路径的前进方向的前方。

[0087] 示意性的如图7所示，节点p为当前节点，箭头所指方向是搜索方向，该搜索方向为向右的轴方向，黑色节点是阻挡节点，在节点p的搜索方向上发现节点x。节点x、节点n和阻
挡节点互为邻居节点，且节点n位于搜索方向的前方，此时，节点p经过节点x到达节点n的路
径的长度比任何不经过节点x的路径的长度均短。可以认为，节点n是节点x的强迫邻居，节
点x是节点n的跳点。

[0088] 2、第二跳点：具有中间跳点的节点。

[0089] 中间跳点是指搜索方向是对角方向时，在对角方向相邻的两个轴方向中的任一方向上搜索到的具有强迫邻居的节点。示意性的如图8所示，节点p是当前节点，节点y是节点p
的对角节点，粗箭头为节点y的搜索方向，节点y的候选搜索方向相邻的两个轴方向分别为
d1、d2箭头指向的方向。其中，在d1方向上发现节点f1是具有强迫邻居的节点，在d2方向上
发现节点f2是具有强迫邻居的节点，则可以认为，节点f1、节点f2是节点y的中间跳点；在节
点f1和节点f2任意一个存在时，节点y是具有中间跳点的节点。

[0090] 根据前述内容，当前节点是起始节点、终止节点、第一跳点和第二跳点中的一个。本申请实施例提供的寻路方法中，根据当前节点的不同，其搜索方向也不同，具体遵循以下
搜索方向的确定规则。

[0091] （1）当前节点为起始节点的情况下。

[0092] 需要在六个轴方向和六个对角方向上均进行搜索，先进行轴方向上的搜索，再进行对角方向上的搜索。

[0093] 示意性的如图9所示，节点p为当前节点，实线箭头为轴方向，虚线箭头为对角方向。

[0094] （2）当前节点为第一跳点的情况下。

[0095] 第一跳点的候选搜索方向包括两类，一类是第一跳点的原搜索方向，一类是强迫邻居所在的轴方向、以及原搜索方向与强迫邻居所在的轴方向之间的对角方向。

[0096] 示意性的如图10所示，节点x为第一跳点，黑色节点为阻挡节点，节点n1和节点n2均为节点x的强迫邻居，实线箭头为搜索到节点x的原搜索方向，虚线箭头从上至下依次为
节点n1所在的轴方向、节点n1所在的轴方向和原搜索方向之间的对角方向、节点n2所在的
轴方向、节点n2所在的轴方向和原搜索方向之间的对角方向。此时，若节点x成为当前节点，
则其搜索方向包括图中的实线箭头和虚线箭头所指向的五个方向，先进行轴方向上的搜
索，再进行对角方向上的搜索。

[0097] （3）当前节点为第二跳点的情况下。

[0098] 第二跳点的候选搜索方向包括两类，一类是第二跳点的原搜索方向，一类是中间跳点所在的轴方向。

[0099] 示意性的如图11所示，节点y为第一跳点，黑色节点为阻挡节点，节点f1为节点y的中间跳点，实线箭头为搜索到节点y的原搜索方向，虚线箭头为节点f1所在的轴方向。此时，
若节点y成为当前节点，则其搜索方向包括图中的实线箭头和虚线箭头所指向的两个方向，
先进行轴方向上的搜索，再进行对角方向上的搜索。

[0100] 步骤306：确定跳点的父节点。

[0101] 示意性的，父节点包括寻路路径中到达所述跳点的前一个转角节点。

[0102] 父节点是达到跳点的前一个转角节点。比如，寻路路径依次经过节点a、节点b、节点c上，上述节点均不是起始节点和终止节点中的一个。节点a到达节点b的方向为向右的水
平方向，节点b向下一个节点c的前进方向为向上的垂直方向。其中，节点b是跳点，节点a是
节点b的父节点。

[0103] 示意性的，在确定跳点的父节点的同时或之后，将跳点加入第一节点集合中，相当于更新第一节点集合，使得跳点成为待搜索的节点中的一个。

[0104] 步骤308：在搜索到寻路路径的终止节点后，从终止节点开始逐跳回溯父节点以生成所述寻路路径。

[0105] 根据前述内容，父节点是寻路路径中到达跳点的前一个转角节点，将父节点进行连接，即可得到寻路路径。具体的，当搜索到终止节点后，从终止节点向后回溯直至找到起
始节点，从终止节点回溯到起始节点的连线即为寻路路径。

[0106] 在正六边形网格地图的坐标系中，认为运动物体在轴方向上进行移动，在对角方向上无法进行移动，因此需要在两个对角节点之间插入中间点。其中，中间点是与两个对角
节点均相邻的邻居节点。示意性的如图6所示，节点A和节点B是对角节点，若运动物体需要
从节点A移动到节点B，则需要在寻路路径加入节点（+1，0，‑1）和节点（+1，‑1，0）中的一个。
此时，形成的寻路路径的节点信息包括节点A、节点（+1，0，‑1）、节点B，或者包括节点A、节点
（+1，‑1，0）、节点B。

[0107] 示意性的，本申请实施例提供的寻路方法，可以用在任一正六边形网格地图中，包括但不限于如下地图中的至少一种：游戏地图、智能机器的行走地图。

[0108] 在上述网格地图中，针对不同的运动物体，每个节点内存储的障碍物信息也会发生变化，也即，针对不同的运动物体有不同的阻挡节点。比如，网格地图上存在某一障碍物，
该障碍物所在的一个节点上存储有如下信息：该节点对于第一运动物体是障碍物所在的节
点，对于第二运动物体不是障碍物所在的节点。本申请实施例提供的寻路方法，可以根据阻
挡节点的动态变化进行实时更新和动态判断，以支持运动物体对于阻挡节点动态变化的需
求。具体的，在一次寻路搜索结束后，服务器实时更新阻挡节点的动态变化，随后再进行下
一次的寻路搜索。

[0109] 综上所述，本申请实施例提供的地图寻路方法，通过沿正六边形的轴方向或对角方向中的至少一个方向搜索跳点，基于搜索到的跳点和当前节点确定每个跳点的父节点，
从终止节点逐跳回溯一个或多个父节点以生成寻路路径。该寻路方法中，通过确定寻路路
径中的转角节点即可生成最优的寻路路径，减少了寻路搜索过程中所需要搜索的节点的数
量，无需对所有节点进行寻路搜索，从而提高了寻路搜索的速度。

[0110] 在寻路搜索中，当前节点的候选搜索方向包括正六边形的轴方向或对角方向中的至少一个，在不同的候选搜索方向下，得到的跳点也是不同的，以下将针对不同的候选搜索
方向展开具体阐述。

[0111] 示意性的如图12所示，本申请实施例提供的地图寻路方法包括如下步骤。

[0112] 步骤402：根据待搜索的节点的权重值确定当前节点。

[0113] 示意性的，待搜索的节点的权重值是起始节点到达待搜索的节点的路径的长度和待搜索的节点到达终止节点的预估路径的长度之和。也即，待搜索的节点的权重值是两个
路径长度之和，两个路径长度分别是起始节点到达待搜索的节点的路径的长度、待搜索的
节点到达终止节点的预估路径。其中，预估路径是待搜索的节点到达终止节点的预计代价，
可以是两个节点的直线路径，也可以是基于相关函数计算得到的估计路径，以下以预估路
径采用启发函数计算得到为例。

[0114] 示意性的，将权重值最小的节点设置为当前节点。

[0115] 具体的，节点n的权重值可视为f(n)=g(n)+h(n)。示意性的，g(n)是起始节点到达节点n的路径的长度，h(n)是节点n到达终止节点的预估路径。

[0116] 在正六边形网格地图的坐标系中，路径的长度视为节点到节点之间的距离之和，一个节点到邻居节点的距离为1，到对角节点的距离为2。示意性的如图7所示，节点p到邻居
节点x的距离为1，节点p到对角节点n的距离为2。

[0117] 其中，g(n)是起始节点到达节点n经过的距离。比如，起始节点经过多个节点到达节点n，此时g(n)相当于每两个节点之间的距离之和。

[0118] h(n)是节点n到达终止节点可能经过的距离，该距离称之为节点n到达终止节点的预计代价，可采用启发函数进行计算。假设节点n的坐标值为（x1，y1，z1），终止节点的坐标
值为（x2，y2，z2），根据启发函数可以求得如下式子：

[0119] g(n)= (abs(x2‑x1) + abs(y2‑y1)+abs(z2‑z1))/2 ，

[0120] 其中，abs（i）函数是绝对值函数。

[0121] 比如，节点n的坐标值为（1，2，‑3），终止节点的坐标值为（0，‑3，3）,则g(n)= (abs(0‑1) + abs((‑3)‑2)+abs(3‑(‑3)))/2，计算可得，g(n)的值为6。

[0122] 步骤403：沿当前节点的候选搜索方向进行搜索，得到候选搜索方向上的跳点。

[0123] 其中，跳点是寻路路径中候选的转角节点，转角节点是路径前进方向发生改变的节点。

[0124] 示意性的，候选搜索方向、跳点、转角节点的阐述可参考步骤304中的内容，在此不再赘述。

[0125] 由于在不同的候选搜索方向下，得到的跳点也是不同的。

[0126] 在候选搜索方向包括轴方向时，执行步骤4041；在候选搜索方向包括对角方向时，执行步骤4042。示意性的，步骤4041和步骤4042可以只执行其一，也可以两步均执行。可选
的，在两步均执行的情况下，先执行步骤4041，再执行步骤4042。

[0127] 以下将分别从轴方向和对角方向两类候选搜索方向进行阐述。

[0128] 一、当前节点的候选搜索方向包括轴方向。

[0129] 步骤4041：沿当前节点的轴方向进行搜索，得到第一跳点。

[0130] 示意性的，第一跳点是具有强迫邻居的节点，强迫邻居是第一跳点和阻挡节点共同相邻的节点，强迫邻居位于轴方向的前方，阻挡节点是障碍物所在的节点。

[0131] 在搜索到第一跳点后，在该搜索方向的寻路搜索结束。比如，在节点a向右的轴方向上搜索到了第一跳点后，节点a将不再向右的轴方向上继续进行寻路搜索，其搜索方向根
据下一个当前节点确定。

[0132] 根据前述内容，第一跳点是寻路路径中可能存在的转角节点。因此，需要将第一跳点设置为待搜索的节点中的一个进行寻路搜索，此时，需要判断第一跳点是否是待搜索的
节点中的一个，也可以认为是需要判断第一跳点是否存在于第一节点集合中。根据判断结
果，有如下两种可选的执行步骤。

[0133] 步骤405：响应于第一跳点不是待搜索的节点中的一个，将当前节点确定为第一跳点的父节点。

[0134] 比如，在节点a向右的轴方向上搜索到了第一跳点，第一跳点不存在于第一节点集合中，将节点a确定为第一跳点的父节点，将第一跳点加入第一节点集合中。

[0135] 步骤406：响应于第一跳点是待搜索的节点中的一个，根据第一路径和第二路径确定第一跳点的父节点。

[0136] 示意性的，第一路径是寻路路径的起始节点经过当前节点到达第一跳点的路径，第二路径是起始节点不经过当前节点到达第一跳点的路径。

[0137] 此时，根据第一路径和第二路径的长度的不同，第一跳点的父节点也不同，具体的，步骤406有如下两种可选的实现方式。

[0138] 响应于第一路径的长度小于第二路径的长度，将到达第一跳点的前一个转角节点确定为第一跳点的父节点；

[0139] 响应于第一路径的长度不小于第二路径的长度，将当前节点确定为第一跳点的父节点。

[0140] 运动物体在网格地图中移动时，路径越长，走过的节点越多。为得到最优寻路路径，应该选择前进路线较长的路径；若多条路径的长度均相同，则应该选择转角节点较少的
路径，其他路径可作为备选路径。本申请实施例中，若两条路径的长度相同，优选经过当前
节点的路径，以减少对其他路径的多次寻路搜索。

[0141] 据此，在搜索到第一跳点后，若第一路径的长度较短，相当于起始节点经过当前节点到达第一跳点的路径的长度较短，而由于第一跳点位于第一节点集合中，可以找到到达
第一跳点的前一个转角节点。因此，将第一跳点的前一个转角节点确定为父节点。若第一路
径的长度长，相当于起始节点经过当前节点到达第一跳点的路径的长度较长，此时经过当
前节点可以得到较短的路径长度。因此，将当前节点确定为第一跳点的父节点。

[0142] 比如，在节点a向右的轴方向上搜索到了第一跳点，节点a包括于第一节点集合中，计算得到：起始节点经过节点a到达第一跳点的路径的长度为7，起始节点不经过节点a到达
第一跳点的路径的长度为5，则将节点a确定为第一跳点的父节点。

[0143] 在当前节点的候选搜索方向是轴方向的情况下，由于网格地图是有边界的，当在轴方向上逐次搜索过每一个节点后，若不能找到第一跳点，相当于这一轴方向上没有第一
跳点。示意性的如图7所示，从当前节点p出发，向往右的轴方向上进行寻路搜索，可见该方
向上找不到第一跳点。此时，结束该轴方向上的寻路搜索。据此，本申请实施例提供的地图
寻路方法中，还包括如下步骤。

[0144] 步骤407：在未搜索到第一跳点的情况下，获取另一个待搜索的节点作为当前节点，重新从步骤403开始执行。

[0145] 相当于，沿另一个待搜索的节点的候选搜索方向进行搜索，得到候选搜索方向上的跳点。示意性的，待搜索的节点从第一节点集合中获取。此时，另一个待搜索的节点的候
选搜索方向可以是轴方向，也可以是对角方向，在同时包括轴方向和对角方向的情况下，先
进行轴方向上的寻路搜索，再进行对角方向上的寻路搜索。

[0146] 示意性的，步骤405、步骤406和步骤407只能择一执行，不能同时执行。

[0147] 二、当前节点的候选搜索方向包括对角方向。

[0148] 步骤4042：沿当前节点的对角方向进行搜索，得到第二跳点。

[0149] 示意性的，第二跳点是具有中间跳点的节点，中间跳点是在第二跳点的对角方向相邻的两个轴方向中的任一方向上搜索到的具有强迫邻居的节点，强迫邻居是中间跳点和
阻挡节点共同相邻的节点，强迫邻居位于当前搜索方向的前方，阻挡节点是障碍物所在的
节点。

[0150] 在当前节点的候选搜索方向是对角方向时，由于运动物体无法在对角方向上进行移动，本申请实施例提供的寻路方法中，将对角方向上的搜索分为两个轴方向上的搜索。

[0151] 示意性的，步骤“沿当前节点的对角方向进行搜索”有如下实现方式：沿当前节点的对角方向相邻的两个轴方向分别进行搜索。示意性的如图8所示，节点y的候选搜索方向
是右上的对角方向，在进行寻路搜索过程中，将右上的对角方向分为两个轴方向，分别为d1
方向和d2方向，这两个轴方向与右上的对角方向相邻。

[0152] 在搜索到第二跳点后，在该搜索方向的寻路搜索结束。比如，在节点a向右上的对角方向上搜索到了第二跳点后，节点a将不再向右上的对角方向上继续进行寻路搜索，其搜
索方向根据下一个当前节点确定。

[0153] 根据前述内容，第二跳点是寻路路径中可能存在的转角节点。因此，需要将第二跳点设置为待搜索的节点中的一个进行寻路搜索，此时，需要判断第二跳点是否存在于第一
节点集合中，根据判断结果，有如下可选的执行步骤。

[0154] 步骤408：响应于第二跳点不是待搜索的节点中的一个，将当前节点确定为第二跳点的父节点。

[0155] 比如，在节点a向右上的对角方向上搜索到了第二跳点，第二跳点不存在于第一节点集合中，将节点a确定为第二跳点的父节点，将第二跳点加入第一节点集合中。

[0156] 步骤409：响应于第二跳点是待搜索的节点中的一个，根据第三路径和第四路径确定第二跳点的父节点。

[0157] 示意性的，第三路径是寻路路径的起始节点经过当前节点到达第二跳点的路径，第四路径是起始节点不经过当前节点到达第二跳点的路径。

[0158] 此时，根据第三路径和第四路径的长度的不同，第二跳点的父节点也不同，具体的，步骤409有如下两种可选的实现方式。

[0159] 响应于第三路径的长度小于第四路径的长度，将到达第二跳点的前一个转角节点确定为第二跳点的父节点；

[0160] 响应于第三路径的长度不小于第四路径的长度，将当前节点确定为第二跳点的父节点。

[0161] 与第一跳点的阐述相似，在搜索到第二跳点后，若第三路径的长度较短，相当于起始节点经过当前节点到达第二跳点的路径的长度较短，而由于第二跳点位于第一节点集合
中，可以找到到达第二跳点的前一个转角节点。因此，将第二跳点的前一个转角节点确定为
父节点。若第三路径的长度长，相当于起始节点经过当前节点到达第二跳点的路径的长度
较长，此时经过当前节点可以得到较短的路径长度。因此，将当前节点确定为第二跳点的父
节点。

[0162] 比如，在节点a向右上的对角方向上搜索到了第二跳点，节点a包括于第一节点集合中，计算得到：起始节点经过节点a到达第二跳点的路径的长度为5，起始节点不经过节点
a到达第二跳点的路径的长度为7，则将到达第二跳点的上一个转角节点确定为第二跳点的
父节点。

[0163] 与当前节点的候选搜索方向是轴方向的情况相似，由于网格地图是有边界的，当在对角方向上逐次搜索过每一个节点后，若不能找到第二跳点，相当于在当前节点的这一
对角方向上没有第二跳点，此时，结束当前节点在该对角方向上的寻路搜索。据此，本申请
实施例提供的地图寻路方法中，还包括步骤410和步骤411两种可选的执行步骤。

[0164] 步骤410：在未搜索到第二跳点的情况下，将当前节点的对角节点更新为新的当前节点，重新从步骤4042开始执行。

[0165] 其中，对角节点是原有的当前节点在对角方向上移动一格的节点。相当于，将正在进行寻路搜索的节点向对角方向上移动一格，得到正在进行寻路搜索的节点的对角节点，
沿对角节点的对角方向重新进行搜索。示意性的如图8所示，节点p是当前节点，粗箭头方向
为搜索方向，节点p在右上的对角方向上未搜索到第二跳点，此时沿右上的对角方向移动一
格，得到节点y，从节点y出发，沿右上的对角方向重新进行搜索。

[0166] 由于当前节点在向对角方向上进行移动一格时，可能无法找到对角节点，或者对角节点是阻挡节点。示意性的，本申请实施例提供的寻路方法中，还包括如下步骤。

[0167] 在对角节点不存在，或者，在对角节点是阻挡节点的情况下，获取另一个待搜索的节点作为当前节点，重新从步骤403开始执行。示意性的，待搜索的节点从第一节点集合中
获取。

[0168] 步骤411：在未搜索到第二跳点的情况下，获取另一个待搜索的节点作为当前节点，重新从步骤403开始执行。

[0169] 相当于，沿第一节点集合中的另一个待搜索的节点的候选搜索方向进行搜索，得到候选搜索方向上的跳点。示意性的，待搜索的节点从第一节点集合中获取。此时，另一个
待搜索的节点的候选搜索方向可以是对角方向，也可以是对角方向，在同时包括对角方向
和对角方向的情况下，先进行对角方向上的寻路搜索，再进行对角方向上的寻路搜索。

[0170] 示意性的，步骤408、步骤409、步骤410和步骤411只能择一执行，不能同时执行。

[0171] 步骤412：在搜索到寻路路径的终止节点后，从终止节点开始逐跳回溯父节点以生成所述寻路路径。

[0172] 由于寻路搜索的候选搜索方向趋向于终止节点的位置，因此，无论搜索方向是是轴方向还是对角方向，在搜索到终止节点时，寻路结束，从终止节点回溯一个或多个父节点
已生成寻路路径。

[0173] 示意性的，步骤412与步骤308相同，可作参考，在此不再赘述。

[0174] 综上所述，根据当前节点的候选搜索方向的不同，本申请实施例提供了多种跳点的父节点的确定方法，使得父节点的确定趋向于最优选择，从而使得生成的寻路路径能够
成为最优路径。

[0175] 图13示出了本申请实施例提供的地图寻路方法的另一种方法流程图，可用于以正六边形网格地图作为场景的大型多人在线游戏（Massive Multiplayer Online，MMO）、策略
类游戏（Simulation Game，SLG）等中以提高此类游戏中地图中的寻路速度，能够快速准确
地为玩家提供一条从起始节点到终止节点的移动路径。以当前节点包括于第一节点集合为
例，本申请实施例提供的地图寻路方法包括如下步骤。

[0176] 步骤501：将起始节点加入第一节点集合并设置候选搜索方向。

[0177] 其中，起始节点是起点所在的节点，起始节点的候选搜索方向包括六个轴方向和六个对角方向。

[0178] 步骤502：判断第一节点集合是否为空。

[0179] 第一节点集合为空，相当于没有待搜索的节点；第一节点集合不为空，相当于存在至少一个待搜索的节点。在第一节点集合为空的情况下，寻路结束；在第一节点集合不为空
的情况下，执行步骤503。

[0180] 步骤503：在第一节点集合不为空的情况下，根据节点的权重值确定当前节点。

[0181] 示意性的，当前节点的确定可参考步骤402的内容，在此不再赘述。

[0182] 步骤504：判断当前节点是否是终止节点。

[0183] 步骤505：在当前节点是终止节点的情况下，根据父节点和终止节点生成寻路路径。

[0184] 步骤506：在当前节点不是终止节点的情况下，沿当前节点的候选搜索方向进行寻路搜索。

[0185] 其中，在当前节点的候选搜索方向既包括轴方向，也包括对角方向的情况下，先在轴方向上进行所述，再在对角方向上进行搜索。无论在哪个方向上进行搜索，在搜索到跳
点、或者是遇到边界或阻挡节点时结束该方向上的寻路搜索，在其他方向上继续进行寻路
搜索。

[0186] 步骤507：沿当前节点的轴方向进行搜索。

[0187] 步骤508：判断是否搜索到第一跳点。

[0188] 示意性的，在搜索到第一跳点的情况下，执行步骤509；在未搜索到第一跳点情况下，执行步骤502。

[0189] 步骤509：在搜索到第一跳点的情况下，将第一跳点或第二跳点设置为新的跳点。

[0190] 步骤510：沿当前节点的对角方向进行搜索。

[0191] 步骤511：判断是否搜索到第二跳点。

[0192] 示意性的，在搜索到第二跳点的情况下，执行步骤509；在未搜索到第二跳点情况下，执行步骤512。

[0193] 步骤512：在未搜索到第二跳点的情况下，将对角节点确定为当前节点，直至对角节点不存在或对角节点为阻挡节点。

[0194] 具体的，在对角节点存在时，执行步骤510，在对角节点不存在或对角节点是阻挡节点时，执行步骤502。

[0195] 示意性的，步骤507和步骤508，步骤510、步骤511和步骤512形成的两组步骤，可以只执行其一，不可以同时执行；若两组步骤均存在，先执行步骤507和步骤508，再执行步骤
510、步骤511和步骤512。

[0196] 步骤513：判断新的跳点是否已搜索。

[0197] 在新的跳点已经被搜索过的情况下，执行步骤502；在新的跳点未被搜索过的情况下，执行步骤514。

[0198] 步骤514：判断新的跳点是否在第一节点集合中。

[0199] 步骤515：新的跳点不在第一节点集合中的情况下，将当前节点确定为新的跳点的父节点，将新的跳点加入到第一节点集合中。

[0200] 步骤516：新的跳点在第一节点集合中的情况下，根据起始节点经过或者不经过当前节点到达新的跳点的路径确定父节点。

[0201] 其中，步骤515和步骤516中确定父节点的具体方法可参考前述内容，在此不再赘述。

[0202] 示意性的，在执行完步骤515或者步骤516后，重新执行步骤502。

[0203] 示意性的如图14所示，本申请提供了寻路方法的一个示例性的实施例。其中，节点1为起始节点，节点z为终止节点，黑色节点为阻挡节点，点阵填充的节点是已经搜索过的节
点。根据立方体坐标系，节点1的坐标值为（‑2，1，1），节点z的坐标值为（3，‑2，‑1）。

[0204] 据此，从节点1到节点z的寻路路径的寻路搜索包括如下步骤。

[0205] 首先，将节点1加入到第一节点集合中，并将节点1的候选搜索方向设置为六个轴方向和六个对角方向。

[0206] 步骤1：确定当前节点，沿节点1的候选搜索方向进行搜索，确定搜索到的跳点和跳点的父节点。

[0207] 此时，第一节点集合中只有节点1，将节点1设置为当前节点。

[0208] 结合图14中的第一个正六边形网格，从节点1出发，先沿六个轴方向进行寻路搜索，得到节点2和节点3为第一跳点；再沿六个对角方向进行寻路搜索，未找到第二跳点。根
据立方体坐标系，节点2的坐标值为（‑2，0，2），节点3的坐标值为（1，1，‑2）。

[0209] 节点2和节点3均不在第一节点集合中，因此，将当前节点确定为节点2和节点3的父节点，将节点2和节点3加入到第一节点集合中。也即，跳点2和跳点3的父节点均为节点1。

[0210] 步骤2：重新确定当前节点，并沿当前节点的候选搜索方向进行搜索，确定搜索到的跳点和跳点的父节点。

[0211] 此时，第一节点集合中有节点2和节点3，根据前述内容，节点n的权重值可通过公式f(n)=g(n)+h(n)得到。计算可得：

[0212] f(2)=1+ (abs(3‑(‑2)) + abs((‑2)‑0)+abs((‑1)‑2))/2=6，

[0213] f(3)=3+(abs(3‑1) + abs((‑2)‑1)+abs((‑1)‑(‑2)))/2=6。

[0214] 在两个节点的权重值相同时，考虑当前节点到跳点的距离。也即，在f(n)相同的情况下，优先选择g(n)的值大的节点。据此，将节点3确定为新的当前节点。

[0215] 结合图14中的第一个和第二个正六边形网格，节点3的原搜索方向为右上的轴方向，节点4是节点3的强迫邻居。当节点3成为当前节点时，其搜索方向包括原搜索方向、强迫
邻居所在的轴方向以及原搜索方向和强迫邻居所在的轴方向之间的对角方向。也即，节点3
的候选搜索方向包括：右上的轴方向、水平向右的轴方向以及右上的对角方向。

[0216] 先进行轴方向上的寻路搜索，可以得到节点4为第一跳点；再进行对角方向上的寻路搜索，未发现第二跳点。根据立方体坐标系，节点4的坐标值为（2，0，‑2）。

[0217] 节点4不在第一节点集合中，因此，将当前节点作为节点4的父节点，将节点4加入到第一节点集合中。也即，节点4的父节点为节点3。

[0218] 步骤3：再次确定当前节点，并沿当前节点的候选搜索方向进行搜索，确定搜索到的跳点和跳点的父节点。

[0219] 此时，第一节点集合中有节点2和节点4，根据前述内容，节点n的权重值可通过公式f(n)=g(n)+h(n)得到。计算可得：

[0220] f(2)=1+ (abs(3‑(‑2)) + abs((‑2)‑0)+abs((‑1)‑2))/2=6，

[0221] f(4)=4+(abs(3‑2) + abs((‑2)‑0)+abs((‑1)‑(‑2)))/2=6。

[0222] 在两个节点的权重值相同时，考虑当前节点到跳点的距离。也即，在f(n)相同的情况下，优先选择g(n)的值大的节点。据此，将节点4确定为新的当前节点。

[0223] 结合图14中的第二个和第三个正六边形网格，节点4的原搜索方向为水平向右的轴方向，节点5是节点4的强迫邻居。当节点4成为当前节点时，其搜索方向包括原搜索方向、
强迫邻居所在的轴方向以及原搜索方向和强迫邻居所在的轴方向之间的对角方向。也即，
节点4的候选搜索方向包括：水平向右的轴方向、右下的轴方向以及右下的对角方向。

[0224] 先进行轴方向上的寻路搜索，可以得到节点6为第一跳点；再进行对角方向上的寻路搜索，可以得到节点z为第二跳点。节点6和节点z不在第一节点集合中，因此，将当前节点
作为节点6和节点z的父节点。也即，节点6和节点z的父节点为节点4。

[0225] 此时，由于搜索到的跳点中包括终止节点z，可根据确定的多个父节点和终止节点（即节点z）生成寻路路径的节点信息，其中多个父节点包括节点1、节点3和节点4。其中，节
点1到节点3的距离为3，节点3到节点4的距离为1，节点4到节点z的距离为2，则节点1到节点
z的距离为6，可以认为，寻路路径的长度为6。

[0226] 由于节点4和节点z是对角节点，因此需要在两个对角节点中插入中间点。示意性的如图15所示，节点4和节点z 共同相邻的两个邻居节点分别是节点5和节点7。此时，可生
成如下两条寻路路径。

[0227] 图15的（a）中示出的粗线条即为寻路路径一：运动物体从节点1出发，经节点3、节点4和节点7到达节点z。

[0228] 图15的（b）中示出的粗线条即为寻路路径二：运动物体从节点1出发，经节点3、节点4和节点5到达节点z。

[0229] 综上所述，本申请实施例提供了一种地图寻路方法，通过从终止节点逐跳回溯父节点，从而生成寻路路径的最优路径，减少了寻路搜索过程所需要搜索的节点的数量，提高
了寻路搜索的速度。

[0230] 以下为本申请的装置实施例，对于装置实施例中未详细描述的细节，可参考上述方法实施例。

[0231] 图16示出了本申请实施例提供的地图寻路装置的框图，所述装置包括确定模块1620、搜索模块1640和生成模块1660；

[0232] 确定模块1620，用于确定地图中的待搜索的当前节点；

[0233] 搜索模块1640，用于沿当前节点的候选搜索方向进行搜索，得到候选搜索方向上的跳点，跳点是寻路路径中候选的转角节点，转角节点是路径前进方向发生改变的节点；

[0234] 确定模块1620，还用于确定跳点的父节点，父节点包括寻路路径中到达跳点的前一个转角节点；

[0235] 生成模块1660，用于在搜索到寻路路径的终止节点后，从终止节点开始逐跳回溯父节点以生成寻路路径。

[0236] 在本申请的一种可能实现的方式下，所述搜索模块1640用于：沿当前节点的轴方向进行搜索，得到第一跳点；其中，第一跳点是具有强迫邻居的节点，强迫邻居是第一跳点
和阻挡节点共同相邻的节点，强迫邻居位于轴方向的前方，阻挡节点是障碍物所在的节点。

[0237] 在本申请的一种可能实现的方式下，所述确定模块1620用于：响应于第一跳点不是待搜索的节点中的一个，将当前节点确定为第一跳点的父节点。

[0238] 在本申请的一种可能实现的方式下，所述确定模块1620用于：响应于第一跳点是待搜索的节点中的一个，根据第一路径和第二路径确定第一跳点的父节点；其中，第一路径
是寻路路径的起始节点经过当前节点到达第一跳点的路径，第二路径是起始节点不经过当
前节点到达第一跳点的路径。

[0239] 在本申请的一种可能实现的方式下，所述确定模块1620用于：响应于第一路径的长度小于第二路径的长度，将到达第一跳点的前一个转角节点确定为第一跳点的父节点。

[0240] 在本申请的一种可能实现的方式下，所述确定模块1620用于：响应于第一路径的长度不小于第二路径的长度，将当前节点确定为第一跳点的父节点。

[0241] 在本申请的一种可能实现的方式下，所述搜索模块1640还用于：在未搜索到第一跳点的情况下，获取另一个待搜索的节点作为当前节点，重新从沿当前节点的候选搜索方
向进行搜索，得到候选搜索方向上的跳点的步骤开始执行。

[0242] 在本申请的一种可能实现的方式下，所述搜索模块1640用于：沿当前节点的对角方向进行搜索，得到第二跳点；其中，第二跳点是具有中间跳点的节点，中间跳点是在第二
跳点的对角方向相邻的两个轴方向中的任一方向上搜索到的具有强迫邻居的节点，强迫邻
居是中间跳点和阻挡节点共同相邻的节点，强迫邻居位于当前搜索方向的前方，阻挡节点
是障碍物所在的节点。

[0243] 在本申请的一种可能实现的方式下，所述确定模块1620用于：响应于第二跳点不是待搜索的节点中的一个，将当前节点确定为第二跳点的父节点。

[0244] 在本申请的一种可能实现的方式下，所述确定模块1620用于：响应于第二跳点是待搜索的节点中的一个，根据第三路径和第四路径确定第二跳点的父节点；其中，第三路径
是寻路路径的起始节点经过当前节点到达第二跳点的路径，第四路径是起始节点不经过当
前节点到达第二跳点的路径。

[0245] 在本申请的一种可能实现的方式下，所述确定模块1620用于：响应于第三路径的长度小于第四路径的长度，将到达第二跳点的前一个转角节点确定为第二跳点的父节点。

[0246] 在本申请的一种可能实现的方式下，所述确定模块1620用于：响应于第三路径的长度不小于第四路径的长度，将当前节点确定为第二跳点的父节点。

[0247] 在本申请的一种可能实现的方式下，所述搜索模块1640还用于：在未搜索到第二跳点的情况下，将当前节点的对角节点更新为新的当前节点，重新从沿当前节点的对角方
向进行搜索，得到第二跳点的步骤开始执行，对角节点是原有的当前节点在对角方向上移
动一格的节点。

[0248] 在本申请的一种可能实现的方式下，所述搜索模块1640还用于：在未搜索到第二跳点的情况下，获取另一个待搜索的节点作为当前节点，重新从沿当前节点的候选搜索方
向进行搜索，得到候选搜索方向上的跳点的步骤开始执行。

[0249] 在本申请的一种可能实现的方式下，所述确定模块1620用于：根据待搜索的节点的权重值确定当前节点，待搜索的节点的权重值是起始节点到达待搜索的节点的路径的长
度和待搜索的节点到达终止节点的预估路径的长度之和。

[0250] 图17示出了本申请一个示例性实施例提供的终端20000的结构框图。该终端2000可以是：智能手机、平板电脑、MP3播放器（Moving Picture Experts Group Audio Layer 
III，动态影像专家压缩标准音频层面3）、MP4（Moving Picture Experts Group Audio 
Layer IV，动态影像专家压缩标准音频层面4）播放器、笔记本电脑或台式电脑。终端2000还
可能被称为用户设备、便携式终端、膝上型终端、台式终端等其它名称。

[0251] 通常，终端2000包括有：处理器2001和存储器2002。

[0252] 处理器2001可以包括一个或多个处理核心，比如4核心处理器、8核心处理器等。处理器2001可以采用DSP（Digital Signal Processing，数字信号处理）、FPGA（Field－
Programmable Gate Array，现场可编程门阵列）、PLA（Programmable Logic Array，可编程
逻辑阵列）中的至少一种硬件形式来实现。处理器2001也可以包括主处理器和协处理器，主
处理器是用于对在唤醒状态下的数据进行处理的处理器，也称CPU（Central Processing 
Unit，中央处理器）；协处理器是用于对在待机状态下的数据进行处理的低功耗处理器。在
一些实施例中，处理器2001可以在集成有GPU（Graphics Processing Unit，图像处理器），
GPU用于负责显示屏所需要显示的内容的渲染和绘制。一些实施例中，处理器2001还可以包
括AI（Artificial Intelligence，人工智能）处理器，该AI处理器用于处理有关机器学习的
计算操作。

[0253] 存储器2002可以包括一个或多个计算机可读存储介质，该计算机可读存储介质可以是非暂态的。存储器2002还可包括高速随机存取存储器，以及非易失性存储器，比如一个
或多个磁盘存储设备、闪存存储设备。在一些实施例中，存储器2002中的非暂态的计算机可
读存储介质用于存储至少一个指令，该至少一个指令用于被处理器2001所执行以实现本申
请中方法实施例提供的虚拟角色的控制方法。

[0254] 在一些实施例中，终端2000还可选包括有：外围设备接口2003和至少一个外围设备。处理器2001、存储器2002和外围设备接口2003之间可以通过总线或信号线相连。各个外
围设备可以通过总线、信号线或电路板与外围设备接口2003相连。具体地，外围设备包括：
射频电路2004、触摸显示屏2005、摄像头组件2006、音频电路2007、定位组件2008和电源
2009中的至少一种。

[0255] 外围设备接口2003可被用于将I/O（Input /Output，输入/输出）相关的至少一个外围设备连接到处理器2001和存储器2002。在一些实施例中，处理器2001、存储器2002和外
围设备接口2003被集成在同一芯片或电路板上；在一些其它实施例中，处理器2001、存储器
2002和外围设备接口2003中的任意一个或两个可以在单独的芯片或电路板上实现，本实施
例对此不加以限定。

[0256] 射频电路2004用于接收和发射RF（Radio Frequency，射频）信号，也称电磁信号。射频电路2004通过电磁信号与通信网络以及其它通信设备进行通信。射频电路2004将电信
号转换为电磁信号进行发送，或者，将接收到的电磁信号转换为电信号。可选地，射频电路
2004包括：天线系统、RF收发器、一个或多个放大器、调谐器、振荡器、数字信号处理器、编解
码芯片组、用户身份模块卡等等。射频电路2004可以通过至少一种无线通信协议来与其它
终端进行通信。该无线通信协议包括但不限于：万维网、城域网、内联网、各代移动通信网络
（2G、3G、4G及5G）、无线局域网和/或WiFi(Wireless Fidelity，无线保真）网络。在一些实施
例中，射频电路2004还可以包括NFC（Near Field Communication，近距离无线通信）有关的
电路，本申请对此不加以限定。

[0257] 触摸显示屏2005用于显示UI（User Interface，用户界面）。该UI可以包括图形、文本、图标、视频及其它们的任意组合。当触摸显示屏2005还具有采集在触摸显示屏2005的表
面或表面上方的触摸信号的能力。该触摸信号可以作为控制信号输入至处理器2001进行处
理。此时，触摸显示屏2005还可以用于提供虚拟按钮和/或虚拟键盘，也称软按钮和/或软键
盘。在一些实施例中，触摸显示屏2005可以为一个，设置终端2000的前面板；在另一些实施
例中，触摸显示屏2005可以为至少两个，分别设置在终端2000的不同表面或呈折叠设计；在
再一些实施例中，触摸显示屏2005可以是柔性显示屏，设置在终端2000的弯曲表面上或折
叠面上。甚至，触摸显示屏2005还可以设置成非矩形的不规则图形，也即异形屏。触摸显示
屏2005可以采用LCD(Liquid Crystal Display，液晶显示屏)、OLED(Organic Light‑
Emitting Diode，有机发光二极管)等材质制备。

[0258] 摄像头组件2006用于采集图像或视频。可选地，摄像头组件2006包括前置摄像头和后置摄像头。通常，前置摄像头设置在终端的前面板，后置摄像头设置在终端的背面。在
一些实施例中，后置摄像头为至少两个，分别为主摄像头、景深摄像头、广角摄像头、长焦摄
像头中的任意一种，以实现主摄像头和景深摄像头融合实现背景虚化功能、主摄像头和广
角摄像头融合实现全景拍摄以VR（Virtual Reality，虚拟现实）拍摄功能或者其它融合拍
摄功能。在一些实施例中，摄像头组件2006还可以包括闪光灯。闪光灯可以是单色温闪光
灯，也可以是双色温闪光灯。双色温闪光灯是指暖光闪光灯和冷光闪光灯的组合，可以用于
不同色温下的光线补偿。

[0259] 音频电路2007可以包括麦克风和扬声器。麦克风用于采集用户及环境的声波，并将声波转换为电信号输入至处理器2001进行处理，或者输入至射频电路2004以实现语音通
信。出于立体声采集或降噪的目的，麦克风可以为多个，分别设置在终端2000的不同部位。
麦克风还可以是阵列麦克风或全向采集型麦克风。扬声器则用于将来自处理器2001或射频
电路2004的电信号转换为声波。扬声器可以是传统的薄膜扬声器，也可以是压电陶瓷扬声
器。当扬声器是压电陶瓷扬声器时，不仅可以将电信号转换为人类可听见的声波，也可以将
电信号转换为人类听不见的声波以进行测距等用途。在一些实施例中，音频电路2007还可
以包括耳机插孔。

[0260] 定位组件2008用于定位终端2000的当前地理位置，以实现导航或LBS（Location Based Service，基于位置的服务）。定位组件2008可以是基于美国的GPS（Global 
Positioning System，全球定位系统）、中国的北斗系统或俄罗斯的伽利略系统的定位组
件。

[0261] 电源2009用于为终端2000中的各个组件进行供电。电源2009可以是交流电、直流电、一次性电池或可充电电池。当电源2009包括可充电电池时，该可充电电池可以是有线充
电电池或无线充电电池。有线充电电池是通过有线线路充电的电池，无线充电电池是通过
无线线圈充电的电池。该可充电电池还可以用于支持快充技术。

[0262] 在一些实施例中，终端2000还包括有一个或多个传感器2010。该一个或多个传感器2010包括但不限于：加速度传感器2011、陀螺仪传感器2012、压力传感器2013、指纹传感
器2014、光学传感器2015以及接近传感器2016。

[0263] 加速度传感器2011可以检测以终端2000建立的坐标系的三个坐标轴上的加速度大小。比如，加速度传感器2011可以用于检测重力加速度在三个坐标轴上的分量。处理器
2001可以根据加速度传感器2011采集的重力加速度信号，控制触摸显示屏2005以横向视图
或纵向视图进行用户界面的显示。加速度传感器2011还可以用于游戏或者用户的运动数据
的采集。

[0264] 陀螺仪传感器2012可以检测终端2000的机体方向及转动角度，陀螺仪传感器2012可以与加速度传感器2011协同采集用户对终端2000的3D动作。处理器2001根据陀螺仪传感
器2012采集的数据，可以实现如下功能：动作感应（比如根据用户的倾斜操作来改变UI）、拍
摄时的图像稳定、游戏控制以及惯性导航。

[0265] 压力传感器2013可以设置在终端2000的侧边框和/或触摸显示屏2005的下层。当压力传感器2013设置在终端2000的侧边框时，可以检测用户对终端2000的握持信号，由处
理器2001根据压力传感器2013采集的握持信号进行左右手识别或快捷操作。当压力传感器
2013设置在触摸显示屏2005的下层时，由处理器2001根据用户对触摸显示屏2005的压力操
作，实现对UI界面上的可操作性控件进行控制。可操作性控件包括按钮控件、滚动条控件、
图标控件、菜单控件中的至少一种。

[0266] 指纹传感器2014用于采集用户的指纹，由处理器2001根据指纹传感器2014采集到的指纹识别用户的身份，或者，由指纹传感器2014根据采集到的指纹识别用户的身份。在识
别出用户的身份为可信身份时，由处理器2001授权该用户执行相关的敏感操作，该敏感操
作包括解锁屏幕、查看加密信息、下载软件、支付及更改设置等。指纹传感器2014可以被设
置终端2000的正面、背面或侧面。当终端2000上设置有物理按键或厂商Logo时，指纹传感器
2014可以与物理按键或厂商Logo集成在一起。

[0267] 光学传感器2015用于采集环境光强度。在一个实施例中，处理器2001可以根据光学传感器2015采集的环境光强度，控制触摸显示屏2005的显示亮度。具体地，当环境光强度
较高时，调高触摸显示屏2005的显示亮度；当环境光强度较低时，调低触摸显示屏2005的显
示亮度。在另一个实施例中，处理器2001还可以根据光学传感器2015采集的环境光强度，动
态调整摄像头组件2006的拍摄参数。

[0268] 接近传感器2016，也称距离传感器，通常设置在终端2000的前面板。接近传感器2016用于采集用户与终端2000的正面之间的距离。在一个实施例中，当接近传感器2016检
测到用户与终端2000的正面之间的距离逐渐变小时，由处理器2001控制触摸显示屏2005从
亮屏状态切换为息屏状态；当接近传感器2016检测到用户与终端2000的正面之间的距离逐
渐变大时，由处理器2001控制触摸显示屏2005从息屏状态切换为亮屏状态。

[0269] 本领域技术人员可以理解，图17中示出的结构并不构成对终端2000的限定，可以包括比图示更多或更少的组件，或者组合某些组件，或者采用不同的组件布置。

[0270] 本申请还提供了一种计算机设备，计算机设备包括处理器和存储器，存储器中存储有至少一条程序代码，程序代码由处理器加载并执行以实现如上的地图寻路方法。

[0271] 本申请还提供了一种计算机可读存储介质，计算机可读存储介质中存储有至少一条程序代码，程序代码由处理器加载并执行以实现如上的地图寻路方法。

[0272] 本申请还提供了一种计算机程序产品或计算机程序，该计算机程序产品或计算机程序包括计算机指令，该计算机指令存储在计算机可读存储介质中。计算机设备的处理器
从计算机可读存储介质读取该计算机指令，处理器执行该计算机指令，使得该计算机设备
执行上述可选实现方式中提供的地图寻路方法。

[0273] 应当理解的是，在本文中提及的“多个”是指两个或两个以上。“和/或”，描述关联对象的关联关系，表示可以存在三种关系，例如，A和/或B，可以表示：单独存在A，同时存在A
和B，单独存在B这三种情况。字符“/”一般表示前后关联对象是一种“或”的关系。

[0274] 本领域普通技术人员可以理解实现上述实施例的全部或部分步骤可以通过硬件来完成，也可以通过程序来指令相关的硬件完成，所述的程序可以存储于一种计算机可读
存储介质中，上述提到的存储介质可以是只读存储器，磁盘或光盘等。

[0275] 以上所述仅为本申请的可选实施例，并不用以限制本申请，凡在本申请的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本申请的保护范围之内。