文档介绍：基于A*算法的DIRECTX9应用设计 邓卜冉(软件工程专业,浙江工业大学计算机学院,浙江,杭州310000)摘要:通过对A*算法的深入研究以directx的方式实现了一个由A*算法作寻径方法的3D程序(没有考虑Y轴),用二维数组来存储地图数据。使用优先级队列实现对F的排序。关键词:A*;Directx;Astaralgorithm;游戏;pathfinding;寻径; AnApplicationdesignbasedontheA*AlgorithmwithDirectx9Dengburan(puterScience,ZhejiangUniversityofTechnology,Zhejiang,Hangzhou,310000,China)Abstract:BuildaprogramimplementedtheA*AIalgorithmwithDirectx9Technology,basedonadeepresearchforA*.Andbecauseofsomelimits,thereisnoYinthisprogram,:A*;Directx;Astaralgorithm;game;pathfinding;背景当我们旅行到一个陌生的城市,又没有地图,我们要找路怎么办?方法一,可以找人问路。但是问到的不一定是最短的路线。方法二,用googlemaps。这个显然是最好的方法。那么googlemaps又是怎样每次都能找到能到达输入的目的地的最短的路线的?当我们玩游戏的时候,比如在callofdutyblackops中的苏联集中营的场景中,玩家操纵的主角需要面对无穷尽的敌人,但同时场景地形复杂,有很多的障碍物,那些敌人却能巧妙的躲过障碍物,以最快的速度冲到主角身边,给玩家造成麻烦。Treyarch的工程师又是如何运用AI实现这样的功能呢?就目前而言,这两个问题的答案非pathfinding莫属了。pathfinding分类广度优先搜索(BFS)深度优先搜索(DFS)迪科斯彻算法(Dijkstra)A*算法B*算法…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* isavariantofDijkstra',A*,calledthe heuristic(启发式),improvesthebehaviorrelativetoDijkstra',A*isequivalenttoDijkstra',A*continuestofindoptimalpaths,butrunsfaster(byvirtueofexaminingfewernodes).Whentheheuristicisexactlythetruedistance,A*examinesthefewestnodes.(However,putesthetruedistance.)Astheheuristicincreases,A*examinesfewernodesbutnolonge