Постановка и анализ задачи поиска пути между двумя точками при разработке игр

Весьма популярны алгоритмы поиска пути и в сфере видеоигр, являясь частью игрового ИИ (Искусственного Интеллекта). Наиболее актуальной для таких ИИ является система navmesh (навигационная сетка), поскольку для таких ИИ доступна вся информация о пространстве поиска, а навигационная сетка помимо поиска отлично справляется с структурированием этой информации, облегчая её использования другими элементами игрового ИИ. Также, поиск пути по реальной местности актуален в роботостроении, поскольку в функции многих роботов входит перемещение по местности, а если эта местность не имеет форму выпуклой однородной геометрической фигуры, то для поиска пути по ней придётся использовать более или менее сложный алгоритм поиска пути. Настоящая работа посвящена изучению и сравнению алгоритмов поиска минимального расстояния, применяемых при разработке компьютерных игр. Одни алгоритмы, которые могут быть применены как поиск по ширине и глубине, направлены на первую проблему, исчерпывая все возможности. Работа этих алгоритмов основана на переборе всех возможных путей от исходной точки до точки назначения. Данные алгоритмы не подходят для использования в приложениях реального времени в виду7 их малой скорости, и не подходят играм (в большинстве случаев) так как основная задача большинства - поиск кратчайшего пути. Большая часть разновидностей модификации алгоритмов A* (A star) и Дейкстры, в основном ищут пути посредством эвристики. Эти алгоритмы являются одними из лучших общих алгоритмов для реального времени, которые ищут путь на графе без предварительной обработки. Эвристика - это совокупность приёмов и методов, облегчающих и упрощающих решение познавательных, конструктивных, практических задач. Алгоритмы, позволяющие найти путь между7 2 точками, имеют весьма широкий спектр применений, при этом для каждого из них, как правило, используется своя модификация алгоритмов поиска пути. У этих алгоритмов есть прямое назначение - поиск пути на модели реальной местности (как правило, граф или навигационная сетка), что позволяет активно использовать эти алгоритмы и их модификации в навигационных программах, наиболее простым примером которых является система навигации GPS (Global Positioning System - глобальная система позиционирования).

Formulation and analysis the problem of finding a path between two points when developing games

Very popular pathfinding algorithms in the field of video games, as part of the game AI (Artificial Intelligence). The most relevant for such AI is the navmesh system (navigation grid), because all information about the search space is available for such AI, and the navigation grid in addition to the search copes with the structuring of this information, facilitating its use by other elements of the game AI. Also, the search for a path on the real terrain is relevant in robotics, since the functions of many robots include moving around the area, and if this area does not have the form of a convex homogeneous geometric figure, then you will have to use a more or less complex algorithm to find a path. This work is devoted to the study and comparison of algorithms for finding the minimum distance used in the development of computer games. Some algorithms that can be applied as a search in width and depth, aimed at the first problem, exhausting all possibilities. The operation of these algorithms is based on the search of all possible paths from the starting point to the destination point. These algorithms are not suitable for use in real - time applications in vidu7 of their low speed, and are not suitable for games (in most cases) as the main task of the majority is to find the shortest path. Most of the modifications of a* (a star) and Dijkstra algorithms are mainly looking for ways by means of heuristics. These algorithms are some of the best General real-time algorithms that look for a path on a graph without preprocessing. Heuristics is a set of techniques and methods that facilitate and simplify the solution of cognitive, constructive, practical problems. Algorithms that allow to find a path between 7 and 2 points have a very wide range of applications, and for each of them, as a rule, a modification of the path search algorithms is used. These algorithms have a direct purpose-to find a path on a real terrain model (usually a graph or a navigation grid), which allows you to actively use these algorithms and their modifications in navigation programs, the simplest example of which is the GPS navigation system (Global Positioning System).