{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,19]],"date-time":"2026-08-19T19:50:14Z","timestamp":1787169014528,"version":"3.56.0"},"reference-count":25,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2024,5,16]],"date-time":"2024-05-16T00:00:00Z","timestamp":1715817600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["42376180"],"award-info":[{"award-number":["42376180"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["41771478"],"award-info":[{"award-number":["41771478"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Navigation systems are extensively used in everyday life, but the conventional A* algorithm has several limitations in path planning applications within these systems, such as low degrees of freedom in path planning, inadequate consideration of the effects of special regions, and excessive nodes and turns. Addressing these limitations, an enhanced A* algorithm was proposed using regular hexagonal grid mapping. First, the approach to map modeling using hexagonal grids was described. Subsequently, the A* algorithm was refined by optimizing the calculation of movement costs, thus allowing the algorithm to integrate environmental data more effectively and flexibly adjust node costs while ensuring path optimality. A quantitative method was also introduced to assess map complexity and adaptive heuristics that decrease the number of traversed nodes and increase the search speed. Moreover, a turning penalty measure was implemented to minimize unnecessary turns on the planned paths. Simulation results confirmed that the improved A* algorithm exhibits superior performance, which can dynamically adjust movement costs, enhance search efficiency, reduce turns, improve overall path planning quality, and solve critical path planning issues in navigation systems, greatly aiding the development and design of these systems and making them better suited to meet modern navigation requirements.<\/jats:p>","DOI":"10.3390\/ijgi13050166","type":"journal-article","created":{"date-parts":[[2024,5,16]],"date-time":"2024-05-16T09:30:03Z","timestamp":1715851803000},"page":"166","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Improved A* Navigation Path-Planning Algorithm Based on Hexagonal Grid"],"prefix":"10.3390","volume":"13","author":[{"given":"Zehua","family":"An","sequence":"first","affiliation":[{"name":"School of Earth Sciences and Engineering, Hohai University, Nanjing 210098, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7764-4272","authenticated-orcid":false,"given":"Xiaoping","family":"Rui","sequence":"additional","affiliation":[{"name":"School of Earth Sciences and Engineering, Hohai University, Nanjing 210098, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chaojie","family":"Gao","sequence":"additional","affiliation":[{"name":"School of Earth Sciences and Engineering, Hohai University, Nanjing 210098, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2024,5,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1145\/359156.359164","article-title":"An Algorithm for Planning Collision Free Paths Among Polyhedral Obstacles","volume":"22","author":"Wesley","year":"1979","journal-title":"Commun. ACM"},{"key":"ref_2","first-page":"16","article-title":"Summarization of intelligent pathfinding-oriented 3D scene","volume":"53","author":"Gao","year":"2017","journal-title":"Comput. Eng. Appl."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1016\/j.aei.2016.04.007","article-title":"BIM-oriented indoor network model for indoor and outdoor combined route planning","volume":"30","author":"Teo","year":"2016","journal-title":"Adv. Eng. Inform."},{"key":"ref_4","first-page":"102994","article-title":"A fine-grained navigation network construction method for urban environments","volume":"113","author":"Lou","year":"2022","journal-title":"Int. J. Appl. Earth Obs. Geoinf."},{"key":"ref_5","first-page":"1103","article-title":"Dynamic Planning Method for Indoor-Fire Escape Path Based on Navigation Grid","volume":"55","author":"Zhu","year":"2020","journal-title":"J. Southwest Jiaotong Univ."},{"key":"ref_6","first-page":"141","article-title":"Research on gridding and path planning of environmental map","volume":"43","author":"Liu","year":"2021","journal-title":"Ship Sci. Technol."},{"key":"ref_7","first-page":"111","article-title":"Indoor Route Planning Under Regular Hexagonal Grid Considering","volume":"45","author":"Wang","year":"2020","journal-title":"Geomat. Inf. Sci. Wuhan Univ."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Meysami, A., Cuilli\u00e8re, J.-C., Fran\u00e7ois, V., and Kelouwani, S. (2022). Investigating the Impact of Triangle and Quadrangle Mesh Representations on AGV Path Planning for Various Indoor Environments: With or without Inflation. Robotics, 11.","DOI":"10.3390\/robotics11020050"},{"key":"ref_9","first-page":"48","article-title":"An Overview of Pathfinding in Navigation Mesh","volume":"12","author":"Xiao","year":"2012","journal-title":"Int. J. Comput. Sci. Netw. Secur."},{"key":"ref_10","first-page":"132","article-title":"An Ant Colony Algorithm Based on Grid Methodfor Mobile Robot Path Planning","volume":"27","author":"Zhu","year":"2005","journal-title":"Robot"},{"key":"ref_11","first-page":"71","article-title":"Research on image processing algorithms on hexagonal grid","volume":"5","author":"Liu","year":"2001","journal-title":"Comput. Eng. Des."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"107327","DOI":"10.1016\/j.compeleceng.2021.107327","article-title":"A Collision-Aware Mobile Robot Navigation in Grid Environment using Improved Breadth First Search","volume":"94","author":"Tripathy","year":"2021","journal-title":"Comput. Electr. Eng."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Gang, T. (2021). R-DFS: A Coverage Path Planning Approach Based on Region Optimal Decomposition. Remote Sens., 13.","DOI":"10.3390\/rs13081525"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"10253","DOI":"10.1007\/s12652-020-02794-2","article-title":"A dynamic fire escape path planning method with BIM","volume":"12","author":"Wang","year":"2021","journal-title":"J. Ambient Intell. Humaniz. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1007\/s44176-022-00004-1","article-title":"Travel route planning of core scenic spots based on best-worst method and genetic algorithm: A case study","volume":"1","author":"Tu","year":"2022","journal-title":"Manag. Syst. Eng."},{"key":"ref_16","first-page":"12484","article-title":"Path Planning of Mobile Robot based on Improved Ant Colony Algorithm","volume":"22","author":"Baker","year":"2022","journal-title":"Sci. Technol. Eng."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A Formal Basis for the Heuristic Determination of Minimum Cost Paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_18","first-page":"105","article-title":"Building Internal Path Planning Algorithm and its Application Reviewed Research","volume":"10","author":"Su","year":"2014","journal-title":"Geomat. Spat. Inf. Technol."},{"key":"ref_19","first-page":"1697","article-title":"Research on Robot Shortest Path Planning with Improved A* Algorithm","volume":"51","author":"Chen","year":"2023","journal-title":"Comput. Digit. Eng."},{"key":"ref_20","first-page":"307","article-title":"Static Route Planning of Surface Ships Based on Improved A* Algorithm","volume":"58","author":"Wu","year":"2022","journal-title":"Comput. Eng. Appl."},{"key":"ref_21","first-page":"750","article-title":"Improved A* Algorithm for Time\u2014Dependent Vehicle Routing Problem","volume":"19","author":"Zhang","year":"2012","journal-title":"Control. Eng. China"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Li, X., Hu, X., Wang, Z., and Du, Z. (2020, January 15\u201317). Path Planning Based on Combination of Improved A-STAR Algorithm and DWA Algorithm. Proceedings of the 2020 2nd International Conference on Artificial Intelligence and Advanced Manufacture (AIAM), Manchester, UK.","DOI":"10.1109\/AIAM50918.2020.00025"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Ju, C., Luo, Q., and Yan, X. (2020, January 23\u201325). Path Planning Using an Improved A-star Algorithm. Proceedings of the 2020 11th International Conference on Prognostics and System Health Management (PHM-2020 Jinan), Jinan, China.","DOI":"10.1109\/PHM-Jinan48558.2020.00012"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Zhang, H., Li, M., and Yang, L. (2018). Safe Path Planning of Mobile Robot Based on Improved A* Algorithm in Complex Terrains. Algorithms, 11.","DOI":"10.3390\/a11040044"},{"key":"ref_25","first-page":"181","article-title":"Indoor robot path planning based on improved A* algorithm","volume":"45","author":"Zhou","year":"2022","journal-title":"Mod. Electron. Tech."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/13\/5\/166\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:43:26Z","timestamp":1760107406000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/13\/5\/166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,16]]},"references-count":25,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2024,5]]}},"alternative-id":["ijgi13050166"],"URL":"https:\/\/doi.org\/10.3390\/ijgi13050166","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,16]]}}}