Flash平台上自动寻路(A)算法优化设计(5)
时间:2017-06-22 17:34 来源:毕业论文 作者:毕业论文 点击:次
（3） 拐角问题 在算法描述中有提到这样一个判断：拐角判断，检查与该邻节点同一列（或者行），与当前节点同一行（或者列）的节点是否为不可通过，如果为不可通过，则跳过继续处理下一个邻节点，否则继续。这里确切的含义指的是物体绕过一个障碍物的边缘时是否能抄近路，即：是否允许物体切过障碍物。本次设计选择不抄近路的策略。如下图所示 图 2.3 拐角问题示意图 此时A*寻路算法进行的步骤是，检查当前节点的周围邻节点的情况，根据不同的情况做出不同的选择和处理。其中黑色点代表当前节点，灰色区域代表正在检查的节点。如果不加处理，则灰色的节点会被添加进开启列表中，并且他的父节点会指向黑色节点，路径也就变成了超近路的情况。 处理方法： 检查与该邻节点同一列（或者行），与当前节点同一行（或者列）的节点是否为不可通过。如下图所示。这样在遇到拐角的情况时，当前节点不会把图中灰色节点的父节点指向自己，从而避免了拐角走斜线的问题。 图 2.4 拐角问题的解决方法示意图 （4） 代价问题 由A*寻路算法的所得出的最佳路径不仅仅指最短路径，更加确切的含义是指代价最小的路径。每个区块可以为其设置相应的代价系数，在计算区块代价时，乘上这些系数，这样就会产生人物绕过森林，选择陆地行走的效果。在这里有2种策略： 图 2.5代价问题示意图 1. 如果人物进入了森林（人物已经在森林中了，此时开始寻路），则他会在森林中寻找最佳路径而不去考虑外面的公路，但如果人物是从森林外开始寻路，则他会绕过森林走公路。这种策略表现起来比较自然，但需要添加一些逻辑判断。 2. 如果人物进入了森林，当外界有公路时，他会优先考虑走出森林沿着公路走。这种策略实现起来比较简单，但是表现不是很自然。 本次设计选用第二种策略。 （5） A*类的使用 A*类使用流程描述： 1. 新建一个Grid数据类型，通过构造函数设置区块图的列数和行数。 2. 设置每个节点的是否可达以及代价。节点默认是可达的，代价系数为1。 3. 设置起点和终点。 4. 实例化一个Astar类型，将Grid类型放入Astar的findPath(grid:Grid) :Boolean，读取结果，如果返回值是false，则没有产生路径，如果返回值是true则有路径产生，读取Astar类实例的path属性。 5. 通过循环读path数组，并且读取每个项的x和y属性。 图 2.6 A*类使用流程图 2.2 模块划分 2.2.1 前台模块 （1） 模块设计概述 寻路程序划分为3个模块：地图显示模块，数据加载存储模块，人物控制模块，分别对应3个主要的类：GameView，GameData，GameController。文档类（flash中对于当前编译类的一种说法）的构造函数在运行时，实例化3个类的对象，并且通过每个类所提供的方法，实现外部数据读取以及地图和人物的加载、人物的鼠标、寻路控制。 通讯程序主要功能有：与FMS服务器socket连接模块、与MySQL数据库操作模块。Socket使用自定义的报文协议。协议中包含玩家移动的起点和终点以及聊天交互时候的消息报文内容。MySQL和客户端时间使用PHP来交互通讯。 （2） 数据加载模块 数据加载存储模块主要负责外部数据的加载、存储，地图数据模型的构建以及A*寻路算法所使用的数据模型的构建。主程序首先会调用这个类中的loadMap方法加载存放地图信息的XML文件，监听数据加载完成事件。在完成事件发生后进行显示、人物添加操作。对应类是GameData。 (责任编辑：qin) |