基于校园场景漫游系统的寻路算法设计

张国强 李军

（湖南涉外经济学院 信息科学与工程学院 湖南省长沙市 410081）

1 引言

在开发游戏项目时，寻路算法是其中一个不可或缺的重要组成部分。寻路算法的主要目的是在不同地形的限制下，寻找一条消耗代价值最低的路径，从而节省游戏内人物完成地点移动的时间和负担。Unity3D 自带的寻路算法，往往对全程路段都进行了算法规划，进而给CPU 运行带来了较大负担。使得大部分设备无法流畅运行本系统。本文基于此背景之下，引入A*寻路算法，重新对NavMesh 寻路功能，进行设计优化。

2 技术引入

2.1 A*算法简介

A*算法（A-Star），一种启发式，精确而又高效的直接寻路算法，基于传统的Dijkstra 寻路算法的优化改进，于1968年P.E.Hart、N.J.Nilsson 和B.RaPhael 发表的论文之中被提出，在相关领域中被广泛应用。在没有预处理的情况下，A*算法是最有效的直接搜索算法。其基本公式为：

（其中F(N)表示初始点经过N 到目标点寻路消耗值估计，G(N)表示从预构设最优集合，即状态空间中所获取的初始点到目标点N 的实际寻路消耗值，H(N)是从点N 到目标点的最优解的预估寻路消耗值）。

2.2 曼哈顿距离简介

在几何空间中，如何计算两点距离，将其引入并解决问题，显得至关重要，在几何度量空间学中，主要采用了欧氏距离和曼哈顿距离这两种距离来进行表示。曼哈顿距离：赫尔曼•闵可夫斯基，仅用两个点在坐标系上的轴差的绝对值来表示，在十九世纪，提出来的几何学用于，主要表示两个点在标准坐标系上的绝对轴距总和。

3 算法设计

3.1 寻路算法的分析

本文针对的Unity3D 引擎，如果全程使用其所自带的NavMesh寻路功能进行寻址。在每次进行寻址时，都会对起点到终点进行静态的全路程最短路径搜索，大大耗费了系统资源。A*算法在大部分情况下的处理效率都优于Dijkstra 算法，因此在角色点到各建筑物所在标识点之间的路径，优先采用A*算法来进行处理，这样能够有效提高寻址功能效率。在Unity3D 项目中，物体所呈现的坐标值基本为整数，因此在考虑到寻路算法时，会采用以曼哈顿距离为代价值的A*算法。

图1：算法设计思路

图2：三维空间内基于曼哈顿距离的领接节点

图3：三维空间寻路算法测试

由于是已经固定好的地图环境，且各大建筑之间存在着主流道路走法。所以将各大建筑物之间的路径进行线段划分，将线段两段为计算节点，以A*算法进行路线规划，并存入系统中。在进行路径导航时，先通过实时获取的坐标轴信息，对临近建筑坐标点进行寻路，到达后沿当前建筑和目标建筑的预存储道路进行前行。与NavMesh 组件相比较，主要减少了后期固定建筑点的寻址消耗，在长距离导航的情况下，可以减少大量系统资源（在选取目标地点建筑为临近建筑的时候，本算法和NavMesh 组件所耗资源相近）。

3.2 代价值函数设计

为了得到A*算法公式中的G(N)和H(N)，必须要计算出两点之间的距离，并以此小号作为节点所要考虑的优先级，因此编写了一个GetDistance()的方法，计算寻址所需两点之间的距离。

G(N)是实际代价值，即当前点和目标点的路径距离，由两点之间三维标准坐标轴的进行计算。

H(N)为估计代价值，即当前节点和目标点的路径代价估计，当前节点和G 计算而出的启发函数。

如在具体的应用环境下有特定的需求，可以重新设置A*算法公式下的代价函数G(N)和估计代价值H(N)的权重k1和k2。在默认情况下采用k1=k2=1 的权重比例。

3.3 寻路算法实现

如何构建并创造启发函数H（N），是A*算法和Dijkstra 算法的主要区别，以A*算法为核心思想，Unity3D 所规划的网格整数坐标点作为节点，设计一个关乎启发函数H（N）的优先级作为其选取的选取顺序，将有可能成为最小消耗路径的节点压入优先队列进行遍历，从而决定最小消耗值路径。具体设计思路如下和图1 所示：

（1）建立了两个集合，KeyList()（存储会参加竞争最小消耗值路径决策的位置点集合）和RbList()（存储不会参加竞争最小消耗值路径的位置点集合）。

（2）把初始位置节点（在操作界面中发起寻路的最近的网格整数坐标点）压入KeyList()，并将其优先级设置为0（最高级优先级）。

（3）若KeyList()为非空集合，选择KeyList()内优先级最高的节点K，对此节点K 进行判断。

若节点K 为寻路终点：从节点K 开始逐步回溯追寻其父节点，一直达到起点，并将返回的结果集反向调入到移动类之中，系统中的人物开始根据所寻找的最小消耗值路径进行路径寻址。

若节点K 非寻路终点：将节点K 从KeyList()删除，加入到RbList()中。随后并将节点K 附近所有的非RbList()集合内领接节点加入KeyList()并设置其父节点为节点K，并将其节点根据曼哈顿距离设置优先级，三维空间内领接节点如图2 所示，内部方块为节点K，外部6 方向方块为子节点。

3.4 导航系统实现

将所设计好的A*算法所倒序返回的节点集合，作为在实际环境中角色移动的唯一依据。创建PlayerNavigation()方法，在此方法下，完成基于A*算法的自动寻路。

（1）构建A-StarPoint 集合，用来接收其返回的节点集合。

（2）撰写Updata()方法，以0.7f 为实时刷新速率，获取角色X，Y，Z 三轴坐标。

（3）撰写Walk()方法，以A-StarPoint 集合是否为空作为依据，依据A-StarPoint 集合顶端节点，进行角色移动。角色在可行区域内，不断按照顶端节点进行移动，直至集合为空，则到达A*算法结束目的地。

（4）设计WalkMapping 类，用来预处理各大建筑之间的最短路关系。通过人工规划路线，将道路分割成线段的形式，并在线段路线两点，设立坐标点，以此为寻路节点，并通过A*算法预处理，将处理结果，以键值对的形式存放，两个建筑的特定路线因此被存储下来。

用户在寻路时，根据输入的实时地点和目标地点，先找到最近的建筑物特定坐标点信息，实时使用PlayerNavigation()方法，获取用户当前位置到建筑物特定坐标点的最优路径，待用户到达此建筑物特定坐标点后，调用WalkMapping 类里已存放好的建筑物之间移动路径，进行移动。

4 仿真实验测试

在Unity3D 引擎下，利用Probuilder 组件建立起1:1:1 的立方体块群，并在此上面引入本文所设计的本文算法与传统的Dijkstra算法进行对比。测试环境如图3（额外展示了被加入KeyList()集合和RbList()集合的节点所在方块，理论上参与的节点越少，效率越高，对系统资源的占用越少）所示。

通过选取初始节点的不同，使用两种寻路算法进行测试，测试数据如表1 所示。

表1：本文算法和Dijkstra 算法实验数据

从表中可以明显看出，本文算法的耗时要远低于Dijkstra，且在面对障碍性明显的路段时，本文算法比Dijkstra 的处理时所使用系统资源更少。根据测试过程中所展示的KeyList()和RbList()所用节点，发现在大多数情况下本文算法所遍历的节点更少。因此可以得出本文算法在时间复杂度和空间复杂度都是相对Dijkstra 算法更优的算法。

对于与处理好的WalkMapping 类，系统仅需存储其预定路线，需要的内存和时间极少，此次不做参与测试。

5 结语

Unity3D 引擎中的NavMesh 寻路组件被本文所设计的寻路算法所取缔，并后续引入到了校园场景漫游系统中，本算法针对其环境，更加迅速的寻找到最小消耗值路径，并且降低了系统的资源占用率，大大优化了程序在运行寻址功能时的系统开销，满足了所拥有的设备性能较为不足的用户群体，流畅使用导航功能的需求。但是知识浅薄，技术短缺，本算法仍有许多缺陷不足以及改进空间，后期应学习参考ARA*算法和D*算法对此算法进行改进优化，并考虑在静态搜索结束后，根据玩家指令所产生的非最小消耗值路径上的位移，进行实时路径演变处理，使其寻路效率更高、系统资源占用率更低且更加实时动态化，符合用户需求。