文档介绍：编辑版word
页脚下载后可删除，如有侵权请告知删除！
编辑版word
基于A*算法的DIRECTX9应用设计
邓卜冉
（软件工程专业，浙江工业大学计算机学院，浙江，杭州 310000）
摘要：通过对A*算法的深入研究以directx的方式实现了一个由A*算法作寻径方法的3D程序（没有考虑Y轴），用二维数组来存储地图数据。使用优先级队列实现对F的排序。
关键词：A*；Directx；A star algorithm；游戏；pathfinding；寻径；

An Application design based on the A*Algorithm with Directx9
Deng 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;
背景
当我们旅行到一个陌生的城市，又没有地图，我们要找路怎么办？
方法一,可以找人问路。但是问到的不一定是最短的路线。
方法二，用google maps。这个显然是最好的方法。
那么google maps又是怎样每次都能找到能到达输入的目的地的最短的路线的？
编辑版word
页脚下载后可删除，如有侵权请告知删除！
编辑版word
当我们玩游戏的时候，比如在call of duty black ops中的苏联集中营的场景中，玩家操纵的主角需要面对无穷尽的敌人，但同时场景地形复杂，有很多的障碍物，那些敌人却能巧妙的躲过障碍物，以最快的速度冲到主角身边，给玩家造成麻烦。 Treyarch的工程师又是如何运用AI实现这样的功能呢？
就目前而言，这两个问题的答案非pathfinding莫属了。
pathfinding分类
广度优先搜索（BFS）
深度优先搜索（DFS）
迪科斯彻算法（Dijkstra）
A*算法
B*算法
…
A*算法介绍

A*搜寻算法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。
该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。
在此算法中，g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离。因此，A*算法的公式为：f(n)=g(n)+h(n)。这个公式遵循以下特性：
编辑版word
页脚下载后可删除，如有侵权请告知删除！
编辑版word
如果h(n)为0，只需求出g(n)，即求出起点到任意顶点n的最短路径，则转化为单源最短路径问题，即Dijkstra算法
如果h(n)<=n到目标的实际距离，则一定可以求出最优解。而且h(n)越小，需要计算的节点越多，算法效率越低。
A* is a variant of Dijkstra's 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 the heuristic(启发式), improves t