CN109276884A - 游戏路径生成方法和装置 - Google Patents

Abstract

本发明涉及一种游戏路径生成方法和装置，该方法包括主路径生成步骤和至少一个分支路径生成步骤：所述主路径生成步骤包括：从游戏地图的预定区域范围内选择一个位置作为起始点，选择起始出发方向，利用平滑连接的弧线和直线进行路径随机探索和生成步骤，并记录生成的路径作为主路径，直至到达地图边界；所述分支路径生成步骤包括：在已生成的主路径上的预定范围内随机选择一个点作为分支路径起始点和与主路径的交叉点，选择与主路径交叉的方向作为分支路径起始出发方向，利用平滑连接的弧线和直线进支路径随机探索和生成步骤，并记录生成的路径作为分支路径。本发明通过设计算法，使用计算机生成路径，生产环节无需人工参与，极大节省人力资源。路经生成速度极快，大幅提升游戏生产效率。

Description

游戏路径生成方法和装置

技术领域

本发明涉及计算机技术，尤其涉及一种游戏路径生成方法和装置。

背景技术

塔防游戏即指一类通过在地图上建造炮塔或类似建筑物攻击和阻挡敌人前进，以保卫己方大本营的策略类游戏。塔防游戏深受玩家们喜爱因为他的特点在于随着游戏的深入，游戏难度增加，刺激程度随之增加，并且对于玩家而言更具挑战性。

在塔防游戏中，地图的设计尤其是路径设计十分重要。由于在一些游戏的设定中，怪物会沿预定的路径行进，因此路径的走向和形状在很大程度上决定了防守的难易程度从而影响当前关卡的游戏性和刺激性。在传统的塔防游戏生产过程中，塔防游戏地图的设计会经历背景策划，路径设计，防御塔塔点(或称塔坑点)设计，美工实现等环节，并且涉及到具体关卡的配置时，还会包括数值策划师对防御塔和怪物的属性战斗力等进行数值化的设计和平衡调整。在这一完整过程中，由于参与人数，工种众多，往往导致了游戏路径的设计和生产效率低下，设计流程过长，游戏内容不足等问题。

传统塔防游戏中的路径普遍使用直接加载的方法产生。直接加载法就是由设计人员预先设计游戏关卡中的地图数据，然后在游戏加载时直接调用相关数据。这是一种最直接的路径设计方法，且游戏运行时加载可以做到十分快速。但是，一方面游戏路径被固化，另一方面考虑到实际生产的效率，路径的设计时间往往是漫长的，极大降低了整体游戏生产的效率。并且存储预先设计好的路径数据需要增加游戏数据的存储空间。

直接加载的塔防游戏路径生成方法一方面需要具有专业知识的相关策划和设计人员参与，需要不断进行调试和修改，因此这样的设计方式往往效率低下，生产需要很多时间，且消耗人力和其他资源。另一方面，预先设计好的路径数据会增加游戏数据的存储空间，使得游戏的便携性降低。

在一些其他类型游戏的生产中，有时会使用过程内容生成(Procedural ContentGeneration，简称PCG)技术来通过计算机进行游戏内容生产。PCG技术是一种可以遵照一定设计规律自动随游戏进行生成例如关卡，地图，怪物等游戏内容的技术。该技术通过一个随机种子和一系列由设计师调整的参数，将一些游戏内容排列组合产生“新”的内容。

PCG技术虽然在一定程度上可以解决延长游戏时间和增加游戏不确定性的需求，但也有诸多问题。动态的生成算法大多过于复杂，执行效率较低。由于PCG技术的基础是由设计师设计产生的游戏部件，生成的内容其实都有一定的局限性。它们都是有限元素的排列组合，玩家很快就会穷尽这些元素，对新的内容失去新鲜感。因此在经历较长游戏过程之后，产生的游戏内容会给玩家带来一种“与无限的随机数作战”的感受。不仅不能带来新鲜感，而且会对重复游戏内容的敷衍产生反感。

不仅如此，由于随机性，游戏的平衡性会在很大程度被上影响。例如游戏中的人物或物品的属性通过随机生成，原本是为了给玩家提供“无限的可能”，但在游戏设计时，开发者为了使装备库/人物库庞大，复杂，难以重复，往往会将随机范围设置的过于广泛，这样过分的使用随机也会导致游戏的结果严重依赖于随机因素本身，而非人的决策和控制等因素。玩家为了得到最大化的利益会反复读取存档进行特定随机事件直到产出符合玩家心理的情况。这些问题可以归结为随机的滥用问题。实际上，过低的随机数往往可以看作是对玩家产生负面影响的“惩罚”，而在游戏中玩家不应因为“脸黑”而受到惩罚，而应该是因为一些地方做的不好希望玩家下次改进才会受到惩罚。

因此，需要一种能够由计算机代替人工来自动生成游戏关卡路径的方法。

发明内容

本发明的实施方式鉴于现有技术的上述问题提出，旨在提供一种游戏路径生成方法及装置，以解决现有技术中存在的一种或更多种的缺点，至少提供一种有益的选择。

为了实现本发明的目的，本发明的实施方式提供了以下的方面。

根据本发明的一方面，提供了一种游戏路径生成方法，该方法包括主路径生成步骤和至少一个分支路径生成步骤，所述主路径生成步骤包括：从游戏地图的预定区域范围内选择一个位置作为起始点，选择起始出发方向，利用平滑连接的弧线和直线进行路径随机探索和生成步骤，并记录生成的路径作为主路径，直至到达地图边界；所述分支路径生成步骤包括：在生成的主路径的预定范围内随机选择一个点作为分支路径起始点和与主路径的交叉点，选择与主路径交叉的方向作为分支路径起始出发方向，利用平滑连接的弧线和直线进支路径随机探索和生成步骤，并记录生成的路径作为分支路径。

在一实施例中，所述游戏地图的预定区域范围是指所述游戏地图中部的预定区域范围；所述主路径生成步骤还包括：在已生成的主路径到达地图边界后，从所述起始点开始沿着与起始出发方向相反的出发方向，利用平滑连接的弧线和直线进行路径随机探索和生成步骤，使得所述主路径从所述起始点延伸，直至再次到达地图边界。

在一实施例中，所述剪枝条件包括：与已有的路径重合或相交。

在一实施例中，所述剪枝策略优化步骤还包括：如果在一条路径的生成过程中撤销弧线或直线的次数超过预定阈值，则删除该条路径。

在一实施例中，所述主路径生成步骤或所述分支路径生成步骤中的所述利用平滑连接的弧线和直线进行路径随机探索和生成步骤还包括：评价策略优化步骤，在当前生成的主路径或分支路径已经到达地图边界的情况下，确定该路径是否满足预定的路径可用性条件，如果不满足，则清除当前生成的主路径或分支路径，并重新执行主路径或分支路径生成步骤。

在一实施例中，所述路径可用性条件包括：当前生成的主路径或分支路径的路径覆盖率大于预定阈值。

在一实施例中，所述路径可用性条件还包括分支路径长度小于主路径长度。

在一实施例中，所述主路径生成步骤中的起始出发方向与地图的一个边界垂直；并且所述分支路径生成步骤中的分支路径起始出发方向与交叉点处主路径的方向垂直。

根据本发明的另一方面，还提供一种游戏路径生成装置，该装置包括处理器和存储器，所述存储器用于存储计算机指令，所述处理器用于执行所述存储器中存储的计算机指令，当处理器执行存储器上存储的计算机指令时所述游戏路径生成装置用于完成如前所述的游戏路径生成方法。

根据本发明的另一方面，还提供一种计算机程序存储介质，其上存储有计算机程序代码，在该代码被执行时实现如前所述的游戏路径生成方法。

基于本发明的技术方案，由计算机代替人工来自动生成游戏关卡路径，并且具有快速、低成本、自动地生成游戏路径的优点，并克服了传统游戏路径设计中的种种不足。

附图说明

参照下面结合附图对本发明实施例的说明，会更加容易地理解本发明的以上和其它目的、特点和优点。

图1为本发明实施例中路径的圆弧表示方法示例。

图2为本发明一实施例中塔防游戏路径的自动生成方法的流程示意图。

图3为本发明实施例中进行第一次搜索到达边界的示意图。

图4为本发明实施例中经过两次搜索得到完整路径的示意图。

图5为本发明实施例中主路径和分支路径的示意图。

图6为本发明实施例中主路径生成方法的流程示意图。

图7为本发明实施例中分支路径生成方法的流程示意图。

图8为本发明实施例中利用自动路径生成方法生成的关卡路径的示例。

图9为本发明实施例中游戏路径生成装置的框图事宜。

具体实施方式

下面参照附图来说明本发明的实施方式。在所述的说明和附图中，详细公开了本发明的特定实施方式，指明了本发明的原理可以被采用的方式。应该理解，本发明在范围上并不因而受到限制。在所附权利要求的精神和条款的范围内，本发明包括许多改变、修改和等同。

应当注意，为了清楚的目的，附图和说明中省略了与本发明无关的、本领域普通技术人员已知的部件和处理的表示和描述。

针对一种实施方式描述和/或示出的特征可以以相同或类似的方式在一个或更多个其它实施方式中使用，与其它实施方式中的特征相组合，或替代其它实施方式中的特征。

应该强调，术语“包括/包含”在本文使用时指特征、要素、步骤或组件的存在，但并不排除一个或更多个其它特征、要素、步骤或组件的存在或附加。

为了解决传统游戏的路径设计中设计效率低下、设计流程长、人力和资金投入大、随机性滥用而导致的游戏内容不足等等问题，在本发明实施例中，提出了一种用计算机代替人工，自动地生成大量游戏路径的方法。作为示例性实施例，本发明基于蒙特卡洛树搜索方法来进行游戏中路径的自动搜索和生成，并采用枝剪策略和评价策略来进行路径的优化，从而快速、低成本、自动地生成游戏路径，克服了传统游戏路径设计中的种种不足，大大提高了游戏生成效率，并增强了游戏的趣味性和挑战性。

蒙特卡洛树搜索(Monte Calro Tree Search,MCTS)是一种人工智能问题中可做出最优决策的方法，一般是在组合博弈中的行动(move)规划形式。它是一种在随机或伪随机基础之上，对于搜索空间进行搜索，并在搜索到达一定深度的时候对搜索结果的价值进行评分，根据各节点的评分进行筛选和剪枝的技术。它结合了随机模拟的一般性和树搜索的准确性。MCTS是一种启发式的搜索策略，能够基于对搜索空间的随机抽样来扩大搜索树，从而分析搜索任务中的每一步应该怎么选择才能够获得最佳结果。

蒙特卡洛树搜索可以高效的对随机空间进行搜索并得出价值高的结果。本发明的方法相当于是蒙特卡洛树搜索的一种变体，可以有效的解决PCG方法中随机数滥用带来的搜索空间过大的问题以及随机数滥用的问题，并大大提高了游戏路径设计的效率和游戏的趣味性。

下面详细描述本发明实施例的基于蒙特卡洛树搜索的游戏路径生成方法，该游戏路径生成方法可以在计算机上实现，每台计算机均具有存储器和处理器，例如，处理器可以是CPU、微处理器等。图9所示为本发明实施例中实现游戏路径生成方法的装置的示意性框图，该装置包括处理器910和存储器920。存储器920用于存储计算机程序，处理器910通过执行计算机程序来实现游戏路径生成方法。可选的，该装置还可包括传输接口(有线接口或无线网络接口)930以及显示器940。传输接口930用于与外部装置进行通信，以传输数据。显示器940可用于显示生成的路径。图9中示出的结构仅为示例，还可以包括更多或更少的部件。

本发明首先提出一种路径的表示方法，即用若干个不同的圆弧和直线的“平滑”连接来表示一条路线。其中所谓的平滑连接意味着每一段弧线或直线都是沿着上一段路径末尾的方向生成的，例如，确保弧线平滑连接的方法为：生成一段弧线的时候，确保该弧线的曲率圆心在上一段路径终点处的切线方向的垂线上。基于这种表示方法可以表示游戏路径信息。图1所示为本发明实施例中圆弧和直线平滑连接来表示路径10的路径表示方法示意图。

在本发明实施例中，可以设计为在游戏地图上生成一条主路径和多条分支路径。无论是主路径还是分支路径，每一条路径的生成步骤都可包含基于蒙特卡洛树搜索机制的随机探索步骤、剪枝策略优化和评价策略优化这3部分。其中剪枝策略是在探索过程中，对于每一次的探索，将不符合策略要求的探索或路径筛选掉，从而提高路径可用性，减少探索次数，提高路径生成效率。评价策略例如是在路径生成后，对路径的合理性进行评估，从而觉得是否将该路径应用于游戏中。

图2所示为本发明一实施例中游戏路径的自动生成方法的流程示意图。如图2所示，该方法可包括主路径生成步骤S210-S220以及分支路径生成步骤S230，其中步骤S230可执行多次以产生多条分支路径。

在本实施例中，设定只有一条路径是主路径，其余的路径视为主路径上的分支，即分支路径。由此，定义一个完整的路径生成过程包括一次主路径生成以及若干次分支路径生成步骤。主路径生成步骤中主路径由2次路径搜索生成的2段路径平滑连接而成。其中：

在步骤S210，从游戏地图中预定区域范围内选择一个位置作为起始点，选择起始出发方向，利用平滑连接的弧线和直线进行路径随机探索和生成步骤，并记录生成的路径作为第一段主路径。

上述预定区域范围例如可以是地区中心区域的预定范围，但本发明并不限于此。

作为一示例，可以以地图中心附近区域内随机选择一个位置作为起始点，以并随机选择一个方向作为起始出发方向，从起始点以及起始出发方向开始，利用平滑连接的弧线和直线进行路径随机探索。本示例中对起始点的随机选择是指按照一定的随机概率选择地图中心附近区域内的点作为起始点。对起始出发方向的选择同样可以按照一定的随机概率进行。路径随机探索过程中，可每间隔预定数量的像素(如每间隔7个像素，但并不限于此)，记录路径上的点坐标，将若干点坐标组成的列表作为路径的表示。

此外，在随机探索过程中，每一次探索可以按照一定概率决定用弧线还是直线来扩展(延长)路径。每一次探索中所用的直线或曲线可以是固定参数的，如固定的直线长度、固定的弧线弧度和固定的半径等，也可以是可变参数的。游戏中地图的大小是固定的，可通过预先设定不同的圆弧的弧度和半径组合以及直线长度等参数，通过多次实验在地图上基于不同参数进行随机选择来生成路径，经过人工判断优选路径可选取合适的参数。可人工选择一套若干组关于路径中直线和弧线的参数，包括直线长度，弧线半径和弧线弧度等，并将参数记录到参数库中。后续路径的随机探索可以基于预先设定的参数选择规则和预设的随机概率来进行。

在一些实施例中，还可以预先设置路径中直线和曲线的比例并存储在参数库中，以使得在路径探索时考虑预先直线和圆弧的比例，随机从参数库中取得当前该次探索的直线或弧线参数。

本一些实施例中，每次路径随机探索步骤可包括沿当前出发方向生成一段弧线或直线。可进行多次路径随机探索来扩展路径，直至路径到达地图边界，由此，便生成了主路径中的第一段主路径。

可选地，在第一段主路径的生成过程中，每次路径随机探索之后，本发明还可以基于预定的剪枝策略将不符合要求的探索的路径筛选掉，从而提高路径生成效率。也即，利用平滑连接的弧线和直线进行路径随机探索和生成的步骤除了包括路径探索步骤之外，还包括剪枝策略优化步骤，剪枝策略优化步骤确定生成的弧线或直线是否满足预定的剪枝条件，若满足，则撤销最新生成的弧线或直线，并重新执行路径生成步骤。作为一示例，剪枝策略例如可以包括：路径中产生闭环路径。这样在每次探索中，可检测随机探索会不会与已经确定的路径产生闭环，如果有闭环，可将路径的状态还原到此次探索之前的情况并撤销本次探索出的新路经。然后重新以一定概率随机选择进一步要探索的路径。此外，剪枝策略优化步骤还可包括：如果一次路径生成过程中，撤回超过一定次数仍不能生成完整路径，则删除整条已经生成的路径，返回随机探索中的起始步骤，重新选择起始点，进行新一次的路经生成，这样可以避免搜索算法收敛到一个不可行的情况，产生不合理的路径。

可选地，进行路径随机探索和生成的步骤还可包括：评价策略优化步骤，在当前生成的主路径或分支路径已经到达地图边界的情况下，确定该路径是否满足预定的路径可用性条件，如果不满足，则清除当前生成的主路径或分支路径，并重新执行主路径或分支路径生成步骤。其中路径可用性条件包括：当前生成的主路径或分支路径的路径覆盖率大于预定阈值。

在一示例中，可将整个地图等分为n*m的区域(n，m为大于等于2的自然数，二者可以相同也可以不同)，如4*4的区域，对路径通过的区域数量进行统计，计算通过的区域与全部区域数量的比值作为路径覆盖率。判断若路径覆盖率大于预设阈值时，则认为当前生成的路径合格，否则删除当前生成的路径，重新进行生成。路径覆盖率的预设阈值例如可以是50％-80％，优选为75％，但本发明并不限于该示例性阈值，而是可以更大或更小。

图3所示为经过步骤S210之后生成的第一段主路径的示意图。

在步骤S220，生成第一段主路径之后，可继续从起始点开始沿着与步骤S210中的起始出发方向(第一起始出发方向)相反的第二起始出发方向，利用平滑连接的弧线和直线进行路径随机探索和生成步骤，并记录生成的路径作为第2段主路径，直至再次到达地图边界。

该步骤中，除了第二起始出发方向与第一起始出发方向相反外，其他的可参照步骤S210执行。

本步骤中利用平滑连接的弧线和直线进行路径随机探索和生成步骤可以与前一步骤S210相同，在此不再赘述。

图4所示为经过步骤S220的第二次搜索之后生成的完整的主路径的示意图。

在本发明另一实施例中，也可以仅用一次随机搜索操作来实现主路径的生成，此时可以将起始点选择在游戏地图的边界，起始出发方向也优选地设置为与出发点所在的边界垂直。其他操作可以参见步骤S210，在此不再赘述。

在步骤S220，进行分支路径生成。该步骤中，在已生成的主路径上的预定范围内随机选择一个点作为分支路径起始点和与主路径的交叉点，选择与主路径交叉的方向作为分支路径起始出发方向，利用平滑连接的弧线和直线进支路径随机探索和生成步骤，并记录生成的路径作为分支路径。

作为一个示例，优选地设计为分支路径起始出发方向与交叉点处主路径的方向垂直，但本发明并不限于此。

该分支路径形成步骤中，除了起始点和的起始出发方向与主路径生成步骤不同，其他的可操作可与主路径生成步骤相同，例如，利用平滑连接的弧线和直线进支路径随机探索和生成的步骤也同样包括路径随机探索步骤、剪枝策略优化步骤和评价策略优化步骤，其中，路径随机探索步骤、剪枝策略优化步骤和评价策略优化步骤的操作规则可以与主路径生成步骤一致，在此不再赘述。

另选的，本步骤中，评价策略优化步骤中，还可有一个额外的路径可用性条件，该额外的路径可用性条件可包括分支路径长度小于主路径长度，以此保证主路径长于分支路径。

图5为本发明实施例中得多的主路径和分支路径的示意图，如图5中所示，除了主路径11之外，还形成了分支路径12。

本发明实施例中，路径的整个生成过程可以看做是使用了蒙特卡洛树搜索算法的一种变体。一条路径的生成过程如下：首先在地图中选取一个起始点，并选取一个初始方向，然后通过随机探索一步一步为当前路径增加线段直到到达边界。在随机探索的过程中检测是否满足剪枝条件以及是否满足结束条件，若满足剪枝条件则撤回此次生成的路径，从上一段开始重新生成，若满足结束条件则将当前路径传入评价策略评价是否合理，若合理则保留，否则重头开始重新生成路径。

图6为本发明实施例中主路径生成方法的具体流程示意图。图7为本发明实施例中分支路径生成方法的具体流程示意图。

如图6所示，该示例中主路径的形成过程包括：

步骤S61，在地图的中心点附近区域内随机选择初始点和初始方向。

设定地图为1048×768的长方形范围，将地图分为四个象限，初始化覆盖率计数器(area_count)，该计数器用于计算生成的路径在几个象限中出现过，从而确定路径的覆盖率。在本发明其他实施方式中，还可以将地图均分为更多个区域，而不是仅仅4个象限，如分为n*m(n＞2，m＞2)的矩形块，通过判断路径占据的矩形块的多少来确定路径覆盖率。

中心点的定义：矩形地图的几何中心点。中心点附近区域的定义：以中心点为圆心，半径为R(R的取值范围[0，地图宽度的一半])围成的圆形区域。

可按照一定的概率任意选一个位于中心附近的点作为起始点(如图3中的圆点)，起始点初始方向可设定为与边缘垂直。

步骤S62，按照预先设定的一个概率分布选取一段直线或曲率半径为r，转角为a的弧线段，如果选取的是弧线，弧线需与当前前进方向吻合。

路径生成过程中，弧线半径、弧度、直线长度等配置信息，以及直线和弧线的出现比例可以灵活进行调整。

步骤S63，对生成的路径进行剪枝策略优化，判断当前生成的路线是否与已有路线重合或相交？

如果既不重合又不相交，则继续执行步骤S65。如果重合或相交，则执行步骤S64，撤回当前生成的弧线或直线，并返回S62，重新生成一段弧线或直线。

步骤S65，判断生成的路线是否与地图边界相交(即判断是否到达边界)，若是，则执行步骤S66，对生成的路径进行评价策略优化，判断当前生成的主路径或分支路径的路径覆盖率大于预定阈值。本实施例中，预定阈值可以取值为3/4，即路径要占据4个象限中的3个象限。该预定阈值可以修改。

本实施例中，通过覆盖率计时器的值是否大于3来确定路径是否占满3/4地图。

如果确定路径占满3/4地图，则确定该路径可用，于是输出路径。

如果路径没有占满3/4地图，则执行步骤S67，删除(清空)当前生成的整条路径，并返回步骤S61，重新生成路径。

经由图6的上述流程，可以生成主路径。接下来描述分支路径的示例性生成流程。如图7所示，该示例中分支路径的形成过程包括：

步骤S71，在已经生成主路径上的一定范围内随机选择一点作为初始点，并设定初始方向与主路径在该点的方向垂直。

步骤S72，按照预先设定的一个概率分布选取一段直线或者曲率半径为r，转角为a的弧线段，如果选取的是弧线，弧线需与当前前进方向吻合。

路径生成过程中，弧线半径、弧度、直线长度等配置信息，以及直线和弧线的出现比例可以灵活进行调整。

步骤S73，对生成的路径进行剪枝策略优化，判断当前生成的路线是否与已有路线重合或相交？

如果既不重合又不相交，则继续执行步骤S75。如果重合或相交，则执行步骤S74，撤回当前生成的弧线或直线，并返回S72，重新生成一段弧线或直线。

步骤S75，判断生成的路线是否与地图边界相交(即判断是否到达边界)，若是，则执行步骤S76，对生成的路径进行评价策略优化，判断路径长度是否大于预定阈值且小于主路径长度。如果生成的分支路径长度小于主路径长度且大于设定的预定阈值，则确定路径可用，于是输出路径。

如果生成的分支路径长度大于于主路径长度或小于设定的预定阈值，则执行步骤S77，删除(清空)当前生成的整条路径，并返回步骤S71，重新生成路径。

经由图7的上述流程，可以生成分支路径。

本发明的如上方法步骤中，有的步骤的执行顺序可以并行执行或互换，而不限于图中示出的顺序。

图8中的(a)-(c)指出的通过本发明的方法生成的游戏关卡路径的示例。

本发明实施例中，枝剪策略和评价策略可以灵活进行修改。

本发明通过如上设计的路径生成算法，使用计算机生成路径，生产环节无需人工参与，极大节省人力资源。路经生成速度极快，大幅提升游戏生产效率。并且，本发明通过若干直线和弧线拟合路径可产生自然的路径效果。

本发明通过蒙特卡洛随机搜索方法对路径进行拓展并且结合剪枝策略与评价策略，代替PCG中通过完全随机产生游戏内容的方式，可以改进原有PCG技术中随机滥用的问题。并且通过对市面上受欢迎的游戏路径的分析，得到一些路径的构成部件的模式，并配合剪枝策略和评价策略，保证大量产生的路径，大量随机情况下路径的合理性，从而保证游戏的游戏性和挑战性。本发明的方法不仅适用于塔防游戏关卡路径的生成，还可以用于其他需要设计路径的游戏当中。

本发明实施例的如上方法可在计算机上通过执行计算机程序来实现。由此，本发明提供一种游戏路径生成装置，该装置包括处理器和存储器，所述存储器用于存储计算机指令，所述处理器用于执行所述存储器中存储的计算机指令，当处理器执行存储器上存储的计算机指令时所述游戏路径生成装置用于完成如上所述的游戏路径生成方法。

本公开还涉及存储介质，其上可以存储有计算机程序代码，当程序代码被执行时可以实施本发明的游戏路径生成方法的各种实施例，该存储介质可以是有形存储介质，诸如光盘、U盘、软盘、硬盘等。

本领域普通技术人员可以意识到，结合本文中所公开的实施方式描述的各示例性的单元及方法步骤，能够以硬件、软件或者二者的结合来实现。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。

结合本文中所公开的实施方式描述的方法或算法的步骤可以用硬件(计算机等逻辑装置)执行的软件来实现。所述软件在被执行时，可以使所述硬件(计算机等逻辑装置)实现上述的方法或其组成步骤，或使所述硬件(计算机等逻辑装置)充当上面所述的本发明的装置部件。

软件可以置于随机存储器(RAM)、内存、只读存储器(ROM)、电可编程ROM、电可擦除可编程ROM、寄存器、硬盘、可移动磁盘、CD-ROM、或技术领域内所公知的任意其它形式的存储介质中。

以上描述的实施例都是示例性的，不是对本发明的限制，本领域技术人员根据本发明的精神，可以想到各种变型和修改，这些变型和修改也在本发明的范围内。

Claims (11)

1.一种游戏路径生成方法，其特征在于，该方法包括主路径生成步骤和至少一个分支路径生成步骤：

所述主路径生成步骤包括：

从游戏地图的预定区域范围内选择一个位置作为起始点，选择起始出发方向，利用平滑连接的弧线和直线进行路径随机探索和生成步骤，并记录生成的路径作为主路径，直至到达地图边界；

所述分支路径生成步骤包括：

在已生成的主路径上的预定范围内随机选择一个点作为分支路径起始点和与主路径的交叉点，选择与主路径交叉的方向作为分支路径起始出发方向，利用平滑连接的弧线和直线进支路径随机探索和生成步骤，并记录生成的路径作为分支路径。

2.根据权利要求1所述的方法，其特征在于，所述游戏地图的预定区域范围是指所述游戏地图中部的预定区域范围；

所述主路径生成步骤还包括：在已生成的主路径到达地图边界后，从所述起始点开始沿着与起始出发方向相反的出发方向，利用平滑连接的弧线和直线进行路径随机探索和生成步骤，使得所述主路径从所述起始点延伸，直至再次到达地图边界。

3.根据权利要求1或2所述的方法，其特征在于，所述主路径生成步骤或所述分支路径生成步骤中的所述利用平滑连接的弧线和直线进行路径随机探索和生成步骤包括：

路径探索步骤，沿当前出发方向生成一段弧线或直线；

剪枝策略优化步骤，确定生成的弧线或直线是否满足预定的剪枝条件，若满足，则撤销最新生成的弧线或直线，并重新执行路径生成步骤。

4.根据权利要求3所述的方法，其特征在于：

所述剪枝条件包括：与已有的路径重合或相交。

5.根据权利要求3所述的方法，其特征在于，所述剪枝策略优化步骤还包括：

如果在一条路径的生成过程中撤销弧线或直线的次数超过预定阈值，则删除该条路径。

6.根据权利要求1或2所述的方法，其特征在于，所述主路径生成步骤或所述分支路径生成步骤中的所述利用平滑连接的弧线和直线进行路径随机探索和生成步骤还包括：

评价策略优化步骤，在当前生成的主路径或分支路径已经到达地图边界的情况下，确定该路径是否满足预定的路径可用性条件，如果不满足，则清除当前生成的主路径或分支路径，并重新执行主路径或分支路径生成步骤。

7.根据权利要求6所述的方法，其特征在于：

所述路径可用性条件包括：当前生成的主路径或分支路径的路径覆盖率大于预定阈值。

8.根据权利要求7所述的方法，其特征在于：

所述路径可用性条件还包括分支路径长度小于主路径长度。

9.根据权利要求1所述的方法，其特征在于：

所述主路径生成步骤中的起始出发方向与地图的一个边界垂直；并且

所述分支路径生成步骤中的分支路径起始出发方向与交叉点处主路径的方向垂直。

10.一种游戏路径生成装置，其特征在于，该装置包括处理器和存储器，所述存储器用于存储计算机指令，所述处理器用于执行所述存储器中存储的计算机指令，当处理器执行存储器上存储的计算机指令时所述游戏路径生成装置用于完成如权利要求1-9中任意一项所述的游戏路径生成方法。

11.一种计算机程序存储介质，其上存储有计算机程序代码，在该代码被执行时实现权利要求1-9中任意一项所述的游戏路径生成方法。