摘 要

导航能力是一个智能移动机器人的基本能力，路径规划则是导航技术的基础和重要组成部分。机器人利用已知的场景能够构建出自己能理解的环境地图，自己规划出一条从起始点到目标点的最优路线。导航能力和路径规划能力对于智能小车来说是一个必备的基本功能。它能是智能小车高效快速的到达目标位置，提高小车的工作效率，节省小车的工作时间。

本文针对一个中国古镇这一个虚拟场景，以鼠标点击的地方为目标点。同时结合室外环境的特点，遍历地图进行节点划分，通过遍历节点信息。进行路径分析并编程实现能够自动沿着最短路径从起点到终点的计算方法。

关键词：最短路径；虚拟场景；路径规划

Abstract

Navigation capability is the basic capability of an intelligent mobile robot, and path planning is the basis and important component of navigation technology. Robots can construct environment maps that they can understand by using known scenes, and plan an optimal route from the starting point to the target point by themselves. Navigation ability and path planning ability are essential basic functions for intelligent car. It can make the intelligent car reach the target position efficiently and quickly, improve the working efficiency of the car and save the working time of the car.

This paper aims at a virtual scene of an ancient Chinese town, where the mouse clicks. At the same time, according to the characteristics of the outdoor environment, traversing the map to divide the nodes, and traversing the node information. Path analysis and programming can automatically follow the shortest path from the beginning to the end of the calculation method.

Key words: shortest path; virtual scene; path planning

目录

第1章 绪论 1

1.1 研究背景及意义 1

1.2 国内外研究现状 1

1.2.1 虚拟技术国内外现状 1

1.2.2 路径规划研究的发展 2

1.3本文研究内容及结构安排 3

第2章 虚拟环境的创建 5

2.1虚拟环境仿真软件的选择 5

2.1.1虚拟仿真介绍 5

2.1.2 ProModel 5

2.1.3 Flexsim 5

2.1.4 Unity 3D 5

2.2地图的创建 6

2.2.1栅格法 6

2.2.2四叉树法 6

2.2.3可见点法 7

2.3虚拟场景的创建 7

2.4图的遍历方法 8

2.4.1 深度优先搜索 9

2.4.2 广度优先搜索 10

2.5小结 11

第3章 路径规划 12

3.1 路径规划算法研究 12

3.1.1 Dijkstra算法 12

3.1.2 Dijkstra算法分析 12

3.1.3 算法的改进 14

3.1.4 A星算法的提出 14

3.1.5 A星算法的实现 14

3.2 寻路算法的问题分析 15

3.3 A星算法的优化 15

3.4 小结 16

第4章 寻路算法运用于虚拟场景 16

4.1 虚拟场景下的问题分析 16

4.2 智能寻路算法在应用时的调整 16

4.2.1 地图预处理 16

4.2.2 路径的平滑处理 17

4.3寻路算法在虚拟现实场景下的应用 18

4.4基于虚拟场景的小车路径规划的实现 19

第5章 总结 21

5.1 毕业设计回顾 21

5.2 不足与展望 21

参考文献 23

致 谢 24

第1章 绪论

近年来，硬件增长速度越来越快，以及图像渲染引擎一直在不断更新。虚拟现实技术也吸引着来自其他越来越多的关注。随着智能AI技术的发展，如何在虚拟现实场景中实现路径规划的成为了越来越来门话题。本文讨论如何在虚拟环境中实现自动寻路算法，从国内外的研究现状出发，探讨如何在虚拟场景中更好的实现寻路算法。并且在虚拟环境中路径算法的遇到的问题进行描述和解决方案。探讨虚拟环境中路径规划需要改进的方向。

1.1 研究背景及意义

近年来，随着计算机硬件的飞速发展，图像处理技术已越来越先进。虚拟现实技术得到了较为快速的发展。在虚拟场景中，我们可以以3D的形式展示我们设计的世界。这个“世界”完全是可以在现实生活中的再现，也可以是顽强出于别人的想象世界。我们可以简单而有真实的表达出我们所的内容。正因为虚拟环境的迅速发展，现在虚拟世界已经渐渐的成为了人们离不开的一种必备技术。而在虚拟场景中的如何使路径规划更加实用，也是路径规划发展的必经之路。它在一定程度上决定着虚拟场景的功能的完善程度，也很大的程度上影响着用户的体验

另外，随着智能AI越来越先进，人工智能的应用领域也越来越广泛，更是推出了能够自动驾驶的自动驾驶的小车，虽然在现实生活中能自动驾驶的小车出现了一点小问题，导致它的推行遭到了延迟。不过在虚拟环境中，自动寻路功能越来受到别人的欢迎。通过虚拟仿真技术仿真出与现实相差不多的场景，然后去完成小车自动驾驶功能，是在这项功能还不够成熟之前研究的最好做法。因此如何将智能寻路算法合理的运用在虚拟场景中，将虚拟现实技术和人工智能技术更好的结合起来成为了智能技术发展的重要问题

1.2 国内外研究现状

1.2.1 虚拟技术国内外现状

虚拟现实技术在问世之后就受到了世界各国的好评。特别是发达国家更是对虚拟像是技术进行了深入的研究。虚拟现实技术在美国最先问世。而美国的虚拟现实技术也代表着这个世界上虚拟现实技术的最高水平。就目前而言，美国在该领域的研究主要集中在感知、用户界面还有软件和硬件四个方面。

美国曾经做过一个实验：将数据手套工程化，可以将它变成可用性比较高的产品。在约翰逊空间中心完成了空间站操纵的实时仿真。现在改实验室正在所做一个叫“虚拟行星探索”的试验计划。现在已经建立了航空、卫星维护VR训练系统，空间站VR训练系统，并且已经建立了可以供全国使用的VR的教育系统。

从上个世纪90年代的时候开始，因为虚拟系统具有很逼真的现实效果，美国率先将虚拟现实技术用于军事领域。到现在为止，美国军方常常用虚拟现实技术用来做以下四个方面；一通过虚拟现实技术去模拟战场系统，测设武器的杀伤范围和杀伤效果；二通过虚拟现实技术进行单兵模拟训练；三是模拟各个军队联合的演戏；四是通过虚拟现实技术对指挥员进行指挥训练。

虽然，我国目前的VR技术相比于一些发达国家有差距，但我国政府部门和科研单位已经开始对虚拟仿真进行了高度重视，对此，我国相关部门依据国情对VR技术制定了研究的计划。国家自然科学基金委员会携手国家高级技术研究发展计划在九五规划中确定了VR技术的研究项目。与此同时，国内重点院校都纷纷自发投入到了VR技术的研究工作。从西工大的电子工程系创建了我国首个开展VR技术研究的研究中心开始，国内其他学校和院系积极响应，各种研究中心如雨后春笋般成立，研究成果不断被发布出来

在早期对VR技术进行研究的各个机构当中，北京航宇航天大学计算机系依据自身强大的实力成为了该研究的权威之一。在硬件方面，他们不仅研究了VR技术的知识基础，还重点研究了物体的表示以及处理，并且在视觉接口上面有重大发现。除此以外，他们对软件部分也进行了深度探索，很多算法被逐步提出，还能够实现分布式的虚拟环境的网络设计。

不仅仅是在北京方面有突破，浙大重点实验室也取得了可喜的成就，该实验室自行开发了桌面虚拟环境实时的漫游系统。同时还提供了方便的交互工具，使得整个系统的实时性和画面感都上什了一个层次。另外他们在这方面还研究出一套新的快速漫游算法和网格的生成算法，大大的推动了虚拟现实技术的发展。

1.2.2 路径规划研究的发展

路径规划算法是一个上个世纪60年代就提出来的算法了。经过多年来的发展也越来越成熟。这种算法常常用于机器人、无人机等等领域，早期的路径规划算法是先将所需要的规划路径抽象成为一个图片。然后遍历图中的左所有节点以后，通过这个节点信息从图中找出来最优路径，这中算法虽然简单，但是却有着计算耗时长，存储空间大。而且计算不准确等等特点。

在上个世纪60年代，A星算法开始被证明出来这种方法在路径规划证的准确度和效率比较高。虽然当时的A星算法耗时间非常长，但是并不影响以A星算法广受欢迎，并且为它基础的各种衍生算法开始应用在虚拟场景的各个行业。

这个问题直到20年后，被Pang指出来，他在A星算法运行的过程中将之前遍历过的节点信息加入到了寻路算法的迭代过程中，从而使算法能够更快从当前节点找到目标节点。但是这样的利用寻路过程中的历史信息来寻路的算法还是有着很大的偶然性和盲目性。

在2004年，为了解决A星算法的问题，一种边缘的寻路算法被Koenig提出，边缘寻路算法的主要思路是将路径中需要遍历的节点放到两个列表当中，然后对这些节点进行删减处理。然而这种算法还是没有解决同一个节点会遍历很多遍的问题。

2008年，XiaoXunSun和Koenig以A星算法的改进算法为基础，设计了一个函数预估A星算法的代价，该算法可以通过自己遍历过的信息来预估当前的代价值。自此和近代相似的A星算法开始面世了。

随着VR技术的高速发展，人们对寻路算法的要求也越来越高，也许寻路算法到未来可能会越来越复杂，越来越难得理解。但是它一定会越来越快，计算的路径也越来越准确。同时还会有着其他不可思议的功能，来适应各个方面的要求。如今在虚拟仿真的场景里面合理的运用路径规划算法，是虚拟场景发展的一个必不可少的路径，同时也为路径规划算法带来了新的思路和挑战。

1.3本文研究内容及结构安排

本文研究了一种在虚拟环境中（中国古镇），在知道目标地点后，能从现在的位置沿着最优路径到达指定位置的智能小车。完成了对虚拟环境的创建，并且提出了一种基于全地图的路径规划算法。主要研究内容如下：

(1)对虚拟环境的坐标的处理：通过仿真软件创建的虚拟环境中，我们能够直接获取他们的坐标，通过创建列表的方式进行对坐标的存储或者运算。

(2)地形的处理：我们根据图像识别的原理，将我创建的虚拟环境地形网格化，在有障碍物里面的网格设置成不可以通过的隔层。然后在没有障碍物的网格里设置成可以通行的隔层，这样以来方便设置节点和进行最短路径的算法运行了。

(3)算法的选择：根据毕业设计的要求，将地形进行网格化以后，如果我们继续选用最初的Dijsktra算法的话，那么我们的计算量就会非常的打，而且需要的存储空间也非常的大。所以我选择了基于Dijsktra（迪杰斯特拉）算法的基础上提出来的一种新算法。来完成自动寻路的功能。

根据以上内容，本文结构安排下：

第一章介绍了本课题的研究背景和意义。描述了虚拟仿真技术的国内外现状以及寻路算法的发展做了简单的总结。阐述了本文的研究内容和结构安排

第二章介绍了常用的一些国内外虚拟仿真软件。并且选择出这次研究课题选择的虚拟仿真软件和选择该软件的理由，以及如何创建虚拟环境的方法。

第三章介绍了寻路算法的基本原理，分析了寻路算法的不足之处，并且对寻路算法提出了改进方案

第四章介绍了寻路算法如何运用在创建的虚拟环境当中，并且对地图进行了一些优化和对算法做出了一些平滑性处理。

第五章 对全篇论文进行了总结提出了本次论文中的不足和对未来的展望。

第2章 虚拟环境的创建

在智能机器人领域，智能AI能力的检测很大程度上依赖于虚拟环境的创建，研究虚拟环境的创建就是在研究智能AI在测试过程中出现一些问题的环境模拟。如果能够事先建立好良好的虚拟环境，那么之后的智能小车的路径规划测试都有很大的现实意义。相反的，如果我们事前不能很好的创建虚拟环境，那么智能小车在得到指令以后就不能准确的判断目标的位置和下一步的动向。另外，路径规划就只能成为纸上谈兵，不能运用于现实生活为人类服务了。 因此虚拟环境的创建是智能AI技术必不可少的一部分。

2.1虚拟环境仿真软件的选择

2.1.1虚拟仿真介绍

目前市面上的虚拟仿真软件百花齐放，不同的软件运用于不同的领域。如果用错了软件，那么虚拟环境的构建就变的非常的麻烦。而且做出来的仿真效果也不是非常的好。因此选择一个合适的虚拟软件往往会让自己达到事倍功半的效果。

2.1.2 ProModel

ProMode是通用的仿真软件，它除了可以用来仿真各种物流与供应链系统，还可以用来对其他各种领域的系统进行仿真，典型的如：生产系统、服务系统、交通运输系统等

2.1.3 Flexsim

Flexsim是一套系统仿真模型设计、制作与分析工具软件。它集计算机三维图像处理技术、仿真技术、人工智能技术、数据处理技术为一体，专门面向制造、物流等领域。

2.1.4 Unity 3D

Unity3D是由Unity Technologies开发的一个让使用者轻松创建诸如三维视频、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具，是一个全面整合的专业引擎。

考虑到在这次研究的过程中，我们不仅仅需要创造出一个虚拟环境出来，我们还要在上面计算出最短路径出来。而Unity 3D它不仅仅可以模拟出比较逼真的物理特性出来，它还可以在编辑的时候就能够看到效果。并且它的脚本语言为C#，这对于我们学过C 的学生来说，有着比较不错的优势。综合多种考虑，最终我选择了Unity3D作为我完成虚拟仿真的软件。

2.2地图的创建

虚拟场景中所有的路径规划算法都是基于场景地图的创建的，路径规划不仅仅考虑的是算法问题，还要考虑地图中的地形和障碍物与路径之间的关系。一个良好的地图的创建方法可以很大程度上减少路径规划算法的运行时间。在虚拟场景中，一般进行路径规划需要经过两个阶段。首先，虚拟场景的各个元素都是美工模型组合而成的，彼此之间并没有什么太大的联系。但是为了将算法合理的运用到场景上面，我们需要将地图抽象成图这种数据结构。因为对于图这种数据结构来说，有着很多的很成熟的搜索和遍历图片的算法。这样，可以将虚拟场景中的一些模型抽象成图片的顶点和边缘，方便之后的路径规划。在将虚拟场景转换成数据结构。第一阶段就算完成了。第二及阶段需要用合理的算法运用到图片之中完成路径算法。将虚拟现实场景抽象成图片的方法非常的多，但是:栅格法、四叉树法、可见点法这三种算法是最长见也是最常用的算法

2.2.1栅格法

栅格法是一个想法特别简单的方法，首先将场景的地图均匀划分成一些栅格，而每一个栅格都可以看成是这个图的一个顶点，之后的寻路算法都在这个图的结构里面进行。划分栅格的方式很灵活，可以根据图形的形状自行的调整栅格的形状。由于一般的图片都是矩形的。所以常见的还是用正方形将场景的地图划分成栅格的集合。

用正方形栅格法把地图均匀的划分成相同的正方形的网格。每一个正方形各自抽象成一个图的一个节点。如果当前格子障碍物的面积大于格子的百分之40，我们就认为这个节点是障碍物，就这个格子抽象出的节点为障碍点，设置成不可通行的节点。

从栅格法的划分来看，这中方法只适合用于比较简单的2D场景，因为场景如果越复杂，那么就需要划分出很多格子来，这样以来就需要非常大的内存来存储节节点。这样不仅仅消耗内存，也很大程度上影响算法的运算速度

2.2.2四叉树法

四叉树法是栅格法的一种改进算法，这种算法在栅格法的基础上，对栅格法进行的改进。改进了栅格法需要消耗大量存储空间去存储节点的问题，四叉树法对场景地图进行划分的时候不再是进行无差别的均匀划分。它根据场景中不同的地形特点会对着当前的格子进行进一步划分。将地形简单的地方运用大格子划分。复杂的地方对着大格子再进行划分，一直到格子里面只有一个元素为止。

2.2.3可见点法

可见点法和上面两种完全不同，它以关键点作为图的顶点来存储的，这样的话地图的存储只需要存储一些关键点就好了。这样以来可以有效的降低存储地图的空降。也因为这个原因。可见点法的关键点的设置非常的重要。因为这个方法如果关键点设置的不好，那么寻找出来的路径就不会是最短路径。另外这些关键点一般都是人工设置的，如果地图比较复杂的话。那么人为设置的关键点工作量就非常大。而且人工设置的关键点在一定程度上也不能保证算法的准确性。并不能保证它的寻找出来的路径就是真正的最短路径。

2.3虚拟场景的创建

本课题研究的是虚拟环境（中国古镇）的地图创建。在开发过程中，首先采用3Dmax进行建模，对古镇的各个区域进行分割。参看百度实景图比例，对中国的各个古代建筑分别进行建模。然后按照现代城市的规划方式将他们拼接在一起。在建模的过程中，充分考虑到资源利用问题，为了减去计算机不必要的负担，我在建模的时候只建了外形，而并没有对模拟内部进行构建。而对于仿真来说，通过贴图来提供模型的真实感。建模好以后，导出为.FOX格式，在导入Unity 3d进行组装，完成虚拟场景的创建。

图2.1中国建筑1（没有贴图）

图2.2中国建筑1（贴图之后）

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：