《基于A算法的DIRECTX9应用设计说明》由会员分享，可在线阅读，更多相关《基于A算法的DIRECTX9应用设计说明（20页珍藏版）》请在金锄头文库上搜索。
1、基于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 Universi
2、ty 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
3、 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中
4、的联集中营的场景中，玩家操纵的主角需要面对无穷尽的敌人，但同时场景地形复杂，有很多的障碍物，那些敌人却能巧妙的躲过障碍物，以最快的速度冲到主角身边，给玩家造成麻烦。 Treyarch的工程师又是如何运用AI实现这样的功能呢？就目前而言，这两个问题的答案非pathfinding莫属了。2. pathfinding分类1. 广度优先搜索（BFS）2. 深度优先搜索（DFS）3. 迪科斯彻算法（Dijkstra）4. A*算法5. B*算法3. A*算法介绍3.1.概述A*搜寻算法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游
5、戏的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 com
6、monly 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(启发式),
7、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 heuris
8、tic 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
9、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_scorestar
10、t 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(
11、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_scor
12、ey := 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点，有一堵墙横在他们之间。下
13、面是插图，绿色的是起点A点，红色的是终点B点，填充着蓝色方块的区域作为它们之间的墙。首先我们需要清楚的是我们把我们的搜索区域划分为了方格阵列。为了简化搜索区域，目前为止我们做的只是第一步。这种独特的方法把我们的搜索区域简化成了二维数组，每一个二维数组中的元素代表着图片里的小方格，并且它能记录两种状态，分别是walkable和unwalkable，我们通过弄清楚从A到B需要哪些格子，来找到这条通路。一旦通路建立，我们的person从一个方格的中心移动至下一个方格的中心，直到到达目的地为止。这些中心店叫做”nodes”（节点）。如果你读过其他的关于路径挖掘的东西，你会发现人们经常会讨论到nodes
14、。干嘛不直接叫它们方块得了，因为搜索区域还能划分为除了方块的其他的什么东西，比如说矩形，六边形，三角形或者其他形状。我们可以把nodes置于任意的地方，当然得放进图形里面，可以是边缘也可以是中心地带或者其他什么地方。我们正在使用这套系统（本文涉及的），只是因为它是最简单的。4.2开始搜索之前我们已经把搜索区域简化为一个个可控的节点，第一步我们把这个区域给网格化了，接下来就是找到最短路径了。我们从A点开始，检查临近它的方格，然后再向外做一般性的检查（跟之前一样），直到找到目标我们才停下来。我们通过下面几条来开始搜索：从A点开始，并且把A添加到一个列表，叫”open list”，被考虑到的方块都跟它有关系。这个列表就像一个购物列表一般，目前为止列表里只有一个元素，当然之后会有更多的元素。它包含了最短路径经过的方块，同时可能也有其他方块。简单来说，这是一个存放需要检查到的方块的列表。首先剔除全部的诸如墙壁，水或者其他的非法地形，接着查看所有的可行的并且能走到的方块，它们必须是起点的邻接点。然后把他们也添加至open list中。遍历
