Windows游戏编程 第七章.doc

297 第7章 寻 路 算 法第7章 寻 路 算 法在玩角色扮演或者即时战略游戏中，会经常做这样一件事情：将所控制的一个或者多个角色移动到指定的地点；而不管指定的地点在哪儿，只要它能够到达，角色都会准确并且以最佳的方式走到该地点。玩者是不会理会角色是如何到达目的地的。对于编代码的，就得想方设法把玩者所控制的角色送到目的点。这些送角色到目的点的方法，被统称为“寻路算法”。本书要设计的游戏是角色扮演类，当然会涉及到寻路算法。本章就来详细地介绍寻路算法。7.1 A-Star寻路算法A-Star算法是很著名的一个寻路算法。它把地面分为一个一个相同大小的方块(有的是六边形或者其他)，角色是踏着这些方块行走的，即角色的步长是以方块为单位的。如果角色的步长是一个方块，则它所站在的方块的四周有八个方块。角色要走，只能走这八个方块之一(如图7-1所示)。图7-1 方块的四周方块如何选择这八个方块，关系到寻路的效率。有一种很笨的但很容易理解的方法：对这八个方块，每个都选择一次(即每个都走一次)，选择后同样采取这样的方法选择八个方块。则几乎会搜遍整个场景。这样的效率显然是非常低的。本节将根据A-Star算法的基本思想讨论采用什么样的方式搜索方块。7.1.1 模仿人类的搜索角色或者怪物在场景中搜索路径，除了可以知道周围是否有障碍以及目的点在什么方向外，没有任何可以利用的条件。这类似于人处于一个漆黑的洞中，想要寻找洞口出来一样。但有一点是不同的：角色可以知道目的地在什么方向，而人不知道洞口在什么方向。为了更好地说明，假设人知道洞口在什么方向。则，人是这样搜索出路的：因为什么都看不到，人会用手触摸墙壁。这就存在两个搜索方向，一个是向右，另一个是向左。先以向右的方向搜索，即沿着洞壁从左到右的方向前进。前进的目的是寻找洞口。当人朝着洞口的方向没有墙壁挡住时，比较积极的做法是：朝着洞口的方向前进，直到遇到墙壁，再沿着墙壁以从左到右的方向搜索前进；比较消极的做法是：不朝着洞口的方向前进，而继续沿着墙壁搜索前进。人可以简单地分为，求功心切的或者积极的人和远见的或者沉稳的人。求功心切的人，一旦遇到任何可能的情况，会做出很大的或者积极的反应；所以，当他朝着洞口的方向没有墙壁挡住时，他会向着洞口的方向前进。沉稳的人处理突如其来的事件是这样的：先思考可能是什么原因，如果不是很重大的事，他会按照自己原来考虑到的方式做事；所以，当这种人朝着洞口的方向没有墙壁挡住时，他会继续沿着墙壁搜索前进，他相信墙壁与洞口是相连着的。沉稳的人的搜索方式称为“吸附式”搜索，求功心切的人的搜索方式称为“半吸附式”搜索。如图7-2和7-3表示了这两种搜索方式，其中虚线表示方向，实线表示搜索路径。 图7-2 吸附式搜索 图7-3 半吸附式搜索如果在搜索过的墙壁上作记号，以后遇到这些记号，则说明回到了原来的位置(即兜了一圈)。像图7-3的半吸附式搜索，到最后这个人将会见到他所作的记号，即他的第一次尝试没有找到洞口。在图7-2和图7-3的洞中，吸附式显得比半吸附式有更高的优越性。而洞的墙壁形状是千奇百怪的。如图7-4和图7-5所示，这时半吸附式搜索比吸附式搜索更有优越性。 图7-4 吸附式搜索存在的缺陷 图 7-5 半吸附式的优越性从图7-2到图7-5中，可以看出吸附式搜索与半吸附式搜索各有所长。如果将两者结合起来使用，将是很完美的一个搜索方法。可以这样做：当使用吸附式方法搜索时得到的结果是兜了一圈时，则改用半吸附式搜索；当采用半吸附式搜索时，如遇到了新的墙壁(即当人朝着洞口的方向没有墙壁挡住时，向着洞口方向前进再一次遇到的墙壁)，则采用吸附式搜索；如此循环；所以，吸附式搜索是主要的搜索过程，半吸附式搜索是为了跨越到新的墙壁进行吸附式搜索。以这样的方式结合，能够解决几乎所有可能出现的情况。之所以说它是“几乎”是因为搜索的步数是有限制的。当搜索的步数超出了上限，且没有找到洞口时，将被认为是无法到达洞口。7.1.2 地形的表示现实中，人会按照7.1.1小节所介绍的方式从漆黑的洞中搜索出路。与此类似的游戏当中的角色，也应该根据人的这些方式搜索找到目的点。洞里的墙壁就相当于场景中的障碍，洞口相当于角色的目的点。不同的是，为了知道什么是障碍，和减少搜索时间，游戏程序把场景分为相同大小的方块；而洞的地面是连续的。当场景中某处的地形是不可逾越的高山、河流等时，那么此处的方块的属性是障碍属性。可以建立一个全局WORD型地形数组。这个数组的元素个数正好是场景的方块个数，每个元素的值就代表着对应方块的地形，即这些元素与划分好的场景中的方块是一一对应的。所以，以后提到“地形数组的元素”就等于提到“场景中的方块” 。以这样的方式为场景中的方块指定属性值：把可行走地形的方块的值定义为0，障碍属性的方块的值定义为非零值。7.1.3 两种搜索方式的模拟场景中除了场景边界上的方块，每个方块都有这样的一个属性：方块的周围有且只有八个方块(如图7-1所示)。现在给这八个方块编号。编号的方式是从左上角开始，按顺时针方向从0依次递增到7(如图7-6所示)。搜索时遇到障碍，则说明八个方块中的一个或者几个的属性将是障碍属性。以顺时针方向或者逆时针方向循环八个方块，如果循环到的方块是非障碍属性的方块，则移动到这个方块；同时以同样的方式搜索下一方块。从哪一个方块开始循环，这得根据是否是第一次在障碍边缘搜索；如果是第一次在障碍边缘搜索，则把“八个方块”中最靠近目的点的方块作为开始循环的方块；不是第一次在障碍边缘搜索，则以关联方块作为开始循环的方块。关联方块是这样定义的：在以指定的方向循环“八个方块”时，如果得到的方块是非障碍属性的方块，就下移；则这个作为下移的方块的前一个循环方块称为关联方块。由此可知，顺时针方向循环和逆时针方向循环，对应于现实中的人搜索出洞的两个方向(向右和向左)。如图7-7所示的地形，下面将按上述的方法搜索从起点目的点的路径。首先，起点朝着目的点的方向没有障碍，也可以这么解释：起点的“八个方块”中，靠近目的点的方块不是障碍属性的方块。所以，可以直接朝着目的点的方向前进一个方块，假设这个方块是A。移动到方块A后，变成如图7-8所示的路径。 图7-6 八个方块的编号 图7-7 例子得到方块A后，检测其是否是障碍。可以看出它不是障碍。所以可以继续朝着目的点直线前进一方块。得到方块B，如图7-9所示。 图 7-8 第一步搜索 图7-9 第二步搜索得到方块B后，检测其属性，为非障碍属性。以方块B作为起点，朝着目的点方向直线前进。显然，得到的方块是障碍属性的。所以，此时方块B处于障碍的边缘。以吸附式搜索路径。因为是第一次在障碍的边缘搜索路径，所以以B方块的“八个方块”中最靠近目的点的方块作为关联方块。如图7-10中的方块0就是方块B的“八个方块”中最靠近目的点的方块，即关联方块；其中方块4与方块A是重叠的。以方块B的关联方块(图7-10中的方块0)作为开始方块，以顺时针方向(也可以以逆时针方向)循环方块B的“八个方块”，得到的第1个非障碍属性的方块是方块1，将其标号为C，则方块C的关联方块是方块1的上一循环方块，即方块0，将其标号为G0。则得到的路径如图7-11所示，其中方块G0与方块7是重叠的，方块B与方块5是重叠的。 图 7-10 方块B的“八个方块” 图7-11 第三步搜索同样以方块C的关联方块G0作为开始方块，以顺时针方向循环方块C的“八个方块”。则得到的第1个非障碍方块是图7-11中的方块2，将其标号为D，方块2的前一个循环方块是方块1；所以，方块D的关联方块是方块1，将其标号为G1。则路径变为如图7-12所示，其中方块7与方块G1重叠，方块6与方块C重叠以同样的方式搜索，将得到方块E、F和G，如图7-13所示。 图 7-12 第四步搜索 图 7-13 第七步搜索如果是吸附式搜索，则得到的路径是闭合的如图7-14。如果是半吸附式搜索，则得到G方块后，就意味着可以直线到达目的点，如图7-15所示。 图7-14 吸附式的路径 图7-15 半吸附式的路径对于图7-14的路径是这样得到的：当搜索到方块R后，下一个方块就是以前搜索过的方块B，所以兜了一圈，找不到到达目的点的路径。而图7-15中，当搜索到方块G时，方块G到目的点之间没有障碍方块，可以直线到达目的点，所以得出了方块H、I和J。以上是以顺时针方向找到的路径。也可以以逆时针方向寻找路径，道理是一样的。通常两个方向都搜索，然后比较这两个方向的路径，取较短的路径。如果场景中只有一个怪物和一个角色，则以吸附式搜索和半吸附式搜索的结合搜索路径，不会耗费很多时间。而通常情况下，场景中的怪物是很多的。每个怪物都要进行一次寻路搜索则耗费的时间是很多的。所以，可以只采用吸附式或者半吸附式搜索。当只采用一种搜索方式时，到达目的点的可能性将降低。因为，当第一次搜索不到(兜了一圈)时，将停止搜索。此时对于吸附式搜索将抛弃闭合的路径，只采用第一段的直线路径。对于半吸附式，搜索到多少步的路径就行走多少步。经过多次验证，得出半吸附式搜索的性能与效率是最好的。同时它到达目的点的可能性也是很高的；虽然在图7-3所示的半吸附式没有搜索到目的点，但是它只是按顺时针方向搜索的，如果按逆时针方向搜索则可以到达目的点；所以应该采取两个方向都搜索的做法；再者，这次的搜索没有到达目的点，走完这次的路径，再进行搜索时，就不一定不能到达目的点了；所以，半吸附式搜索到达目的点的可能性很高。而吸附式搜索只能进行一次搜索，即这次搜索得到的路径是闭合的，下一次的搜索肯定也是闭合的；所以没有必要进行多次搜索。因此，在怪物比较多的情况下，可以只采用半吸附式搜索路径。7.2 生 成 算 法寻路算法是游戏算法中很重要的一个算法，为了更好地运用此算法，应该将它封装起来。下面的CGetPath类，包含了A-STAR寻路算法的两种搜索方式以及它们的结合。7.2.1 建立CGetPath类CGetPath类的声明文件CGetPath.h的代码如下：/*-| CGetPath.h| A-Star寻路算法相关处理功能| (c) mochsh,2004-*/#include /路径结构声明typedef struct PATH POINT Pos; PATH * before; PATH * next; PATH, * LPPATH;class CGetPathprotected: LONG lSquareC;/格子的宽度 LONG lHarfSquC;/格子宽度的一半 LPWORD Square;/场景地形数组首地址 LONG lMaxStep;/试探的最大步数 LONG lCount;/当前搜索的步数 LONG SceneW;/场景的宽度(像素单位) LONG SceSquareW;/场景的宽度(方块单位) LONG SceneH;/场景的高度(像素单位) LONG SceSquareH;/场景的高度(方块单位) RECT MonsterRect;/怪物激活区的大小public: /构造函数 CGetPath( LONG SquareC, LPVOID lpSquare, DWORD SceW, DWORD SceH, RECT MonsterRt ); CGetPath( void ); /变量设置 void Set_lSquareC( LONG SquareC ) lSquareC=SquareC; lHarfSquC=lSquareC/2; LONG w=MonsterRect.right-MonsterRect.left; LONG h=MonsterRect.bottom-MonsterRect.top; lMaxStep = (w/lSquareC)*(h/lSquareC); SceSquareW=SceneW/lSquareC; SceSquareH=SceneH/lSquareC; void Set_Square( LPVOID lpSquare ) Square=(LPWORD)lpSquare; void Set_SceneW( LONG SceW ) SceneW=SceW; SceSquareW=SceneW/lSquareC; void Set_SceneH( LONG SceH ) SceneH=SceH; SceSquareH=SceneH/lSquareC; void Set_MonsterRect(RECT rect) MonsterRect=rect; LONG w=MonsterRect.right-MonsterRect.left; LONG h=MonsterRect.bottom-MonsterRect.top; lMaxStep = (w/lSquareC)*(h/lSquareC); /功能函数 LONG MakeSquare(LONG y, LONG x); LONG GetSquareFromPos( POINT ); POINT GetPosFromSquare( LONG ); LONG Distance( POINT StartPos, POINT DestPos ); LONG Distance( LONG StartSquare, LONG DestSquare ); POINT AdjustPos( POINT Pos ); LPLONG GetAroundSquare( POINT Pos ); LONG GetNearSquare( POINT Pos, POINT DestPos ); BOOL Movable( POINT StartPos, POINT DestPos,LPPATH &lpPath, BOOL bFlags ); LPPATH GetLastMember( LPPATH lpPath ); BOOL IsWalkableSquare( LONG lSquare ); LONG DoFor( LONG lIndex, LONG lFlags ); POINT GetNextPos( POINT p1,LPLONG lpRelateSqu,LONG lFlags ); BOOL IsOldPos( POINT NextPos, LPPATH lpPath ); void DeletePath( LPPATH lpPath ); BOOL ArcSearch( POINT StartPos, POINT DestPos, LPPATH &lpPath, LPPATH lpOldPath, LONG lFlags ); BOOL RoundSearch( POINT StartPos,POINT DestPos, LPPATH &lpPath,LONG lFlags ); LPPATH MethodOne( POINT p1, POINT DestPos, LPLONG lplGet, LONG lFlags ); LPPATH MethodTwo( POINT p1, POINT DestPos, LPLONG lplGet, LONG lFlags ); LPPATH MethodThree( POINT p1, POINT DestPos, LPPATH lpPath1, LPLONG lplGet, LONG lFlags ); BOOL GetBasicPath( POINT p1, POINT DestPos, LPPATH &lpPath, LPLONG bGet, LONG lFlags ); LONG GetPathCount( LPPATH lpPath ); LPPATH GetTheBestPath( POINT StartPos, POINT DestPos, LONG lFlags ); /外部调用成员变量 LONG Get_lSquareC( void )return lSquareC; LONG Get_lHarfSquC( void )return lHarfSquC; LPWORD Get_Square( void ) return Square; LONG Get_lMaxStep( void )return lMaxStep; LONG Get_lCount( void ) return lCount; LONG Get_SceneW( void ) return SceneW; LONG Get_SceneH( void ) return SceneH; LONG Get_SceSquareW(void)return SceSquareW; LONG Get_SceSquareH(void) return SceSquareH; RECT Get_MonsterRect(void)return MonsterRect;代码分析：本书所提到的路径是由一步一步构成的，且采用链表的方式记录路径。所以应该为路径定义一个数据结构，即CGetPath.h文件的开头所定义的PATH结构。接下来是CGetPath类的变量声明。它们的用途在代码中都有解释。因为要计算场景有多少个方块以及怪物或者角色的步长等等，所以，定义了lSquareC成员，以记录场景方块的大小(方块是正方形)。当提到“怪物或角色处于某方块”时，是说怪物或角色处于方块的中央。所以，当调整怪物或角色的位置时，会经常用到方块大小的一半。为了方便，定义了lHarfSquC成员，以记录方块宽度的一半。CGetPath类通过MonsterRect所表示的区域大小来计算搜索步数的上限。外部通过调用GetTheBestPath成员函数来搜索路径。7.2.2 辅助函数和初始化下面将即将介绍的这些成员函数代码都保存在CGetPath.cpp文件上。这个文件的头部是这样的：#include #include #include CGetPath.h#define SafeDeletePath(p) DeletePath(p);p=NULL;其中宏SafeDeletePath将在介绍成员函数DeletePath时说明。1. 两维地形数组CGetPath类所使用的地形数组是一维的。而在操作方块时，是以两维的方式来操作的。所以，可以通过定义MakeSquare函数来把两维的表达方式转化为一维的。MakeSquare函数的具体代码如下：/* 函数名：MakeSquare(.) 属于CGetPath类的成员* 功能：求两维方式所表达的方块* (c) mochsh, 2004*/inline LONG CGetPath:MakeSquare(LONG y, LONG x) if( y=SceSquareH | y=SceSquareW | x0 ) return -1; return y*SceSquareW+x;2. 指定位置对应的方块成员函数GetSquareFromPos的功能是求出指定位置所在的方块。其具体代码如下：/* 函数名：GetSquareFromPos(.) 属于CGetPath类的成员* 功能：求出指定位置所对应的方块* (c) mochsh, 2004*/inline LONG CGetPath:GetSquareFromPos( POINT Pos ) return MakeSquare( Pos.y / lSquareC, Pos.x / lSquareC);所以，GetSquareFromPos的返回值是以一维数组的表达方式表达的。3. 指定方块的位置既然会经常将位置转化为方块，也会经常涉及到将方块转化为位置，此时的位置应该是方块的中央位置。成员函数GetPosFromSquare的功能就是求出指定方块的中央位置。其具体代码如下：/* 函数名：GetPosFromSquare(.) 属于CGetPath类的成员* 功能：求出指定方块的中央位置* (c) mochsh, 2004*/inline POINT CGetPath:GetPosFromSquare( LONG lSqu ) LONG y = lSqu/SceSquareW; LONG x = lSqu-y*SceSquareW; POINT pos; pos.x = lHarfSquC +x*lSquareC; pos.y = lHarfSquC +y*lSquareC; return pos;4. 两个位置间的距离在7.1.3节中曾提到过：当第一次在障碍边缘搜索时，将以“八个方块”中最靠近目的点的方块作为关联方块。这里涉及到了两点之间的距离问题。成员函数Distance的功能是求两点或者两个方块间的距离，其可重载。具体代码如下：/* 函数名：Distance(.) 属于CGetPath类的成员* 功能：求两个位置间的距离* (c) mochsh, 2004*/inline LONG CGetPath:Distance ( POINT StartPos, POINT DestPos ) LONG dx=StartPos.x-DestPos.x; LONG dy=StartPos.y-DestPos.y; return (LONG)sqrtf(FLOAT)(dx*dx+dy*dy);/* 功能: 重载，求两个方块间的距离*/inline LONG CGetPath:Distance(LONG StartSquare, LONG DestSquare ) POINT StartPos = GetPosFromSquare(StartSquare); POINT DestPos = GetPosFromSquare(DestSquare); return Distance(StartPos,DestPos);5. 调整位置当给定起点和目的点时，这两个点不一定处于方块的中央。所以，在求路径前，得先调整这两个位置。AdjustPos成员函数的功能是将指定的位置调整为所处的方块的中央位置。其具体代码如下：/* 函数名: AdjustPos(.) 属于CGetPath类的成员* 功能 : 调整指定位置，使其处于所在方块的中央* (c) mochsh, 2004*/inline POINT CGetPath:AdjustPos( POINT P ) return GetPosFromSquare(GetSquareFromPos(P);7.2.3 求“八个方块”在7.1.3节中，曾提到每个不处于场景边界上的方块的周围都有“八个方块”。并且在搜索的过程中，主要通过这“八个方块”来搜索路径。所以，求出这八个方块是非常必要的。而处于场景边界上的方块的“八个方块”的情况是不同的。如图7-16所示(假设场景的宽度是三个方块，高度也是三个方块)。图7-16 场景边界上的方块从图中可以看出，左上角的方块LT的“八个方块”缺少方块0、方块1、方块2、方块6和方块7。上边界的方块T的“八个方块”缺少方块0、方块1和方块2。右上角的方块RT缺少方块0、方块1、方块2、方块3和方块4。右边界的方块R的“八个方块”缺少方块2、方块3和方块4。右下角的方块RB的“八个方块”缺少方块2、方块3、方块4、方块5和方块6。底边上的方块B的“八个方块”缺少方块4、方块5和方块6。左下角的方块LB的“八个方块”缺少方块4、方块5、方块6、方块7和方块0。左边界的方块L的“八个方块”缺少方块0、方块6和方块7。成员函数GetAroundSquare的功能是求方块的“八个方块”。其代码如下：/* 函数名：GetAroundSquare(.) 属于CGetPath类的成员* 功能：获得指定位置的四周方块,其返回值是八个元素的数组首地址。* (c) mochsh, 2004*/inline LPLONG CGetPath:GetAroundSquare( POINT Pos ) static LONG lpAroSqu8; LONG lSquare = GetSquareFromPos(Pos); /求以两维方式表达的方块行号 LONG Index = lSquare/SceSquareW; /求以两维方式表达的方块列号 LONG leave = lSquare - Index*SceSquareW; /场景左上角的方块 if( lSquare=0 ) lpAroSqu0=-1; lpAroSqu1=-1; lpAroSqu2=-1; lpAroSqu3=1; lpAroSqu4=SceSquareW+1; lpAroSqu5=SceSquareW; lpAroSqu6=-1; lpAroSqu7=-1; /场景右上角的方块 else if( lSquare=SceSquareW-1 ) lpAroSqu0=-1; lpAroSqu1=-1; lpAroSqu2=-1; lpAroSqu3=-1; lpAroSqu4=-1; lpAroSqu5=lSquare+SceSquareW; lpAroSqu6=lSquare+SceSquareW-1; lpAroSqu7=lSquare-1; /场景右下角的方块 else if( lSquare=SceSquareH*SceSquareW-1 ) lpAroSqu0=lSquare-SceSquareW-1; lpAroSqu1=lSquare-SceSquareW; lpAroSqu2=-1; lpAroSqu3=-1; lpAroSqu4=-1; lpAroSqu5=-1; lpAroSqu6=-1; lpAroSqu7=lSquare-1; /场景左下角的方块 else if( Index=SceSquareH-1 & leave=0 ) lpAroSqu0=-1; lpAroSqu1=lSquare-SceSquareW; lpAroSqu2=lSquare-SceSquareW+1; lpAroSqu3=lSquare+1; lpAroSqu4=-1; lpAroSqu5=-1; lpAroSqu6=-1; lpAroSqu7=-1; /场景左边界上的方块 else if( leave=0 ) lpAroSqu0=-1; lpAroSqu1=lSquare-SceSquareW; lpAroSqu2=lSquare-SceSquareW+1; lpAroSqu3=lSquare+1; lpAroSqu4=lSquare+SceSquareW+1; lpAroSqu5=lSquare+SceSquareW; lpAroSqu6=-1; lpAroSqu7=-1; /场景上边界上的方块 else if( Index=0 ) lpAroSqu0=-1; lpAroSqu1=-1; lpAroSqu2=-1; lpAroSqu3=lSquare+1; lpAroSqu4=lSquare+SceSquareW+1; lpAroSqu5=lSquare+SceSquareW; lpAroSqu6=lSquare+SceSquareW-1; lpAroSqu7=lSquare-1; /场景底边界上的方块 else if( Index=SceSquareH-1 ) lpAroSqu0=lSquare-SceSquareW-1; lpAroSqu1=lSquare-SceSquareW; lpAroSqu2=lSquare-SceSquareW+1; lpAroSqu3=lSquare+1; lpAroSqu4=-1; lpAroSqu5=-1; lpAroSqu6=-1; lpAroSqu7=lSquare-1; /场景右边界上的方块 else if( leave=SceSquareW-1 ) lpAroSqu0=lSquare-SceSquareW-1; lpAroSqu1=lSquare-SceSquareW; lpAroSqu2=-1; lpAroSqu3=-1; lpAroSqu4=-1; lpAroSqu5=lSquare+SceSquareW; lpAroSqu6=lSquare+SceSquareW-1; lpAroSqu7=lSquare-1; /不在场景边界上的方块 else lpAroSqu0=lSquare-SceSquareW-1; lpAroSqu1=lSquare-SceSquareW; lpAroSqu2=lSquare-SceSquareW+1; lpAroSqu3=lSquare+1; lpAroSqu4=lSquare+SceSquareW+1; lpAroSqu5=lSquare+SceSquareW; lpAroSqu6=lSquare+SceSquareW-1; lpAroSqu7=lSquare-1; return lpAroSqu;因为将地形数组以两维的方式来表达，能更容易地表示上面提到的九种情况。所以，GetAroundSquare函数的开头将一维数组转化为两维数组。然后通过两维数组来判定属于哪种情况，再做相应地处理。最后返回记录“八个方块”的数组的首地址。7.2.4 求“近”方块在7.1.3节中提到过：当第一次在障碍边缘搜索时，将以“八个方块”中最靠近目的点的方块作为关联方块。成员函数GetNearSquare的功能就是求“八个方块”中的最近方块。其具体代码如下：/* 函数名：GetNearSquare(.) 属于CGetPath类的成员* 功能：求指定位置的对应于指定目的位置的近方块* (c) mochsh, 2004*/LONG CGetPath:GetNearSquare( POINT Pos, POINT DestPos ) LPLONGlpSquare; LONG destSquare; LONG lDis8; /将目的位置转化为方块 destSquare = GetSquareFromPos(DestPos); /获得四周的方块 lpSquare = GetAroundSquare( Pos ); /求四周方块到目的方块的距离 for( WORD i=0;i8;i+ ) lDisi=Distance(lpSquarei,destSquare); /求最小距离 WORD Min=0;/假设第1个是最小值 for( i=0;ilDisi) Min = i; return lpSquareMin;代码分析：函数的第一部分分别求出“八个方块”到目的点的距离，并以一个LONG型的有八个元素的数组lDis记录这些距离。第二部分求出lDis数组中八个元素的最小值。然后返回这个最小距离所对应的方块。7.2.5 Bresenham算法当起点与目的点之间没有障碍时，可以直线到达目的点。所以，当知道是这样的情况时，就没有必要使用吸附式或者半吸附式搜索路径,而直接以直线的方式行进，这可以得到最好的路径。本节主要介绍如何通过利用Bresenham算法获得直线路径。1. Bresenham算法原理如果路径不是由一个一个的方块组成，则表达一条直线路径将是很容易的事，只需一个简单的直线方程就解决问题。路径是由方块组成的，一个方程显然不能用来表达一个路径。但是可以尽量地选择靠近这个方程所表示的直线。如图7-17所示，虚线是原直线，采用虚线附近的方块来组成方块表示的直线。图7-17 用方块来表示的直线根据图7-17，当从某点可以直线到达目的点时，可以采用由这两点确定的直线附近的方块来组成路径。如何选择直线附近的方块，目前有较常用的三种算法：数值微分法(DDA)、中点画线法和Bresenham算法。而计算机图形学领域使用最广泛的直线表示算法是Bresenham算法。所以，下面来详细介绍Bresenham算法。如图7-18所示，求出起点与终点的横向差dx和纵向差dy，这两个值都是以方块为单位的。图7-18中的dx等于11个方块(不包含起点方块)，dy等于5个方块。可以看出这条用方块表示的直线L共有11个方块(理由是dx大于dy所以采用dx的值)。如果从起点方块开始往终点方向选择方块，所要做的就是求出横向和纵向的坐标就可以了。从图中可以看出：对于横向坐标，只要每次在横向坐标往终点方向前进一方块就可以了。对于纵向坐标，正好是横向坐标前进两个方块时，就前进一方块。现在来说明可以以上面提到的方式选择方块的原因。先看看dx和dy。dx是11，dy是5，dx约等于dy的两倍。而起点与终点间有固定的方块数，就是说把dx 和dy划分为相同的份数；则dx的每一份的大小正好是一个方块，dy的每一份的大小是5/11个方块 。所以，在纵向坐标方向上，需要约累积dy的两份才等于一个方块；与此相对应的dx也累积了两份，这两份的大小正好是两个方块。图7-18所示的是当dx大于dy的情况。对于dy大于dx的情况也是一样的道理。在从起点往终点直线寻找方块的时候