Advanced Pathfinding in a Grid using A-Star Algorithm with
Dynamic Obstacles and Weighted Paths
Abstract:
This project presents an advanced pathfinding system using the A-Star algorithm within a
dynamically changing grid environment. The grid is designed with weighted paths, allowing the
algorithm to account for variable movement costs. Dynamic obstacles are introduced to simulate
real-time changes in the environment, providing a challenging scenario for path recalculation. The
project includes performance comparison metrics such as execution time, path cost, and adaptability
to changing conditions. This approach highlights the efficiency of A-Star in finding optimal paths in
complex, dynamic environments while allowing for future extensions with other heuristic algorithms.
Keywords:
A-Star algorithm, pathfinding, dynamic obstacles, weighted paths, grid navigation, heuristic search,
real-time path optimization, algorithm performance analysis, artificial intelligence, robotics, game
development
Literature Review:
The literature review in the paper highlights the significance of pathfinding algorithms in various
fields, particularly in game development. It references several studies that demonstrate the
application of algorithms like A-Star in optimizing navigation and decision-making processes for
artificial intelligence in games. The review emphasizes the importance of efficient pathfinding in
enhancing user experience and gameplay dynamics, citing works that explore algorithmic efficiency
and the impact of obstacles on pathfinding performance .
Candra, A., Budiman, M. A., & Pohan, R. I. (2021). Application of A-Star Algorithm on Pathfinding
Game. *Journal of Physics: Conference Series*, 1898, 012047. IOP Publishing. doi:10.1088/1742-
6596/1898/1/012047.
The literature review in the paper discusses the challenges faced by traditional pathfinding
algorithms, particularly the A* algorithm, in complex environments such as logistics warehouses. It
highlights the limitations of existing map modeling techniques, including the Voronoi diagram and
grid methods, which struggle with obstacle detection and excessive path nodes. The review
emphasizes the necessity for a hybrid approach that combines the strengths of these methods to
enhance pathfinding efficiency, paving the way for the proposed dynamic fusion pathfinding
algorithm (DFPA) that integrates Delaunay triangulation and an improved A* algorithm.
Ayawli, A., Liu, Z., Liu, H., Lu, Z., & Zeng, Q. (2021). A Dynamic Fusion Pathfinding Algorithm Using
Delaunay Triangulation and Improved A* Algorithm for Mobile Robots. IEEE Access, 9, 20621-
20634. https://doi.org/10.1109/ACCESS.2021.3055231
The literature review in the paper systematically examines the A* algorithm's effectiveness in
pathfinding, comparing it with other methods and exploring potential enhancements. It analyzes 40
recent quantitative studies, focusing on A*'s strengths, such as its stability and efficiency in various
applications, particularly in gaming. The review underscores the role of heuristic functions in
improving decision-making within informed search algorithms. The authors aim to provide a
comprehensive understanding of A*'s characteristics and its relevance in contemporary pathfinding
challenges.
Citation:
Foead, D., et al. (2021). A systematic literature review on A* pathfinding algorithm. Procedia
Computer Science, 179, 507-514. doi:10.1016/j.procs.2021.01.034
The paper presents a comprehensive examination of the A Star algorithm, highlighting its
effectiveness in solving shortest path problems in various applications, particularly in robotics and
gaming. It contrasts the A Star algorithm with the Dijkstra algorithm, emphasizing the former's
efficiency in pathfinding within obstacle-laden environments. The study employs the Raster Method
and the Manhattan Distance Formula to model the exploration area, demonstrating the algorithm's
practical implementation through simulations in Matlab. Overall, the research underscores the
significance of intelligent pathfinding in modern technology.
Citation: Yan, Y. (2023). Research on the A Star Algorithm for Finding Shortest Path. In *Highlights in
Science, Engineering and Technology MCEE 2023* (Vol. 46, pp. 154-160). Beijing-Dublin International
College at BJUT, Beijing University of Technology.
The literature review in this paper discusses the significance of pathfinding algorithms in video
games, particularly in Tower Defense games. It highlights the Flow Field algorithm's advantages in
managing multiple units and detecting obstacles, while also noting its high resource consumption in
larger maps. The A-Star algorithm is presented as a widely used alternative, known for its efficiency
in various pathfinding scenarios. The review emphasizes the need for comparative studies to
enhance understanding and application of these algorithms in real-time strategy games.
Citation: Comparison of Flow Field and A-Star Algorithm for Pathfinding in Tower Defense Game.
IJMRA, Volume 5 Issue 09 September 2022, www.ijmra.in.
In this study, Ou et al. (2022) propose an improved A* algorithm to address common issues in path
planning, such as excessive turning points and slow search speeds. The approach introduces path
smoothing and a safety mechanism, which improves the smoothness and safety of the robot's
movement by reducing the number of unnecessary turns. Additionally, a steering cost model and an
adaptive cost function were introduced to enhance search efficiency. The improvements led to a
significant reduction in average search time and nodes, making the algorithm more effective for
mobile robot navigation in obstacle-filled environments.
Ou et al., "Improved A* Path Planning Method Based on the Grid Map," 2022.
The paper presents a novel Geometric A-Star Algorithm aimed at improving path planning for
Automated Guided Vehicles (AGVs) in port environments. It addresses the limitations of traditional A-
star algorithms, particularly in generating irregular paths with excessive turning angles. By
incorporating filter functions and cubic B-spline interpolation, the proposed method enhances path
smoothness and ensures continuous speed and acceleration during AGV motion. This research
contributes to the field of robotics and automation by providing a more efficient and reliable path
planning solution for AGVs operating in complex environments.
Citation: G. Tang et al., "Geometric A-Star Algorithm: Improved A-Star Algorithm for AGV Path
Planning in Port Environment .
Liu et al. (2022) combine the optimized A-Star algorithm with the Artificial Potential Field (APF)
method to improve path planning efficiency for home cleaning robots. The fusion of these algorithms
helps address the limitations of the traditional A-Star, such as high computation and the tendency to
fall into local optima. Their approach also uses the least squares method to ensure smoother path
trajectories. The study showed that this hybrid algorithm significantly reduced path-planning time
compared to traditional A-Star, bidirectional A-Star, and other algorithms like the Ant Colony
Optimization, demonstrating superior performance in dynamic environments.
Liu et al., "Research on Path-Planning Algorithm Integrating Optimization A-Star Algorithm and
Artificial Potential Field Method," 2022.
