USE OF CELLULAR AUTOMATA ALGORITHMS IN MINIMUM PATH SEARCH PROBLEMS

Abstract

The paper considers the use of cellular automata to improve the search for the shortest path between objects with obstacles on the way. The proposed algorithm is based on a cellular automaton, namely the game "Life). The rules for constructing the structure of the cellular automaton require changes, depending on the requirements of the user. The article presents a possible variant of finding the shortest path with the help of a cellular automaton using the example of a game. The aim of the game is to reach a certain predetermined cell of the playing field for a minimum number of steps. The problem has many analogues and is used in various fields of science from ordinary games to fixed
military strategies.
The considered existing analogues of shortest path search agglomerations have a number of drawbacks. These include working only with the structure of graphs, finding the shortest path from only one vertex and others. There is also a drawback that is inherent in all methods - they always try to move in the direction of the goal, even if it is the wrong path. These disadvantages lead to an increase in the time of implementation of the algorithm, stuck characters in the corners and between obstacles.
In the above algorithm, the field is considered as a field element of a cellular automaton. In the first step, obstacles are randomly generated, which do not appear throughout the game. We define a cell as an object that moves according to a certain set of rules that depend on the filling of neighboring cells.
If there is an obstacle at a given position, then depending on the volume occupied by the figure, we assign a value of 1 or 0 in the characteristic matrix of the corresponding dimension. The rules of movement are determined by the presence of an obstacle, how much this obstacle fills the space (is it possible to move further along the cell, or is it necessary to bypass the obstacles).
With this algorithm, the above disadvantages of the algorithm disappear, and the speed of execution is significantly reduced.
Keywords: minimum path, cellular automaton, rules for constructing cellular automata, algorithms for finding the minimum distance.