摘 要

作为计算机仿生学的重要组成部分，人工智能技术在众多领域都有广泛的应用，如：虚拟现实、仿生机器人、游戏领域等。这些领域都有虚拟角色的存在，它们拥有自主的行为模式，通过与用户的交互提供好的使用体验。

无论是游戏开发者还是玩家，都越来越重视游戏中虚拟角色的智能性，寻路问题是人工智能应用于游戏时要解决的基本问题之一。为了实现在大型3D场景游戏中的智能寻路，提高游戏的交互性与娱乐性，本文对智能寻路技术的现状进行了讨论，从智能寻路的两个阶段（场景地图表示和路径搜索）对现在比较流行的几种智能寻路技术进行了对比分析并选择一个较为合适的方案。通过几种寻路技术的多方面对比，我决定使用A^*算法来实现用栅格法表示的场景的智能寻路，并用C#语言进行编程。随着游戏行业的迅猛发展，A^*算法基于栅格法的寻路方式也难以适应日益复杂的大型3D游戏场景，所以本文最后针对这种算法在复杂场景下可能出现的问题提出一些改进方向，并对智能寻路技术未来的发展趋势进行了讨论。

关键词：智能寻路技术；场景地图；路径搜索

Abstract

As an important part of computer bionics, artificial intelligence technology in a wide range of applications are widely used, such as: virtual reality, bionic robots, games and so on. These areas have the presence of virtual roles, they have an autonomous behavior model, through the interaction with the user to provide a good experience.

Whether it is game developers or players, are increasingly concerned about the virtual role’s intelligence of the game, pathfinding-problem is one of the basic problems need to solve those the application of artificial intelligence in the game. In order to realize the intelligent pathfinding in the large-scale 3D scene games and improve the interactivity and entertainment of the game, this paper discusses the current situation of the intelligent pathfinding technology, and compares several kinds of popular intelligent pathfinding techniques from two stages of intelligent routing (scene map representation and path search) and choose a most suitable scheme. By comparing several aspects of pathfinding technology, I decided to use the A * algorithm to achieve intelligent pathfinding based on the grid method, and use C # language to programming. With the rapid development of the game industry, it is difficult to use A * algorithm based on the grid method to adapt to the increasingly complex large-scale 3D game scenes, so at the end of this article,it mentions algorithm in the complex scene may present some improvement direction, and the future development trend of intelligent pathfinding technology is discussed.

Key Words:intelligent pathfinding technology;scene map;path search

目录

摘要 Ⅰ

Abstract Ⅱ

第1章 绪论 1

1.1 引言 1

1.2 研究现状 1

1.3 研究内容 2

第2章 相关软件的介绍 3

2.1 unity 3D介绍 3

2.1.1 unity 3D基础知识 3

2.1.1.1 游戏对象和组件 4

2.1.1.2 脚本 4

2.1.2 unity 3D的特点 4

2.2 3d Max建模软件的介绍 5

2.2.1 3d Max基础知识 5

2.2.1.1 3d Max的界面介绍 5

2.2.1.2 视口介绍 6

2.2.1.3 坐标介绍 6

2.2.1.4 视图介绍 7

2.2.2 3d Max的优点 8

2.3 本章小结 8

第3章 方案的对比分析 9

3.1 场景地图的表示方法 9

3.1.1 栅格法 9

3.1.2 单元树法 9

3.1.3 可见点法 10

3.1.4 导航网格法 10

3.1.5 方法对比与选择 11

3.2 路径搜索技术 12

3.2.1 盲目式搜索技术 12

3.2.1.1 广度优先搜索算法 12

3.2.1.2 深度优先搜索算法 12

3.2.2 启发式搜索技术 13

3.2.2.1 Dijkstra算法 13

3.2.2.2 Floyd动态规划算法 13

3.2.2.3 A*算法 14

3.2.3 算法对比与选择 14

3.3 本章小结 15

第4章 算法的仿真 16

4.1 导入模型与算法的流程 16

4.1.1 将3d Max模型导入unity 3D 16

4.1.2 将C 的代码嵌入到Unity3D 16

4.2 寻路算法的仿真 16

第5章 结论 18

5.1 研究总结 18

5.2 发展趋势展望 18

参考文献 19

附录A 20

致谢 22

第1章 绪论

1.1 引言

近年来，随着人工智能的兴起，运用人工智能来解决问题已经成为众多领域的热门研究课题，游戏领域也不例外。在游戏设计中，游戏开发者越来越重视虚拟角色行为的智能性与可靠性。虚拟角色的寻路问题是游戏领域的一个重要问题，智能寻路技术在其中的应用对于增加游戏的逼真性、提高游戏的娱乐性和可玩性以便吸引玩家有着至关重要的作用。

随着大型3D游戏的风靡，虚拟角色的智能性与逼真性成为吸引玩家的重要因素，复杂的游戏场景使虚拟角色的寻路面临巨大的挑战。为了增加游戏的逼真性与智能性，我们需要解决智能寻路这一基本问题。路径搜索技术中，A*算法是最高效、消耗内存最少的算法，因此，基于栅格法的地图表示的A*算法是目前使用最广泛的寻路算法，本文主要讨论了这种算法。

1.2 研究现状

由于日本及一些欧洲国家的起步较早，国外游戏产业正处于黄金发展期，游戏特别是手机游戏早已渗透进人们的生活，成为文化产业重要的组成部分，拉动国民经济的发展。相对于国外，随着我国经济的飞速发展以及电子产品硬件、互联网的发展，我国的游戏产业也处于高速发展时期，再加上国家相关政策的扶持，我国的游戏产业步入正轨，在经济增长中展现出强劲动力^[1]。寻路问题是人工智能在游戏中要解决的基本问题之一，智能寻路也是游戏中虚拟角色需要具备的能力之一，游戏场景的复杂性以及计算机资源本身的限制使得智能寻路成为极具挑战性的任务。虚拟角色通常需要满足可靠、高效、逼真等要求，但是这些特点在实现的过程中往往互相冲突，所以我们必须在所有方案中有所取舍，选择能较好地满足以上要求的方案。

智能寻路分为两个阶段：场景地图的表示和路径搜索。目前，使用比较多的场景地图表示法包括：栅格法、单元树法（四叉树、八叉树）、可见点法以及导航网格法等，路径搜索算法有盲目式搜索算法和启发式搜索算法。由于盲目式搜索算法的效率不高，主要采用启发式搜索算法。启发式搜索算法主要有Dijkstra算法、Floyd动态规划算法以及A*算法，其中使用最广泛、效率最高的是A*算法。随着大型游戏中越来越复杂的场景的出现，将遗传算法等人工智能技术用于游戏正成为研究热点。

1.3 研究内容

本次研究以Unity 3D场景下的虚拟角色为对象，对游戏开发过程中的智能寻径相关技术进行研究。在介绍了研究背景、目的以及相关游戏开发引擎和建模软件，分析了游戏设计中的寻路思想以及对比了多种路径搜索算法在搜索策略、时间效率、空间消耗与应用场合等各方面的特点后，本论文最终决定选择应用最广泛的基于栅格法的A*算法，并用C#调用C 程序在unity 3D环境下对该算法进行了仿真。

第2章 相关软件的介绍

2.1 unity 3D介绍

对于游戏来说，游戏引擎就是游戏表现的核心，本次使用的是unity 3D游戏引擎。Unity 3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具，支持多种脚本语言编辑和线上游戏的开发，是一个全面整合的专业游戏引擎。Unity 3D类似于Director,Blender game engine, Virtools 或 Torque Game Builder等利用交互的图型化开发环境为首要方式的软件，它可以发布游戏至Windows、Mac、Wii、iPhone、WebGL(需要HTML5)、Windows phone 8和Android平台，也可以利用Unity web player插件发布网页游戏，支持Mac 和Windows的网页浏览，而且它的网页播放器也被Mac widgets所支持^[2]。

2.1.1 unity 3D基础知识

在unity 3D游戏引擎下，游戏开发主要分为两个部分：一部分是在编辑器上进行资源的编辑，另一部分是使用脚本对资源进行控制，使其执行相应的行为。图2.1所示为unity 3D的主菜单。