一种路径规划方法与流程

1.本发明涉及计算机技术领域，具体涉及一种路径规划方法。


背景技术：

2.角色扮演类游戏存在完整的环境、场景、人物、剧情等因素，游戏体验好、可玩性高，广受玩家欢迎。对游戏中角色行动进行路径规划是角色扮演类游戏当前提升玩家体验的重要方向，尤其是对于场景复杂、地图面积巨大、任务剧情繁琐的游戏，帮助玩家进行路径规划可极大提升玩家的游戏体验。
3.当前在游戏中进行路径规划的方式包括将三维地图平面化为二维地图进行路径规划、在三维地图中引入高度差数据进行路径规划等。然而，当前的路径规划方法仅能满足角色由起点向终点移动的基本需求，忽略了游戏中具有独特设计的位置，对于进行游戏场景探索的需求无法满足，玩家容易丧失游戏兴趣，降低整体游戏体验。并且，当前游戏路径规划并未考虑不同玩家的个性化需求，导致游戏体验不佳。


技术实现要素：

4.针对上述存在的拘束局限性，本发明提出了一种路径规划方法，通过确定预估可行域、筛选偏好位置进行路径搜索，充分考虑玩家的偏好特征，同时提升路径搜索的效率。
5.为实现上述目的，本发明采用了以下技术方案：一种路径规划方法，所述方法包括以下步骤：步骤1、获得起点位置与终点位置；所述起点位置与终点位置分别为起点和终点的坐标值；步骤2、获取游戏地图的地图数组，若地图数组不存在，则根据游戏地图创建地图数组；所述地图数组为二维数组，用于存储游戏地图数据；步骤3、在地图数组的预估可行域内根据用户偏好模型计算所有关键位置的偏好度，并筛选出偏好位置；所述预估可行域是指从起点位置到终点位置可能路径的存在区域；步骤4、进搜寻算法初始化；步骤5、搜索路径，获得规划路径数据。
6.本发明与现有技术相对比，本发明具有以下优点：（1）将关键位置和用户偏好度作为游戏路径规划的考虑因素，既满足了角色移动的需求，同时也充分考虑了玩家的个性化探索需求，根据用户特征进行路径规划，提升游戏玩家的游戏体验。
7.（2）在进行正式的路径搜索前进行预估可行域的确定，在预估可行域内进行偏好位置筛选和路径规划，可有效提升路径搜索的效率。
8.上述说明仅是本发明技术方案的概述，为了能够更清楚了解本发明的技术手段，
而可依照说明书的内容予以实施，并且为了让本发明的上述和其他目的、特征和优点能够更明显易懂，以下特举较佳实施例，并配合附图，详细说明如下。
附图说明
9.图1为本发明实施例提供的一种路径规划方法的步骤图。
10.图2为本发明实施例提供的一种筛选偏好位置的步骤图。
11.图3为本发明实施例提供的一种邻居节点遍历操作的流程图。
12.图4为本发明实施例提供的一种节点搜索的流程图。
具体实施方式
13.以下由特定的具体实施例说明本发明的实施方式，熟悉此技术的人士可由本说明书所揭露的内容轻易地了解本发明的其他优点及功效，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。为了进一步了解本发明，下面结合最佳实施例对本发明作进一步的详细说明。
14.本发明的发明点是提供一种路径规划方法，根据用户路径偏好特征，规划由起点至终点的路径，充分满足不同玩家的个性化需求。
15.本发明的一方面在于一种路径规划方法，参考图1，所述方法包括以下步骤：步骤1、获得起点位置与终点位置；所述起点位置与终点位置分别为起点和终点的坐标值；步骤2、获取游戏地图的地图数组，若地图数组不存在，则根据游戏地图创建地图数组；所述地图数组为二维数组，用于存储游戏地图数据；步骤3、在地图数组的预估可行域内根据用户偏好模型计算所有关键位置的偏好度，并筛选出偏好位置；所述预估可行域是指从起点位置到终点位置可能路径的存在区域；步骤4、进搜寻算法初始化；步骤5、搜索路径，获得规划路径数据。
16.作为一种实施例，步骤2中，创建地图数组的具体方式包括以下步骤：步骤221、获取游戏地图，并确定可行区域；所述可行区域为可以自由移动的地图区域；步骤222、根据游戏地图形式将游戏地图转换为地图数组，具体方式为：若游戏地图是基于网格的地图，则创建二维数组并将每一个网格的状态映射到二维数组对应坐标的元素中；若游戏数据基于多边形，则采用网格化方法将游戏地图转化为网格区域，再将网格区域中的每一网格映射到二维数组对应坐标的元素中；步骤223、在地图数组中标记障碍位置及关键位置。
17.作为一种实施例，参考图2，步骤3具体包括以下步骤：步骤31、根据地图数组、起点位置、终点位置确定预估可行域；
步骤32、若预估可行域为空，则结束整个路径规划步骤；若预估可行域不为空，则将预估可行域内所有关键位置的位置特征数据输入用户偏好模型中，获得所有关键位置的偏好度；所述用户偏好模型是用于根据用户特征数据及位置特征数据预测用户偏好度的机器学习模型；步骤33、筛选出偏好度大于预设偏好值的关键位置节点作为偏好位置，并将其余关键位置的偏好度置为0。
18.可以理解的是，对于游戏中相对复杂且面积巨大的游戏地图，采用先确定预估可行域，再在预估可行域内进行路径规划，相较于直接在全地图进行路径规划可显著降低计算资源消耗，提高路径规划效率。
19.作为一种实施例，步骤31中所述预估可行域通过以下方式得到：步骤311a、创建节点队列、节点访问字典、节点路径字典、节点深度字典、可行路径列表，并初始化；所述节点队列用于存储待搜索节点，初始化时将起点节点存入节点队列中；所述节点访问字典用于记录各节点的访问状态，初始化时将起点节点的访问状态设为已访问；所述节点路径字典用于记录从起点节点到各节点的访问路径，初始化时将将节点的访问路径设为起始节点自身；所述节点深度字典用于记录各节点的深度层级，初始化时将起始节点的深度层级设为0；所述可行路径列表用于存储由起点到终点的可行路径，初始化时所述可行路径列表为空列表；步骤312a、若当前节点队列为空，则进入步骤313a；否则进行循环搜索，具体包括：步骤312a1、从节点队列中取出一个节点，并将取出的节点作为当前搜索节点；步骤312a2、判断当前搜索节点的深度层级，若深度层级超过预设搜索深度阈值，则进入步骤313a；否则进入步骤312a3；步骤312a3、判断当前搜索节点是否为终点节点，若为终点节点，则将此时终点节点的访问路径存入可行路径列表中；否则进入步骤312a4；步骤312a4、遍历当前搜索节点的邻居节点，直到所有邻居节点被遍历操作；参考图3，所述遍历操作为：获取当前邻居节点，判断该邻居节点是否已被访问；若该邻居节点未被访问，则将该邻居节点添加至节点队列中，设置该邻居节点的访问状态为已访问，设置该邻居节点的深度层次为当前搜索节点深度层级加1，设置该邻居节点的访问路径为当前搜索节点访问路径加该邻居节点；若该邻居节点已被访问，则跳过该邻居节点，进入下一邻居节点；步骤313a、若此时可行路径列表为空，则预估可行域为空；若此时可行路径不为空，则预估可行区域为所有可行路径包围的区域。
20.作为一种实施例，步骤31中所述预估可行域通过以下方式得到：步骤311b、对地图数组进行压缩得到压缩地图数组，并确定起点位置和终点位置在压缩地图数组中的位置；
对地图数组的压缩方式为：采用预设窗口大小的滑动窗口按照预设特征提取步长对地图数组进行压缩，在每个窗口内对比窗口数据与预设窗口模板进行对比，若与预设窗口模板相同，则该窗口内的数据压缩为1（代表该窗口内的地图可通过），否则该窗口内的数据压缩为0（代表该窗口内的地图不可通过）；所述预设窗口模板是预设的具备可通过特征的若干地图块数组；所述预设窗口模板的大小与所述预设窗口大小一致；步骤312b、采用dijkstra算法在压缩地图数组中获得从起点到终点的最短路径；步骤313b、将最短路径中各节点两侧预设扩展范围内的区域作为压缩地图可行域；步骤314b、根据压缩地图可行域还原原始的地图数组中的预估可行域。
21.作为一种实施例，所述用户偏好模型通过以下方式获得：收集用户特征数据、位置特征数据及用户偏好度数据，并进行数据处理，得到原始数据集；将所述原始数据集拆分为训练集和测试集，并基于训练集借助机器学习算法进行模型训练；借助测试集对模型进行评估并调整优化模型直到满足预设模型效果，得到用户偏好模型。
22.所述原始数据集由输入数据和输出数据组成，输入数据中的每个元素均由用户特征数据、位置特征数据组成，输出数据中的每个元素为与输入数据相对应的偏好度。
23.例如，输入数据中第i个元素可表示为（ui,li）其中ui表示用户u的用户特征数据，li表示位置l的位置特征数据；则输出数据中第i个元素可表示为pi,pi表示用户u对位置l的偏好度。
24.所述偏好度用于描述用户对游戏中特定地理位置的偏好情况，通过以下步骤获得用户偏好度数据：s1、获得用户的历史行为数据并进行数据预处理，所述历史行为数据是用户在游戏过程中的移动轨迹数据；s2、对用户的历史行为数据进行特征提取，获得用户路径特征值，所述路径特征值包括访问频率、停留时间、访问时间段分布、访问持续时间分布、路径距离、位置类型、操作设备；s3、进行特征值归一化，获得标准路径特征值；s4、根据所述标准路径特征值加权求和计算用户偏好度，具体地，用户偏好度的计算方式如下：
25.其中，μ
(x,y)
为坐标为(x,y)位置的偏好度,w
j(x,y)
为编号为j的特征值的权重，f
j(x,y)
为坐标(x,y)位置的第j特征值的数值。
26.所述机器学习算法可选择线性回归、决策树、随机森林、支持向量机、神经网络中的任意一种算法。上述算法均为当前成熟的算法，本领域技术人员基于前述实施例的描述均可顺利实现，在此不再赘述。
27.作为一种实施例，步骤4具体包括以下步骤：
步骤41、初始化起点节点与终点节点，具体包括：创建起点节点对象及终点节点对象；起点节点对象与终点节点对象的坐标数据对应于所述起点位置与所述终点位置；起点节点对象与终点节点对象的步数代价（g_cost）、距离代价（h_cost）、节点代价（cost）均置为0；起点节点对象与终点节点对象的父节点均为none；步骤42、初始化开放列表和关闭列表，将起点节点存入开放列表中，此时关闭列表为空列表。
28.需要说明的是，节点对象的数据结构由坐标数据、步数代价、距离代价、节点代价、父节点、是否为偏好位置、偏好度这六个属性组成。所述起点节点对象和所述终点节点对象均属于节点对象。
29.作为一种实施例，步骤5具体包括以下步骤：步骤51、当开放列表不为空时，选择开放列表中节点代价最低的节点作为当前确认节点，将当前确认节点存入关闭列表中并将其从开放列表中移除；步骤52、若当前确认节点不为终点节点，则对当前确认节点的所有邻居节点进行节点搜索，更新开放列表后返回步骤51；若当前确认节点为终点节点，搜索路径结束；所述节点搜索是指更新邻居节点的节点代价并根据邻居节点的特征更新开放列表；步骤53、创建路径列表并将终点节点存入所述路径列表；步骤54、根据父节点找到对应的节点并存入路径列表，直到回溯到起点节点；步骤55、对路径列表进行反序，得到规划路径数据。
30.作为一种实施例，参考图4，步骤52中，节点搜索具体包括：（1）获取当前邻居节点数据，判断是否跳过当前邻居节点，判断方式为：若当前邻居节点是障碍节点或已存在与关闭列表中，则跳过当前邻居节点；（2）计算当前邻居节点的节点代价；所述节点代价的计算方式为：
31.其中cost为当前邻居节点的节点代价，gcost为当前邻居节点的步数代价，hcost为当前邻居节点的距离代价，α为当前邻居节点的偏好度权重；所述步数代价是指当前邻居节点与起点节点的距离；所述距离代价是指当前邻居节点与终点节点的距离；所述距离可采用曼哈顿距离或欧几里得距离中的任意一种计算；所述偏好度权重的计算方法为：
32.其中α为偏好度权重，β为当前邻居节点的偏好度，所属偏好度由步骤32计算得到；（3）更新当前邻居节点的节点代价并将当前确认节点设置为当前邻居节点的父节点；（4）判断当前邻居节点是否存在于开放列表中，若不存在于开放列表中，则将当前邻居节点存入开放列表中；若当前邻居节点存在于开放列表中，则对开放列表中对应的节点进行更新。
33.作为一种实施例，除步骤1-5外，所述方法还包括：步骤6、获得用户实际路径，计算实际路径与规划路径的路径相似性，当路径相似性小于预设相似度阈值时，记录该用户的实际路径数据并增加规划失效次数；在预设优化周期内计算规划失效比，若规划失效比大于预设失效阈值时，进行用户偏好模型调整优化。
34.具体地，所述路径相似性的计算方法如下：在实际路径中选取与规划路径中各节点具有相同纵坐标的节点，计算所有对应节点间横坐标的标准差，计算公式为：
35.其中，为s路径相似度，pi为编号为i的节点在实际路径中的横坐标，qi为编号为i的节点在规划路径中的横坐标，n为节点总数。
36.所述规划失效比的计算方法为规划失效次数与规划次数的比值。
37.本发明的另一方面在于一种路径规划系统，所述系统包括数据收集模块、数据处理模块、模型训练模块、路径分析模块、系统优化模块。
38.所述数据收集模块用于收集游戏地图数据、用户特征数据、位置特征数据及用户偏好度数据。
39.所述数据处理模块用于对所述数据收集模块所收集到的数据进行数据清洗和数据处理，并将处理后的数据存储至数据库中。
40.所述模型训练模块用于借助机器学习算法，使用数据处理模块处理的数据借助机器学习算法进行用户偏好模型训练及调优。
41.所述路径分析模块通过前述步骤1-6的方法实现路径规划。
42.所述系统优化模块根据用户实际移动路径与规划路径数据按照步骤7进行模型优化。
43.作为一种实施例，本发明所述方法可在软件和/或软件与硬件的组合体中被实施，例如，可采用专用集成电路(asic)、通用计算机或任何其他类似硬件设备来实现。
44.本发明所述的方法可以软件程序的形式实施，所述软件程序可以通过处理器执行以实现上文所述步骤或功能。同样地，所述软件程序(包括相关的数据结构)可以被存储到计算机可读记录介质中，例如，ram存储器，磁或光驱动器或软磁盘及类似设备。
45.另外，本发明所述方法的一些步骤或功能可采用硬件来实现，例如，作为与处理器配合从而执行各个步骤或功能的电路。
46.另外，本发明所述的方法的一部分可被应用为计算机程序产品，例如计算机程序指令，当其被计算机执行时，通过该计算机的操作，可以调用或提供根据本技术的方法和/或技术方案。而调用本发明所述方法的程序指令，可被存储在固定的或可移动的记录介质中，和/或通过广播或其他信号承载媒体中的数据流而被传输，和/或被存储在根据所述程序指令运行的计算机设备的工作存储器中。
47.作为一种实施例，本发明还提供一个装置，该装置包括用于存储计算机程序指令的存储器和用于执行程序指令的处理器，其中，当该计算机程序指令被该处理器执行时，触
发该装置运行基于前述的多个实施例的方法和/或技术方案。
48.需要说明的是，对于前述的各方法实施例，为了简单描述，故将其都表述为一系列的动作组合，但是本领域技术人员应该知悉，本技术并不受所描述的动作顺序的限制，因为依据本技术，某些步骤可以采用其他顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施例均属于可选实施例，所涉及的动作和模块并不一定是本技术所必须的。
49.最后，需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者终端设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者终端设备所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括所述要素的过程、方法、物品或者终端设备中还存在另外的相同要素。
50.另外，各个实施例之间的技术方案可以互相结合，但是必须是以本领域普通技术人员能够实现为基础，当技术方案的结合出现相互矛盾或无法实现时应当认为这种技术方案的结合不存在，也不在本发明要求保护的范围之内。
51.以上所述，仅是本发明的较佳实施例而已，并非对本发明作任何形式上的限制，虽然本发明已以较佳实施例揭露如上，然而并非用以限定本发明,任何熟悉本专业的技术人员，在不脱离本发明技术方案范围内,当可利用上述揭示的技术内容作出些许更动或修饰为等同变化的等效实施例,但凡是未脱离本发明技术方案的内容，依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化与修饰，均仍属于本发明技术方案的范围内。

技术特征：
1.一种路径规划方法，其特征在于，所述方法包括以下步骤：步骤1、获得起点位置与终点位置；步骤2、获取游戏地图的地图数组，若地图数组不存在，则根据游戏地图创建地图数组；步骤3、在地图数组的预估可行域内根据用户偏好模型计算所有关键位置的偏好度，并筛选出偏好位置；所述预估可行域是指从起点位置到终点位置可能路径的存在区域；步骤4、进搜寻算法初始化；步骤5、搜索路径，获得规划路径数据。2.根据权利要求1所述的方法，其特征在于，步骤2中，创建地图数组的具体方式包括以下步骤：步骤221、获取游戏地图，并确定可行区域；所述可行区域为可以自由移动的地图区域；步骤222、根据游戏地图形式将游戏地图转换为地图数组，具体方式为：若游戏地图是基于网格的地图，则创建二维数组并将每一个网格的状态映射到二维数组对应坐标的元素中；若游戏数据基于多边形，则采用网格化方法将游戏地图转化为网格区域，再将网格区域中的每一网格映射到二维数组对应坐标的元素中；步骤223、在地图数组中标记障碍位置及关键位置。3.根据权利要求1所述的方法，其特征在于，步骤3具体包括以下步骤：步骤31、根据地图数组、起点位置、终点位置确定预估可行域；步骤32、若预估可行域为空，则结束整个路径规划步骤；若预估可行域不为空，则将预估可行域内所有关键位置的位置特征数据输入用户偏好模型中，获得所有关键位置的偏好度；所述用户偏好模型是用于根据用户特征数据及位置特征数据预测用户偏好度的机器学习模型；步骤33、筛选出偏好度大于预设偏好值的关键位置节点作为偏好位置，并将其余关键位置的偏好度置为0。4.根据权利要求3所述的方法，其特征在于，步骤31中所述预估可行域通过以下方式得到：步骤311a、创建节点队列、节点访问字典、节点路径字典、节点深度字典、可行路径列表，并初始化；步骤312a、若当前节点队列为空，则进入步骤313a；否则进行循环搜索，具体包括：步骤312a1、从节点队列中取出一个节点，并将取出的节点作为当前搜索节点；步骤312a2、判断当前搜索节点的深度层级，若深度层级超过预设搜索深度阈值，则进入步骤313a；否则进入步骤312a3；步骤312a3、判断当前搜索节点是否为终点节点，若为终点节点，则将此时终点节点的访问路径存入可行路径列表中；否则进入步骤312a4；步骤312a4、遍历当前搜索节点的邻居节点，直到所有邻居节点被遍历操作；所述遍历操作为：若该邻居节点未被访问，则将该邻居节点添加至节点队列中，设置该
邻居节点的访问状态为已访问，设置该邻居节点的深度层次为当前搜索节点深度层级加1，设置该邻居节点的访问路径为当前搜索节点访问路径加该邻居节点；若该邻居节点已被访问，则跳过该邻居节点，进入下一邻居节点；步骤313a、若此时可行路径列表为空，则预估可行域为空；若此时可行路径不为空，则预估可行区域为所有可行路径包围的区域。5.根据权利要求1所述的方法，其特征在于，所述用户偏好模型通过以下方式获得：收集用户特征数据、位置特征数据及用户偏好度数据，并进行数据处理，得到原始数据集；将所述原始数据集拆分为训练集和测试集，并基于训练集借助机器学习算法进行模型训练；借助测试集对模型进行评估并调整优化模型直到满足预设模型效果，得到用户偏好模型；所述原始数据集由输入数据和输出数据组成，输入数据中的每个元素均由用户特征数据、位置特征数据组成，输出数据中的每个元素为与输入数据相对应的偏好度。6.根据权利要求5所述的方法，其特征在于，所述偏好度用于描述用户对游戏中特定地理位置的偏好情况，通过以下步骤获得用户偏好度数据：s1、获得用户的历史行为数据并进行数据预处理，所述历史行为数据是用户在游戏过程中的移动轨迹数据；s2、对用户的历史行为数据进行特征提取，获得用户路径特征值，所述路径特征值包括访问频率、停留时间、访问时间段分布、访问持续时间分布、路径距离、位置类型、操作设备；s3、进行特征值归一化，获得标准路径特征值；s4、根据所述标准路径特征值加权求和计算用户偏好度。7.根据权利要求1所述的方法，其特征在于，步骤41、初始化起点节点与终点节点，具体包括：创建起点节点对象及终点节点对象；起点节点对象与终点节点对象的坐标数据对应于所述起点位置与所述终点位置；起点节点对象与终点节点对象的步数代价（g_cost）、距离代价（h_cost）、节点代价（cost）均置为0；起点节点对象与终点节点对象的父节点均为none；步骤42、初始化开放列表和关闭列表，将起点节点存入开放列表中，此时关闭列表为空列表。8.根据权利要求1所述的方法，其特征在于，步骤5具体包括以下步骤：步骤51、当开放列表不为空时，选择开放列表中节点代价最低的节点作为当前确认节点，将当前确认节点存入关闭列表中并将其从开放列表中移除；步骤52、若当前确认节点不为终点节点，则对当前确认节点的所有邻居节点进行节点搜索，更新开放列表后返回步骤51；若当前确认节点为终点节点，搜索路径结束；所述节点搜索是指更新邻居节点的节点代价并根据邻居节点的特征更新开放列表；步骤53、创建路径列表并将终点节点存入所述路径列表；步骤54、根据父节点找到对应的节点并存入路径列表，直到回溯到起点节点；
步骤55、对路径列表进行反序，得到规划路径数据。9.根据权利要求8所述的方法，其特征在于，步骤52中，节点搜索具体包括：（1）判断是否跳过当前邻居节点，判断方式为：若当前邻居节点是障碍节点或已存在与关闭列表中，则跳过当前邻居节点；（2）计算当前邻居节点的节点代价；（3）更新当前邻居节点的节点代价并将当前确认节点设置为当前邻居节点的父节点；（4）判断当前邻居节点是否存在于开放列表中，若不存在于开放列表中，则将当前邻居节点存入开放列表中；若当前邻居节点存在于开放列表中，则对开放列表中对应的节点进行更新。10.根据权利要求9所述的方法，其特征在于,所述节点代价的计算方式为：；其中cost为当前邻居节点的节点代价，gcost为当前邻居节点的步数代价，hcost为当前邻居节点的距离代价，α为当前邻居节点的偏好度权重；所述步数代价是指当前邻居节点与起点节点的距离；所述距离代价是指当前邻居节点与终点节点的距离；所述距离可采用曼哈顿距离或欧几里得距离中的任意一种计算；所述偏好度权重的计算方法为：；其中α为偏好度权重，β为当前邻居节点的偏好度，所属偏好度由步骤32计算得到。

技术总结
本发明提出了一种路径规划方法，所述方法包括：获得起点位置与终点位置；获取游戏地图的地图数组，若地图数组不存在，则根据游戏地图创建地图数组；在地图数组的预估可行域内根据用户偏好模型计算所有关键位置的偏好度，并筛选出偏好位置；所述预估可行域是指从起点位置到终点位置可能路径的存在区域；进搜寻算法初始化；搜索路径，获得规划路径数据；借由上述方法，可实现根据用户特征进行路径规划，提升游戏玩家的游戏体验。游戏玩家的游戏体验。游戏玩家的游戏体验。


技术研发人员：郝林杰
受保护的技术使用者：深圳尚米网络技术有限公司
技术研发日：2023.06.29
技术公布日：2023/8/1