基于启发式搜索算法的地图寻径的研究

摘要

随着计算机技术及因特网技术在中国的发展，中国游戏产业逐渐形成规模。尤其是这几年，国家提倡电脑游戏软件的自主研发，因此各种游戏引擎软件中的技术和算法成为了人们研发的热点，其中地图寻径算法是游戏引擎软件中最重要的算法之一。最常用的地图寻径算法是一种启发式搜索算法--A*算法。而传统的A*算法在数据结构优化方面没有做足够的研究，因此在这方面还有优化的余地。其次，各种对A*算法的研究过于理论化，而将A*算法实际的使用在项目当中的研究极少，这也是地图寻径算法研究的一个欠缺。 本文针对以上所述的两点不足进行了研究和探讨。首先，通过设计算法演示程序研究了A*算法在地图寻径中的执行过程，对其整个过程中的各种操作进行了详细分析，针对分析结果提出了几种数据结构的设计，并将新设计的数据结构用于算法当中，通过算法的执行，对各种优化结果做比较，得到最优的数据结构设计。其次，本文将抽象的A*算法实例化，对算法进行适应实际应用的扩展，并对实际中出现的各种问题进行研究和探讨，设计出相应的解决方案，并设计一个小型的演示程序，使优化后的A*算法应用于实际的地图寻径中，实现真实的地图寻径程序，对理论做出验证，达到本文所提出的目标，弥补目前对这方面研究的欠缺，对后人有一定的借鉴意义。

目录

文摘

英文文摘

声明

第1章 绪论

1.1 课题的背景及意义

1.2 研究现状

1.3 研究目的及内容

1.4 论文的组织结构

第2章 搜索算法简介

2.1 概述

2.2 状态空间

2.2.1状态空间描述

2.2.2状态图示法

2.2.3显式状态空间搜索

2.3 传统搜索算法

2.3.1回溯法

2.3.2宽度优先搜索

2.3.3深度优先搜索

2.4 启发式搜索算法

2.4.1启发式搜索的必要性

2.4.2评价函数

2.4.3有序搜索算法

2.4.4 A*算法

2.5 A*算法在地图寻径中的应用

2.6 本章小结

第3章 A*算法数据结构的改进

3.1 A*算法过程分析

3.1.1地图结构设计

3.1.2 A*算法过程

3.1.3分析结论

3.2 传统的数据结构设计

3.2.1常用数据结构简介

3.2.2传统A*算法数据结构的分析

3.3 数据结构的改进

3.3.1设置标志代替查找

3.3.2哈希表简介

3.3.3两个原理

3.3.4新的数据结构的设计

3.4 算法测试

3.4.1测试软件的设计

3.4.2测试结论

3.5 本章小结

第4章 A*算法的应用

4.1 寻径协调算法

4.1.1寻径协调算法的需要性

4.1.2寻径协调算法的设计

4.2 测试软件的设计

4.2.1界面设计

4.2.2程序设计

4.3 测试结论

4.4 本章小结

结论

参考文献

致谢