一种寻路验证方法及装置的制作方法
专利名称：一种寻路验证方法及装置的制作方法
技术领域：
本发明涉及寻路技术，尤指一种寻路验证方法及装置。
背景技术：
在游戏中，寻路算法通常采取一种简化的方法，将地图按一定的间隔进行横纵切害I]，划分为多个格子(Tile)，每个格子有两种状态可行走和不可行走。图I为现有游戏中实现寻路的路径示意图，如图I所示，斜线阴影格子的区域是不可行走的区域，白色格子的区域是可行走的区域。寻路算法(如A*算法)通过一定的计算方式，得到从点A到点B的一条路径，如图中虚线所示的折线；然后对这条折线进行优化，判断出C点是多余的，进而 简化为A直接到B的实线路径。其中，A*(读作A Star)算法是一种常用于在游戏中，计算地图上的一个点到达另外一个点的行走路径的寻路(PathFinding)算法。寻路完成后，客户端将计算出的包含两个点A、B的直线路径发送给服务器，服务器需要验证通过寻路得到的路径能否从A点直接到达B点，传统验证的技术方式是“直线逼近法”验证，即取AB直线上的多个中间点，通过判断中间点是否可行走，进而得出整条直线是否可行走。图2为现有实现验证路径的示意图，如图2所示，在AB直线路径上取C、D两个中间点，比如在AB直连线上，每隔一定距离选取采样点，通常距离为I个格子(Tile)的尺寸。通过判断C、D两点是否可行走，即判断C、D两点是否处于可行走的格子(Tile)中.因为C、D是相邻的格子，所以可以表示C、D之间的任何点都是可行走的，从而得出AB整条路线是否可行走。现有验证路径的算法中，因为C、D的选取过程是根据直线方程来计算出C、D的具体位置，其中涉及了浮点运算、乘除法运算，因此，计算C，D两点的方法比较耗时，直线方程计算涉及大量的乘除法以及浮点运算，对于服务器而言降低了系统性能，而估算法会使得验证结果不准确；而且，随着A，B两点距离的增加，需要验证的中间点数量也随之增多，尤其是在地图较大时，这种长距离的寻路验证严重损害了服务器的负载能力。
发明内容
有鉴于此，本发明的主要目的在于提供一种寻路验证方法及装置，能够大大减少服务器在做路径验证时的时间消耗，而且验证结果准确可靠。为达到上述目的，本发明的技术方案是这样实现的—种寻路验证方法，包括通过扫描及融合获取可行走区域，其中，采用逐层迭代方法实现数据的融合为；在逐级迭代中，记录每个格子所属的区域，以及该区域的起始格子、该区域的大小信息，直至扫描到没有更大的区域存在为止；判断出待验证的路径包含在可行走区域中，验证该路径直接可达。所述逐层迭代包括每次扫描中，查看一个指定尺寸的正方形内的所有格子是否均可行走，如果是，则表示该正方形区域是一个大的可行走区域；所述每个区域记录的信息包括当前正方形的尺寸；正方形的起始格子序号；每次扫描后，得到地图上所有的可行走的指定尺寸的正方形区域；在按照从小尺寸到大尺寸的顺序，对地图进行多次扫描后，逐渐形成一系列可行走的正方形区域，并且，包含在大尺寸正方形中的小正方形被融合掉。所述验证该路径直接可达包括判断出所述待验证的路径的两个端点均处于相同的区域。该方法还包括如果判断出所述待验证的路径的两个端点不同处于相同的区域，进一步通过采样路径验证确定路径AB是否直接可达。一种寻路验证装置，至少包括融合单元，处理单元，其中，融合单元，用于通过扫描及融合获取可行走区域，并将可行走区域信息传递给处 理单元；，其中，采用逐层迭代方法实现数据的融合为；在逐级迭代中，记录每个格子所属的区域，以及该区域的起始格子、该区域的大小信息，直至扫描到没有更大的区域存在为止;处理单元，用于根据接收到的可行走区域信息以及来自客户端的待验证路径信息，在判断待验证的路径包含在可行走区域中，并发出验证该路径是否直接可达的验证结果。从上述本发明提供的技术方案可以看出，包括通过融合获取可行走区域，在判断出需要验证的路径包含在可行走区域中，验证该路径直接可达。本发明方法通过找出大的可行走区域，并判断出待验证的路径的两点同处于该可行走区域中，服务器立刻返回该待验证的路径直接可达的路径验证结果。从本发明方法可见，不再需要验证中间的路径点，这样，大大减少了服务器在做路径验证时的时间消耗，而且验证结果准确可靠。
图I为现有游戏中实现寻路的路径示意图；图2为现有实现验证路径的示意图；图3为本发明实现验证路径的示意图；图4为本发明寻路验证方法的流程图；图5为本发明寻路验证装置的组成结构示意图。
具体实施例方式图3为本发明实现验证路径的示意图，如图3所示，在左边的竖条阴影区域中，包含了 4*4共16个格子，而且各个格子之间是可以相互直接可达的。换句话说，路径AB所在的这个区域是可行走的。因此，如图4所示，本发明寻路验证方法包括步骤400 :通过扫描及融合获取可行走区域。本步骤具体包括采用逐层迭代方法实现数据的融合第一次迭代，按1*1格子的区域大小扫描整张地图；第二次迭代，按2*2格子的区域大小扫描整张地图；第三次迭代，按4*4格子的区域大小扫描整张地图；如此依次进行扫描，并在每个格子的数据块中记录它所属的区域(区域就是大的可行走的正方形，包含多个可行走的格子)，以及区域的起始格子、区域的大小等信息；直至扫描到没有更大的区域存在为止(地图的最大尺寸限制了可扫描的正方形的尺寸，所以从1*1的正方形区域开始，一直扫描到地图最大尺寸的正方形)。上述每次扫描中，都会查看一个指定尺寸的正方形内的所有格子是否均可行走，如果是，则表示这个正方的矩形是一个大的可行走区域。每个区域记录的信息包括当前正方形的尺寸；正方形的起始格子序号。每次扫描后，得到的是地图上所有的可行走的指定尺寸的正方形区域。在按照从小尺寸到大尺寸的顺序，对地图进行 多次扫描后，逐渐形成一系列可行走的正方形区域，这些区域的大小可能不同，并且，包含在大尺寸正方形中的小正方形被融合掉。本步骤中，通过融合多个小的格子，得到一个大的可行走区域的算法，就是数据融
合算法。步骤401 :判断出需要验证的路径包含在可行走区域中，验证该路径直接可达。整个融合过程结束后，每个格子均已记录该格子所属的那个区域。本步骤中，判断路径AB的两个端点均处于相同的区域(按照步骤400，本发明只记录经过融合后可行走的正方形区域，而不可行走的区域不作记录。因此，也只验证AB是否在可行走的区域内)，则可以确定路径AB直接可达。本步骤还包括如果判断出路径AB的两个端点不同处于相同的区域，而中间通过第三个正方形区域连接，那么，路径AB也可能是直接可达的，此时，可以使用最原始的采样判断法来验证是否可达，具体实现属于本领域技术人员的惯用技术手段，这里不再赘述。本发明方法通过逐层迭代式的路径融合后，对每一个小的格子(Tile)，都记录有该格子所处的大区域的位置信息。这样，以定位点A和B是否处于同一个大区域为例来看，首先得到A、B两点所处的小格子，然后根据记录的该小格子所在的大区域信息，很直接地就返回A和B两点是否处于同一个大区域中.而不需要遍历所有的大区域信息后判断A和B是否在大区域中，也是是说，本发明方法降低了运算量.提高了寻路的速度。需要说明的是，本发明数据融合算法不仅可以应用于服务器端的路径验证，同样也适用于客户端的寻路算法。本发明方法通过找出大的可行走区域，并判断出待验证的路径的两点同处于该可行走区域中，服务器立刻返回该待验证的路径直接可达的路径验证结果。从本发明方法可见，不再需要验证中间的路径点，这样，大大减少了服务器在做路径验证时的时间消耗，而且验证结果准确可靠。在面对大地图时，本发明通过融合出一个非常大的可行走区域，这样，区域中的所有点都是可直接到达的，显然大大减少了服务器在做路径验证时的时间消耗。针对本发明方法，还提供一种寻路验证，其组成结构如图5所示，至少包括融合单元，处理单元，其中，融合单元，用于通过融合获取可行走区域，并将可行走区域信息传递给处理单元;处理单元，用于根据接收到的可行走区域信息以及来自客户端的待验证路径信息，判断需要验证的路径是否包含在可行走区域中，并发出验证该路径是否直接可达的验证结果。本发明寻路验证装置可以设置在服务器中，也可以单独作为一验证设备存在。
以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。
权利要求
1.一种寻路验证方法，其特征在于，包括 通过扫描及融合获取可行走区域，其中，采用逐层迭代方法实现数据的融合为；在逐级迭代中，记录每个格子所属的区域，以及该区域的起始格子、该区域的大小信息，直至扫描到没有更大的区域存在为止； 判断出待验证的路径包含在可行走区域中，验证该路径直接可达。
2.根据权利要求I所述的寻路验证方法，其特征在于，所述逐层迭代包括 每次扫描中，查看一个指定尺寸的正方形内的所有格子是否均可行走，如果是，则表示该正方形区域是一个大的可行走区域；所述每个区域记录的信息包括当前正方形的尺寸；正方形的起始格子序号； 每次扫描后，得到地图上所有的可行走的指定尺寸的正方形区域； 在按照从小尺寸到大尺寸的顺序，对地图进行多次扫描后，逐渐形成一系列可行走的正方形区域，并且，包含在大尺寸正方形中的小正方形被融合掉。
3.根据权利要求I所述的寻路验证方法，其特征在于，所述验证该路径直接可达包括判断出所述待验证的路径的两个端点均处于相同的区域。
4.根据权利要求3所述的方法，其特征在于，该方法还包括如果判断出所述待验证的路径的两个端点不同处于相同的区域，进一步通过采样路径验证确定所述待验证的路径是否直接可达。
5.一种寻路验证装置，其特征在于，至少包括融合单元，处理单元，其中， 融合单元，用于通过扫描及融合获取可行走区域，并将可行走区域信息传递给处理单元；其中，采用逐层迭代方法实现数据的融合为；在逐级迭代中，记录每个格子所属的区域，以及该区域的起始格子、该区域的大小信息，直至扫描到没有更大的区域存在为止； 处理单元，用于根据接收到的可行走区域信息以及来自客户端的待验证路径信息，在判断待验证的路径包含在可行走区域中，并发出验证该路径是否直接可达的验证结果。
全文摘要
本发明提供了一种寻路验证方法，包括通过扫描及融合获取可行走区域，再判断出需要验证的路径包含在可行走区域中，从而验证该路径直接可达。本发明方法通过找出大的可行走区域，并判断出待验证的路径的两点同处于该可行走区域中，服务器立刻返回该待验证的路径直接可达的路径验证结果。从本发明方法可见，不再需要验证中间的路径点，这样，大大减少了服务器在做路径验证时的时间消耗，而且验证结果准确可靠。
文档编号G09B29/00GK102800242SQ20111013692
公开日2012年11月28日 申请日期2011年5月25日 优先权日2011年5月25日
发明者张伟 申请人:腾讯科技(深圳)有限公司
技术领域：
本发明涉及寻路技术，尤指一种寻路验证方法及装置。
背景技术：
在游戏中，寻路算法通常采取一种简化的方法，将地图按一定的间隔进行横纵切害I]，划分为多个格子(Tile)，每个格子有两种状态可行走和不可行走。图I为现有游戏中实现寻路的路径示意图，如图I所示，斜线阴影格子的区域是不可行走的区域，白色格子的区域是可行走的区域。寻路算法(如A*算法)通过一定的计算方式，得到从点A到点B的一条路径，如图中虚线所示的折线；然后对这条折线进行优化，判断出C点是多余的，进而 简化为A直接到B的实线路径。其中，A*(读作A Star)算法是一种常用于在游戏中，计算地图上的一个点到达另外一个点的行走路径的寻路(PathFinding)算法。寻路完成后，客户端将计算出的包含两个点A、B的直线路径发送给服务器，服务器需要验证通过寻路得到的路径能否从A点直接到达B点，传统验证的技术方式是“直线逼近法”验证，即取AB直线上的多个中间点，通过判断中间点是否可行走，进而得出整条直线是否可行走。图2为现有实现验证路径的示意图，如图2所示，在AB直线路径上取C、D两个中间点，比如在AB直连线上，每隔一定距离选取采样点，通常距离为I个格子(Tile)的尺寸。通过判断C、D两点是否可行走，即判断C、D两点是否处于可行走的格子(Tile)中.因为C、D是相邻的格子，所以可以表示C、D之间的任何点都是可行走的，从而得出AB整条路线是否可行走。现有验证路径的算法中，因为C、D的选取过程是根据直线方程来计算出C、D的具体位置，其中涉及了浮点运算、乘除法运算，因此，计算C，D两点的方法比较耗时，直线方程计算涉及大量的乘除法以及浮点运算，对于服务器而言降低了系统性能，而估算法会使得验证结果不准确；而且，随着A，B两点距离的增加，需要验证的中间点数量也随之增多，尤其是在地图较大时，这种长距离的寻路验证严重损害了服务器的负载能力。
发明内容
有鉴于此，本发明的主要目的在于提供一种寻路验证方法及装置，能够大大减少服务器在做路径验证时的时间消耗，而且验证结果准确可靠。为达到上述目的，本发明的技术方案是这样实现的—种寻路验证方法，包括通过扫描及融合获取可行走区域，其中，采用逐层迭代方法实现数据的融合为；在逐级迭代中，记录每个格子所属的区域，以及该区域的起始格子、该区域的大小信息，直至扫描到没有更大的区域存在为止；判断出待验证的路径包含在可行走区域中，验证该路径直接可达。所述逐层迭代包括每次扫描中，查看一个指定尺寸的正方形内的所有格子是否均可行走，如果是，则表示该正方形区域是一个大的可行走区域；所述每个区域记录的信息包括当前正方形的尺寸；正方形的起始格子序号；每次扫描后，得到地图上所有的可行走的指定尺寸的正方形区域；在按照从小尺寸到大尺寸的顺序，对地图进行多次扫描后，逐渐形成一系列可行走的正方形区域，并且，包含在大尺寸正方形中的小正方形被融合掉。所述验证该路径直接可达包括判断出所述待验证的路径的两个端点均处于相同的区域。该方法还包括如果判断出所述待验证的路径的两个端点不同处于相同的区域，进一步通过采样路径验证确定路径AB是否直接可达。一种寻路验证装置，至少包括融合单元，处理单元，其中，融合单元，用于通过扫描及融合获取可行走区域，并将可行走区域信息传递给处 理单元；，其中，采用逐层迭代方法实现数据的融合为；在逐级迭代中，记录每个格子所属的区域，以及该区域的起始格子、该区域的大小信息，直至扫描到没有更大的区域存在为止;处理单元，用于根据接收到的可行走区域信息以及来自客户端的待验证路径信息，在判断待验证的路径包含在可行走区域中，并发出验证该路径是否直接可达的验证结果。从上述本发明提供的技术方案可以看出，包括通过融合获取可行走区域，在判断出需要验证的路径包含在可行走区域中，验证该路径直接可达。本发明方法通过找出大的可行走区域，并判断出待验证的路径的两点同处于该可行走区域中，服务器立刻返回该待验证的路径直接可达的路径验证结果。从本发明方法可见，不再需要验证中间的路径点，这样，大大减少了服务器在做路径验证时的时间消耗，而且验证结果准确可靠。
图I为现有游戏中实现寻路的路径示意图；图2为现有实现验证路径的示意图；图3为本发明实现验证路径的示意图；图4为本发明寻路验证方法的流程图；图5为本发明寻路验证装置的组成结构示意图。
具体实施例方式图3为本发明实现验证路径的示意图，如图3所示，在左边的竖条阴影区域中，包含了 4*4共16个格子，而且各个格子之间是可以相互直接可达的。换句话说，路径AB所在的这个区域是可行走的。因此，如图4所示，本发明寻路验证方法包括步骤400 :通过扫描及融合获取可行走区域。本步骤具体包括采用逐层迭代方法实现数据的融合第一次迭代，按1*1格子的区域大小扫描整张地图；第二次迭代，按2*2格子的区域大小扫描整张地图；第三次迭代，按4*4格子的区域大小扫描整张地图；如此依次进行扫描，并在每个格子的数据块中记录它所属的区域(区域就是大的可行走的正方形，包含多个可行走的格子)，以及区域的起始格子、区域的大小等信息；直至扫描到没有更大的区域存在为止(地图的最大尺寸限制了可扫描的正方形的尺寸，所以从1*1的正方形区域开始，一直扫描到地图最大尺寸的正方形)。上述每次扫描中，都会查看一个指定尺寸的正方形内的所有格子是否均可行走，如果是，则表示这个正方的矩形是一个大的可行走区域。每个区域记录的信息包括当前正方形的尺寸；正方形的起始格子序号。每次扫描后，得到的是地图上所有的可行走的指定尺寸的正方形区域。在按照从小尺寸到大尺寸的顺序，对地图进行 多次扫描后，逐渐形成一系列可行走的正方形区域，这些区域的大小可能不同，并且，包含在大尺寸正方形中的小正方形被融合掉。本步骤中，通过融合多个小的格子，得到一个大的可行走区域的算法，就是数据融
合算法。步骤401 :判断出需要验证的路径包含在可行走区域中，验证该路径直接可达。整个融合过程结束后，每个格子均已记录该格子所属的那个区域。本步骤中，判断路径AB的两个端点均处于相同的区域(按照步骤400，本发明只记录经过融合后可行走的正方形区域，而不可行走的区域不作记录。因此，也只验证AB是否在可行走的区域内)，则可以确定路径AB直接可达。本步骤还包括如果判断出路径AB的两个端点不同处于相同的区域，而中间通过第三个正方形区域连接，那么，路径AB也可能是直接可达的，此时，可以使用最原始的采样判断法来验证是否可达，具体实现属于本领域技术人员的惯用技术手段，这里不再赘述。本发明方法通过逐层迭代式的路径融合后，对每一个小的格子(Tile)，都记录有该格子所处的大区域的位置信息。这样，以定位点A和B是否处于同一个大区域为例来看，首先得到A、B两点所处的小格子，然后根据记录的该小格子所在的大区域信息，很直接地就返回A和B两点是否处于同一个大区域中.而不需要遍历所有的大区域信息后判断A和B是否在大区域中，也是是说，本发明方法降低了运算量.提高了寻路的速度。需要说明的是，本发明数据融合算法不仅可以应用于服务器端的路径验证，同样也适用于客户端的寻路算法。本发明方法通过找出大的可行走区域，并判断出待验证的路径的两点同处于该可行走区域中，服务器立刻返回该待验证的路径直接可达的路径验证结果。从本发明方法可见，不再需要验证中间的路径点，这样，大大减少了服务器在做路径验证时的时间消耗，而且验证结果准确可靠。在面对大地图时，本发明通过融合出一个非常大的可行走区域，这样，区域中的所有点都是可直接到达的，显然大大减少了服务器在做路径验证时的时间消耗。针对本发明方法，还提供一种寻路验证，其组成结构如图5所示，至少包括融合单元，处理单元，其中，融合单元，用于通过融合获取可行走区域，并将可行走区域信息传递给处理单元;处理单元，用于根据接收到的可行走区域信息以及来自客户端的待验证路径信息，判断需要验证的路径是否包含在可行走区域中，并发出验证该路径是否直接可达的验证结果。本发明寻路验证装置可以设置在服务器中，也可以单独作为一验证设备存在。
以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。
权利要求
1.一种寻路验证方法，其特征在于，包括 通过扫描及融合获取可行走区域，其中，采用逐层迭代方法实现数据的融合为；在逐级迭代中，记录每个格子所属的区域，以及该区域的起始格子、该区域的大小信息，直至扫描到没有更大的区域存在为止； 判断出待验证的路径包含在可行走区域中，验证该路径直接可达。
2.根据权利要求I所述的寻路验证方法，其特征在于，所述逐层迭代包括 每次扫描中，查看一个指定尺寸的正方形内的所有格子是否均可行走，如果是，则表示该正方形区域是一个大的可行走区域；所述每个区域记录的信息包括当前正方形的尺寸；正方形的起始格子序号； 每次扫描后，得到地图上所有的可行走的指定尺寸的正方形区域； 在按照从小尺寸到大尺寸的顺序，对地图进行多次扫描后，逐渐形成一系列可行走的正方形区域，并且，包含在大尺寸正方形中的小正方形被融合掉。
3.根据权利要求I所述的寻路验证方法，其特征在于，所述验证该路径直接可达包括判断出所述待验证的路径的两个端点均处于相同的区域。
4.根据权利要求3所述的方法，其特征在于，该方法还包括如果判断出所述待验证的路径的两个端点不同处于相同的区域，进一步通过采样路径验证确定所述待验证的路径是否直接可达。
5.一种寻路验证装置，其特征在于，至少包括融合单元，处理单元，其中， 融合单元，用于通过扫描及融合获取可行走区域，并将可行走区域信息传递给处理单元；其中，采用逐层迭代方法实现数据的融合为；在逐级迭代中，记录每个格子所属的区域，以及该区域的起始格子、该区域的大小信息，直至扫描到没有更大的区域存在为止； 处理单元，用于根据接收到的可行走区域信息以及来自客户端的待验证路径信息，在判断待验证的路径包含在可行走区域中，并发出验证该路径是否直接可达的验证结果。
全文摘要
本发明提供了一种寻路验证方法，包括通过扫描及融合获取可行走区域，再判断出需要验证的路径包含在可行走区域中，从而验证该路径直接可达。本发明方法通过找出大的可行走区域，并判断出待验证的路径的两点同处于该可行走区域中，服务器立刻返回该待验证的路径直接可达的路径验证结果。从本发明方法可见，不再需要验证中间的路径点，这样，大大减少了服务器在做路径验证时的时间消耗，而且验证结果准确可靠。
文档编号G09B29/00GK102800242SQ20111013692
公开日2012年11月28日 申请日期2011年5月25日 优先权日2011年5月25日
发明者张伟 申请人:腾讯科技(深圳)有限公司
最新回复(0)