基于A算法的DIRECTX9應(yīng)用設(shè)計(jì)

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