[关键词] 自动寻路; A*算法; 人工智能; 节点
1.2 系统开发的目标及意义
系统开发目标是在silverlight下实现自动寻路，并能对路径计算，无法到达的地点的提示。实现以最小最优的距离达到实现寻路的目的。系统开发的意义是节省时间，节省工作量，为玩家用户提供方便快捷的游戏体验。
文的目的是通过对已有的寻路算法进行介绍，尽量使用一种能在最短的时间之内找到最优的路径的算法。本文首先对路径搜索的相关理论技术，包括图搜索、盲目搜索算法和启发式搜索算法等进行了全面的分析。由于A*算法是现在游戏中最广泛采用的寻路算法，所以本文以A*算法为主要研究内容。然后，在分析A*算法的缺点的基础上，从几个方面提出了基于A*算法的改进和优化的寻路算法。
本文主要研究内容如下:
分析比较目前常用的路径搜索方法，详细分析了A*算法，分析出它的不足之处。经过分析发现它主要有以下不足:估价函数对A*算法的搜索起到关键性作用，但是受到主观因素等的限制，因而估价函数的选取是一个比较复杂的问题;A*算法中最耗费搜索时间的就是搜索OPEN表中的F值最小的节点，如何提高在OPEN表中查找节点的速度成为了一个难点。
通过选取合适的估价函数，编写一个简单的使用A*算法进行模拟寻路的程序，通过鼠标的点击，自动由起始点到目标点形成一个最合适的路径，并能够绕过障碍，对于无法到达的地方，能够进行提示。
系统开发的意义：
自动寻路作为人工智能在游戏领域中最常见的应用，它能否高效的寻找出路经，直接关系到此系统的开发的成功与否，因为在实际的应用中，我们不能要求玩家浪费大量时间在寻路上，自动寻路本身是为玩家提供方便的，如果自动寻路不能高效的运行，那么这个系统就是失败的，在我国的很多游戏中，的确有自动寻路，但是它们有很多不足，比如有时候会在一个地域来回的移动无法绕过障碍，有时不能选取最佳的路线，会舍近求远。有时可能由于地图过大路线过多，在路径的计算中浪费大量时间，致使玩家的时间浪费在等待之中，这些，都是自动寻路的应用中存在的并且急需解决的问题，而本文中，通过开发模拟的寻路系统，希望能够在这些方面做出改进，为以后的开发提供参考与助力。
目 录
1 概述 1
1.1 本课题背景和现状的研究 1
1.1.1 系统开发背景 1
1.1.2 系统研究现状 1
1.2 系统开发的目标及意义 3
2 需求分析 4
2.1 系统需求 4
2.2 技术需求 4
2.3 系统可行性分析 5
3 几种常见的寻路算法简介 6
3.1 最短路径算法 6
3.2 几种常见的最短路径算法的介绍 7
3.2.1 迪杰斯特拉算法 7
3.2.2 BELLMAN-FORD算法 9
3.2.3 A*寻路算法 10
3.3 A*算法的扩展改进 13
3.3.1 通过排序方法改进open表的读取速度 14
3.3.2 通过优化open表的数据结构提高效率 15
4 系统的设计与实现 16
4.1 程序的实现效果 16
4.2 地图的设置 17
4.2.1 障碍的详细设置 17
4.2.2 地图初始化 17
4.3 寻路算法的实现 20
4.4 本程序中寻路的详细实现过程讲解 21
5 系统的软件及硬件需求 27
5.1 开发环境和运行环境 27
5.2 电脑硬件要求 27
结束语 28
参考文献 29
致谢 30