基于A算法的DIRECTX9应用设计

21基于A*算法的DIRECTX9应用设计邓卜冉 （软件工程专业，浙江工业大学计算机学院，浙江，杭州 310000）摘要：通过对A*算法的深入研究以directx的方式实现了一个由A*算法作寻径方法的3D程序（没有考虑Y轴），用二维数组来存储地图数据。使用优先级队列实现对F的排序。关键词：A*；Directx；A star algorithm；游戏；pathfinding；寻径；An Application design based on the A*Algorithm with Directx9Deng buran(Colledge of Computer Science ,Zhejiang University of Technology, Zhejiang, Hangzhou, 310000,China)Abstract: Build a program implemented the A* AI algorithm with Directx9 Technology, based on a deep research for A*.And because of some limits, there is no Y in this program, although this is a 3D program. I use a 2 dimension array to handle the map information and a priority queue to sort the nodes depending on the F cost.Key words: A*; Directx; A star algorithm; game; pathfinding;1. 背景当我们旅行到一个陌生的城市，又没有地图，我们要找路怎么办？方法一,可以找人问路。但是问到的不一定是最短的路线。方法二，用google maps。这个显然是最好的方法。那么google maps又是怎样每次都能找到能到达输入的目的地的最短的路线的？当我们玩游戏的时候，比如在call of duty black ops中的苏联集中营的场景中，玩家操纵的主角需要面对无穷尽的敌人，但同时场景地形复杂，有很多的障碍物，那些敌人却能巧妙的躲过障碍物，以最快的速度冲到主角身边，给玩家造成麻烦。 Treyarch的工程师又是如何运用AI实现这样的功能呢？就目前而言，这两个问题的答案非pathfinding莫属了。2. pathfinding分类1. 广度优先搜索（BFS）2. 深度优先搜索（DFS）3. 迪科斯彻算法（Dijkstra）4. A*算法5. B*算法3. A*算法介绍3.1.概述A*搜寻算法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。在此算法中，g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离。 因此，A*算法的公式为：f(n)=g(n)+h(n)。 这个公式遵循以下特性：如果h(n)为0，只需求出g(n)，即求出起点到任意顶点n的最短路径，则转化为单源最短路径问题，即Dijkstra算法如果h(n)=n到目标的实际距离，则一定可以求出最优解。而且h(n)越小，需要计算的节点越多，算法效率越低。A*is a variant of Dijkstras algorithm commonly used in games. Instead of looking at the distance from the start node, A* chooses nodes based on the estimated distance from the start to the finish. The estimate is formed by adding the known distance from the start to a guess of the distance to the goal. The guess, called theheuristic(启发式), improves the behavior relative to Dijkstras algorithm. When the heuristic is 0, A* is equivalent to Dijkstras algorithm. As the heuristic estimate increases and gets closer to the true distance, A* continues to find optimal paths, but runs faster (by virtue of examining fewer nodes). When the heuristic is exactly the true distance, A* examines the fewest nodes. (However, it is generally impractical to write a heuristic function that always computes the true distance.) As the heuristic increases, A* examines fewer nodes but no longer guarantees an optimal path. In many games this is acceptable and even desirable, to keep the algorithm running quickly.3.2.伪代码function A*(start,goal) closedset := the empty set /已经被估算的节点集合 openset := set containing the initial node /将要被估算的节点集合 g_scorestart := 0 /g(n) h_scorestart := heuristic_estimate_of_distance(start, goal) /f(n) f_scorestart := h_scorestart while openset is not empty x := the node in openset having the lowest f_score value/最小的F if x = goal return reconstruct_path(came_from,goal) remove x from openset/从openlist中移除 add x to closedset foreach y in neighbor_nodes(x) if y in closedset continue tentative_g_score := g_scorex + dist_between(x,y) if y not in openset add y to openset tentative_is_better := true elseif tentative_g_score g_scorey tentative_is_better := true else tentative_is_better := false if tentative_is_better = true came_fromy := x g_scorey := tentative_g_score h_scorey := heuristic_estimate_of_distance(y, goal) f_scorey := g_scorey + h_scorey return failure function reconstruct_path(came_from,current_node) if came_fromcurrent_node is set p = reconstruct_path(came_from,came_fromcurrent_node) return (p + current_node) else return current_node4. A*算法实现我们通过以下过程来逐步得到A*算法的实现方法4.1引言：搜索区域我们可以假设有一个东西需要从A点到B点，有一堵墙横在他们之间。下面是插图，绿色的是起点A点，红色的是终点B点，填充着蓝色方块的区域作为它们之间的墙。首先我们需要清楚的是我们把我们的搜索区域划分为了方格阵列。为了简化搜索区域，目前为止我们做的只是第一步。这种独特的方法把我们的搜索区域简化成了二维数组，每一个二维数组中的元素代表着图片里的小方格，并且它能记录两种状态，分别是walkable和unwalkable，我们通过弄清楚从A到B需要哪些格子，来找到这条通路。一旦通路建立，我们的person从一个方格的中心移动至下一个方格的中心，直到到达目的地为止。这些中心店叫做”nodes”（节点）。如果你读过其他的关于路径挖掘的东西，你会发现人们经常会讨论到nodes。干嘛不直接叫它们方块得了，因为搜索区域还能划分为除了方块的其他的什么东西，比如说矩形，六边形，三角形或者其他形状。我们可以把nodes置于任意的地方，当然得放进图形里面，可以是边缘也可以是中心地带或者其他什么地方。我们正在使用这套系统（本文涉及的），只是因为它是最简单的。4.2开始搜索之前我们已经把搜索区域简化为一个个可控的节点，第一步我们把这个区域给网格化了，接下来就是找到最短路径了。我们从A点开始，检查临近它的方格，然后再向外做一般性的检查（跟之前一样），直到找到目标我们才停下来。我们通过下面几条来开始搜索：从A点开始，并且把A添加到一个列表，叫”open list”，被考虑到的方块都跟它有关系。这个列表就像一个购物列表一般，目前为止列表里只有一个元素，当然之后会有更多的元素。它包含了最短路径经过的方块，同时可能也有其他方块。简单来说，这是一个存放需要检查到的方块的列表。首先剔除全部的诸如墙壁，水或者其他的非法地形，接着查看所有的可行的并且能走到的方块，它们必须是起点的邻接点。然后把他们也添加至open list中。遍历这些方块，把A点作为他们的父节点。这项工作很重要，尤其是当我们需要回溯寻径的时候。这点稍后讨论。把起点A点从open list中移除，添加到一个”closed list”中，这个表目前你不需要再去管它。 到了这一步，你应该得到了跟下图一样的图像。中间黑绿色的方块就是起始点，周围的淡蓝色的边框表示它已经被添加至closed list中，邻接的方块都被添加至open list中以供检查，它们的边框是淡绿色。每一个方块都有一个指向父节点的灰色的指针，就目前看它们都指向起始点A。之后，我们需要从open list中选择一个邻接点，或多或少重复之前的过程，这些之后会讲到。但是我们到底要选哪一个呢？答案自然是需要F（表价函数）值最少的。4.3路径消耗计算解决选择哪一个方块这一问题的关键是搞定下面的方程式：1. F = G + H2. G =从A点到给定方块的移动消耗 3. H =从给定点到终点B的估计移动消耗。通常这种方法写作启发式，貌似是一种感觉令人摸不着头脑的东西。之所以叫启发式的，是因为它就是靠猜测而已，在找到路线之前我们确实不知道确切的距离，路上可能会碰到各种障碍（一堵墙，水坑或者其他的什么东西），这个例子给你一个结算H值的方法，当然，你也能在其他的文章里找到其他的方法。我们是通过不断的重复遍历openlist找到最低F消耗的方法确定路线的。这篇文章会涉及到以上的一些细节。首先，我们来更近一步看看怎么计算这个消耗方程。就像上面说的，G等于从当前节点到起点的消耗值。在这个例子中，我们需要确定，当前节点的上下左右节点的G值都等于10，而其对角线节点的G值则为14.，之所以这样设定是因为移动到对角线的方块位置需要2的距离（不要害怕这个数字），它大约是垂直或者水平移动消耗的1.414倍。当然用10,14这样的数字就是为了简单，这样能避免计算根号，也除的尽。当然不是因为我们太蠢或者是太讨厌数学，同时，使用整形数还能加速计算机的计算速度。而且你很快就能发现如果不这么做的话，寻路算法会是个费城慢的过程。到目前为止我们已经搞定了确定方块的G值的计算，我们通过找到当前方块到它的父节点方块的消耗的办法来定下来G的值，之后给那个父节点方块的水平或者垂直邻接的方块G赋10，处于对角线的邻接方块G赋14.当我们从起点开始就能排除出去超过一个的点，我们就能发现很明显有这么做的需要H能通过很多办法来估计，这里用的叫Manhattan方法，它是用当前节点到达目标节点的直线距离来表示估计消耗的，当然它是忽略掉各种障碍物的消耗的（也算作计算距离用节点）。然后我们给它乘个10。这玩意之所以叫Manhattan，是因为它一般用来计算城市区块间的距离，我们知道我们不可能通过切出一个区块的角来找到捷径的。读过上面的描述你可能猜想启发式只是一个从当前节点到目的地剩余距离按照直线方式行进的粗略估算.事实并非如此,我们实际上尝试沿着路径估算剩余距离(通常会远一些).我们的估算值越接近实际剩余距离,算法就越快.如果我们高估了剩余距离就不能保证得到的是最短路径了.这就是所谓的不能接受的启发(inadmissible heuristic).从技术上讲，这个例子里面的Manhattan算法因为他超估路径而是不可接受的启发。但是不管怎样我们还是得用它，因为它很理解起来很容易，而且只是轻微的过估。我们找到的路径只在很少的情况下不是最短路径，想知道更多的话，这里有链接。F通过相加G和H值得到。下图显示了第一步查询的结果。每个方格里面都标出了F,G,H的值。一起看一下这些区域.看一下标有字母的区域G=10,这是因为从它到起始区域只需要水平方向上经过一块区域.起始区域正上方和正下方,以及左右的区域的G都是10.对角线上的区域G值都是14.H值是估算到红色区域的曼哈顿距离:只做水平和垂直运动(并忽略掉障碍物)的距离.按照这个方式计算从该区域经过三块区域到达红色区域,因此H值是30;这块区域正上方的区域是四块区域远所以是40,记住只有横向和纵向移动.你可以看出来其它区域的H值是怎么计算出来的了.重申一下,每个区域的F值是G和H之和.继续搜索要继续搜索，我们简单的从openlist里面选择了最低F消耗的方块。然后我们对选定的方块做下面的事情：4. 从openlist里删除这个节点，然后加至closelist.5. 检查所有的邻接方块，除了那些已经在closelist中的或者是不可行的。如果openlist中没有这个节点，添加方块至openlist，为新的方块设置选中方块为父节点。6. 如果openlist里已经有了一个邻接节点，检查是否当前较这个节点更好，换句话说，计算G值看是不是更小了。最后从新计算G和F的值，如果觉得不清楚，看下面的图会好些。好了，让我们看看这么做有什么作用。对于初始的9个方块，在添加起点到closelist里以后，其他的都放进了openlist。目前看来，紧邻当前方块右边的方块F的消耗最低，只有40，所以我们选择这个方块作下一个方块。已经在底下的图中用蓝色高亮显示。首先，我们把它从openlist当中移除，并添加至closelist（这就是为什么现在用蓝色高亮）。然后我们检查邻接方块。右边的方块都是墙，我们可以直接忽略这些方块。左边的已经添加至了closelist中，所以我们也忽略它。其他的四个方块已经在openlist中，所以我们需要用到G的值来检查从当前节点经过这些节点会不会是更好的选择。我们看看正上的方块。它目前的G值是14。如果我们选择经过当前节点到达这个方块，G值的和为20（从起点到右边的为10，然后在到正上方的这个节点，也是10，加一起就是20）。20要比14高，所以它肯定不是更好的路径。你看看图可能更清楚一些。从起始格沿对角线过去比起横向走一格再纵向走一格走来得直接.当我们已经对这四个方块重复了这个过程，并且已经添加至openlist，我们发现经过当前节点的四个方块没一个块有建设性，所以我们不用改变什么。到目前为止，我们检查了所有的邻接点，看似我们已经搞掂了这个方块，而且已经做好准备去搞下一个方块。我们遍历了openlist中的方块，有7个，我们选择F消耗最低的。有趣的是，有两个方块的F值都为54。那，我们选哪个呢？没关系！为了提高速度，你可以直接选择最后添加至表一个元素。后面就会发现这种偏见方法对方块的情况很有效，特别是你越接近目标的时候。但是也不要紧（这就是为什么两个不同版本的A*算法会找到的长度不同的不同路径）那么我们直接选择下面的方块，在起点的右边，如下图所示。这次我们发现右边的节点是块墙，所以我们忽略它。上面的也一样。下面的也得忽略掉，为什么？因为你没法切掉墙的一个角以到达斜向的目的地。你确实需要先先向下走一格，然后再向右走，这样就能走过墙的一角。（注意：这个法则对于切割立方体边角是可选的。它取决于你的节点是怎么安排的）还剩下5个方块。底下的两个还没添加到openlist里，所以我们添加当前节点为它们的父节点。其他3个，2个已经在closelist里，不用考虑（起点，还有当前节点上面的那个，图中都用蓝色高亮了出来）。最后一个方块，左边的，已经检查过了是否能有更小的G值出现，答案显然是否定的。所以我们接下来要做的是检查openlist中的下一个节点。我们重复这一过程，直到有新的节点添加至closelist中，如下图所示。注意开始格下方的两个方块的父节点和前一个图相比已经发生了变化.之前G值为28的方块指向右上方方块,现在它的G值是20并指向正上方的方块.这是在搜索过程中发生的,检查G值发现使用新路径可以使得它的值更小-所以修改了它的父节点并重新计算了F值和G值.这个变化在我们这里显得并不是太重要.不断地检查过程中可能出现很多可能性使得最终到达目的地格子的路径千差万别. 那么怎么样确定一条路径呢?简单讲,从红色方块开始进行回溯,沿着箭头方向从一个格子到它的父节点.最终会回到起始点.如下图所示.从开始点A到目的地B的移动简化成从沿着路径从每一个方块的中心(节点)到下一个格子的中心,直至到达目标.5. DIRECTX程序实现A*算法本例实现游戏中常见的寻路场景，用绿色方块表示起点和终点，红色方块表示墙壁，处于起点的绿色方块根据通过A*找到的路径走到终点绿方块处程序运行截图寻路中已从起点走到终点5.1类设计一共需要设计4个类，分别是1) map2) astar3) point4) node还有struct model用于存放模型相关信息如mesh，世界矩阵等struct modelLPD3DXMESH myMesh;D3DMATERIAL9* myMeshMaterials; / Materials for our meshLPDIRECT3DTEXTURE9* myMeshTextures; / Textures for our meshDWORD mydwNumMaterials; / Number of mesh materialsD3DXMATRIX matWorld,rotation,translation; / Matrixfloat m_XRotation, m_YRotation, m_ZRotation,m_XPos, m_YPos, m_ZPos;/设定坐标变量;为了实现openlist中更具F值排序，本文采用STL中的priority_queue来实现，于此同时需要重载node类的运算符，根据G+H来确定优先级priority_queue openlist; / openlist for the nodes to checkcloselist的实现则简单许多，使用STL中的vectorvector closelist; / closelist for the nodes to be cheked类图如下Astar.h#include map.h#includetime.h#include #include#includeusing namespace std;class astarpublic :astar();astar();map mymap;/地图vector wallpoints;/地图中有墙的位置坐标用于directx绘制point startpoint;/起点point endpoint;/终点priority_queue openlist;/open表用于检查节点vector closelist;/存放最终路径int wallcount;/墙的数量public:void init();void setStart(int x,int y);void setEnd(int x,int y);void search();double distance(int x1,int y1,int x2,int y2);bool closeContainNode(node *n);void print();5.2函数设计Astar.cpp5.2.1初始化函数/-/ Name: astar:init()/ Desc: init the necessary variables about A* method/-void astar:init()/设置时间种子srand(time(NULL);point p;for(int k(0);k20;k+)/随机设置块墙for(int j(0);j20;j+)int i=rand()%100;if(i=0&topright.y=0&topleft.y=0&topleft.x=0&footleft.x=0)/根据当前节点的位置为周围邻接个点的g赋值,并且绑定currnode为父节点添加至优先级队列if(mymap.mtopleft.xtopleft.y.state!=0)/检查当前topleft节点是否为不可行的mymap.mtopleft.xtopleft.y.g=14.0f;if(!closeContainNode(&mymap.mtopleft.xtopleft.y)mymap.mtopleft.xtopleft.y.parent=&currnode;openlist.push(mymap.mtopleft.xtopleft.y);if(mymap.mtopright.xtopright.y.state!=0)mymap.mtopright.xtopright.y.g=14.0f;if(!closeContainNode(&mymap.mtopright.xtopright.y)mymap.mtopright.xtopright.y.parent=&currnode;openlist.push(mymap.mtopright.xtopright.y);if(mymap.mfootright.xfootright.y.state!=0)mymap.mfootright.xfootright.y.g=14.0f;if(!closeContainNode(&mymap.mfootright.xfootright.y)mymap.mfootright.xfootright.y.parent=&currnode;openlist.push(mymap.mfootright.xfootright.y);if(mymap.mfootleft.xfootleft.y.state!=0)mymap.mfootleft.xfootleft.y.g=14.0f;if(!closeContainNode(&mymap.mfootleft.xfootleft.y)mymap.mfootleft.xfootleft.y.parent=&currnode;openlist.push(mymap.mfootleft.xfootleft.y);if(mymap.mfoot.xfoot.y.state!=0)mymap.mfoot.xfoot.y.g=10.0f;if(!closeContainNode(&mymap.mfoot.xfoot.y)mymap.mfoot.xfoot.y.parent=&currnode;openlist.push(mymap.mfoot.xfoot.y);if(mymap.mleft.xleft.y.state!=0)mymap.mleft.xleft.y.g=10.0f;if(!closeContainNode(&mymap.mleft.xleft.y)mymap.mleft.xleft.y.parent=&currnode;openlist.push(mymap.mleft.xleft.y);if(mymap.mright.xright.y.state!=0)mymap.mright.xright.y.g=10.0f;if(!closeContainNode(&mymap.mright.xright.y)mymap.mright.xright.y.parent=&currnode;openlist.push(mymap.mright.xright.y);if(mymap.mtop.xtop.y.state!=0)mymap.mtop.xtop.y.g=10.0f;if(!closeContainNode(&mymap.mtop.xtop.y)mymap.mtop.xtop.y.parent=&currnode;openlist.push(mymap.mtop.xtop.y);/end/todo.closelist.push_back(openlist.top();/把终点也放入closelistMesh.cpp5.2.3初始化几何信息函数/-/ Name: InitGeometry()/ Desc: Load the mesh and build the material and texture arrays/-HRESULT InitGeometry(LPD3DXMESH *m_pMesh,D3DMATERIAL9 *m_pMeshMaterials,LPDIRECT3DTEXTURE9 *m_pMeshTextures,DWORD *m_dwNumMaterials,char *textname,int type) /Unicode装换LPD3DXBUFFER pD3DXMtrlBuffer;WCHAR str315;MultiByteToWideChar( 0,0, textname, 15, str3, 15);LPCWSTR filename = str3;/convertion end / Load the mesh from the specified file if( FAILED( D3DXLoadMeshFromX( filename, D3DXMESH_SYSTEMMEM, g_pd3dDevice, NULL, &pD3DXMtrlBuffer, NULL, m_dwNumMaterials, m_pMesh ) ) ) / If model is not in current folder, try parent folder if( FAILED( D3DXLoadMeshFromX( L.cube2.x, D3DXMESH_SYSTEMMEM, g_pd3dDevice, NULL, &pD3DXMtrlBuffer, NULL, m_dwNumMaterials, m_pMesh ) ) ) MessageBox( NULL, LCould not find tiger.x, LMeshes.exe, MB_OK ); return E_FAIL; / We need to extract the material properties and texture names from the / pD3DXMtrlBuffer D3DXMATERIAL* d3dxMaterials = ( D3DXMATERIAL* )pD3DXMtrlBuffer-GetBufferPointer(); *m_pMeshMaterials = new D3DMATERIAL9*m_dwNumMaterials; if( m_pMeshMaterials = NULL ) return E_OUTOFMEMORY; *m_pMeshTextures = new LPDIRECT3DTEXTURE9*m_dwNumMaterials; if( *m_pMeshTextures = NULL ) return E_OUTOFMEMORY; for( DWORD i = 0; i 0 ) / Create the texture if( FAILED( D3DXCreateTextureFromFileA( g_pd3dDevice, d3dxMaterialsi.pTextureFilename, m_pMeshTexturesi ) ) ) / If texture is not in current folder, try parent folder const CHAR* strPrefix = .; CHAR strTextureMAX_PATH; strcpy_s( strTexture, MAX_PATH, strPrefix ); strcat_s( strTexture, MAX_PATH, d3dxMaterialsi.pTextureFilename ); / If texture is not in current folder, try parent folder