基于Flash 3D技术的浙江财经学院漫游系统的研究

谢杨洁++张钊维++叶鹏飞++杨瑶瑶

摘要：本文首先提取三维虚拟漫游场景的特征向量，在此基础上进行路径选择，并提出基于A*算法的优化方案。该方案将提取的特征向量离散化为二进制信息单元，以欧拉距离为基础结合橡皮条算法进行启发函数的优化选取。

关键词：A*算法 规避障碍 最短路径 栅格化

中图分类号：TP311.52 文献标识码：A 文章编号：1007-9416（2014）08-0099-02

3D漫游动画技术是继多媒体技术之后的21世纪代表性技术。基于Flash3D技术的校园3D漫游系统将使观察者逼真的感受到校园场景分布，地图导游，充分感受校园的美好风光。而许多漫游系统都缺乏高效性，用户在使用过程中会碰到大量的延迟。本文主要讨论优化漫游过程中的路径选择算法，以提高漫游系统的效率和速度。

1 漫游环境的表示

漫游环境的表示是将现实3D环境转换成虚拟环境的过程。对虚拟环境的表示基本上有4 种方法[1]：①障碍物的多边形表示；②无障区域的表示；③均匀网格方法；④路径图。而无障区域的表示与路径图被公认为不适于表示复杂的3D环境，另外Schwartz和Sharir[2]曾经在报告中指出在3D情况中，多边形表示方法的运行时间复杂度会达到指数级。因此，大多数的3D虚拟环境的表示都选择了网格表示法。本文中我们将采用的正是二进制网格表示的方法。其实质为通过对虚拟环境的栅格化实现从模拟信息到数字信息的转化。

1.1 环境栅格化

人物的行走只是发生在地面的二维平面上，所以在研究碰撞检验时，地面的占据情况足够来表示行走的可行性。基于规矩形的栅格单元，首先提取三维虚拟场景特征向量，对其进行均匀网格化，并用二进制来表示特征向量的信息。根据一般的制图习惯，将图形的左下角的顶点作为坐标原点，而以坐标原点出发水平向右为水平方向（X轴）正方向，以坐标源点出发竖直向上为垂直方向（Y轴）正方向。每一个单元格用一个二维数组map[i][j]表示，map[i][j]的值为在X轴正上方j个单元，在Y轴正右方i个单元所存储的环境信息。map即为我们所建立的数字地图。对于静态环境，这种离散只需要执行一次。

1.2 障碍物的二进制表示

对于任何一个单元点均包含自己的特定值。其中，当值为0的时候表示在虚拟三维环境中，该点是可以通行的。相反，当值取1的时候则表示该点已被占据。即对于任意一个单元格中的值，我们可以用下列表达式进行描述

由此可见，针对已知的虚拟环境如图1-1，对其进行栅格化，我们可以得到如图1-2的结果。

转化后的图形依旧保持三维影像的平面感，在进行数据处理时需要将平面按顺时针进行45°的旋转。如图1-3。

2 算法描述

2.1 算法定义

A*算法是一种静态网格路径求解最短路径最有效的方法。算法实际上可以理解为一种贪心的过程，每个阶段都要使用贪心的思想来寻找代价最小的路径。使用合适的启发函数可以高效地找出两点之间的最佳路径。事实上，A*算法的关键部分正是启发函数，这个启发函数不是由 A*算法本身决定的，而是根据实际情况进行自主选择。也正是这种特性使得A*算法具备更强的可移植性和适用性。

2.2 估价函数

A*算法的估价函数的形式为一个简单的加法表达式

，

其含义为x点到出发点的代价。其中h（x）表示x点到出发点的估计代价，而g（x）则表示x点到起点的实际代价，是一个确定常数值。凡是一定能找到最佳求解路径的搜索算法称为可采纳的（admissible），数学上已严格证明A*算法是可采纳的。其充要条件是：对任意结点n，都有，

h（n）是n到目标的实际最短距离[3]。这时，也称h（n）是可采纳的且必然存在。

A*算法的选择原则为启发函数必须可纳，否则算法将无法保证最后的解是最优的。在启发函数可采纳的前提条件下应尽量使h（x）的值接近h（x）导数的值。在h（x）=0情况下，A*算法将完全退化成一般深度搜索的dijkstra算法，虽然能找到最优解，但是失去启发式搜索的启发信息。所以在估价函数的选择过程中应尽量使。

因此，对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即

如图2-1。这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。但是在模拟现实的环境中必然存在障碍物，而对障碍物的规避会不可避免的导致代价的增大。所以单纯的欧拉距离会直接导致估计代价小于实际代价而致使算法不可采纳。为此，本文采取基于欧拉路径的优化路径，如图2-2。步骤如下：

Step1：选取原点与目标点的欧拉距离。

Step2：若遇到障碍物，沿着障碍物的边沿到达障碍物边界。

Step3：以新到达的边界点为原点，重复步骤1和步骤2直到到达目标点。

表面上来看，优化欧拉的计算繁琐复杂，点与点之间的估计代价不能一下子确定。但是对于一个静态环境而言，点与点之间的估计代价是可以确定的，即启发函数值的计算只要进行一次即可。所以只好做好前序工作，就可以使路径的寻找更加准确高效。优化后的路径和橡皮条算法[4]所得到的路径有类似之处，但相比之下该路径会更短。

2.3 算法的实现

算法实现的过程可用以下步骤简要描述：

Step1：设置两个顶点集合T和S。其中，S中存放已找到最短路径的顶点。初始状态时，集合S中只有一个顶点，即原点V0；T中存放当前还未找到最短路径的顶点；

Step2：求得从S中的顶点到T中的顶点的所有路径中代价最小的路径，假设该节点为Vk。将Vk加入到顶点集合S中。endprint

Step3：继续重复步骤2，直到所有顶点都加入到集合S中，或从集合S中的任意顶点出发到集合T中的任意顶点都不存在可行路径。

为了实现以上步骤来完成最短路径的搜索，除了以上的S与T集合以为，另外需要设置2个关键数组。

（1）fval[i]：表示当前找到的从原点V0到终点Vi的最小代价、初始状态下，fval[i]为gval[V0][i]，为邻接矩阵的第V0行，表示V0点到终点Vi的实际代价。

（2）path[i]：表示在最短路径顶点Vi的前一个顶点号。对于后期实现路径的可视化至关重要。

其中，最关键的核心数组是fval[ ]。通过对fval的递推修改，时刻更新保存最小代价。其递推公式如下：

初始：fval[k]=gval[V0][Vk]，V0为原点

由此可见，对于每次查找我们需要对fval[i]做反复操作：

Step1：在fval里查找属于S集合并且fval[i]值最小的节点u。

Step2：将u加入集合S。

Step3：修改其他顶点的fval及path。当节点k属于S，同时节点k可以直接到达节点u，即在k与u之间至少存在一条可行路径并且fval[u]+g[u][k]

3 结果测试

3.1 测试环境

本次算法研究的测试环境为CodeBlocks 8.02。以一个8*8的网格作为虚拟环境测试。其中，障碍物占据8个连续的单元块。测试的结果只输出算法所选择的最短路径，如A->C->D->B。另外，在满足多元规划的同时必然满足单元规划，所以这里单元测试不再进行。根据输出的路径，我们进行人工制图检测算法的可行性。

3.2 测试

测试条件：测试数据规定A处出发，需要达到的点为B，C，D。

算法求得路径为：A->B->C->D。（如图4-3所示）

4 结语

本文提出了在虚拟障碍环境中进行全局漫游的路径规划算法。该方法以提取的特征向量为基础，通过二进制信息存储的方式对其进行离散化，结合启发函数的优化实现基于A*算法的多元路径选择。但目前算法只是停留在针对静态环境的搜索，对于动态的环境还要进行下一步的研究。

参考文献

[1]Jones L A， Lang J H. A state observer for the Permanent-Magnet Synchronous Motor [J]. IEEE Trans. on Industrial Electronics

（S0278-0046），1989，36（3）：374-382.

[2]Chen S， Nahrstedt K. Distributed QoS Routing with Imprecise State Information. In Proceedings of 7th IEEE International Conference on Computer， Communications and Networks （ICCCN'98）， Lafayette， LA， 1998，10：614-621.

[3]钟敏.A*算法估价函数的特性分析[J].武汉工程职业技术学院学报，2006，6：31-33.

[4]陈勇，王栋，陈戈.一种三维虚拟场景自动漫游的快速路径规划算法[J].系统仿真学报，2007，7：2507-2554.

Step3：继续重复步骤2，直到所有顶点都加入到集合S中，或从集合S中的任意顶点出发到集合T中的任意顶点都不存在可行路径。

为了实现以上步骤来完成最短路径的搜索，除了以上的S与T集合以为，另外需要设置2个关键数组。

（1）fval[i]：表示当前找到的从原点V0到终点Vi的最小代价、初始状态下，fval[i]为gval[V0][i]，为邻接矩阵的第V0行，表示V0点到终点Vi的实际代价。

（2）path[i]：表示在最短路径顶点Vi的前一个顶点号。对于后期实现路径的可视化至关重要。

其中，最关键的核心数组是fval[ ]。通过对fval的递推修改，时刻更新保存最小代价。其递推公式如下：

初始：fval[k]=gval[V0][Vk]，V0为原点

由此可见，对于每次查找我们需要对fval[i]做反复操作：

Step1：在fval里查找属于S集合并且fval[i]值最小的节点u。

Step2：将u加入集合S。

Step3：修改其他顶点的fval及path。当节点k属于S，同时节点k可以直接到达节点u，即在k与u之间至少存在一条可行路径并且fval[u]+g[u][k]

3 结果测试

3.1 测试环境

本次算法研究的测试环境为CodeBlocks 8.02。以一个8*8的网格作为虚拟环境测试。其中，障碍物占据8个连续的单元块。测试的结果只输出算法所选择的最短路径，如A->C->D->B。另外，在满足多元规划的同时必然满足单元规划，所以这里单元测试不再进行。根据输出的路径，我们进行人工制图检测算法的可行性。

3.2 测试

测试条件：测试数据规定A处出发，需要达到的点为B，C，D。

算法求得路径为：A->B->C->D。（如图4-3所示）

4 结语

本文提出了在虚拟障碍环境中进行全局漫游的路径规划算法。该方法以提取的特征向量为基础，通过二进制信息存储的方式对其进行离散化，结合启发函数的优化实现基于A*算法的多元路径选择。但目前算法只是停留在针对静态环境的搜索，对于动态的环境还要进行下一步的研究。

参考文献

[1]Jones L A， Lang J H. A state observer for the Permanent-Magnet Synchronous Motor [J]. IEEE Trans. on Industrial Electronics

（S0278-0046），1989，36（3）：374-382.

[2]Chen S， Nahrstedt K. Distributed QoS Routing with Imprecise State Information. In Proceedings of 7th IEEE International Conference on Computer， Communications and Networks （ICCCN'98）， Lafayette， LA， 1998，10：614-621.

[3]钟敏.A*算法估价函数的特性分析[J].武汉工程职业技术学院学报，2006，6：31-33.

[4]陈勇，王栋，陈戈.一种三维虚拟场景自动漫游的快速路径规划算法[J].系统仿真学报，2007，7：2507-2554.

Step3：继续重复步骤2，直到所有顶点都加入到集合S中，或从集合S中的任意顶点出发到集合T中的任意顶点都不存在可行路径。

为了实现以上步骤来完成最短路径的搜索，除了以上的S与T集合以为，另外需要设置2个关键数组。

（1）fval[i]：表示当前找到的从原点V0到终点Vi的最小代价、初始状态下，fval[i]为gval[V0][i]，为邻接矩阵的第V0行，表示V0点到终点Vi的实际代价。

（2）path[i]：表示在最短路径顶点Vi的前一个顶点号。对于后期实现路径的可视化至关重要。

其中，最关键的核心数组是fval[ ]。通过对fval的递推修改，时刻更新保存最小代价。其递推公式如下：

初始：fval[k]=gval[V0][Vk]，V0为原点

由此可见，对于每次查找我们需要对fval[i]做反复操作：

Step1：在fval里查找属于S集合并且fval[i]值最小的节点u。

Step2：将u加入集合S。

Step3：修改其他顶点的fval及path。当节点k属于S，同时节点k可以直接到达节点u，即在k与u之间至少存在一条可行路径并且fval[u]+g[u][k]

3 结果测试

3.1 测试环境

本次算法研究的测试环境为CodeBlocks 8.02。以一个8*8的网格作为虚拟环境测试。其中，障碍物占据8个连续的单元块。测试的结果只输出算法所选择的最短路径，如A->C->D->B。另外，在满足多元规划的同时必然满足单元规划，所以这里单元测试不再进行。根据输出的路径，我们进行人工制图检测算法的可行性。

3.2 测试

测试条件：测试数据规定A处出发，需要达到的点为B，C，D。

算法求得路径为：A->B->C->D。（如图4-3所示）

4 结语

本文提出了在虚拟障碍环境中进行全局漫游的路径规划算法。该方法以提取的特征向量为基础，通过二进制信息存储的方式对其进行离散化，结合启发函数的优化实现基于A*算法的多元路径选择。但目前算法只是停留在针对静态环境的搜索，对于动态的环境还要进行下一步的研究。

参考文献

[1]Jones L A， Lang J H. A state observer for the Permanent-Magnet Synchronous Motor [J]. IEEE Trans. on Industrial Electronics

（S0278-0046），1989，36（3）：374-382.

[2]Chen S， Nahrstedt K. Distributed QoS Routing with Imprecise State Information. In Proceedings of 7th IEEE International Conference on Computer， Communications and Networks （ICCCN'98）， Lafayette， LA， 1998，10：614-621.

[3]钟敏.A*算法估价函数的特性分析[J].武汉工程职业技术学院学报，2006，6：31-33.

[4]陈勇，王栋，陈戈.一种三维虚拟场景自动漫游的快速路径规划算法[J].系统仿真学报，2007，7：2507-2554.