A STUDY OF THE PERFORMANCE OF ANY-ANGLE THETA* ALGORITHMS ON WEIGHTED GRID MAPS FOR ROUTE PLANNING

Abstract

Context. The article addresses the study of free-direction pathfinding algorithms, in particular the Theta* algorithm, and evaluates their performance on weighted grid maps in order to determine optimal routes for delivering goods to a firearms store. This research is carried out in the broader context of developing an information system for tracking and managing arms sales and logistics under complex conditions. One of the main motivations is that any-angle methods can produce more realistic and natural-looking paths compared to the classical A* algorithm.
Objective. The purpose of the study is to analyze the performance of three Theta*-based algorithms – Basic Theta*, Lazy Theta*, and Strict Theta*– on both uniform and weighted square grids, with special emphasis on execution time and path cost metrics. The work aims to generalize the applicability of these algorithms to weighted environments and to propose improvements suitable for real-world route planning scenarios.
Method. The principles of A*, the three Theta* variants, and path post-processing smoothing techniques are presented. The research describes the transition from unweighted uniform square grids to weighted grids and highlights the complexity of calculating accurate path costs when applying any-angle approaches. Visual demonstrations of algorithmic behavior were implemented using the Unity game engine. Performance metrics were measured separately for uniform and weighted grids to ensure comparative analysis.
Results. The results include comparative evaluations of Basic Theta*, Lazy Theta*, Strict Theta*, and classical A* algorithms. The analysis identifies conditions under which each algorithm performs effectively, as well as factors that limit their applicability in weighted environments. It is shown that path length and path cost may differ substantially in weighted grids, leading to new considerations for cost-based optimization. Based on the experiments, a generalization of the Basic Theta* algorithm is proposed to enhance its suitability for weighted square grids, and a potential extension of the Strict Theta* algorithm to this context is outlined.
Conclusions. The findings demonstrate that while any-angle algorithms provide smoother and more realistic routes, their effectiveness in weighted environments depends on careful adaptation of cost functions. The research highlights their value not only for simulating complex virtual environments and agent behaviors in games and robotics but also for practical applications in logistics, particularly in the development of an information system for tracking and managing firearms sales. The proposed algorithmic adaptations may contribute to improving delivery planning and supply chain efficiency, including the modeling of weapons delivery routes under wartime conditions.