• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 11
    • 下载费用:30 金币  

    重庆时时彩5星遗漏: 一种游戏寻路方法和装置.pdf

    关 键 词:
    一种 游戏 方法 装置
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    摘要
    申请专利号:

    CN201611089845.8

    申请日:

    2016.12.01

    公开号:

    CN106582023A

    公开日:

    2017.04.26

    当前法律状态:

    实审

    有效性:

    审中

    法律详情: 实质审查的生效IPC(主分类):A63F 13/56申请日:20161201|||公开
    IPC分类号: A63F13/56(2014.01)I 主分类号: A63F13/56
    申请人: 北京像素软件科技股份有限公司
    发明人: 刘璐
    地址: 102200 北京市昌平区科技园区白浮泉路10号2号楼1104A
    优先权:
    专利代理机构: 北京品源专利代理有限公司 11332 代理人: 孟金喆;胡彬
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201611089845.8

    授权公告号:

    |||

    法律状态公告日:

    2017.05.24|||2017.04.26

    法律状态类型:

    实质审查的生效|||公开

    摘要

    本发明公开了一种游戏寻路方法和装置。游戏寻路方法包括:获取游戏运行指令,从游戏地图文件中读取可行走区域数据,其中,游戏地图文件中预存有可行走区域数据;根据移动路径的寻找指令,获取所述移动路径的起点坐标和终点坐标,根据所述起点坐标、终点坐标和可行走区域数据确定所述移动路径。本发明解决了现有的寻路算法中计算路径碰撞点的性能较低的问题,根据游戏玩家发出移动路径的寻找指令中的起点坐标、终点坐标和预存的可行走区域数据确定移动路径,不仅提高了计算路径碰撞点的性能,而且利用预存可行走区域数据有效减少查找的多边形数据,从而减少了动态寻路的计算量,进而快速高效的得到游戏角色的移动路径。

    权利要求书

    1.一种游戏寻路方法,其特征在于,包括:
    获取游戏运行指令,从游戏地图文件中读取可行走区域数据,其中,所述游戏地图文件
    中预存有所述可行走区域数据,所述可行走区域数据为对可行走区域配置数据进行预处理
    得到,所述可行走区域由至少一个多边形单元格组成;
    根据移动路径的寻找指令,获取所述移动路径的起点坐标和终点坐标,根据所述起点
    坐标、终点坐标和可行走区域数据确定所述移动路径。
    2.根据权利要求1所述的游戏寻路方法,其特征在于,在所述从游戏地图文件中读取可
    行走区域数据之前,所述方法还包括:
    获取所述可行走区域配置数据;
    根据所述可行走区域配置数据获取所述可行走区域中每个多边形单元格的顶点数据
    和边数据;
    根据所述多边形单元格的顶点数据计算多边形单元格的重心坐标;
    根据可行走区域中每个多边形单元格的重心坐标和顶点数据进行计算,得到每个多边
    形单元格的相邻多边形单元格,并对每个多边形单元格的相邻多边形单元格分别做出相邻
    标识;
    将所述可行走区域中每个多边形单元格的顶点数据、边数据、重心坐标和相邻标识作
    为可行走区域数据存储到所述游戏地图文件中。
    3.根据权利要求2所述的游戏寻路方法,其特征在于,根据所述起点坐标、终点坐标和
    可行走区域数据确定所述移动路径,包括:
    根据所述起点坐标和所述可行走区域数据,获取起点所在的多边形单元格,并将其作
    为目标单元格;
    循环执行如下步骤,直到目标线段与目标单元格不存在相交点、或者不存在与所述目
    标单元格相邻的多边形单元格为止,其中,所述目标线段为所述移动路径的起点和终点的
    连线:
    a根据所述目标线段的起点坐标、终点坐标和所述目标单元格的顶点数据判断所述目
    标线段和所述目标单元格是否存在相交点,若不存在相交点,则将所述目标线段作为所述
    移动路径,若存在相交点,则将所述目标线段的起点和所述相交点的连线作为行走路段;
    b根据所述目标单元格的相邻多边形的标识数据判断是否存在与所述目标单元格相邻
    的多边形单元格,若是,则将所述待寻路径的起点更新为所述相交点、将所述目标单元格更
    新为与所述目标单元格相邻的多边形单元格,若否,则将获取到的至少一个行走路段作为
    所述移动路径。
    4.根据权利要求1-3任一项所述的游戏寻路方法,其特征在于,所述多边形单元格包括
    规则多边形单元格和不规则多边形单元格。
    5.一种游戏寻路装置,其特征在于,包括:
    可行走区域数据获取???,用于获取游戏运行指令,从游戏地图文件中读取可行走区
    域数据,其中,所述游戏地图文件中预存有所述可行走区域数据,所述可行走区域数据为对
    可行走区域配置数据进行预处理得到,所述可行走区域由至少一个多边形单元格组成;
    移动路径确定???,根据移动路径的寻找指令,获取所述移动路径的起点坐标和终点
    坐标,根据所述起点坐标、终点坐标和可行走区域数据确定所述移动路径。
    6.根据权利要求5所述的游戏寻路装置,其特征在于,所述装置还包括:
    可行走区域配置数据获取???,用于获取所述可行走区域配置数据;
    单元格数据获取???,用于根据所述可行走区域配置数据获取所述可行走区域中每个
    多边形单元格的顶点数据和边数据;
    重心坐标???,用于根据所述多边形单元格的顶点数据计算多边形单元格的重心坐
    标;
    相邻标识计算???,用于根据可行走区域中每个多边形单元格的重心坐标和顶点数据
    进行计算,得到每个多边形单元格的相邻多边形单元格,并对每个多边形单元格的相邻多
    边形单元格分别做出相邻标识;
    可行走区域数据存储???,用于将所述可行走区域中每个多边形单元格的顶点数据、
    边数据、重心坐标和相邻标识作为可行走区域数据存储到所述游戏地图文件中。
    7.根据权利要求6所述的游戏寻路装置,其特征在于,所述移动路径确定??榘ǎ?br />目标单元格获取单元,用于根据所述起点坐标和所述可行走区域数据,获取起点所在
    的多边形单元格,并将其作为目标单元格;
    循环中止判断单元,用于执行如下步骤,直到目标线段与目标单元格不存在相交点、或
    者不存在与所述目标单元格相邻的多边形单元格为止,其中,所述目标线段为所述移动路
    径的起点和终点的连线:
    相交点判断单元,用于根据所述目标线段的起点坐标、终点坐标和所述目标单元格的
    顶点数据判断所述目标线段和所述目标单元格是否存在相交点,若不存在相交点时,则将
    所述目标线段作为所述移动路径;当存在相交点时,则将所述目标线段的起点和所述相交
    点的连线作为行走路段;
    相邻多边形判断单元,用于根据所述目标单元格的相邻多边形的标识数据判断是否存
    在与所述目标单元格相邻的多边形单元格,若是,则将所述待寻路径的起点更新为所述相
    交点、将所述目标单元格更新为与所述目标单元格相邻的多边形单元格;若否,则将获取到
    的至少一个行走路段作为所述移动路径。
    8.根据权利要求5-7任一项所述的游戏寻路装置,其特征在于,所述多边形单元格包括
    规则多边形单元格和不规则多边形单元格。

    说明书

    一种游戏寻路方法和装置

    技术领域

    本发明实施例涉及计算机图形技术领域,尤其涉及一种游戏寻路方法和装置。

    背景技术

    随着游戏技术的发展,游戏地图做的越来越大,一个流畅高效的寻路实现能够带
    给玩家更好的用户体验。

    目前绝大部分游戏中的寻路主要有两种:一种是采用A*算法来计算的,这种方法
    能够计算出从一个点到另一个点的路线。然而该算法的性能与使用的场景大小有非常大的
    关系,场景非常大并且寻路距离非常远的情况下性能会急剧下降。

    另一种是采用一种多边形的寻路算法,该算法虽然能够比较快速的计算出寻路数
    据,但是计算碰撞点的性能会较低。

    发明内容

    本发明提供一种游戏寻路方法和装置,以解决现有的寻路算法中计算路径碰撞点
    的性能较低的问题。

    第一方面,本发明实施例提供了一种游戏寻路方法,包括:

    获取游戏运行指令,从游戏地图文件中读取可行走区域数据,其中,所述游戏地图
    文件中预存有所述可行走区域数据,所述可行走区域数据为对可行走区域配置数据进行预
    处理得到,所述可行走区域由至少一个多边形单元格组成;

    根据移动路径的寻找指令,获取所述移动路径的起点坐标和终点坐标,根据所述
    起点坐标、终点坐标和可行走区域数据确定所述移动路径。

    第二方面,本发明实施例还提供了一种游戏寻路装置,该装置包括:

    可行走区域数据获取???,用于获取游戏运行指令,从游戏地图文件中读取可行
    走区域数据,其中,所述游戏地图文件中预存有所述可行走区域数据,所述可行走区域数据
    为对可行走区域配置数据进行预处理得到,所述可行走区域由至少一个多边形单元格组
    成;

    移动路径确定???,根据移动路径的寻找指令,获取所述移动路径的起点坐标和
    终点坐标,根据所述起点坐标、终点坐标和可行走区域数据确定所述移动路径。

    本发明实施例根据游戏玩家发出移动路径的寻找指令中的起点坐标、终点坐标和
    预存的可行走区域数据确定移动路径,解决现有的寻路算法中,计算路径碰撞点的性能较
    低的问题。不仅提高了计算路径碰撞点的性能,而且利用预存可行走区域数据有效减少查
    找的多边形数据,从而减少了动态寻路的计算量,进而快速高效的得到游戏角色的移动路
    径。

    附图说明

    图1是本发明实施例一中的一种游戏寻路方法流程示意图;

    图2是本发明实施例二中的一种游戏寻路方法流程示意图;

    图3是本发明实施例三中的一种游戏寻路装置结构示意图。

    具体实施方式

    下面结合附图和实施例对本发明作进一步的详细说明??梢岳斫獾氖?,此处所描
    述的具体实施例仅仅用于解释本发明,而非对本发明的限定。另外还需要说明的是,为了便
    于描述,附图中仅示出了与本发明相关的部分而非全部结构。

    实施例一

    图1为本发明实施例一提供的一种游戏寻路方法流程示意图,本实施例可适用于
    游戏角色寻找移动路径的过程中情况,该方法可以由一种游戏寻路装置来执行,该装置可
    以由软件和/或硬件的方式来实现。如图1所示,该方法包括:

    S110、获取游戏运行指令,从游戏地图文件中读取可行走区域数据,其中,所述游
    戏地图文件中预存有所述可行走区域数据,所述可行走区域数据为对可行走区域配置数据
    进行预处理得到,所述可行走区域由至少一个多边形单元格组成。

    所述游戏运行指令可以是游戏开启指令??尚凶咔蚺渲檬菸杂蜗返赝嫉木?br />体信息,包括对地图地表、地图物体摆放和地图属性等信息配置数据,根据可行走区域配置
    数据生成游戏地图文件。

    所述游戏地图文件包括可行走区域数据和不可行走区域数据。游戏角色进行移动
    时仅可以在可行走区域中寻找路径。所述可行走区域数据用于存储所述可行走区域。这样
    的设置好处在于,游戏角色移动时的移动路径在可行走区域中选取,避免了与不可行走区
    域的碰撞。

    S120、根据移动路径的寻找指令,获取所述移动路径的起点坐标和终点坐标,根据
    所述起点坐标、终点坐标和可行走区域数据确定所述移动路径。

    移动路径的寻找指令通常由游戏玩家发出。移动路径的寻找指令包括移动路径的
    起点坐标、终点坐标和移动路径开始运算指令。移动路径计算指令用于驱动运算操作的开
    始。

    所述可行走区域多个多边形单元格覆盖形成,运算操作开始时,所述方法从起点
    所在的多边形单元格开始运算,并逐一对相关多边形单元格进行运算,进而获取到移动路
    径。

    本实施例的技术方案,根据游戏玩家发出移动路径的寻找指令中的起点坐标、终
    点坐标和预存的可行走区域数据确定移动路径,解决现有的寻路算法中,计算路径碰撞点
    的性能较低的问题。不仅提高了计算路径碰撞点的性能,而且利用预存可行走区域数据有
    效减少查找的多边形数据,从而减少了动态寻路的计算量,进而快速高效的得到游戏角色
    的移动路径。

    实施例二

    图2是本发明实施例二中的一种游戏寻路方法流程示意图,本实施例在实施例一
    的基础上,进一步阐述了可行走区域数据的生成操作,如图2所示,该方法包括:

    S210、获取所述可行走区域配置数据。

    所述可行走区域配置数据可以根据具体的游戏策划设定,通常通过用于编辑游戏
    中虚拟场景的工具软件获取,例如地图编辑器。

    S220、根据所述可行走区域配置数据获取所述可行走区域中每个多边形单元格的
    顶点数据和边数据。

    所述用于编辑游戏中虚拟场景的工具软件根据可行走区域配置数据生成游戏地
    图,所述游戏地图包括可行走区域和不可行走区域。

    游戏地图生成完成后,所述方法会获取可行走区域中每个多边形单元格的顶点数
    据和边数据。所述顶点数据包括顶点坐标和顶点间的关系。所述边数据包括多边形包括边
    的数量、每一条边的长度和边与多变形单元格的关系,例如是否属于多变形单元格的共用
    边、属于哪些多变形单元格的共用边等。

    进一步的,所述多边形单元格包括规则多边形单元格和不规则多边形单元格。

    S230、根据所述多边形单元格的顶点数据计算多边形单元格的重心坐标。

    重心坐标可以用于判断多边形单元格是否相邻。

    S240、根据可行走区域中每个多边形单元格的重心坐标和顶点数据进行计算,得
    到每个多边形单元格的相邻多边形单元格,并对每个多边形单元格的相邻多边形单元格分
    别做出相邻标识;

    具体的,获取两个多边形单元格的重心坐标,并计算两个重心坐标连线与所述多
    边形单元格中边的交点,当所述交点存在且仅有一个时,则判定这两个对边形为相邻多边
    形,并对每个多边形单元格的相邻多边形单元格分别做出相邻标识。

    S250、将所述可行走区域中每个多边形单元格的顶点数据、边数据、重心坐标和相
    邻标识作为可行走区域数据存储到所述游戏地图文件中。

    将顶点数据、边数据、重心坐标和相邻标识作为可行走区域数据存储到所述游戏
    地图文件的好处在于,在游戏运行中可直接获取与移动路径计算的相关信息,减少了运算
    量。

    S260、获取游戏运行指令,从游戏地图文件中读取可行走区域数据,其中,所述游
    戏地图文件中预存有所述可行走区域数据,所述可行走区域数据为对可行走区域配置数据
    进行预处理得到,所述可行走区域由至少一个多边形单元格组成;

    S270、根据移动路径的寻找指令,获取所述移动路径的起点坐标和终点坐标,根据
    所述起点坐标、终点坐标和可行走区域数据确定所述移动路径。

    进一步的,根据所述起点坐标、终点坐标和可行走区域数据确定所述移动路径包
    括:

    S271、根据所述起点坐标和所述可行走区域数据,获取起点所在的多边形单元格,
    并将其作为目标单元格;

    计算思路具体为:计算所述起点和坐标原点的连线与多边形单元格各个边的交
    点,当所述交点仅由一个且交点位置与单元格的顶点不重合时,则判断该多边形单元格为
    目标单元格。

    循环执行如下步骤,直到目标线段与目标单元格不存在相交点、或者不存在与所
    述目标单元格相邻的多边形单元格为止,其中,所述目标线段为所述移动路径的起点和终
    点的连线:a根据所述目标线段的起点坐标、终点坐标和所述目标单元格的顶点数据判断所
    述目标线段和所述目标单元格是否存在相交点,若不存在相交点,则将所述目标线段作为
    所述移动路径,若存在相交点,则将所述目标线段的起点和所述相交点的连线作为行走路
    段;b根据所述目标单元格的相邻多边形的标识数据判断是否存在与所述目标单元格相邻
    的多边形单元格,若是,则将所述待寻路径的起点更新为所述相交点、将所述目标单元格更
    新为与所述目标单元格相邻的多边形单元格,若否,则将获取到的至少一个行走路段作为
    所述移动路径。

    移动路径包括一个或多个行走路段。具体的,当目标线段与目标单元格不存在相
    交点,则目标线段在目标单元格内,则判定移动所述起点和终点都在目标单元格内,此时行
    走路段即为移动路径。

    当判断结果为不存在与所述目标单元格相邻的多边形单元格时,可判定所述目标
    单元格处于可行走区域的边缘位置,无法继续行走。此时移动路径为多个行走路段连接而
    成。

    本实施例的技术方案,通过在游戏运行前生成预设的可行走区域数据,在路径计
    算过程中的所需的中间量可以直接获取,有效减少了动态寻路计算量,进而快速高效的得
    到游戏角色的移动路径。

    实施例三

    图3所示为本发明实施例三提供的一种游戏寻路装置结构示意图,如图3所示,该
    游戏寻路装置包括:可行走区域数据获取???10和移动路径确定???20。

    其中,可行走区域数据获取???10,用于获取游戏运行指令,从游戏地图文件中
    读取可行走区域数据,其中,所述游戏地图文件中预存有所述可行走区域数据,所述可行走
    区域数据为对可行走区域配置数据进行预处理得到,所述可行走区域由至少一个多边形单
    元格组成;

    移动路径确定???20,根据移动路径的寻找指令,获取所述移动路径的起点坐标
    和终点坐标,根据所述起点坐标、终点坐标和可行走区域数据确定所述移动路径。

    进一步的,所述装置还包括:

    可行走区域配置数据获取???,用于获取所述可行走区域配置数据;

    单元格数据获取???,用于根据所述可行走区域配置数据获取所述可行走区域中
    每个多边形单元格的顶点数据和边数据;

    重心坐标???,用于根据所述多边形单元格的顶点数据计算多边形单元格的重心
    坐标;

    相邻标识计算???,用于根据可行走区域中每个多边形单元格的重心坐标和顶点
    数据进行计算,得到每个多边形单元格的相邻多边形单元格,并对每个多边形单元格的相
    邻多边形单元格分别做出相邻标识;

    可行走区域数据存储???,用于将所述可行走区域中每个多边形单元格的顶点数
    据、边数据、重心坐标和相邻标识作为可行走区域数据存储到所述游戏地图文件中。

    进一步的,所述移动路径确定??榘ǎ?br />

    目标单元格获取单元,用于根据所述起点坐标和所述可行走区域数据,获取起点
    所在的多边形单元格,并将其作为目标单元格;

    循环中止判断单元,用于执行如下步骤,直到目标线段与目标单元格不存在相交
    点、或者不存在与所述目标单元格相邻的多边形单元格为止,其中,所述目标线段为所述移
    动路径的起点和终点的连线:

    相交点判断单元,用于根据所述目标线段的起点坐标、终点坐标和所述目标单元
    格的顶点数据判断所述目标线段和所述目标单元格是否存在相交点,若不存在相交点时,
    则将所述目标线段作为所述移动路径;当存在相交点时,则将所述目标线段的起点和所述
    相交点的连线作为行走路段;

    相邻多边形判断单元,用于根据所述目标单元格的相邻多边形的标识数据判断是
    否存在与所述目标单元格相邻的多边形单元格,若是,则将所述待寻路径的起点更新为所
    述相交点、将所述目标单元格更新为与所述目标单元格相邻的多边形单元格;若否,则将获
    取到的至少一个行走路段作为所述移动路径。

    进一步的,所述多边形单元格包括规则多边形单元格和不规则多边形单元格。

    本实施例的技术方案,根据游戏玩家发出移动路径的寻找指令中的起点坐标、终
    点坐标和预存的可行走区域数据确定移动路径,解决现有的寻路算法中,计算路径碰撞点
    的性能较低的问题。不仅提高了计算路径碰撞点的性能,而且利用预存可行走区域数据有
    效减少查找的多边形数据,从而减少了动态寻路的计算量,进而快速高效的得到游戏角色
    的移动路径。

    本发明实施例所提供的游戏寻路装置可以用于执行本发明实施例所提供的游戏
    寻路方法,具备相应的功能和有益效果。未在本实施例中详尽描述的技术细节,可参见本发
    明任意实施例提供的游戏寻路方法。

    注意,上述仅为本发明的较佳实施例及所运用技术原理。本领域技术人员会理解,
    本发明不限于这里所述的特定实施例,对本领域技术人员来说能够进行各种明显的变化、
    重新调整和替代而不会脱离本发明的?;し段?。因此,虽然通过以上实施例对本发明进行
    了较为详细的说明,但是本发明不仅仅限于以上实施例,在不脱离本发明构思的情况下,还
    可以包括更多其他等效实施例,而本发明的范围由所附的权利要求范围决定。

    关于本文
    本文标题:一种游戏寻路方法和装置.pdf
    链接地址://www.4mum.com.cn/p-6038407.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
  • 2018香港一波中特最准 法甲赛程表20162017 福利彩票网站申请 pk10单双大小历史记录 码报资料2018生肖 时时彩组三历史最大遗漏多少期 浙江飞鱼彩票走势图 赌博线上娱乐平台出租 kk棋牌下载安装 江西多乐彩软件 皇朝国际娱乐会所 黑龙江省两家福利彩票投注站之间的距离至少应相隔多少米 河北11选5走势图号码 福彩3d开奖号码 888电玩城棋牌 黑龙江十一选五开奖走势图