Винокурова С.Е. Модификация метода навигационного графа для поиска пути в трехмерном пространстве

Аннотация: Поиск пути это задача нахождения наилучшего, оптимального маршрута между двумя точками пространства. Применение алгоритмов поиска пути позволяет управлять перемещением персонажей в трехмерном пространстве с автоматическим обходом препятствий, что позволяет пользователю полностью погрузиться в моделируемую 3D реальность за счет обеспечения решения проблем перемещения программной средой. В статье предлагается модификация метода навигационного графа для поиска пути в трехмерном пространстве за счет задания отдельного навигационного графа для каждого 3D объекта. В этом случае навигационный граф задает пути перемещения внутри и вокруг составного 3D-объекта или вокруг одиночного 3D-объекта. Модифицированный алгоритм в значительной степени требует меньших затрат для задания навигационного графа, позволяет рассчитывать путь с более естественной траекторией передвижения и позволяет производить поиск пути с обходом перемещающихся объектов. Предложенный метод подходит для применения в реальном времени, в том числе благодаря предложенным в данной статье оптимизациям.

Ключевые слова:

Abstract: Path finding is a task of defining the optimal rout between two points in a space. Use of path finding algorithms allows controlling the moving of a character in 3D space with obstacles being avoided automatically, giving user the opportunity to fully immerse in the simulated 3D reality since the solutions to the problems of avatar moves is provided by the software environment itself. The article presents a modification of the navigation graph method of path finding in 3D space by setting a separate navigation graph for each 3D object. In that case each navigation graph specifies the paths inside and around a complex 3D object or a path around a simple 3D object. The modified algorithm is of significantly less computational cost for setting navigation graph, provides a more natural path and allows finding a rout with bypassing of moving objects. The proposed method is suitable for real-time applications and specifically due to the optimizations suggested in this article.

Keywords: