采用边缘检测的游戏智能导航网格生成方法  

Research on Generation Method of Game Intelligent Navigation Grid Based on Edge Detection

作　　者：郭锐 曾美玲 李富龙 邱国鹏[1] 陈立龙[1] GUO Rui;ZENG Meiling;LI Fulong;QIU Guopeng;CHEN Lilong(School of Art and Design,Sanming University,Sanming 365004,China;YongZhou Normal College,Yongzhou 625100,China)

机构地区：[1]三明学院艺术与设计学院,福建三明365004 [2]永州师范高等学科学校,湖南永州625100

出　　处：《三明学院学报》2024年第3期25-35,共11页Journal of Sanming University

基　　金：福建省以马克思主义为指导的哲学社会科学学科基础理论研究基地重大项目(FJ2021MJDZ029);福建省中青年教师教育科研项目(JAS22149,JAT231113);三明市引导性科技项目(2021-G-2)。

摘　　要：提出一种基于边缘检测的智能导航网格生成方法,旨在解决大型二维游戏地图动态导航制图耗时长、搜索节点过多的问题。该方法通过离线构建四叉树索引碰撞体对象,以实现高效实时查询。在线寻路时,通过实时查询四叉树或遍历导航区域,将不可行走区域标识为黑色区域,可行走区域标识为白色区域。然后,使用Sobel边缘检测算子提取可行走区域的边缘轮廓点,并形成导航几何。最后,使用切耳算法生成凸多边形导航网格。实验结果表明,与传统的地图建模方法相比,该方法在导航网格生成效率和响应速度方面均具有显著的优势。This paper proposes an edge detection-based intelligent navigation grid generation method aimed at address⁃ing the issues of lengthy time consumption and excessive search nodes in dynamic navigation mapping of large-scale game maps.The method involves offline construction of a quadtree index for collision objects to achieve efficient real-time queries.During online pathfinding,the quadtree is queried in real-time or the navigation area is traversed to identify non-walkable ar⁃eas as black regions and walkable areas as white regions.Subsequently,the Sobel edge detection operator is applied to extract the edge contour points of the walkable areas,and a navigation geometry is generated.Finally,the Ear Clipping algorithm is utilized to generate convex polygon navigation grids.Experimental results demonstrate significant advantages of this method in terms of navigation grid generation efficiency and response speed when compared to traditional map modeling methods.

关 键 词：四叉树 SOBEL边缘检测 切耳算法 智能导航网格 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]