地图寻路方法和装置、存储介质和电子装置
技术领域
本申请涉及互联网领域，具体而言，涉及一种地图寻路方法和装置、存储介质和电子装置。
背景技术
目前，在游戏地图中，可以为游戏地图中的虚拟角色进行寻路，生成导航路径，上述游戏地图可以是MMO(Massive Multiplayer Online，大型多人在线)游戏大地图。寻路是指：给定地图上的起点和终点，寻找由起点到终点的一条路径。在进行寻路时，要求所寻的路径是可行的，且尽可能短。
当起点和终点位于不同的地图中时，需要寻找一条跨越多个地图的路径，例如，从塔的当前层到目标层(如，19层至4层)的路径。如果向另一张地图发起寻路请求，该地图尚未加载，导航网格数据获取不到，则无法生成路径。相关技术中，一般采用在游戏运行时加载所有地图的导航数据，以便生成跨地图路径。然而，由于加载的地图数量较多，需要占用过多的内存，导致游戏容易卡顿的问题。
因此，相关技术中的跨地图寻路方式，存在由于需要加载的地图数量过多导致的游戏容易卡顿的问题。
发明内容
本申请实施例提供了一种地图寻路方法和装置、存储介质和电子装置，以至少解决相关技术中的跨地图寻路方式存在由于需要加载的地图数量过多导致的游戏容易卡顿的问题。
根据本申请实施例的一个方面，提供了一种地图寻路方法，包括：确定移动起点所在的第一地图中的第一路径，其中，第一路径为移动起点至第一地图的目标出口的路径；确定移动终点所在的第二地图中的第二路径，其中，第二路径为第二地图的目标入口至移动终点的路径；根据第一路径、第二路径、以及预先存储的多个地图中的各个地图的入口与出口之间的路径，获取由移动起点至移动终点的第三路径，其中，多个地图包括第一地图和第二地图，在多个地图的具有关联关系的两个关联地图中，第一关联地图的出口与第二关联地图的入口关联。
根据本申请实施例的另一个方面，提供了一种地图寻路装置，包括：第一确定单元，用于确定移动起点所在的第一地图中的第一路径，其中，第一路径为移动起点至第一地图的目标出口的路径；第二确定单元，用于确定移动终点所在的第二地图中的第二路径，其中，第二路径为第二地图的目标入口至移动终点的路径；第一获取单元，用于根据第一路径、第二路径、以及预先存储的多个地图中的各个地图的入口与出口之间的路径，获取由移动起点至移动终点的第三路径，其中，多个地图包括第一地图和第二地图，在多个地图的具有关联关系的两个关联地图中，第一关联地图的出口与第二关联地图的入口关联。
根据本申请实施例的又一个方面，还提供了一种计算机可读的存储介质，该存储介质中存储有计算机程序，其中，该计算机程序被设置为运行时执行上述任一项方法实施例中的步骤。
根据本申请实施例的又一个方面，还提供了一种电子装置，包括存储器和处理器，存储器中存储有计算机程序，处理器被设置为运行计算机程序以执行上述任一项方法实施例中的步骤。
在本申请实施例中，采用保存地图传送门之间(入口与出口之间)的路径之间路径的方式，通过确定移动起点所在的第一地图中的第一路径，其中，第一路径为移动起点至第一地图的目标出口的路径；确定移动终点所在的第二地图中的第二路径，其中，第二路径为第二地图的目标入口至移动终点的路径；根据第一路径、第二路径、以及预先存储的多个地图中的各个地图的入口与出口之间的路径，获取由移动起点至移动终点的第三路径，其中，多个地图包括第一地图和第二地图，在多个地图的具有关联关系的两个关联地图中，第一关联地图的出口与第二关联地图的入口关联，由于每张地图存储传送门之间的路径，在进行地图寻路时，只需加载起点所在地图和终点所在地图的全部或者部分导航数据，其他地图则无需加载或者只需加载很少的导航数据，因此，可以达到减少所需加载的地图数量的目的，达到减少导航数据对内存的占用、提高游戏运行流畅性的技术效果，进而解决了相关技术中的跨地图寻路方式存在由于需要加载的地图数量过多导致的游戏容易卡顿的问题。
附图说明
此处所说明的附图用来提供对本申请的进一步理解，构成本申请的一部分，本申请的示意性实施例及其说明用于解释本申请，并不构成对本申请的不当限定。在附图中：
图1是根据本申请实施例的地图寻路方法的硬件环境的示意图；
图2是根据本申请实施例的一种可选的地图寻路方法的流程图；
图3是根据本申请实施例的一种可选的地图寻路方法的示意图；
图4是根据本申请实施例的另一种可选的地图寻路方法的示意图；
图5是根据本申请实施例的又一种可选的地图寻路方法的示意图；
图6是根据本申请实施例的又一种可选的地图寻路方法的示意图；
图7是根据本申请实施例的又一种可选的地图寻路方法的示意图；
图8是根据本申请实施例的又一种可选的地图寻路方法的示意图；
图9是根据本申请实施例的又一种可选的地图寻路方法的示意图；
图10是根据本申请实施例的又一种可选的地图寻路方法的示意图；
图11是根据本申请实施例的另一种可选的地图寻路方法的流程图；
图12是根据本申请实施例的一种可选的地图寻路装置的示意图；
图13是根据本申请实施例的一种电子装置的结构框图。
具体实施方式
为了使本技术领域的人员更好地理解本申请方案，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本申请一部分的实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都应当属于本申请保护的范围。
需要说明的是，本申请的说明书和权利要求书及上述附图中的术语“第一”、“第二”等是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。应该理解这样使用的数据在适当情况下可以互换，以便这里描述的本申请的实施例能够以除了在这里图示或描述的那些以外的顺序实施。此外，术语“包括”和“具有”以及他们的任何变形，意图在于覆盖不排他的包含，例如，包含了一系列步骤或单元的过程、方法、系统、产品或设备不必限于清楚地列出的那些步骤或单元，而是可包括没有清楚地列出的或对于这些过程、方法、产品或设备固有的其它步骤或单元。
根据本申请实施例的一方面，提供了一种地图寻路方法的方法实施例。可选地，在本实施例中，上述地图寻路方法可以应用于如图1所示的由终端101和服务器103所构成的硬件环境中。如图1所示，服务器102通过网络与终端101连接，可用于为终端或终端上安装的客户端提供服务(如游戏服务、应用服务等)，可在服务器上或独立于服务器设置数据库105，用于为服务器103提供数据存储服务，上述网络包括但不限于：广域网、城域网或局域网，终端101并不限定于PC(Personal Computer，个人计算机)、手机、平板电脑等。本申请实施例的地图寻路方法可以由服务器103来执行，也可以由终端101来执行，还可以是由服务器103和终端101共同执行。其中，终端101执行本申请实施例的地图寻路方法也可以是由安装在其上的客户端来执行。
可选地，本申请实施例中提供了一种地图寻路方法，图2是根据本申请实施例的一种可选的地图寻路方法的流程图，如图2所示，该方法可以包括以下步骤：
步骤S202，确定移动起点所在的第一地图中的第一路径，其中，第一路径为移动起点至第一地图的目标出口的路径；
步骤S204，确定移动终点所在的第二地图中的第二路径，其中，第二路径为第二地图的目标入口至移动终点的路径；
步骤S206，根据第一路径、第二路径、以及预先存储的多个地图中的各个地图的入口与出口之间的路径，获取由移动起点至移动终点的第三路径，其中，多个地图包括第一地图和第二地图，在多个地图的具有关联关系的两个关联地图中，第一关联地图的出口与第二关联地图的入口关联。
通过上述步骤S202至步骤S206，通过确定移动起点所在的第一地图中的第一路径，其中，第一路径为移动起点至第一地图的目标出口的路径；确定移动终点所在的第二地图中的第二路径，其中，第二路径为第二地图的目标入口至移动终点的路径；根据第一路径、第二路径、以及预先存储的多个地图中的各个地图的入口与出口之间的路径，获取由移动起点至移动终点的第三路径，其中，多个地图包括第一地图和第二地图，在多个地图的具有关联关系的两个关联地图中，第一关联地图的出口与第二关联地图的入口关联，解决了相关技术中的跨地图寻路方式存在由于需要加载的地图数量过多导致的游戏容易卡顿的问题，减少了导航数据对内存的占用，提高了游戏运行流畅性。
在步骤S202提供的技术方案中，确定移动起点所在的第一地图中的第一路径，其中，第一路径为移动起点至第一地图的目标出口的路径。
本实施例中的地图寻路方法可以应用于地图中控制对象移动的场景，上述地图可以是游戏地图，或者其他场景地图(例如，购物地图等)。
地图寻路可以是在多个地图之间进行的。对于多个地图中的各个地图，每个地图可以具有入口和出口，例如，传送门。在多个地图中可以包含具有关联关系的两个关联地图，在两个关联地图中，一个地图(第一关联地图)的出口可以与另一个地图(第二关联地图)的入口关联。每个地图具有至少一个关联地图。
地图寻路所寻的路径为移动起点至移动终点的路径。移动起点所在的地图为第一地图。在进行地图寻路时，可以确定第一地图中的第一路径，该第一路径为移动起点至第一地图的目标出口的路径。
确定第一地图中的第一路径的方式可以有多种，所有可以进行单一地图内寻路的方式，均可用于本实施例中的地图寻路方法，例如，基于A*算法的寻路，基于Dijkstra算法的寻路。对于单一地图内寻路的方式，本实施例中对此不作具体限定。
该第一地图可以具有一个或多个出口，即，目标出口的数量可以有一个或多个，可以分别确定移动起点至各个目标出口的路径，得到多个第一路径。对于每个目标出口进行寻路所采用的方式可以相同，也可以不同，本实施例中对此不作限定。
在步骤S204提供的技术方案中，确定移动终点所在的第二地图中的第二路径，其中，第二路径为第二地图的目标入口至移动终点的路径。
地图寻路所寻的路径为移动起点至移动终点的路径。移动终点所在的地图为第二地图。在进行地图寻路时，可以确定第二地图中的第二路径，该第二路径为第二地图的目标入口至移动终点的路径。
确定第二地图中的第二路径的方式可以有多种，所有可以进行单一地图内寻路的方式，均可用于本实施例中的地图寻路方法，例如，基于A*算法的寻路，基于Dijkstra算法的寻路。对于单一地图内寻路的方式，本实施例中对此不作具体限定。
该第二地图可以具有一个或多个入口，即，目标入口的数量可以有一个或多个，可以分别确定各个目标入口至移动终点的路径，得到多个第二路径。对于每个目标入口进行寻路所采用的方式可以相同，也可以不同，本实施例中对此不作限定。
在步骤S206提供的技术方案中，根据第一路径、第二路径、以及预先存储的多个地图中的各个地图的入口与出口之间的路径，获取由移动起点至移动终点的第三路径，其中，多个地图包括第一地图和第二地图。
为了减少所需加载的导航数据，可以减少加载导航数据的地图数量，对于多个地图中的各个地图，可以预先存储各个地图的入口与出口之间的路径，也就是，传送门之间的路径。
在游戏运行的过程中，客户端控制的对象当前所在地图(例如，第一地图)的导航网格数据被加载，而无需为每张图都加载导航网格。其它地图只需要一个被初始化但是只有传送门周围导航数据的dtNavMesh空壳。在进行寻路时，可以加载第二地图(终点所在地图)的全部或者部分地图数据。由于已经预先存储了其他地图的入口与出口之间的路径，即使不加载全部的导航数据，也可以得到起点至终点的路径。
可选地，在本实施例中，在进行地图寻路时，根据第一路径、第二路径、以及预先存储的多个地图中的各个地图的入口与出口之间的路径，可以获取由移动起点至移动终点的第三路径。
在第一路径、第二路径为多个情况下，移动起点和移动终点之间的路径可以有多条。可以基于最短路径算法或者其他寻路算法查找移动起点至移动终点之间的一条路径，该路径可以是移动起点至移动终点的最短路径，或者，最快查找到的一条路径。对于获取第三路径的具体方式，本实施例中对此不作具体限定。
作为一种可选的实施例，确定移动起点所在的第一地图中的第一路径包括：
S11，确定第一地图的第一目标区域内的第一子路径，其中，第一目标区域为第一地图包含的多个第一区域中移动起点所在的区域，多个第一区域中的每个第一区域包含允许从每个第一区域进入到每个第一区域的相邻区域的邻接口，第一子路径为移动起点至第一目标区域的邻接口的路径；
S12，根据第一子路径、以及预先存储的每个第一区域的邻接口之间的路径，获取由移动起点至目标出口的第一路径，其中，目标出口属于目标出口所在的第二目标区域的邻接口。
多个地图中的每个地图可以包含有地图单元，该地图单元可以是地图划分的最小单位，每个地图单元可以是多边形。该多边形可以是形状规则的多边形，例如，栅格地图的地图单元为地图中的栅格，栅格为规则的四边形(方格)；该多边形也可以是形状不规则的凸多边形，例如，导航地图的地图单元为地图中的导航网格，导航网格为不规则的凸多边形。
确定移动起点所在的第一地图中的第一路径的方式可以有多种，例如，基于A*算法的寻路，基于Dijkstra算法的寻路。
以A*寻路为例，A*寻路是一种启发式搜索方式，基于导航区域中包含的多边形节点，通过对当前每一个搜索位置(多边形节点)进行估价，确定搜索的方向。A*寻路方式与地图中包含的多边形节点数量有关，多边形节点越多，寻路所需的时间越长，寻路效率越低。
为了提高寻路效率，可以将第一地图(多个地图中的其他地图与第一地图类似)划分为多个第一区域(集群，每个集群可以作为划分的一个高层地图的地图单元)，每个第一区域中包含多个基本地图单元；配置各第一区域的邻接口，即，允许从本区域进入到本区域的相邻区域的入口，并预先存储每个第一区域的邻接口之间的路径。基于保存的各第一区域的邻接口之间的路径，可以进行地图寻路。
需要说明的是，在本实施例中，通过对各个地图进行分层，每一高层地图单元(每个集群，每个区域)的多边形(例如，栅格，导航网格)数量尽可能的平均。得到的层可以认为是地图中的多边形的高层，在多边形之间的寻路可以抽象为集群与集群之间的寻路，即，在更高层地图上进行寻路。
例如，可以将栅格地图划分为多个区域(多个集群，每个区域对应于一个集群)，每个区域为该区域包含的栅格的高层。第一栅格到第二栅格的寻路，可以抽象为第一栅格所在的区域到第二栅格所在的区域的寻路，也就是，在高层地图上进行寻路。
可选地，在本实施例中，在使用第一地图(可以是多个地图中的任意一个)之前，可以先将第一地图划分为多个第一区域。第一地图可以是栅格地图或者导航地图，可以采用不同的方式将栅格地图和导航地图划分为多个区域。
在第一地图为栅格地图的情况下，可以按照第一地图的地图长度和地图宽度，将第一地图划分为大小相等的多个区域。例如，可预先配置每个区域的区域长度和区域宽度，按照区域长度和区域宽度，将第一地图划分为多个区域。
例如，如图3所示，游戏地图为栅格地图，可以对栅格地图中的栅格进行分层，抽象出栅格集群(每个集群相当于一个更高层次地图的地图单元)，每个集群对应于栅格地图中的一片区域，包含该区域内的所有栅格。
在第一地图为导航地图的情况下，可以按照第一地图包含的导航网格数量，将第一地图划分包含相同数量的导航网格的多个区域。例如，可预先配置每个区域中包含的导航网格的数量。按照预先配置的每个区域包含的导航网格的数量，可以将游戏地图划分为多个区域。
导航地图不像栅格地图那样规整，不能按照类似栅格地图一样利用坐标进行分层的方式。导航网格是一系列凸多边形节点组成的图，可以把导航地图中的凸多边形(导航网格)当作图论的节点，凸多边形之间的公共边作为图论的边，抽取出完整的图论模型，那么，对导航地图进行分层可以借助一些基于图论的分层算法：例如，multilevel bisectionalgorithm(多级二分算法)。该算法可以将任意给定的无向图均匀分成若干个集群，每个集群的节点数量在k个左右(k为输入值)。
对于导航地图，当图论的节点被分到各个集群之后，图论中的无向边可以分为两种：第一种无向边是边连接的两个节点都属于同一个集群，第二种无向边是边连接的两个节点属于不同的集群(这样的边可以称为“EdgeCut(割边)”)。第二种无向边连接两个不同的集群，等于就是集群与集群之间的连接关系，第二种无向边可以称为集群与集群的邻接边。
例如，如图4所示，游戏地图为导航地图，可以对导航地图中的导航网格进行分层，抽象出导航网格集群(每个集群相当于一个更高层次地图的节点)，每个集群对应于导航地图中的一片区域，包含该区域内的所有导航网格，每个集群中包含的导航网格的数量为预定值。
通过本实施例，通过对导航地图和栅格地图按照不同的方式划分为多个区域，可以保证区域划分的合理性，进而保证地图寻路的效率。
可选地，在本实施例中，对于第一地图被划分为的多个第一区域，可以分别识别并配置每个第一区域的邻接口。
对于多个第一区域中的任意相邻的两个第一区域，两者如果是连通的，则两个第一区域的邻接位置可以作为区域连通位置。每个第一区域中的连通位置可以是本区域进入相邻区域的区域入口(即，邻接口)，因此，每个第一区域可以包含允许从本区域进入到本区域的相邻区域的入口。
除了本地图中的区域与区域之间的邻接口以外，部分第一区域可以包含由本地图进行到其他地图的出口，或者，由其他区域进入到本区域的入口。两个地图之间的出入口(传送门)可以是相同的，也就是说，该传送门即是本地图传送到另一地图的出口，也是另一地图传送到本地图的入口。本地图与不同地图的传送门可以位于地图的不同位置，不同位置可以是本地图的相同区域中的位置，或者不同区域中的位置。
例如，地图A与地图B之间的传送门位于地图A的一个区域中的位置1，地图A与地图C之间的传送门位于地图A的另一个区域中的位置2。
目标出口位于第一地图的第二目标区域内，目标出口允许从第二目标区域进入到另一个地图中与第二目标区域相邻的区域(逻辑上相邻)，因此，目标出口属于第二目标区域的邻接口。
需要说明的是，对于各个地图中的各个区域，其包含的邻接口除了包含本区域与本地图中的相邻区域之间的入口，还可以包含本地图的出口。如果一个地图的出入口相同的情况下，本地图的出口即为本地图的出入口。
对于栅格地图和导航地图，可以采用不同的方式确定第一地图的各第一区域的邻接口以及邻接口之间的路径。
对于栅格地图，确定多个第一区域中的每个第一区域的邻接口的方式可以是：识别多个第一区域中的每个第一区域的候选邻接口，其中，候选邻接口为每个第一区域中允许从每个第一区域进入到每个第一区域的相邻区域的栅格；在候选邻接口包含连续的多个栅格的情况下，从多个栅格中选取一个栅格作为每个第一区域的一个邻接口；在候选邻接口包含不连续的一个或多个栅格的情况下，将一个或多个栅格确定为每个第一区域的一个或多个邻接口。
为了识别每个第一区域中包含的邻接口，则可以识别多个第一区域中的每个第一区域的候选邻接口。栅格地图中的候选邻接口为每个第一区域中允许从本区域进入到本区域的相邻区域的栅格。
对于识别的候选入口，其可以包含连续的栅格，也可以包含离散的栅格，对于连续栅格，各个栅格均可以作为该区域的邻接口。为减少寻路复杂度，可以从连续栅格中选取一个栅格作为该区域的一个邻接口，连续栅格中的其他栅格不作该区域的邻接口。对于离散栅格，可以直接将其作为该区域的邻接口。
例如，如图5所示，如果相邻集群的入口块(邻接口)的数量有连续的多个，可以选择其中相邻的两个作为该相邻集群的入口，并将入口相连。选择的入口块可以抽象为抽象图中的两个节点，该两个节点之间的边的权重为1。
通过本实施例，在候选邻接口包含连续的多个栅格时选择其中的一个作为邻接口，可以减少寻路复杂度，提高寻路效率。
每个第一区域中的邻接口的数量可以包含一个或者多个。如果一个第一区域中的邻接口的数量为一个，则该第一区域为出入口仅为一个，不存在邻接口之间的路径。如果一个第一区域中的邻接口的数量为多个，可以预先存储第一区域的邻接口之间的路径。
可选地，在本实施例中，可以首先确定多个第一区域中的每个第一区域的邻接口；在多个第一区域中包含具有多个邻接口的第一子区域的情况下，获取第一子区域内的多个邻接口之间的第一参考路径；并保存第一子区域内的多个邻接口之间的第一参考路径。
多个第一区域中的第一子区域包含多个邻接口。如果两个邻接口之间是连通的，则可以查找到两者之间的一条路径(例如，第一参考路径)。如果两个邻接口之间是不连通的，则无法查找到两者之间的路径。
例如，如果一个集群有多个相邻集群，在该集群包含多个出入口，可以在集群内部连接入口，也就是，将每个集群中的各个入口进行连接，得到集群内连接路径。
在得到每个第一区域中的邻接口之间的路径之后，可以保存得到的上述路径(例如，第一参考路径)，得到的路径可以保存在目标数据库中。
第一地图中的地图寻路可以抽象为抽象图中的寻路问题，该抽象图可以是基于图论模型的抽象图。每个第一区域的邻接口可以作为抽象图中的节点，邻接口之间的路径可以作为抽象图中的边，路径的长度可以作为边的权重。
如图6所示，左侧圆圈中的栅格块为同一集群内的入口，对应于抽象图中的节点(右侧中的圆圈)，两个入口之间的路径，对应于抽象图中节点之间的边，路径长度(所经过的栅格块数量)，对应于抽象图中的边的权重(6、8、12等)。
通过本实施例，通过识别并保存每个区域的入口之间的路径，可以便于在地图寻路的过程中使用，提高地图寻路效率。
对于导航地图，确定多个第一区域中的每个第一区域的邻接口可以为以下至少之一：
1)在邻接边上直接选取一个点作为高层集群与高层集群之间的入口。高层集群内路径保存一个入口点与另一个入口点之间的真实路径，最终路径由多个高层集群之间的真实路径拼接起来。
对于上述方式，可以确定多个第一区域中的每个第一区域与每个第一区域的相邻区域之间的邻接边；从每个第一区域的每个邻接边上选取一个邻接点作为每个邻接边上的邻接口，得到每个第一区域的邻接口；在多个第一区域中包含具有多个邻接口的第二子区域的情况下，获取第二子区域内的多个邻接口之间的第二参考路径；保存第二子区域内的多个邻接口之间的第二参考路径。
在确定每个第一区域内的邻接口之间的路径时，可以首先确定每个第一区域与该区域的相邻区域之间的邻接边，然后在邻接边上直接选取一个点作为区域与区域(高层集群与高层集群)之间的入口(邻接口)。
对于包含多个邻接口的第一区域(第二子区域)，可以分别确定多个邻接口中的任意两个邻接口之间的路径。如果两个邻接口之间是连通的，则可以查找到两者之间的一条路径(例如，第二参考路径)。如果两个邻接口之间是不连通的，则无法查找到两者之间的路径。
在得到每个第一区域中的邻接口之间的路径之后，可以保存得到的上述路径(例如，第二参考路径)，得到的路径可以保存在目标数据库中。
可选地，在本实施例中，对于导航网格，高层集群与高层集群之间的边界是EdgeCut类型的公共边(邻接边)，那么高层集群与高层集群之间的入口落在该公共边上。可以在相邻集群的公共边上直接选取一个点作为高层集群与高层集群之间的入口。高层集群内路径保存一个入口点与另一个入口点之间的真实路径(路点路径)，最终路径由多个高层集群之间的真实路径拼接起来。
对于上述场景，假设同一高层集群中与其它高层集群相连的有N个入口，那么该高层集群内一共计算N(N-1)/2次每两个入口间的路径，并存储O(N(N-1)/2)条路径。
通过本实施例，通过识别并保存每个第一区域的邻接口之间的路径，可以便于地图寻路的过程中使用，提高地图寻路效率。
2)先不直接选取一个点，以整条邻接边为入口。高层集群内路径保存的是一个入口邻接边和另一个入口邻接边之间的多边形路径(该路径为一片路径区域)。最终路径由多个高层集群之间的邻接边路径经过整体的StringPull算法等进行提炼得到。
对于上述方式，可以确定多个第一区域中的每个第一区域的邻接边，其中，每个第一区域的邻接边为每个第一区域与每个第一区域的相邻区域之间的邻接口；在多个第一区域中包含具有多个邻接边的第三子区域的情况下，以第三子区域内包含的导航网格为节点，以导航网格之间的公共边为边，搜索第三子区域内的多个邻接边之间的第一路径区域，其中，第一路径区域包含第一路径区域所经过的导航网格；保存第三子区域内的多个邻接边之间的第一路径区域。
对于导航地图中包含的多个第一区域，可以直接选择第一区域之间的整条邻接边作为邻接口，而先不直接选取一个点作为邻接口。对于导航地图中包含的多个第一区域，可以确定每个第一区域与该区域的相邻区域之间的邻接边(公共边)，并将邻接边作为该区域的邻接口。
对于包含多个邻接边的第一区域(第三子区域)，可以分别确定多个邻接边中的任意两个邻接边之间的路径。如果两个邻接边之间是连通的，则可以查找到两者之间的一条路径(例如，第一路径区域)。如果两个邻接边之间是不连通的，则无法查找到两者之间的路径。
在区域内进行邻接边之间的寻路时，可以以区域内包含的导航网格为节点，以导航网格之间的公共边为边，搜索该区域内的任意两个邻接边之间的路径，该路径包含一串凸多边形(即，包含一串导航网格，以及导航网格之间的公共边)，可以认为是一片路径区域(即，第一路径区域)。
在得到每个第一区域中的邻接边之间的路径区域之后，可以保存得到的上述路径区域(例如，第一路径区域)，得到的路径区域可以保存在目标数据库中。
对于导航地图，集群内路径保存的是入口公共边(邻接边)和入口公共边(邻接边)之间的多边形路径。
可选地，在本实施例中，在计算集群内不同入口之间的路径时，由于选择的是一整条公共边作为入口，这个信息属于抽象之后的图论模型上的信息。如果有多个节点A、B、C、D都要向点E进行寻路，可以以E为起点，反向地对所有节点调用单源最短路算法进行寻路。单源最短路算法最终输出的是以E点为根的最短路径搜索树。这样，如果一个集群有K个节点，N个入口点，一共需要保存N棵最短路径搜索树。对于保存一棵树的一种方法是直接存储每个节点的父亲节点，所以一共需要存储K*N个父亲节点即可。
通过本实施例，通过识别并保存每个区域的邻接边之间的路径，可以便于地图寻路的过程中使用，提高地图寻路效率。
在地图寻路的过程中，可以首先确定移动起点到所在区域内的邻接口之间的路径。移动起点位于第一地图中的第一目标区域内，服务器可以确定移动起点至第一目标区域的邻接口的路径(即，第一子路径)。
第一目标区域中的邻接口的数量可以有一个或多个，如果邻接口的数量为一个，该第一子路径可以包括该移动起点至该邻接口的一条路径。如果邻接口的数量为多个，该第一子路径可以包括该移动起点至每个邻接口的一条或多条路径。
在确定第一子路径时，对于栅格地图，可以采用相关技术中已有的地图寻路方法进行寻路，例如，基于A*算法的寻路，基于Dijkstra算法的寻路等，在此不做赘述。对于导航地图，对于邻接口为邻接边上的一个点的场景和为整条邻接边的场景，可以采用不同的方式确定子路径。
对于邻接口为邻接边上的一个点的场景，在计算起点到本集群邻接口的路径时，可以分别从移动起点向各个邻接口发起寻路，例如，基于A*算法的寻路，基于Dijkstra算法的寻路等，在此不做赘述。
例如，假如本集群入口分别是入口点A、B、C、D，起点是S，那么就需要从点S向A、B、C、D四个点发起四次寻路。
对于邻接口为整条邻接边的场景，在计算起点到本集群邻接口的路径时，由于已经对所有图论节点存储了最短路径树，可以首先将移动起点对应到所在的导航网格中，然后基于最短路径树查询该导航网格到各个邻接边的路径。
例如，在计算起点到本集群入口的路径时，由于已经对所有图论节点存储了最短路径树，不需要再进行寻路，如果要查询起点S到入口公共边P的路径，首先在导航网格上把起点S对应到凸多边形SS上，然后在以P为根的最短路径搜索树上，找到SS到P的路径即可(树上每两点间路径是唯一的)。
在得到第一子路径之后，可以根据第一子路径、以及预先存储的每个第一区域的邻接口之间的路径，获取由移动起点至目标出口的第一路径。
通过本实施例，通过将地图划分为多个区域，并预先存储各个区域的邻接口之间路径，可以减少寻路算法的搜索次数，提高地图的寻路效率。
作为一种可选的实施例，根据第一子路径、以及预先存储的每个第一区域的邻接口之间的路径，获取由移动起点至目标出口的第一路径包括：
S21，以移动起点、每个第一区域的邻接口为节点，以第一子路径、以及每个第一区域的邻接口之间的路径为边，搜索移动起点至目标出口之间的路径，得到第一路径。
对于栅格地图和导航地图，可以按照图论模型的方式在第一地图中进行寻路。第一地图可以抽象为图论模型，该图论模型为第一地图的抽象图。在该图论模型中，各个区域的邻接口为节点，各个邻接口之间的路径为边，路径的长度为边的权重。
在得到移动起点至第一目标区域的邻接口之间的第一子路径之后，可以将移动起点作为节点添加到第一地图的图论模型中，将该第一子路径作为与移动起点对应的节点和与第一目标区域的邻接口对应的节点之间的边，该边的权重为第一子路径的长度。
在该第一地图的图论模型中，可以查找与移动起点对应的节点到与目标出口对应的节点之间的路径，得到第一路径。
例如，对于图3所示的栅格地图，其对应的集群入口和集群内入口之间的路径如图7所示，五角星位置为目标出口的位置。如图8所示，在进行地图寻路时，将起点加入到抽象图，圆圈位置为起点，生成起点到所在集群入口之间的路径。
在抽象图中寻路，并提炼路径：在抽象图中通过如A*等寻路方式确定起点至目标之间的路径，得到如图9所示的路径。
通过本实施例，采用图论算法进行地图寻路，可以适用于已有的图论算法，提高地图寻路方式的适用性。
可选地，在本实施例中，对于导航地图中的邻接口为整条邻接边的场景，按照图论算法寻找到的是一片路径区域，可以在该路径区域内确定一条路径作为寻路结果。可以通过以下方式生成第一路径：以移动起点、以及每个第一区域的邻接边为节点，以第一子路径、和第一路径区域为边，搜索移动起点至目标出口的第二路径区域，其中，第二路径区域包含第二路径区域所经过的导航网格；从第二路径区域内获取由移动起点至目标出口的第一路径。
对于导航地图，集群内路径保存的是入口公共边(邻接边)和入口公共边(邻接边)之间的多边形路径，最终可以由多个集群之间的公共边路径(多边形路径)经过路径提炼算法(如，StringPull算法)提炼出真实路径。
在进行地图寻路时，可以将移动起点加入到抽象图中，并将移动起点、以及每个第一区域的邻接边为节点，以第一子路径、和第一路径区域为边，按照图论模型中的寻路算法(例如，A*算法)搜索移动起点至目标出口的一条路径，该路径为一条多边形串，可以还原为导航地图中的一片路径区域，例如，第二路径区域，该第二路径区域包含第二路径区域所经过的导航网格。
在得到第二路径区域之后，可以经过路径提炼算法提炼出移动起点至目标出口的第一路径，例如，按照公共边中点法确定移动起点至目标出口的第一路径。
可选地，在本实施例中，为了减少路径的拐点数量，以保证寻路得到的移动起点至目标出口的路径尽可能短，可以采用如StringPull等算法依靠多边形与多边形之间的公共边来确定路径最终的拐点，从而确定出第一路径。
例如，如图10所示，在进行地图寻路时，可以采用StringPull算法减少拐点数量，维护单调递减的漏斗，将起点对应到凸多边形的公共边上，移动第一条边，漏斗角度减少，确定移动；移动第二条边，漏斗角度仍减少，确定移动；再移动第一条边，漏斗角度继续减少，确定移动；由于无法朝着同一方向移动第二条边，因此还是移动第一条边，此时漏斗的两个边的位置关系发生变化，不允许移动则确定此处需要一个拐点。确定好该拐点之后，可以继续以该拐点为起点调用StringPull算法提炼路径。
通过本实施例，采用图论算法进行地图寻路，并将寻路得到的多边形串还原地图中的路径，不仅可以提高地图寻路效率，更保证了寻得的路径的可行性与更好的路径质量。
作为一种可选的实施例，确定移动终点所在的第二地图中的第二路径包括：
S31，确定第二地图的第三目标区域内的第二子路径，其中，第三目标区域为第二地图包含的多个第二区域中，移动终点所在的区域，多个第二区域中的每个第二区域包含允许从每个第二区域进入到每个第二区域的相邻区域的邻接口，第二子路径为第三目标区域的邻接口至移动终点的路径；
S32，根据第二子路径、以及预先存储的每个第二区域的目标接口之间的路径，获取由目标入口至移动终点的第二路径，其中，每个第二区域的目标接口包括以下至少之一：每个第二区域的邻接口，目标入口。
确定第二地图的目标入口至移动终点的路径的方式可以有多种，例如，基于A*算法的寻路，基于Dijkstra算法的寻路。上述方式需要加载第二地图完整的导航数据，占用一部分的缓存空间。
为了提高寻路效率，第二地图可以被划分为多个第二区域(集群，每个集群可以作为划分的一个高层地图的地图单元)，每个第二区域中包含多个基本地图单元；配置各第二区域的邻接口，即，允许从本区域进入到本区域的相邻区域的入口，并预先存储每个第二区域的邻接口之间的路径。基于保存的各第二区域的邻接口之间的路径，可以进行地图寻路。
将第二地图划分为多个第二区域的方式、配置各第二区域的邻接口的方式、预先存储每个第二区域的目标接口之间的路径的方式、以及基于存储的每个第二区域的邻接口之间的路径确定第二路径的方式与前述类似，在此不做赘述。
通过本实施例，通过将地图划分为多个区域，并预先存储各个区域的邻接口之间路径，可以减少寻路算法的搜索次数，提高地图的寻路效率。
作为一种可选的实施例，根据第二子路径、以及预先存储的每个第二区域的目标接口之间的路径，获取由目标入口至移动终点的第二路径包括：
S41，以移动终点、每个第二区域的目标接口为节点，以第二子路径、以及每个第二区域的目标接口之间的路径为边，搜索目标入口至移动终点的路径，得到第二路径。
可以按照图论模型的方式在第二地图中进行寻路。第二地图可以抽象为图论模型，该图论模型为第二地图的抽象图。在该图论模型中，各第二区域的目标接口为节点，各个目标接口之间的路径为边，路径的长度为边的权重。
在得到第三目标区域的邻接口至移动终点的第二子路径之后，可以将移动终点作为节点添加到第二地图的图论模型中，将该第二子路径作为与移动终点对应的节点和与第三目标区域的邻接口对应的节点之间的边，该边的权重为第二子路径的长度。
在图论模型中查找目标入口至移动终点之间的第二路径的方式与前述类似，在此不做赘述。
通过本实施例，采用图论算法进行地图寻路，并将寻路得到的路径还原为地图中的路径，不仅可以提高地图寻路效率，更保证了寻得的路径的可行性与更好的路径质量。
作为一种可选的实施例，在确定第二地图的第三目标区域内的第二子路径之前，上述方法还包括：
S51，确定第二地图中移动终点所在的第三目标区域；
S52，获取第三目标区域的第一导航数据。
为了减少导航数据对缓存空间的占用，在跨地图寻路发起时，可以仅加载终点地图中终点所在的一小块导航即可，也就是，仅加载第二地图中移动终点所在的第三目标区域的导航数据。
根据移动终点的位置信息，可以确定第二地图中移动终点所在的第三目标区域。第三目标区域可以通过第二地图的地图标识和第三目标区域的区域标识进行表示。
在确定出移动终点所在的第三目标区域之后，可以加载该第三目标区域的导航数据(第一导航数据)，以便进行地图寻路，例如，确定第二子路径。而对于第二地图中除了第三目标区域以外的其他区域的导航数据，可以不进行加载。
移动终点的位置信息可以携带在寻路请求中，该位置信息可以通过地图标识和位置坐标的方式表示，或者，通过地图标识、区域标识和位置坐标的方式表示，根据寻路请求中携带的移动终点的位置信息，可以确定出第三目标区域。
通过本实施例，通过确定并加载终点地图中终点所在的一小块导航，可以减少加载的导航数据的数据量，进而减小导航数据对缓存空间的占用。
作为一种可选的实施例，获取第三目标区域的第一导航数据包括：
S61，从目标缓存中查找第三目标区域的导航数据，其中，目标缓存中缓存有多个导航数据的导航数据队列，多个导航数据为被访问过的导航数据；
S62，在查找到第三目标区域的导航数据的情况下，确定获取到第三目标区域的第一导航数据；
S63，将第一导航数据移动到导航数据队列的队列头部。
寻路系统往往需要根据玩家所在的位置更新路径，在玩家还未到达目标之前，寻路请求可能发起多次，如果每一次都加载目标地图(终点所在地图)导航，即便是一小块，IO代价也会非常大，而如果改变目的地时，则重新加载导航。
为了减少加载的导航数据的数据量，可以通过目标缓存来缓存导航数据，目标缓存中缓存有多个导航数据的导航数据队列，多个导航数据为被访问过的导航数据。
服务器可以从目标缓存中查找第三目标区域的导航数据，例如，通过区域标识、或者地图标识和区域标识的组合进行导航数据查找。如果查找到第三目标区域的导航数据，确定获取到第三目标区域的该第一导航数据，则无需再加载第三目标区域的导航数据。
考虑到一片刚进入在内存中的导航数据，将来有很大可能会被继续使用(例如，发起一次新的请求时)，因此，可以将第一导航数据移动到导航数据队列的队列头部，以便可以被继续使用。
通过本实施例，通过目标缓存来缓存的导航数据，并将最近被使用的导航数据移动到导航数据队列的队列头部，可以减少加载的导航数据的数据量，同时保证数据调用的及时性。
作为一种可选的实施例，在从目标缓存中查找第三目标区域的导航数据之后，上述方法还包括：
S71，在未查找到第三目标区域的导航数据的情况下，加载第三目标区域的第一导航数据；
S72，将第一导航数据保存到导航数据队列的队列头部。
如果从目标缓存中未查找到第三目标区域的导航数据，则可以确定第三目标区域的导航数据最近未被使用过，需要加载并保存第三目标区域的导航数据。
可以通过区域标识、或者地图标识和区域标识的组合加载第三目标区域的导航数据，即，第一导航数据，并将第一导航数据保存到导航数据队列的队列头部，以便可以被继续使用。
通过本实施例，通过加载并将区域的导航数据保存到导航数据队列的队列头部，可以保证数据调用的及时性。
作为一种可选的实施例，将第一导航数据保存到导航数据队列的队列头部包括：
S81，在确定出目标缓存中未被使用的存储空间小于存储第一导航数据所需的存储空间的情况下，移除目标缓存中位于导航数据队列的队列尾部的第二导航数据；
S82，将第一导航数据保存到导航数据队列的队列头部。
由于目标缓存的存储空间有限，因此，其仅能存储一定数量的导航数据。可以配置导航数据队列中的导航数据的数量，例如，导航数据队列仅保存目标数量(例如，5个)的导航数据，可以配置导航数据队列中的导航数据的数据量，例如，导航数据队列仅保存目标数据量(例如，2G)的导航数据。
在将第一导航数据保存到导航数据队列的队列头部时，可以首先确定是否需要移除导航数据队列中的导航数据。如果目标缓存中未被使用的存储空间小于存储第一导航数据所需的存储空间，或者，导航数据队列中的导航数据的数量超过数量阈值，或者，导航数据队列中的导航数据的数据量超过数据量阈值，则需要移除导航数据队列中的导航数据。
移除的导航数据可以是导航数据队列的队列尾部的导航数据，即，第二导航数据，由于最新被使用的导航数据会被移动到导航数据队列的队列首部，则导航数据队列的队列尾部的导航数据为一段时间内都未被访问到的导航数据，该导航数据将来被访问的可能性也很小，因此，可以被优先移除。
在移除导航数据队列的队列尾部的第二导航数据之后，可以再将第一导航数据保存到导航数据队列的队列头部。
例如，一片刚进入在内存中的导航，将来有很大可能继续使用(发起一次新的请求)，而在一段时间内都未被访问到的导航，将来被访问的可能性也很小(改变目的地)，因此，可以基于LRU(Least Recently Used，最近最少使用)算法缓存导航数据。
通过本实施例，通过在满足数据移除条件时移除导航数据队列的队列尾部的导航数据，可以提高数据存储的合理性。
作为一种可选的实施例，根据第一路径、第二路径、以及预先存储的多个地图中的各个地图的入口与出口之间的路径，获取由移动起点至移动终点的第三路径包括：
S91，以移动起点、移动终点、以及各个地图的入口和各个地图的出口为节点，以第一路径、第二路径以及各个地图的入口与出口之间的路径为边，搜索移动起点至移动终点的路径，得到第三路径。
在得到第一路径和第二路径之后，可以按照图论模型的方式在多个地图之间进行寻路。多个地图可以抽象为图论模型，该图论模型为多个地图的抽象图。在该图论模型中，各个地图的出入口为节点，各个地图内的出入口之间的路径为边，路径的长度为边的权重。不同的地图之间，具有关联关系的出入口为该图论模型中的相同节点，从而可以通过一个图论模型标识多个地图。
在得到第一路径和第二路径之后，可以将移动起点和移动终点作为节点添加到多个地图的图论模型中，将该第一路径作为与移动起点对应的节点和与目标出口对应的节点之间的边，该边的权重为第一路径的长度，将该第二路径作为与目标入口对应的节点和与移动终点对应的节点之间的边，该边的权重为第二路径的长度。
在图论模型中查找移动起点至移动终点之间的第三路径的方式与前述类似，在此不做赘述。
通过本实施例，采用图论算法进行地图寻路，并将寻路得到的路径还原为地图中的路径，可以提高地图寻路效率，保证寻得的路径的可行性。
作为一种可选的实施例，在确定移动起点所在的第一地图中的第一路径之前，上述方法还包括：
S101，接收待移动对象的客户端发送的移动请求，移动请求用于请求控制待移动对象由移动起点移动至移动终点；
S102，响应移动请求，确定待移动对象的移动起点和移动终点。
上述地图寻路过程可以是根据待移动对象的客户端发送的移动请求(寻路请求)，该移动请求用于请求查找一条由移动起点至移动终点的路径，以控制待移动对象由移动起点移动至移动终点。
上述多个地图可以是游戏地图或者其他地图。以游戏地图为例，游戏地图可以是目标游戏应用中的地图，该目标游戏可以包括但不限于MMO游戏。该目标游戏应用的用户可以使用其终端设备上运行的该目标游戏应用的客户端通过目标帐号登录到该目标游戏，以控制客户端与目标游戏应用的服务器之间的交互。同一帐号可以控制目标游戏中的一个虚拟角色，也可以同时控制目标游戏中的多个虚拟角色，本实施例中以控制一个虚拟角色为例进行说明。
目标用户可以使用目标帐号登录目标客户端，来启动目标游戏应用。该目标用户控制的虚拟角色为待移动对象。在操作待移动对象在游戏地图中移动的过程中，可以确定此次移动的移动起点和移动终点。该移动起点位于多个地图中的第一地图中，该移动终点位于多个地图中的第二地图中。
待移动对象的客户端(待移动对象可以是目标游戏中目标用户所控制的虚拟对象)可以检测对该客户端执行的操作，响应该操作，生成待移动对象的移动请求，该移动请求用于请求控制待移动对象由移动起点移动到移动终点，并通过与服务器之间的通信连接发送给服务器。
服务器可以接收客户端发送的移动请求，响应该移动请求，服务器可以确定待移动对象的移动起点和移动终点。该移动起点和移动终点可以是通过地图标识和地图中的位置坐标确定的，也可以是通过位置标识确定的，也就是说，移动请求中携带有移动起点和/或移动终点的位置标识。服务器提取该移动请求中的该位置标识，并通过位置标识与位置之间的对应关系，确定出移动起点和/或移动终点所在的地图以及在地图中的位置坐标。
通过本实施例，通过移动请求触发待移动对象在多个地图中的移动，可以提高用户对于地图中的对象的控制能力。
作为一种可选的实施例，在获取由移动起点至移动终点的第三路径之后，上述方法还包括：
S111，生成移动控制指令，其中，移动控制指令用于指示待移动对象按照第三路径进行移动；
S112，将移动控制指令发送给上述待移动对象的客户端，以控制待移动对象按照第三路径由移动起点移动到移动终点。
在由服务器统一控制游戏地图中的对象的移动时，服务器可以使用该第三路径控制待移动对象由移动起点移动到移动终点，并将移动过程同步到显示有待移动对象的客户端上。
可选地，控制待移动对象由移动起点移动到移动终点也可以是由终端设备执行的。服务器可以生成移动控制指令，该移动控制指令用于指示待移动对象按照第三路径移动，并将移动控制指令发送给上述待移动对象的客户端。
客户端在接收到该移动控制指令之后，可以从移动控制指令中提取与该第三路径，并按照第三路径控制待移动对象由移动起点移动到移动终点。
对于显示有待移动对象的其他客户端，可以由该客户端进行位置同步，将待移动对象的位置同步到服务器，并由服器将待移动对象的位置同步到其他客户端。
通过本实施例，通过客户端控制待移动对象的移动，可以减少服务器的运行负担，保证游戏运行的顺畅性。
需要说明的是，本实施例中的地图寻路方法所寻到的路径不一定是最优的(最短路径)，但是，由于集群之间的路径是预先定义并保存的，可以直接使用，无需关心所经过的集群内部的路径细节(因为是预先生成的，也就是定义好的，直接使用即可)，因此该路径是能够快速找出一条路径。
下面结合可选示例对本申请实施例中的地图寻路方法进行说明。本示例中的地图寻路方法应用有游戏场景，游戏地图为栅格地图，或者导航地图，地图划分为的区域为集群，每个集群对应于一个高层次地图中的地图单元。
如图11所示，本示例中的地图寻路方法的流程可以包括如下步骤：
步骤S1102，计算起点和终点在本地图中与入口的路径。
对于多个地图，无需为每张图都加载导航网格，可以加载玩家控制的虚拟对象当前所在地图的导航网格数据，其它地图只需要一个被初始化但是只有传送门周围导航数据的dtNavMesh空壳。
当发起跨地图寻路时，可以加载终点地图中终点所在的一小块导航数据，并计算在起点所在地图中起点与该地图的入口之间的路径，以及在终点所在地图中终点与该地图的入口之间的路径。
步骤S1104，进行跨地图层寻路，得到起点所在地图的入口与终点所在地图的入口之间的路径。
地图与地图之间的连接方式可以是地图传送门，地图传送门可以是地图的入口，可以简化跨地图层寻路为单纯的表查询，预先计算并存储跨地图层每个传送门之间的路径。
根据预先存储的传送门之间的路径，可以获取起点所在地图的入口与终点所在地图的入口之间的路径。
步骤S1106，进行路径拼接，得到起点与终点之间的路径。
将起点在本地图中与入口的路径、起点所在地图的入口与终点所在地图的入口之间的路径、以及终点在本地图中与入口的路径进行拼接，得到起点与终点之间的路径。
通过本示例，通过仅加载终点地图中终点所在的一小块导航数据来完成跨地图寻路，可以减少所需加载的数据量，提高内存利用率，提升寻路效率。
需要说明的是，对于前述的各方法实施例，为了简单描述，故将其都表述为一系列的动作组合，但是本领域技术人员应该知悉，本申请并不受所描述的动作顺序的限制，因为依据本申请，某些步骤可以采用其他顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施例均属于优选实施例，所涉及的动作和模块并不一定是本申请所必须的。
通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到根据上述实施例的方法可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件，但很多情况下前者是更佳的实施方式。基于这样的理解，本申请的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质(如ROM/RAM、磁碟、光盘)中，包括若干指令用以使得一台终端设备(可以是手机，计算机，服务器，或者网络设备等)执行本申请各实施例所述的方法。
根据本申请实施例的另一个方面，还提供了一种用于实施上述地图寻路方法的地图寻路装置。该装置可以应用于上述动画创建设备。图12是根据本申请实施例的一种可选的地图寻路装置的示意图，如图12所示，该装置可以包括：
(1)第一确定单元1202，用于确定移动起点所在的第一地图中的第一路径，其中，第一路径为移动起点至第一地图的目标出口的路径；
(2)第二确定单元1204，与第一确定单元1202相连，与用于确定移动终点所在的第二地图中的第二路径，其中，第二路径为第二地图的目标入口至移动终点的路径；
(3)第一获取单元1206，与第二确定单元1204相连，用于根据第一路径、第二路径、以及预先存储的多个地图中的各个地图的入口与出口之间的路径，获取由移动起点至移动终点的第三路径，其中，多个地图包括第一地图和第二地图，在多个地图的具有关联关系的两个关联地图中，第一关联地图的出口与第二关联地图的入口关联。
需要说明的是，该实施例中的第一确定单元1202可以用于执行本申请实施例中的步骤S202，该实施例中的第二确定单元1202可以用于执行本申请实施例中的步骤S204，该实施例中的第一获取单元1206可以用于执行本申请实施例中的步骤S206。
通过上述模块，通过确定移动起点所在的第一地图中的第一路径，其中，第一路径为移动起点至第一地图的目标出口的路径；确定移动终点所在的第二地图中的第二路径，其中，第二路径为第二地图的目标入口至移动终点的路径；根据第一路径、第二路径、以及预先存储的多个地图中的各个地图的入口与出口之间的路径，获取由移动起点至移动终点的第三路径，其中，多个地图包括第一地图和第二地图，在多个地图的具有关联关系的两个关联地图中，第一关联地图的出口与第二关联地图的入口关联，解决了相关技术中的跨地图寻路方式存在由于需要加载的地图数量过多导致的游戏容易卡顿的问题，减少了导航数据对内存的占用，提高了游戏运行流畅性。
作为一种可选的实施例，第一确定单元1202包括：
第一确定模块，用于确定第一地图的第一目标区域内的第一子路径，其中，第一目标区域为第一地图包含的多个第一区域中移动起点所在的区域，多个第一区域中的每个第一区域包含允许从每个第一区域进入到每个第一区域的相邻区域的邻接口，第一子路径为移动起点至第一目标区域的邻接口的路径；
第一获取模块，用于根据第一子路径、以及预先存储的每个第一区域的邻接口之间的路径，获取由移动起点至目标出口的第一路径，其中，目标出口属于目标出口所在的第二目标区域的邻接口。
作为一种可选的实施例，第一获取模块包括：
第一搜索子模块，用于以移动起点、每个第一区域的邻接口为节点，以第一子路径、以及每个第一区域的邻接口之间的路径为边，搜索移动起点至目标出口之间的路径，得到第一路径。
作为一种可选的实施例，第二确定单元1204包括：
第二确定模块，用于确定第二地图的第三目标区域内的第二子路径，其中，第三目标区域为第二地图包含的多个第二区域中，移动终点所在的区域，多个第二区域中的每个第二区域包含允许从每个第二区域进入到每个第二区域的相邻区域的邻接口，第二子路径为第三目标区域的邻接口至移动终点的路径；
第二获取模块，用于根据第二子路径、以及预先存储的每个第二区域的目标接口之间的路径，获取由目标入口至移动终点的第二路径，其中，每个第二区域的目标接口包括以下至少之一：每个第二区域的邻接口，目标入口。
作为一种可选的实施例，第二确定模块包括：
第二搜索子模块，用于以移动终点、每个第二区域的目标接口为节点，以第二子路径、以及每个第二区域的目标接口之间的路径为边，搜索目标入口至移动终点的路径，得到第二路径。
作为一种可选的实施例，上述装置还包括：
第三确定单元，用于在确定第二地图的第三目标区域内的第二子路径之前，确定第二地图中移动终点所在的第三目标区域；
第二获取单元，用于获取第三目标区域的第一导航数据。
作为一种可选的实施例，第二获取单元包括：
查找模块，用于从目标缓存中查找第三目标区域的导航数据，其中，目标缓存中缓存有多个导航数据的导航数据队列，多个导航数据为被访问过的导航数据；
第三确定模块，用于在查找到第三目标区域的导航数据的情况下，确定获取到第三目标区域的第一导航数据；
移动模块，用于将第一导航数据移动到导航数据队列的队列头部。
作为一种可选的实施例，上述装置还包括：
加载单元，用于在从目标缓存中查找第三目标区域的导航数据之后，在未查找到第三目标区域的导航数据的情况下，加载第三目标区域的第一导航数据；
保存单元，用于将第一导航数据保存到导航数据队列的队列头部。
作为一种可选的实施例，保存单元包括：
移除模块，用于在确定出目标缓存中未被使用的存储空间小于存储第一导航数据所需的存储空间的情况下，移除目标缓存中位于导航数据队列的队列尾部的第二导航数据；
保存模块，用于将第一导航数据保存到导航数据队列的队列头部。
作为一种可选的实施例，第一获取单元1206包括：
搜索单元，用于以移动起点、移动终点、以及各个地图的入口和各个地图的出口为节点，以第一路径、第二路径以及各个地图的入口与出口之间的路径为边，搜索移动起点至移动终点的路径，得到第三路径。
作为一种可选的实施例，上述装置还包括：
接收单元，用于在确定移动起点所在的第一地图中的第一路径之前，接收待移动对象的客户端发送的移动请求，移动请求用于请求控制待移动对象由移动起点移动至移动终点；
第四确定单元，用于响应移动请求，确定待移动对象的移动起点和移动终点。
作为一种可选的实施例，上述装置还包括：
生成单元，用于在获取由移动起点至移动终点的第三路径之后，生成移动控制指令，其中，移动控制指令用于指示待移动对象按照第三路径进行移动；
发送单元，用于将移动控制指令发送给待移动对象的客户端，以控制待移动对象按照第三路径由移动起点移动到移动终点。
此处需要说明的是，上述模块与对应的步骤所实现的示例和应用场景相同，但不限于上述实施例所公开的内容。需要说明的是，上述模块作为装置的一部分可以运行在如图1所示的硬件环境中，可以通过软件实现，也可以通过硬件实现，其中，硬件环境包括网络环境。
根据本申请实施例的又一个方面，还提供了一种用于实施上述模型控制方法的电子装置，该电子装置可以是服务器、终端、或者其组合。
图13是根据本申请实施例的一种电子装置的结构框图，如图13所示，该电子装置包括存储器1302和处理器1304，该存储器1302中存储有计算机程序，该处理器1304被设置为通过计算机程序执行上述任一项方法实施例中的步骤。
可选地，在本实施例中，上述电子装置可以位于计算机网络的多个网络设备中的至少一个网络设备。
可选地，在本实施例中，上述处理器可以被设置为通过计算机程序执行以下步骤：
S1，确定移动起点所在的第一地图中的第一路径，其中，第一路径为移动起点至第一地图的目标出口的路径；
S2，确定移动终点所在的第二地图中的第二路径，其中，第二路径为第二地图的目标入口至移动终点的路径；
S3，根据第一路径、第二路径、以及预先存储的多个地图中的各个地图的入口与出口之间的路径，获取由移动起点至移动终点的第三路径，其中，多个地图包括第一地图和第二地图，在多个地图的具有关联关系的两个关联地图中，第一关联地图的出口与第二关联地图的入口关联。
其中，存储器1302可用于存储软件程序以及模块，如本申请实施例中的模型控制方法和装置对应的程序指令/模块，处理器1304通过运行存储在存储器1302内的软件程序以及模块，从而执行各种功能应用以及数据处理，即实现上述模型控制方法。存储器1302可包括高速随机存储器，还可以包括非易失性存储器，如一个或多个磁性存储装置、闪存、或者其他非易失性固态存储器。在一些实例中，存储器1302可进一步包括相对于处理器1304远程设置的存储器，这些远程存储器可以通过网络连接至终端。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。
作为一种示例，如图13所示，上述存储器1302中可以但不限于包括上述模型控制装置中的第一确定单元1202、第二确定单元1204和第一获取单元1206。此外，还可以包括但不限于上述模型控制装置中的其他模块单元，本示例中不再赘述。
可选地，上述的传输装置1306用于经由一个网络接收或者发送数据。上述的网络具体实例可包括有线网络及无线网络。在一个实例中，传输装置1306包括一个NIC(NetworkInterface Controller，网络适配器)，其可通过网线与其他网络设备与路由器相连从而可与互联网或局域网进行通讯。在一个实例中，传输装置1306为RF(Radio Frequency，射频)模块，其用于通过无线方式与互联网进行通讯。
此外，上述电子装置还包括：显示器1308，用于显示上述客户端的界面；和连接总线1310，用于连接上述电子装置中的各个模块部件。
可选地，本实施例中的具体示例可以参考上述实施例中所描述的示例，本实施例在此不再赘述。
本领域普通技术人员可以理解，图13所示的结构仅为示意，实施上述模型控制方法的设备可以是终端设备，该终端设备可以是智能手机(如Android手机、iOS手机等)、平板电脑、掌上电脑以及MID(Mobile InternetDevices，移动互联网设备)、PAD等终端设备。图13其并不对上述电子装置的结构造成限定。例如，终端设备还可包括比图13中所示更多或者更少的组件(如网络接口、显示装置等)，或者具有与图13所示不同的配置。
本领域普通技术人员可以理解上述实施例的各种方法中的全部或部分步骤是可以通过程序来指令终端设备相关的硬件来完成，该程序可以存储于一计算机可读存储介质中，存储介质可以包括：闪存盘、ROM(Read-Only Memory，只读存储器)、RAM(Random AccessMemory，随机存取器)、磁盘或光盘等。
根据本申请实施例的又一个方面，还提供了一种存储介质。可选地，在本实施例中，上述存储介质可以用于执行模型控制方法的程序代码。
可选地，在本实施例中，上述存储介质可以位于上述实施例所示的网络中的多个网络设备中的至少一个网络设备上。
可选地，在本实施例中，存储介质被设置为存储用于执行以下步骤的程序代码：
S1，确定移动起点所在的第一地图中的第一路径，其中，第一路径为移动起点至第一地图的目标出口的路径；
S2，确定移动终点所在的第二地图中的第二路径，其中，第二路径为第二地图的目标入口至移动终点的路径；
S3，根据第一路径、第二路径、以及预先存储的多个地图中的各个地图的入口与出口之间的路径，获取由移动起点至移动终点的第三路径，其中，多个地图包括第一地图和第二地图，在多个地图的具有关联关系的两个关联地图中，第一关联地图的出口与第二关联地图的入口关联。
可选地，本实施例中的具体示例可以参考上述实施例中所描述的示例，本实施例中对此不再赘述。
可选地，在本实施例中，上述存储介质可以包括但不限于：U盘、ROM、RAM、移动硬盘、磁碟或者光盘等各种可以存储程序代码的介质。
上述本申请实施例序号仅仅为了描述，不代表实施例的优劣。
上述实施例中的集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在上述计算机可读取的存储介质中。基于这样的理解，本申请的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在存储介质中，包括若干指令用以使得一台或多台计算机设备(可为个人计算机、服务器或者网络设备等)执行本申请各个实施例所述方法的全部或部分步骤。
在本申请的上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述的部分，可以参见其他实施例的相关描述。
在本申请所提供的几个实施例中，应该理解到，所揭露的客户端，可通过其它的方式实现。其中，以上所描述的装置实施例仅仅是示意性的，例如所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，单元或模块的间接耦合或通信连接，可以是电性或其它的形式。
所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。
另外，在本申请各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。
以上所述仅是本申请的可选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本申请原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本申请的保护范围。
