基于半边数据结构的A-star路径规划算法及实现.pdf

2023 年 30 期众创空间科技创新与应用Technology Innovation and Application基于半边数据结构的 A-star 路径规划算法及实现古天驰，李晓东*，苏龙生（佛山科学技术学院 计算机系，广东 佛山 528225）路径规划在游戏 AI 自动寻路、航路规划、人工智能避障以及驾车地图导航等现代计算机科学领域中都有着广泛的应用1-2，其主要实现障碍躲避以及最佳路径的选择。A-star 算法则是一种能够达到最优解且常运用于最优路径规划的算法。在路径规划方面，A-star算法通常基于方格地图实现，而方格地图的空间描述局限性较大导致路径选择自由度受限。传统图的邻接表存储结构复杂而使用不便，导致搜索邻接点、线和面时效率较低。而半边数据结构则是一种基于多边形网格的空间数据结构，常用于三维地图表达，具有较强的拓扑性和灵活性，因此其在计算机图形学、三维建模等领域有着广泛的应用3-4。本文提出含邻接边中点信息的半边数据结构，并与利用优化预估代价计算模型的 A-star 算法结合，运用于三角网格3D 地图，可突破方格地图的空间局限，有利于提高网格地图的空间利用率，同时提高路径搜索效率。1算法原理1.1半边数据结构描述半边数据结构是可用于网格中邻接元素查询的一种数据结构，相较于邻接表方式，半边数据结构更有利于点、线及面的拓扑搜索访问，同时半边数据结构对于网格的表达要求是流形结构5，其中三角形是简单的流形结构，故下面是基于三角网格的问题研究。一个网格地图包含点集、边集和面集，其中三角面的每条边为有向边，且逆时针构成环。顶点结构 HE_Vertex 包含坐标及其出半边 edge 的信息；半边结构 HalfEdge 包含目标顶点 target、相邻半边 pair、下一条半边 next 以及所属面 face 的信息；面结构 HE_Face 包含其中一条半边基金项目：佛山科学技术学院国家级大学生创新创业训练计划项目（202211847004）*通信作者：李晓东（1968-），男，硕士，副教授。研究方向为图形图像处理、智能优化算法等。摘要：针对 3D 游戏地形的路径搜索问题，提出基于半边数据结构的具有避障能力的 A-star 最短路径搜索算法。算法利用三角面与邻接边的拓扑关系建立半边数据结构，并以三角面邻接边中点作为路径节点，对比传统的以欧氏距离为预估代价计算模型，提出一种新的预估代价计算模型的 A-star 算法（HEAS），算法可有效规避障碍并找到最优路径。实验表明，HEAS 算法可适用于不同三维地形，并可确保在较短的时间内找到最优路径。实际上，HEAS 算法不仅可应用于 3D 游戏场景下的最优路径搜索，亦可应用于实际三维地形图的最优路径规划问题。关键词：半边数据结构；A-star 算法；路径规划；邻接边中点；3D 游戏中图分类号院TP391文献标志码院A文章编号院2095-2945渊2023冤30-0034-05Abstract:Aiming at the path search problem of 3D game terrain,an A-star shortest path search algorithm with obstacleavoidance ability based on half-edge data structure is proposed.The algorithm uses the topological relationship between thetriangular surface and the adjacent edge to establish a half-edge data structure,and takes the midpoint of the adjacent edge ofthe triangular surface as the path node.Compared with the traditional calculation model based on Euclidean distance,a newpredictive cost calculation model A-star algorithm(HEAS)is proposed,which can effectively avoid obstacles and find the optimalpath.The experimental results show that the HEAS algorithm can be applied to different 3D terrain and can ensure that theoptimal path can be found in a short time.In fact,HEAS algorithm can be applied not only to the optimal path search in 3Dgame scenes,but also to the optimal path planning of practical 3D topographic maps.Keywords:half-side data structure;A-star algorithm;path planning;adjacent edge midpoint;3D gameDOI：10.19981/j.CN23-1581/G3.2023.30.00934-众创空间科技创新与应用Technology Innovation and Application2023 年 30 期edge 的信息（图 1）。图 1半边数据结构示意图为方便 A-star 算法在半边数据结构上的应用，在传统半边结构 HalfEdge 中添加了边的中点坐标信息center，从而方便路径规划过程中相邻半边的搜索以及最终结果路径顶点的确定，有利于后续 A-star 算法基于邻接边中点的路径选择方式的实现（图 2）。图 2含中点信息的半边数据结构三角网格1.2HEAS 算法原理启发式的 A-star 算法在路径规划问题中根据终点已有的启发信息来引导搜索，通过计算每一步的代价来决定下一步的去向，代价的计算模型如下所示。记当前节点自起点累计已花费的代价为 G（n），当前节点到达目标点的预估代价为 H（n），则当前综合总代价 F（n）表示为F（n）=G（n）+H（n）。（1）记 2 个相邻路径节点 V1（x1，y1）和 V2（x2，y2）间的距离计算利用欧氏距离公式d（V1，V2）=（x1-x2）2+（y1-y2）2姨。（2）记当前搜索节点为 Vn，其前驱节点为 Vn-1，目标点为 Vg，当前搜索节点与目标点的相连线段经过障碍的合计距离为 di，其间经过的障碍半边数为 n。传统预估代价 H（n）的计算利用欧式距离，下面通过考虑当前节点与终点连线经过的障碍因素对传统预估代价进行优化，得到新的预估代价计算模型，当前已花费代价 G（n）及优化的预估代价 H（n）分别表示为下列式（3）和式（4）G（n）=G（n-1）+d（Vn，Vn-1）；（3）H（n）=d（Vn，Vg）+n did（Vn，Vg）。（4）下面以具有 162 个单位三角网格的地图为基础，在均匀分布的地图障碍面积占整个地图的不同比例下，分别对利用优化预估函数的 HEAS 算法和传统预估函数运用在 A-star 算法中搜索的三角网格数进行对比测试，如图 3 所示。图 3优化的预估函数与传统预估函数的搜索网格数对比通过测试，可见利用优化后的预估函数，算法搜索的网格数总是小于或等于利用传统预估函数的搜索网格数，且与障碍面积所占地图比例相关，随着障碍面积平均占比的增大，优化的搜索网格数也随之增大。当起点到目标点的路径上不存在障碍时，2 种预估函数的搜索个数相等，而当起点到目标点的路径上存在障碍时，优化的预估函数其搜索网格数总是更少。HEAS 算法应用于多边形网格地图在搜索路径决定下一步节点时，对于路径节点的选择是沿多边形的邻接边的中点，在三角网格基础上即 2 个三角面之间公共边的中点（图 4）。图 4基于邻接边中点的路径选择方式示意图算法每一步搜索将当前搜索半边所在面的其他2条半边纳入搜索范围，同时利用当前搜索半边的中点计算当前累计的已花费代价 G（n）和预估代价 H（n），并始终选择两者之和最小即代价最小的半边继续搜索，当遇障碍无法继续搜索时则从搜索范围内的其他6.2512.5018.75250403020100201510500.004.8910.7817.3818.08地图障碍平均占比（%）35-2023 年 30 期众创空间科技创新与应用Technology Innovation and Application半边继续搜索，如此算法则始终体现出整体逼近终点方向搜索的状态。2算法的实现2.1改进半边数据结构的实现实现路径规划算法前，首先需要利用含半边中点信息的半边数据结构实现三角网格地图的构造。三角网格地图包含顶点集、半边集和面集，需依次构造单位三角面的顶点、半边以及面结构，并通过对半边结构HalfEdge 添加中点坐标的改进，在构造单位半边结构时，利用半边两端顶点坐标计算出半边中点坐标并进行存储，可方便结果路径的节点获取。三角网格地图构造过程描述如下：for 参数面表中的每个面for 该面的三个顶点构造顶点 HE_Vertex 实例并加入到 ver原tices list 中构 造 三 个 半 边HalfEdge 实 例 并 加 入 到halfedges list 中构造一个面 HE_Face 实例并将其 edge 属性设为第一条半边实例将该面加入到地图的面集for vertices list 中每一对顶点实例及 halfedgeslist 中每条半边实例顶点 1 的 edge 属性=当前半边当前半边的 target 属性=顶点 2当前半边的 next 属性=下一条半边当前半边的 face 属性=面实例根据当前顶点对计算当前半边的 center 属性if 当前半边存在相邻半边 then当前半边的 pair 属性=相邻半边将 vertices list 加入到地图的点集将 halfedges list 加入到地图的边集2.2HEAS 算法实现三角网格地图最优路径的搜寻算法执行的辅助结构包含开放队列 open，路径前驱节点容器 path 以及当前累计代价容器 cost。其中开放队列 open 为基于小顶堆的优先队列，用其存储等待搜索的半边节点及其优先值，其中优先值按当前累计已花费代价 G（n）和预估代价 H（n）之和计算，由此确保队头元素总是目前综合代价最小的预搜索半边节点。路径前驱节点容器 path 和当前代价容器 cost 都是键值对 map 容器，path 用于存储已搜索半边节点信息及其搜索过程的前驱半边节点信息，而 cost 则存储各半边节点及其自起始点累计已走的距离。结合上述辅助结构，将利用优化预估代价计算模型的 A-star 算法应用于含邻接边中点信息的半边数据结构所构造的三角网格地图的 HEAS 算法描述如下：if 起点和终点共面 then 路径搜索完成for 当前半边所在面的所有半边if 该半边存在相邻半边 then 加入到 open listwhile open list 不为空 当前半边=open list 中代价最小的半边if 当前半边与目标点所在面相邻 then路径搜索完成for 当前半边所在面的所有半边if 该半边不在 open list 中 or 该半边代价比 cost list 中更小 then将该半边加入到 open list 并计算其总代价将该半边加入到 cost list 并更新其目前代价将该半边加入到 path list 并更新其路径前驱为当前半边算法最终所得的结果路径则存储在 path 容器的记录中，可从目标节点逐层递推地找到各节点的搜索路径前驱节点，从而通过目标点倒推到起始点找到结果目标路径。3实验测试与分析测试环境所使用的开发工具包括 VisualStudio2019 和 OpenGL 应用工具包 v3.7 版本，测试用例为半边数据结构构建的三角网格地图，其中包括障碍区域和不可达三角区域，自定义起点和终点并绘制最短路径，以下在基于半边中点的路径节点选择方式下的可达路径进行测试，其中起点和终点的连线为算法所得结果路径，深色网格表示已搜索过的三角面（图 5）。在整体三角面大小较为均匀的地图基础上，以邻接边中点为路径节点的路径选择方式整体较优，可进一步进行三角面细分6及利用平滑路径算法来优化冗余路径7-8。36-众创空间科技创新与应用Technology Innovation and Application2023 年 30 期在 3 个具有不同障碍分布的三角网格地图中基于邻接边中点的路径节点选择方式，分别对 Dijkstra 算法、贪心的最佳优先搜索算法（GBFS）以及本文提出的HEAS 算法在搜索网格数量和搜索时间 2 个方面的运行情况进行对比，图 6 为测试结果。图 5三角网格测试地图示意以及最短路径测试结果Dijkstra 算法在寻路过程中是以距离起点最近为导向，而 GBFS 算法在寻路过程中则是以距离终点最近为导向，但这种贪心思想所得的最终结果未必是最短的路径。HEAS 算法则是在两者中取得平衡，在寻路过程中以距起点距离和距终点距离综合最近为导向，同时考虑两者代价以做出权衡，所得到的结果路径为最短路径。可见，当地图中有障碍物时，Dijkstra 算法的结果路径总是最优，但在时间效率上欠佳；最佳优先贪心算法在时间效率上最优，但其结果路径并不总是理想的；图 6各路径规划算法对比测试结果Dijkstra 算法GBFS 算法HEAS 算法搜索网格数：怨源搜索时间：员缘援园园员 怨 皂泽搜索网格数：37搜索时间：员1援488 2 皂泽搜索网格数：56搜索时间：员4援687 0 皂泽搜索网格数：91搜索时间：员6援709 3 皂泽搜索网格数：39搜索时间：员0援414 1 皂泽搜索网格数：62搜索时间：员5援836 1 皂泽搜索网格数：怨0搜索时间：员9援734 7 皂泽搜索网格数：41搜索时间：员0援679 8 皂泽搜索网格数：71搜索时间：员4援462 5 皂泽地图1地图2地图3渊下转 45 页冤37-众创空间科技创新与应用Technology Innovation and Application2023 年 30 期而采用居中策略的 HEAS 算法所得到寻路时间效率和结果路径则是综合最优的方案。4结束语本文利用含邻接边中点信息的半边数据结构表达地图的三角网格信息，结合改进的预估代价计算模型的 A-star 算法以及沿三角形的邻接边中点的路径表达方式，证明了 HEAS 算法高效适用于三角形网格的路径规划问题，可以得到综合最优的路径方案，同时三角形网格可从二维空间拓展至三维空间，在解决 3D游戏场景以及实际三维地形图中的诸多寻路导航问题中更具优势。参考文献院1 万平.基于 A-star 算法的航路规划算法设计与仿真研究J.中国水运.航道科技，2018（4）：58-65.2 岳高峰，张萌，沈超，等.移动机器人导航规划的双向平滑 A-star 算法J.中国科学：技术科学，2021，51（4）：459-468.3 ALSHAMMREI S，BOUBAKER S，KOLSI L.Improved di原jkstra algorithm for mobile robot path planning and obstacleavoidanceJ.CMC-COMPUTERS MATERIALS&CONTINUA（S1546-2218），2022，72（3）：5939-5954.4 HUANG J，WANG X H，WANG J.Mesh simplification al原gorithm based on edge curvature metrics and local optimiza原tion J.International Journal of Modeling，Simulation，andScientific Computing，2020，11（1）.5 ZHANG L L，CHENG B Z.Sparse representation and modi原fied tensor projection for hyperspectral anomaly detectionJ.Infrared Physics&Technology，2020（106）：103256.6 LEE D T，SCHACHTER B J.Two algorithms for construct原ingaDelaunaytriangulationJ.InternationalJour-nalofComputer and Information Sciences，1980，9（3）：219-242.7 XU L，CAO M Y，SONG B Y.A new approach to smoothpath planning of mobile robot based on quartic Bezier tran原sition curve and improved PSO algorithm J.Neurocomput原ing，2022（473）：98-106.8 MOHAMED E，ALAA T，ABOUL E H.Bezier curve basedpath planning in a dynamic field using modified genetic al原gorithmJ.Journal of Computational Science，2018（25）：339-350.图 16阀瓣截面图10.2玉-玉断面处的弯曲应力计算滓W=K2QMZ/（tB-c）2=0.135伊5 415/（9-5）2=45.7 MPa臆滓W=186 MPa【合格】，式中：1）系数 K2根据 DMP/D 查表，得 K2=0.135；2）密封面平均直径 DMP=DMN+bM=17+3=20 mm；3）阀瓣尾部外径 D=27 mm；4）阀瓣材料为 TC4，许用弯曲应力滓W=186 MPa。11结束语本文介绍了一种多功能阀门的设计与分析，在满足使用功能的基础上，进行了结构优化，可有效对带固体颗粒的废水、海水介质进行接通或切断。通过应力分析和校核计算，阀门的最大应力值远小于材料的许用应力值，安全系数较高，保证了工况下的完整性和可运行性。参考文献院1 压水堆核电厂阀门 第 10 部分：应力分析和抗震分析：NB/T20010.102010S.2010.2 核设施部件建造规则：ASME BPVC-III2004S.3 陆培文.阀门设计入门与精通M.北京：机械工业出版社，2009.4 陆培文.实用阀门设计手册第M.3 版.北京：机械工业出版社，2012.5 阀门 流量系数和流阻系数试验方法：GB/T 308322014S.2014.6 机械工程师手册编委会.机械工程师手册M.3 版.北京：机械工业出版社，2007.渊上接 37 页冤45-