Efficient Pathfinding on Grid Maps: Comparative Analysis of Classical Algorithms and Incremental Line Search
Pathfinding on grid maps is a cornerstone problem in robotics, autonomous navigation, and game development. Classical algorithms such as A*, Dijkstra’s, and Breadth-First Search (BFS) are known for their ability to guarantee optimal solutions, while others like Depth-First Search (DFS) an...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/11018332/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849334678413115392 |
|---|---|
| author | Amr Elshahed Majid Khan Bin Majahar Ali Ahmad Sufril Azlan Mohamed Farah Aini Binti Abdullah Ts. Lee Jian Aun |
| author_facet | Amr Elshahed Majid Khan Bin Majahar Ali Ahmad Sufril Azlan Mohamed Farah Aini Binti Abdullah Ts. Lee Jian Aun |
| author_sort | Amr Elshahed |
| collection | DOAJ |
| description | Pathfinding on grid maps is a cornerstone problem in robotics, autonomous navigation, and game development. Classical algorithms such as A*, Dijkstra’s, and Breadth-First Search (BFS) are known for their ability to guarantee optimal solutions, while others like Depth-First Search (DFS) and Greedy Best-First Search prioritize speed over optimality. However, these algorithms can be computationally inefficient in large-scale or real-time environments. This paper introduces Incremental Line Search (ILS), a novel optimization strategy that incorporates Bresenham’s line algorithm to define a dynamically adjustable corridor between the start and goal points. By restricting the search to this focused region and expanding only when necessary, ILS significantly reduces computational overhead while preserving optimality in cases where the underlying algorithm guarantees it, and delivering near-optimal paths in others. Extensive experiments were conducted to evaluate the performance of ILS across various metrics, including execution time, visited nodes, and path length, over a total of 6000 grid maps generated with obstacle densities of 10%, 20%, and 30%. On average, ILS achieved a 87.31% reduction in execution time and a 71.44% reduction in node expansions compared to their standard counterparts. Despite these improvements, path quality was preserved: Best-First Search showed a 63.24% improvement in path length, while DFS improved by 86.70%, confirming that ILS not only accelerates computation but also leads to smoother paths in most scenarios. These findings affirm ILS as a highly effective and resilient optimization technique for demanding pathfinding tasks. Its dynamic adaptability renders ILS especially suitable for applications in robotics, autonomous systems, and resource-constrained environments, setting the stage for future advancements in multi-agent navigation and real-time optimization. |
| format | Article |
| id | doaj-art-1af162fe4d2c4bf9ba2ba93702279a5b |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-1af162fe4d2c4bf9ba2ba93702279a5b2025-08-20T03:45:30ZengIEEEIEEE Access2169-35362025-01-0113984739848410.1109/ACCESS.2025.357516811018332Efficient Pathfinding on Grid Maps: Comparative Analysis of Classical Algorithms and Incremental Line SearchAmr Elshahed0https://orcid.org/0000-0002-1242-6581Majid Khan Bin Majahar Ali1https://orcid.org/0000-0002-5558-5929Ahmad Sufril Azlan Mohamed2https://orcid.org/0000-0002-2838-0872Farah Aini Binti Abdullah3Ts. Lee Jian Aun4School of Mathematical Sciences, Universiti Sains Malaysia (USM), George Town, MalaysiaSchool of Mathematical Sciences, Universiti Sains Malaysia (USM), George Town, MalaysiaSchool of Mathematical Sciences, Universiti Sains Malaysia (USM), George Town, MalaysiaSchool of Mathematical Sciences, Universiti Sains Malaysia (USM), George Town, MalaysiaSchool of Mathematical Sciences, Universiti Sains Malaysia (USM), George Town, MalaysiaPathfinding on grid maps is a cornerstone problem in robotics, autonomous navigation, and game development. Classical algorithms such as A*, Dijkstra’s, and Breadth-First Search (BFS) are known for their ability to guarantee optimal solutions, while others like Depth-First Search (DFS) and Greedy Best-First Search prioritize speed over optimality. However, these algorithms can be computationally inefficient in large-scale or real-time environments. This paper introduces Incremental Line Search (ILS), a novel optimization strategy that incorporates Bresenham’s line algorithm to define a dynamically adjustable corridor between the start and goal points. By restricting the search to this focused region and expanding only when necessary, ILS significantly reduces computational overhead while preserving optimality in cases where the underlying algorithm guarantees it, and delivering near-optimal paths in others. Extensive experiments were conducted to evaluate the performance of ILS across various metrics, including execution time, visited nodes, and path length, over a total of 6000 grid maps generated with obstacle densities of 10%, 20%, and 30%. On average, ILS achieved a 87.31% reduction in execution time and a 71.44% reduction in node expansions compared to their standard counterparts. Despite these improvements, path quality was preserved: Best-First Search showed a 63.24% improvement in path length, while DFS improved by 86.70%, confirming that ILS not only accelerates computation but also leads to smoother paths in most scenarios. These findings affirm ILS as a highly effective and resilient optimization technique for demanding pathfinding tasks. Its dynamic adaptability renders ILS especially suitable for applications in robotics, autonomous systems, and resource-constrained environments, setting the stage for future advancements in multi-agent navigation and real-time optimization.https://ieeexplore.ieee.org/document/11018332/Path planningshortest path problemheuristic algorithms |
| spellingShingle | Amr Elshahed Majid Khan Bin Majahar Ali Ahmad Sufril Azlan Mohamed Farah Aini Binti Abdullah Ts. Lee Jian Aun Efficient Pathfinding on Grid Maps: Comparative Analysis of Classical Algorithms and Incremental Line Search IEEE Access Path planning shortest path problem heuristic algorithms |
| title | Efficient Pathfinding on Grid Maps: Comparative Analysis of Classical Algorithms and Incremental Line Search |
| title_full | Efficient Pathfinding on Grid Maps: Comparative Analysis of Classical Algorithms and Incremental Line Search |
| title_fullStr | Efficient Pathfinding on Grid Maps: Comparative Analysis of Classical Algorithms and Incremental Line Search |
| title_full_unstemmed | Efficient Pathfinding on Grid Maps: Comparative Analysis of Classical Algorithms and Incremental Line Search |
| title_short | Efficient Pathfinding on Grid Maps: Comparative Analysis of Classical Algorithms and Incremental Line Search |
| title_sort | efficient pathfinding on grid maps comparative analysis of classical algorithms and incremental line search |
| topic | Path planning shortest path problem heuristic algorithms |
| url | https://ieeexplore.ieee.org/document/11018332/ |
| work_keys_str_mv | AT amrelshahed efficientpathfindingongridmapscomparativeanalysisofclassicalalgorithmsandincrementallinesearch AT majidkhanbinmajaharali efficientpathfindingongridmapscomparativeanalysisofclassicalalgorithmsandincrementallinesearch AT ahmadsufrilazlanmohamed efficientpathfindingongridmapscomparativeanalysisofclassicalalgorithmsandincrementallinesearch AT farahainibintiabdullah efficientpathfindingongridmapscomparativeanalysisofclassicalalgorithmsandincrementallinesearch AT tsleejianaun efficientpathfindingongridmapscomparativeanalysisofclassicalalgorithmsandincrementallinesearch |