基于多边形导航网格地图的改进A * 算法
发布时间：2021-03-31 03:09
针对A*寻路算法在大型地图中搜索路径结点过多、搜索效率过低的问题,提出一种基于多边形导航网格的改进A*算法。首先利用建模工具对地图中障碍物进行剔除,生成可行走域的多边形导航网格;其次对多边形网格进行Delaunay三角剖分,形成三角导航网格,利用二叉堆对A*算法所使用的数据结构进行优化,采用目标范围界限方法对导航网格进行预处理,并将处理A*算法的启发函数进行改进以适用于多边形导航网格,对多边形导航网格生成路径利用漏斗算法进行路径平滑处理,生成实际最优路径;最后利用Unity3d游戏引擎搭建地图寻路实验平台,对比分析算法的性能差距。实验证明,基于多边形导航网格改进A*算法在大型地图中的搜索效率明显高于基于传统方格地图A*算法。
【文章来源】：软件导刊. 2019,18(01)
【文章页数】：5 页
【部分图文】：
地图Delaunay三角剖分
髡??直至满足二叉堆的堆序性。利用二叉堆存储Open列表可快速插入和删除列表中邻居结点，从而提高A*算法的搜索效率。2.3基于目标范围界限的优化目标范围界限是一种在预处理地图信息时快速划分目标点的方法，核心思想是预先计算一个边界框，其中包含所有通过探索其边达到目标最优路径的结点。在进行地图预处理时，对应边界框的参数也相应被存储。当运行寻路算法时，可以实时读取存储边界框的参数，从而只需要对目标结点所处目标范围边界框内的结点进行考察，从而减少所搜索的结点数量，提高搜索效率。图3多边形网格地图目标范围界限计算目标范围界限的方法为：（1）定义选取起始点邻接方向的邻居结点，如图3（a）所示，起始结点分别有A、B、C等3个邻接方向。（2）利用Dijkstra算法遍历邻接方向所有结点，记录从起始点出发进行该方向探索的最优路径点，并作标记。如图3（a）中标记C的三角网格结点，探索下方网格，只有通过标记C的网格才是该方向最优路径的网格结点。（3）当计算完所有网格结点时，划分生成目标结点的范围界限，并且存储在相应文件中。（4）在运用寻路算法之前，读取文件中的目标界限参数，寻路算法只需对目标点所在目标范围界限中的结点进行考察。3优化A*算法实现优化后的A*算法，同样适用于多边形导航网格。方格地图网格都是规则的正方形网格，因此在计算网格距离时，只需要计算网格中心点之间的距离。与方格网格地图不同，经Delaunay剖分所形成的三角网络导航网格具有不朱昌龙，刘黎志：基于多边形导航网格地图的改进A*算法··19
软件导刊2019年规则性，导致G（n）值和h（n）的计算不能统一。因此，为了统一三角网格自身耗费以及提高估价函数的准确性，需要对G（n）值和h（n）的计算方法加以改进。改进策略：G（n）为当前三角网格至下一个网格代价总和，H（n）为三角形中心到目标三角中心的距离。如图4，三角网格自身代价为穿入边AB中点至穿出边AC中点的距离。g(n)=12(x3-x22)2+(y3-y22)2（4）改进后的A*算法如下：输入：ΔS/*起始点，ΔE/*终点输出：PathΠ（ΔS，ΔE）（1）CreateOpenlist，Closelist；（2）WithinBoundingBox（Δ（s），goal））；//搜索在目标点所在目标范围界限内的邻居结点（3）foreachΔ（n）inneighbor（Δs）｛//遍历在目标范围内，起始点的所有可到达的邻接三角网格（4）AddΔ（n）inOpenlist，AddΔsinCloseList；（5）While（Openlist！=null）｛（6）MinHeuristic（Δ（m））inOpenlist；//从Open列表中取出估值F最小的结点Δ（m）（7）if（Δ（m）==Δ（e）｛Break；｝（8）foreach（Δ（m）的每个子结点Δ（X））｛；（9）if（Δ（X）inOpenList）｛（10）if（MinHeuristic（Δ（X））inOpenlist==true）（11）SetΔ（m）asParentNode；Update｝//设Δ（m）为Δ（X）的父结点（12）else
【参考文献】：
期刊论文
[1]基于三角形细分的三角网格模型表面体素化算法[J]. 赵芳垒,敬石开,李向前,邢昊,刘晨燕,宋国华. 计算机集成制造系统. 2017(11)
[2]各向同性三角形重新网格化方法综述[J]. 严冬明,胡楷模,郭建伟,王逸群,张义宽,张晓鹏. 计算机科学. 2017(08)
[3]Dijkstra最短路径算法的堆优化实验研究[J]. 张翰林,关爱薇,傅珂,孙廷凯. 软件. 2017(05)
[4]引入导航网格的室内路径规划算法[J]. 林巍凌. 测绘科学. 2016(02)
[5]利用堆排序优化路径搜索效率的分析[J]. 孙玉昕,章瑾. 武汉工程大学学报. 2013(06)
[6]基于DAF算法的地图寻径研究[J]. 陈娜,黄明和,刘清华. 科学技术与工程. 2010(30)
[7]基于地图分割与以矢量信息描述地图的A*寻路算法[J]. 李立,唐宁九,林涛. 四川大学学报(自然科学版). 2010(04)
[8]一种基于导航网格的路径搜索技术[J]. 王天顺,张莉. 电脑知识与技术. 2010(12)
[9]游戏开发中智能路径搜索算法的研究[J]. 何国辉,陈家琪. 计算机工程与设计. 2006(13)
[10]平面多边形域的快速约束Delaunay三角化[J]. 曾薇,孟祥旭,杨承磊,杨义军. 计算机辅助设计与图形学学报. 2005(09)
硕士论文
[1]基于综合导航网格的智慧旅游动态寻径方法[D]. 王烨萍.西南交通大学 2017
[2]游戏中的智能路径搜索算法及其应用[D]. 李井颂.昆明理工大学 2017
[3]游戏场景中分层寻路算法及地图复杂性度量研究[D]. 周振华.河北大学 2014
[4]游戏地图寻路及其真实性研究[D]. 韩玮.西南大学 2013
[5]人工智能寻路算法在电子游戏中的研究和应用[D]. 詹海波.华中科技大学 2006
[6]基于A*算法的地图寻径的研究[D]. 张前哨.武汉科技大学 2005
本文编号：3110667
【文章来源】：软件导刊. 2019,18(01)
【文章页数】：5 页
【部分图文】：
地图Delaunay三角剖分
髡??直至满足二叉堆的堆序性。利用二叉堆存储Open列表可快速插入和删除列表中邻居结点，从而提高A*算法的搜索效率。2.3基于目标范围界限的优化目标范围界限是一种在预处理地图信息时快速划分目标点的方法，核心思想是预先计算一个边界框，其中包含所有通过探索其边达到目标最优路径的结点。在进行地图预处理时，对应边界框的参数也相应被存储。当运行寻路算法时，可以实时读取存储边界框的参数，从而只需要对目标结点所处目标范围边界框内的结点进行考察，从而减少所搜索的结点数量，提高搜索效率。图3多边形网格地图目标范围界限计算目标范围界限的方法为：（1）定义选取起始点邻接方向的邻居结点，如图3（a）所示，起始结点分别有A、B、C等3个邻接方向。（2）利用Dijkstra算法遍历邻接方向所有结点，记录从起始点出发进行该方向探索的最优路径点，并作标记。如图3（a）中标记C的三角网格结点，探索下方网格，只有通过标记C的网格才是该方向最优路径的网格结点。（3）当计算完所有网格结点时，划分生成目标结点的范围界限，并且存储在相应文件中。（4）在运用寻路算法之前，读取文件中的目标界限参数，寻路算法只需对目标点所在目标范围界限中的结点进行考察。3优化A*算法实现优化后的A*算法，同样适用于多边形导航网格。方格地图网格都是规则的正方形网格，因此在计算网格距离时，只需要计算网格中心点之间的距离。与方格网格地图不同，经Delaunay剖分所形成的三角网络导航网格具有不朱昌龙，刘黎志：基于多边形导航网格地图的改进A*算法··19
软件导刊2019年规则性，导致G（n）值和h（n）的计算不能统一。因此，为了统一三角网格自身耗费以及提高估价函数的准确性，需要对G（n）值和h（n）的计算方法加以改进。改进策略：G（n）为当前三角网格至下一个网格代价总和，H（n）为三角形中心到目标三角中心的距离。如图4，三角网格自身代价为穿入边AB中点至穿出边AC中点的距离。g(n)=12(x3-x22)2+(y3-y22)2（4）改进后的A*算法如下：输入：ΔS/*起始点，ΔE/*终点输出：PathΠ（ΔS，ΔE）（1）CreateOpenlist，Closelist；（2）WithinBoundingBox（Δ（s），goal））；//搜索在目标点所在目标范围界限内的邻居结点（3）foreachΔ（n）inneighbor（Δs）｛//遍历在目标范围内，起始点的所有可到达的邻接三角网格（4）AddΔ（n）inOpenlist，AddΔsinCloseList；（5）While（Openlist！=null）｛（6）MinHeuristic（Δ（m））inOpenlist；//从Open列表中取出估值F最小的结点Δ（m）（7）if（Δ（m）==Δ（e）｛Break；｝（8）foreach（Δ（m）的每个子结点Δ（X））｛；（9）if（Δ（X）inOpenList）｛（10）if（MinHeuristic（Δ（X））inOpenlist==true）（11）SetΔ（m）asParentNode；Update｝//设Δ（m）为Δ（X）的父结点（12）else
【参考文献】：
期刊论文
[1]基于三角形细分的三角网格模型表面体素化算法[J]. 赵芳垒,敬石开,李向前,邢昊,刘晨燕,宋国华. 计算机集成制造系统. 2017(11)
[2]各向同性三角形重新网格化方法综述[J]. 严冬明,胡楷模,郭建伟,王逸群,张义宽,张晓鹏. 计算机科学. 2017(08)
[3]Dijkstra最短路径算法的堆优化实验研究[J]. 张翰林,关爱薇,傅珂,孙廷凯. 软件. 2017(05)
[4]引入导航网格的室内路径规划算法[J]. 林巍凌. 测绘科学. 2016(02)
[5]利用堆排序优化路径搜索效率的分析[J]. 孙玉昕,章瑾. 武汉工程大学学报. 2013(06)
[6]基于DAF算法的地图寻径研究[J]. 陈娜,黄明和,刘清华. 科学技术与工程. 2010(30)
[7]基于地图分割与以矢量信息描述地图的A*寻路算法[J]. 李立,唐宁九,林涛. 四川大学学报(自然科学版). 2010(04)
[8]一种基于导航网格的路径搜索技术[J]. 王天顺,张莉. 电脑知识与技术. 2010(12)
[9]游戏开发中智能路径搜索算法的研究[J]. 何国辉,陈家琪. 计算机工程与设计. 2006(13)
[10]平面多边形域的快速约束Delaunay三角化[J]. 曾薇,孟祥旭,杨承磊,杨义军. 计算机辅助设计与图形学学报. 2005(09)
硕士论文
[1]基于综合导航网格的智慧旅游动态寻径方法[D]. 王烨萍.西南交通大学 2017
[2]游戏中的智能路径搜索算法及其应用[D]. 李井颂.昆明理工大学 2017
[3]游戏场景中分层寻路算法及地图复杂性度量研究[D]. 周振华.河北大学 2014
[4]游戏地图寻路及其真实性研究[D]. 韩玮.西南大学 2013
[5]人工智能寻路算法在电子游戏中的研究和应用[D]. 詹海波.华中科技大学 2006
[6]基于A*算法的地图寻径的研究[D]. 张前哨.武汉科技大学 2005
本文编号：3110667
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3110667.html
