从人类的思维方式中寻找启示：宏观——微观寻径算法（二）

1、从人类的思维方式中寻找启示：宏观微观寻径算法二一TECHZONE技道馆口口口口口口从人类的思维方式中寻找启示宏观文/华南理工大学张颖鹏微观寻径算法遗留问题及其解决方案在六月?游戏创造?发表的文章中,笔者简单地概述了宏观微观算法应用于游戏寻径的整个流程,并留下了个关系到算法是否有效的问题:当一个分块本身并不连通的时候(从同一个分块上面的某一个非障碍物点到同一个分块上面另外一个非障碍物点不存在一条仅仅经过该分块的路径),算法会发生错误吗?如果发生错误,该如何解决?下面我们先来答复第一个问题:会发生错误吗?我们观察下面的图片,按照上一篇所介绍测试两分块联通的方法,分块A和分块B是联通的(因为两个格子

2、接壤的地方并没有障碍物)这会导致什么问题呢?假设我们需要搜索图中s点到t点的路径.从宏观上来看(就是大的分块)是相通的,但从微观上看,实际它们之间并不存在路径现在我们回想一下整个算法的流程,这样的的情况在宏观上搜索出的路径会因为这条路径经过一些本身不联通的格子而可能导致微观上搜索的时候无路可走,最终无法正确找出路.:一_l_.lll】-一.l_lll_|_-,:.68游髓创造2006年12月号一_径.我们不可能要求每一个格子自身是联通的,一旦存在不联通的格子,这个算法就存在潜在性的错误可能.那么我们能够解决这个问题吗?产生这个问题的原因是格子本身的不联通导致分块违反了设计这个算法的原那么一一周

3、一个分块里面的点相互之间的距离是很短的.也就是说我们不能把同一个格子里面的点笼统地看作同一类.如果改变一下这个分类的基准,也许问题就迎刃而解了.再来看回之前提出的那个问题,如果我们把原来的分块A和B分成A1,A2,BI,B2四个分块或者说分成四类的话.A1和A2是不联通的,尽管A2和B1是联通的,但是从宏观上来看,AI跟B1还是不联通的,所以不存在从s到t的路径.同样道理,Al和P,2,A2和B2之间也都不存在路径.这样就符合实际的情况了.那么我们的结论是什么呢?为了让大家逐步理解这个宏观微观算法,在上一篇文章里面所用的分块方法是不严谨的.而严谨的分块方法应该是以格子的一个联通局部作为单位,而

4、不一定是用整个格子作为分块单位.(当然,如果整个格子内部的点都联通,那么这个格子就是一个分块分块小的时候,大局部情况下整个格子就是一个分块.)一些大的格子可能由很多个分块组成.如图o3中红框标示的格子有4个分块,图O4中红框标示的格子有5个分块(蓝色的是障碍).这种分块方式就符合同一个分块里面的点之间的距离相对短的前提假设,让算法不会Hj现致命错误.那么接着就会出现另一个问题:我lItn何得知一个格子里面有多少个分块呢?这就要用到广度优先搜索算法,(有些书上叫墨滴算法,笔者比拟喜欢称其为水波算法,因为算法演示的时候太像水波往扩散了.)通过这个算法,我们就可以从一个点出发,把所有与之联通的点找出

5、来,从而把一个格子分成相互联通的几个分块.接着延续上一篇文章所介绍的算法流程,分块后,测试所有分块之间的连通性(当然,同一个格了里面的分块之间的连通性不必测试)最后同样得到一个表,但是这个表的根本单位不是格子而是一个格子里面相互不联通的一个个区域.至此,整个预处理过程结束.为分块的根本单位改变了,所以寻径的过程也要做相应的小改动一对某一点位置的判断要具体到哪个格子TECHZONE技道馆一的哪个分块.通过这一系列的改良后,整个宏观一微观算法就可以无错地投人使用了.算法的优点,缺点及其改良方向首先要说明的是,笔者在这里进行算法比拟的对象主要是广度优先搜索与及AStar等传统的寻径算法.而对于近年来

6、研究得比拟多的导航点法,分解矩形法等,由于只是表面_卜了解过,井没有用程序实现并测试过,所以只能得到猜测性的结论.算法的优点1.这个算法最大的优点就是快,节约CPU资源.在足够大的地图上,总寻径时间比AStar和广度优先算法等要快两个数量级以上.2.这个算法另外一个特点就是可以把寻径开销分期付款因为通过宏观搜索后,智能体就已经可以知道下一个要走的分块是哪?个,那么仅仅搜索出在本分块里面的微观路径就可以了,等到走到下一个分块,再搜索一个分块里面的微观路径,这样搜索微观路径的时间就被分摊了.这使得过去即时战略游戏运行中的为难场景不会出现:没有大量单位同时寻径的时候游戏运行得很顺畅,一旦大量单位同时

7、寻径的时候,游戏要.住一段时间.这种分摊有效地解决了CPU运算峰值的问题.这个算法本身的总寻径时间就已经很短,加上这些时间可以分摊,迭加起来,这个算法要比传统算法快很多个数量级.3.而且,分摊的不单单是搜索时间,还有储存整条路径的内存(把内存的需求分摊r,就相当于节约了大量内存),对于单位数目庞大的即时战略游戏来说,每一个智能体都要存储一条很长然美观.6.该算法的颓处理还将会为其它的处理提供一个基础,比方游戏的战略据点分析,势力范围分析等与地理状况有关的处理.算法的缺点1.正如算法的最大优点是快,而算法的最大缺点是复杂.算法的复杂表现在几个方而:寻径算法本身由于涉及到递j的预处理过程和递归的搜

8、索过程,算法的设计非常复杂;附带的,寻径过程对于动态障碍物的处理也比拟复杂,删EC畦舢_DECEMBER2006一TECHZONE技道馆在程序实现过程中对于潜伏bug的修改也比拟复杂2.这个算祛不能保证搜索得出的是严格意义上的最短路径.这一点在游戏里面的应用并不重要,甚至在其它实际应用上也并不特别重要.怛从学术角度来说,这一点还是值得提一提,这个算法搜索出最短路径是基于下面这个假设的:微观上的最短路径从宏观上表现出来的也是最短路径.也就是说微观上的最短路径(实际的最短路径),属于左观上的最短路径.而如果币乎台这个假设,那么找出来的路径将不是最短路径极端的情况中.也许找出来的路径比最短路径长许多

9、同时,这个算i击还符合另一条规律:宏观分块越大,找到最短路径偏差褥越厉害.当然这个问题可以很灵活地被解挑的.在此暂不展开讨论.3.如果游戏地图变化频繁.而且变化剧烈,那幺这个算i击也是不适用的因为预处理过程相对单次搜索过程来说是比拟长的f在IO00x1000的地图,三层分析大概要JL十毫秒).而每次地图的巨大变动都需要重新预处理(对人类来说.在这种情况下搜索路径也会有类似的感觉:由于地图变化频繁.过去建立起来的宏观感觉马上就会被打破,而需要重新建立这种感觉).其它问题这个算法的实际应用过程中还将会遇到一些问题,这里笔者简单的说明一下.1.如何处理寻径过程中的动态障碍物?这里党把动态障碍物分成两

10、种:第一种.相对活泼的临时障碍,比方即时战略中的可移动单位.对于这种障碍物,我们进行宏观寻径的过程中大可以当其不存在,也许当走到它旁边的时候它已经早就离开了.尽管还在,也只需要做一个简单的绕开算法就行.第二种,相对固定的长期障碍,比方即时战略里面的不可移动单位,建筑等.它们跟地图上面的固定障碍一样.存在的时间比拟长.我们如何才能把它们当作地图上的障碍一样去处理呢?最笨的方法就是重新预处理一迪建立新的分块连接关系表但事实上不需要这幺做的,只要从新加人的单位所在的微理分块到宏观分块更新一次连接关系表就可以r(除非那个固定单位是建立在战略上的咽喉之地,否那么链接表的改动也是非常有限的)2.如何实现八

11、方向行走?上面介绍的宏现微观算_=击是基于四方向行走的.而大局部即时战略游戏都是基于八方向行走的.那幺这十算法能够实现八方向行走I马?完垒可以,但是需要更加复杂的算法改动这些改动包括使用AStm算法作为每一层的搜索算法3.这个算法能尊实现在带权网格地田上的路径攫素吗?带权网格地图就是行走单位走不同的格子的行走速度可能是不同的.理论上,宏观微现算法解决这个问题是困难的,因为带权值的网格地图违反了一个原那么:同一个蕾毪一蕾2006年12月每分块里面的点相互之间的距离是很蠕的这里说的距离不能理解为绝对距离,应该理解为走那条路径所需要的时间是很少的.但是如果郝个格子挫设置为时间开销特别多,那幺整现搜索

12、啦许会误导了微观上的搜索从而不能搜索出一条严格上最短的路径但是由于游戏里面或者其它很多应用里面对最短的要求并不严格.所以进行?些改良之后还是可以满足这方面的需求.4.分块一定是正方格子吗?从应用的角度来说,这个问题本身并不重要,不过它关系到这个算法的本质.就像前面所不断提到的:同一个分块里面的点相互之间的距离是很短的.这是这个算法能蜉正确运行的原刑还有另外一个原那么就是:同一等级的分块大小接近(这两个原那么从更抽象的层次加以描述是这样的:所有同一类的成员都应该是相似的,所有同等级的类所囊括的范围也应该是相似的).所以只要符台这两个原那么的所有分块方案都是可行的.比方圆,甚至是不规那么的图形(事

13、实上,经过本文开头时所介绍的改良方法后的分块方法就是不规那么图形)这叉引起另外一个问题.分块边缘的点一定耍严格地分到某一分块吗?达也是不一定的,建又涉及到另外一个宏观一微观算法的思想:从较微观的角度去考察一个相对宏观的问题时可以忽略分类的精确性也许到现在有些人还不明白为什么宏观撇观算法能够从某些方面超越久经研究的传统算法.笔者总结了一下,首先是思想上的优势:宏观激现算法是从一个恰当的微观层次去解决一个相对宏观的问题,而传统的算法往往从最为微观的层次去解决所有屡次的问题(虽然有点玄.但是如果读者朋友仔细琢磨的话,肯定能琢睁出这种味遘来).具体在算法实现时候的优势是:第一,把每次搜索过程中都可能要计算的任务先计算了.第二,舍弃过度精确