基于A算法的DIRECTX9應用設計

21基于A*算法的DIRECTX9應用設計鄧卜冉 （軟件工程專業(yè)，浙江工業(yè)大學計算機學院，浙江，杭州 310000）摘要：通過對A*算法的深入研究以directx的方式實現(xiàn)了一個由A*算法作尋徑方法的3D程序（沒有考慮Y軸），用二維數(shù)組來存儲地圖數(shù)據(jù)。使用優(yōu)先級隊列實現(xiàn)對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中的蘇聯(lián)集中營的場景中，玩家操縱的主角需要面對無窮盡的敵人，但同時場景地形復雜，有很多的障礙物，那些敵人卻能巧妙的躲過障礙物，以最快的速度沖到主角身邊，給玩家造成麻煩。 Treyarch的工程師又是如何運用AI實現(xiàn)這樣的功能呢？就目前而言，這兩個問題的答案非pathfinding莫屬了。2. pathfinding分類1. 廣度優(yōu)先搜索（BFS）2. 深度優(yōu)先搜索（DFS）3. 迪科斯徹算法（Dijkstra）4. A*算法5. B*算法3. A*算法介紹3.1.概述A*搜尋算法，俗稱A星算法。這是一種在圖形平面上，有多個節(jié)點的路徑，求出最低通過成本的算法。常用于游戲中的NPC的移動計算，或線上游戲的BOT的移動計算上。該算法像Dijkstra算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發(fā)式的搜索。在此算法中，g(n)表示從起點到任意頂點n的實際距離，h(n)表示任意頂點n到目標頂點的估算距離。 因此，A*算法的公式為：f(n)=g(n)+h(n)。 這個公式遵循以下特性：如果h(n)為0，只需求出g(n)，即求出起點到任意頂點n的最短路徑，則轉(zhuǎn)化為單源最短路徑問題，即Dijkstra算法如果h(n)=n到目標的實際距離，則一定可以求出最優(yōu)解。而且h(n)越小，需要計算的節(jié)點越多，算法效率越低。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(啟發(fā)式), 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 /已經(jīng)被估算的節(jié)點集合 openset := set containing the initial node /將要被估算的節(jié)點集合 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*算法實現(xiàn)我們通過以下過程來逐步得到A*算法的實現(xiàn)方法4.1引言：搜索區(qū)域我們可以假設有一個東西需要從A點到B點，有一堵墻橫在他們之間。下面是插圖，綠色的是起點A點，紅色的是終點B點，填充著藍色方塊的區(qū)域作為它們之間的墻。首先我們需要清楚的是我們把我們的搜索區(qū)域劃分為了方格陣列。為了簡化搜索區(qū)域，目前為止我們做的只是第一步。這種獨特的方法把我們的搜索區(qū)域簡化成了二維數(shù)組，每一個二維數(shù)組中的元素代表著圖片里的小方格，并且它能記錄兩種狀態(tài)，分別是walkable和unwalkable，我們通過弄清楚從A到B需要哪些格子，來找到這條通路。一旦通路建立，我們的person從一個方格的中心移動至下一個方格的中心，直到到達目的地為止。這些中心店叫做”nodes”（節(jié)點）。如果你讀過其他的關于路徑挖掘的東西，你會發(fā)現(xiàn)人們經(jīng)常會討論到nodes。干嘛不直接叫它們方塊得了，因為搜索區(qū)域還能劃分為除了方塊的其他的什么東西，比如說矩形，六邊形，三角形或者其他形狀。我們可以把nodes置于任意的地方，當然得放進圖形里面，可以是邊緣也可以是中心地帶或者其他什么地方。我們正在使用這套系統(tǒng)（本文涉及的），只是因為它是最簡單的。4.2開始搜索之前我們已經(jīng)把搜索區(qū)域簡化為一個個可控的節(jié)點，第一步我們把這個區(qū)域給網(wǎng)格化了，接下來就是找到最短路徑了。我們從A點開始，檢查臨近它的方格，然后再向外做一般性的檢查（跟之前一樣），直到找到目標我們才停下來。我們通過下面幾條來開始搜索：從A點開始，并且把A添加到一個列表，叫”open list”，被考慮到的方塊都跟它有關系。這個列表就像一個購物列表一般，目前為止列表里只有一個元素，當然之后會有更多的元素。它包含了最短路徑經(jīng)過的方塊，同時可能也有其他方塊。簡單來說，這是一個存放需要檢查到的方塊的列表。首先剔除全部的諸如墻壁，水或者其他的非法地形，接著查看所有的可行的并且能走到的方塊，它們必須是起點的鄰接點。然后把他們也添加至open list中。遍歷這些方塊，把A點作為他們的父節(jié)點。這項工作很重要，尤其是當我們需要回溯尋徑的時候。這點稍后討論。把起點A點從open list中移除，添加到一個”closed list”中，這個表目前你不需要再去管它。 到了這一步，你應該得到了跟下圖一樣的圖像。中間黑綠色的方塊就是起始點，周圍的淡藍色的邊框表示它已經(jīng)被添加至closed list中，鄰接的方塊都被添加至open list中以供檢查，它們的邊框是淡綠色。每一個方塊都有一個指向父節(jié)點的灰色的指針，就目前看它們都指向起始點A。之后，我們需要從open list中選擇一個鄰接點，或多或少重復之前的過程，這些之后會講到。但是我們到底要選哪一個呢？答案自然是需要F（表價函數(shù)）值最少的。4.3路徑消耗計算解決選擇哪一個方塊這一問題的關鍵是搞定下面的方程式：1. F = G + H2. G =從A點到給定方塊的移動消耗 3. H =從給定點到終點B的估計移動消耗。通常這種方法寫作啟發(fā)式，貌似是一種感覺令人摸不著頭腦的東西。之所以叫啟發(fā)式的，是因為它就是靠猜測而已，在找到路線之前我們確實不知道確切的距離，路上可能會碰到各種障礙（一堵墻，水坑或者其他的什么東西），這個例子給你一個結(jié)算H值的方法，當然，你也能在其他的文章里找到其他的方法。我們是通過不斷的重復遍歷openlist找到最低F消耗的方法確定路線的。這篇文章會涉及到以上的一些細節(jié)。首先，我們來更近一步看看怎么計算這個消耗方程。就像上面說的，G等于從當前節(jié)點到起點的消耗值。在這個例子中，我們需要確定，當前節(jié)點的上下左右節(jié)點的G值都等于10，而其對角線節(jié)點的G值則為14.，之所以這樣設定是因為移動到對角線的方塊位置需要2的距離（不要害怕這個數(shù)字），它大約是垂直或者水平移動消耗的1.414倍。當然用10,14這樣的數(shù)字就是為了簡單，這樣能避免計算根號，也除的盡。當然不是因為我們太蠢或者是太討厭數(shù)學，同時，使用整形數(shù)還能加速計算機的計算速度。而且你很快就能發(fā)現(xiàn)如果不這么做的話，尋路算法會是個費城慢的過程。到目前為止我們已經(jīng)搞定了確定方塊的G值的計算，我們通過找到當前方塊到它的父節(jié)點方塊的消耗的辦法來定下來G的值，之后給那個父節(jié)點方塊的水平或者垂直鄰接的方塊G賦10，處于對角線的鄰接方塊G賦14.當我們從起點開始就能排除出去超過一個的點，我們就能發(fā)現(xiàn)很明顯有這么做的需要H能通過很多辦法來估計，這里用的叫Manhattan方法，它是用當前節(jié)點到達目標節(jié)點的直線距離來表示估計消耗的，當然它是忽略掉各種障礙物的消耗的（也算作計算距離用節(jié)點）。然后我們給它乘個10。這玩意之所以叫Manhattan，是因為它一般用來計算城市區(qū)塊間的距離，我們知道我們不可能通過切出一個區(qū)塊的角來找到捷徑的。讀過上面的描述你可能猜想啟發(fā)式只是一個從當前節(jié)點到目的地剩余距離按照直線方式行進的粗略估算.事實并非如此,我們實際上嘗試沿著路徑估算剩余距離(通常會遠一些).我們的估算值越接近實際剩余距離,算法就越快.如果我們高估了剩余距離就不能保證得到的是最短路徑了.這就是所謂的不能接受的啟發(fā)(inadmissible heuristic).從技術上講，這個例子里面的Manhattan算法因為他超估路徑而是不可接受的啟發(fā)。但是不管怎樣我們還是得用它，因為它很理解起來很容易，而且只是輕微的過估。我們找到的路徑只在很少的情況下不是最短路徑，想知道更多的話，這里有鏈接。F通過相加G和H值得到。下圖顯示了第一步查詢的結(jié)果。每個方格里面都標出了F,G,H的值。一起看一下這些區(qū)域.看一下標有字母的區(qū)域G=10,這是因為從它到起始區(qū)域只需要水平方向上經(jīng)過一塊區(qū)域.起始區(qū)域正上方和正下方,以及左右的區(qū)域的G都是10.對角線上的區(qū)域G值都是14.H值是估算到紅色區(qū)域的曼哈頓距離:只做水平和垂直運動(并忽略掉障礙物)的距離.按照這個方式計算從該區(qū)域經(jīng)過三塊區(qū)域到達紅色區(qū)域,因此H值是30;這塊區(qū)域正上方的區(qū)域是四塊區(qū)域遠所以是40,記住只有橫向和縱向移動.你可以看出來其它區(qū)域的H值是怎么計算出來的了.重申一下,每個區(qū)域的F值是G和H之和.繼續(xù)搜索要繼續(xù)搜索，我們簡單的從openlist里面選擇了最低F消耗的方塊。然后我們對選定的方塊做下面的事情：4. 從openlist里刪除這個節(jié)點，然后加至closelist.5. 檢查所有的鄰接方塊，除了那些已經(jīng)在closelist中的或者是不可行的。如果openlist中沒有這個節(jié)點，添加方塊至openlist，為新的方塊設置選中方塊為父節(jié)點。6. 如果openlist里已經(jīng)有了一個鄰接節(jié)點，檢查是否當前較這個節(jié)點更好，換句話說，計算G值看是不是更小了。最后從新計算G和F的值，如果覺得不清楚，看下面的圖會好些。好了，讓我們看看這么做有什么作用。對于初始的9個方塊，在添加起點到closelist里以后，其他的都放進了openlist。目前看來，緊鄰當前方塊右邊的方塊F的消耗最低，只有40，所以我們選擇這個方塊作下一個方塊。已經(jīng)在底下的圖中用藍色高亮顯示。首先，我們把它從openlist當中移除，并添加至closelist（這就是為什么現(xiàn)在用藍色高亮）。然后我們檢查鄰接方塊。右邊的方塊都是墻，我們可以直接忽略這些方塊。左邊的已經(jīng)添加至了closelist中，所以我們也忽略它。其他的四個方塊已經(jīng)在openlist中，所以我們需要用到G的值來檢查從當前節(jié)點經(jīng)過這些節(jié)點會不會是更好的選擇。我們看看正上的方塊。它目前的G值是14。如果我們選擇經(jīng)過當前節(jié)點到達這個方塊，G值的和為20（從起點到右邊的為10，然后在到正上方的這個節(jié)點，也是10，加一起就是20）。20要比14高，所以它肯定不是更好的路徑。你看看圖可能更清楚一些。從起始格沿對角線過去比起橫向走一格再縱向走一格走來得直接.當我們已經(jīng)對這四個方塊重復了這個過程，并且已經(jīng)添加至openlist，我們發(fā)現(xiàn)經(jīng)過當前節(jié)點的四個方塊沒一個塊有建設性，所以我們不用改變什么。到目前為止，我們檢查了所有的鄰接點，看似我們已經(jīng)搞掂了這個方塊，而且已經(jīng)做好準備去搞下一個方塊。我們遍歷了openlist中的方塊，有7個，我們選擇F消耗最低的。有趣的是，有兩個方塊的F值都為54。那，我們選哪個呢？沒關系！為了提高速度，你可以直接選擇最后添加至表一個元素。后面就會發(fā)現(xiàn)這種偏見方法對方塊的情況很有效，特別是你越接近目標的時候。但是也不要緊（這就是為什么兩個不同版本的A*算法會找到的長度不同的不同路徑）那么我們直接選擇下面的方塊，在起點的右邊，如下圖所示。這次我們發(fā)現(xiàn)右邊的節(jié)點是塊墻，所以我們忽略它。上面的也一樣。下面的也得忽略掉，為什么？因為你沒法切掉墻的一個角以到達斜向的目的地。你確實需要先先向下走一格，然后再向右走，這樣就能走過墻的一角。（注意：這個法則對于切割立方體邊角是可選的。它取決于你的節(jié)點是怎么安排的）還剩下5個方塊。底下的兩個還沒添加到openlist里，所以我們添加當前節(jié)點為它們的父節(jié)點。其他3個，2個已經(jīng)在closelist里，不用考慮（起點，還有當前節(jié)點上面的那個，圖中都用藍色高亮了出來）。最后一個方塊，左邊的，已經(jīng)檢查過了是否能有更小的G值出現(xiàn)，答案顯然是否定的。所以我們接下來要做的是檢查openlist中的下一個節(jié)點。我們重復這一過程，直到有新的節(jié)點添加至closelist中，如下圖所示。注意開始格下方的兩個方塊的父節(jié)點和前一個圖相比已經(jīng)發(fā)生了變化.之前G值為28的方塊指向右上方方塊,現(xiàn)在它的G值是20并指向正上方的方塊.這是在搜索過程中發(fā)生的,檢查G值發(fā)現(xiàn)使用新路徑可以使得它的值更小-所以修改了它的父節(jié)點并重新計算了F值和G值.這個變化在我們這里顯得并不是太重要.不斷地檢查過程中可能出現(xiàn)很多可能性使得最終到達目的地格子的路徑千差萬別. 那么怎么樣確定一條路徑呢?簡單講,從紅色方塊開始進行回溯,沿著箭頭方向從一個格子到它的父節(jié)點.最終會回到起始點.如下圖所示.從開始點A到目的地B的移動簡化成從沿著路徑從每一個方塊的中心(節(jié)點)到下一個格子的中心,直至到達目標.5. DIRECTX程序?qū)崿F(xiàn)A*算法本例實現(xiàn)游戲中常見的尋路場景，用綠色方塊表示起點和終點，紅色方塊表示墻壁，處于起點的綠色方塊根據(jù)通過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;/設定坐標變量;為了實現(xiàn)openlist中更具F值排序，本文采用STL中的priority_queue來實現(xiàn)，于此同時需要重載node類的運算符，根據(jù)G+H來確定優(yōu)先級priority_queue openlist; / openlist for the nodes to checkcloselist的實現(xiàn)則簡單許多，使用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表用于檢查節(jié)點vector closelist;/存放最終路徑int wallcount;/墻的數(shù)量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函數(shù)設計Astar.cpp5.2.1初始化函數(shù)/-/ 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)/根據(jù)當前節(jié)點的位置為周圍鄰接個點的g賦值,并且綁定currnode為父節(jié)點添加至優(yōu)先級隊列if(mymap.mtopleft.xtopleft.y.state!=0)/檢查當前topleft節(jié)點是否為不可行的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初始化幾何信息函數(shù)/-/ 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