Windows游戏编程 第七章

《Windows游戏编程 第七章》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、•297•第7章寻路算法第7章寻路算法在玩角色扮演或者即时战略游戏中，会经常做这样一件事情：将所控制的一个或者多个角色移动到指定的地点；而不管指定的地点在哪儿，只要它能够到达，角色都会准确并且以最佳的方式走到该地点。玩者是不会理会角色是如何到达目的地的。对于编代码的，就得想方设法把玩者所控制的角色送到目的点。这些送角色到目的点的方法，被统称为“寻路算法”。本书要设计的游戏是角色扮演类，当然会涉及到寻路算法。本章就来详细地介绍寻路算法。7.1A-Star寻路算法A-Star算法是很著名的一个寻路算法

2、。它把地面分为一个一个相同大小的方块(有的是六边形或者其他)，角色是踏着这些方块行走的，即角色的步长是以方块为单位的。如果角色的步长是一个方块，则它所站在的方块的四周有八个方块。角色要走，只能走这八个方块之一(如图7-1所示)。图7-1方块的四周方块如何选择这八个方块，关系到寻路的效率。有一种很笨的但很容易理解的方法：对这八个方块，每个都选择一次(即每个都走一次)，选择后同样采取这样的方法选择八个方块。则几乎会搜遍整个场景。这样的效率显然是非常低的。本节将根据A-Star算法的基本思想讨论采用什么

3、样的方式搜索方块。7.1.1模仿人类的搜索角色或者怪物在场景中搜索路径，除了可以知道周围是否有障碍以及目的点在什么方向外，没有任何可以利用的条件。这类似于人处于一个漆黑的洞中，想要寻找洞口出来一样。但有一点是不同的：角色可以知道目的地在什么方向，而人不知道洞口在什么方向。•297•第7章寻路算法为了更好地说明，假设人知道洞口在什么方向。则，人是这样搜索出路的：因为什么都看不到，人会用手触摸墙壁。这就存在两个搜索方向，一个是向右，另一个是向左。先以向右的方向搜索，即沿着洞壁从左到右的方向前进。前进的

4、目的是寻找洞口。当人朝着洞口的方向没有墙壁挡住时，比较积极的做法是：朝着洞口的方向前进，直到遇到墙壁，再沿着墙壁以从左到右的方向搜索前进；比较消极的做法是：不朝着洞口的方向前进，而继续沿着墙壁搜索前进。人可以简单地分为，求功心切的或者积极的人和远见的或者沉稳的人。求功心切的人，一旦遇到任何可能的情况，会做出很大的或者积极的反应；所以，当他朝着洞口的方向没有墙壁挡住时，他会向着洞口的方向前进。沉稳的人处理突如其来的事件是这样的：先思考可能是什么原因，如果不是很重大的事，他会按照自己原来考虑到的方式做

5、事；所以，当这种人朝着洞口的方向没有墙壁挡住时，他会继续沿着墙壁搜索前进，他相信墙壁与洞口是相连着的。沉稳的人的搜索方式称为“吸附式”搜索，求功心切的人的搜索方式称为“半吸附式”搜索。如图7-2和7-3表示了这两种搜索方式，其中虚线表示方向，实线表示搜索路径。图7-2吸附式搜索图7-3半吸附式搜索如果在搜索过的墙壁上作记号，以后遇到这些记号，则说明回到了原来的位置(即兜了一圈)。像图7-3的半吸附式搜索，到最后这个人将会见到他所作的记号，即他的第一次尝试没有找到洞口。在图7-2和图7-3的洞中，吸

6、附式显得比半吸附式有更高的优越性。而洞的墙壁形状是千奇百怪的。如图7-4和图7-5所示，这时半吸附式搜索比吸附式搜索更有优越性。图7-4吸附式搜索存在的缺陷图7-5半吸附式的优越性•297•第7章寻路算法从图7-2到图7-5中，可以看出吸附式搜索与半吸附式搜索各有所长。如果将两者结合起来使用，将是很完美的一个搜索方法。可以这样做：当使用吸附式方法搜索时得到的结果是兜了一圈时，则改用半吸附式搜索；当采用半吸附式搜索时，如遇到了新的墙壁(即当人朝着洞口的方向没有墙壁挡住时，向着洞口方向前进再一次遇到的

7、墙壁)，则采用吸附式搜索；如此循环；所以，吸附式搜索是主要的搜索过程，半吸附式搜索是为了跨越到新的墙壁进行吸附式搜索。以这样的方式结合，能够解决几乎所有可能出现的情况。之所以说它是“几乎”是因为搜索的步数是有限制的。当搜索的步数超出了上限，且没有找到洞口时，将被认为是无法到达洞口。7.1.2地形的表示现实中，人会按照7.1.1小节所介绍的方式从漆黑的洞中搜索出路。与此类似的游戏当中的角色，也应该根据人的这些方式搜索找到目的点。洞里的墙壁就相当于场景中的障碍，洞口相当于角色的目的点。不同的是，为了知

8、道什么是障碍，和减少搜索时间，游戏程序把场景分为相同大小的方块；而洞的地面是连续的。当场景中某处的地形是不可逾越的高山、河流等时，那么此处的方块的属性是障碍属性。可以建立一个全局WORD型地形数组。这个数组的元素个数正好是场景的方块个数，每个元素的值就代表着对应方块的地形，即这些元素与划分好的场景中的方块是一一对应的。所以，以后提到“地形数组的元素”就等于提到“场景中的方块”。以这样的方式为场景中的方块指定属性值：把可行走地形的方块的值定义为0，障碍属性的方块的值定义为非零值。7.