Рус Eng За 365 дней одобрено статей: 1980,   статей на доработке: 305 отклонено статей: 760 
Библиотека
Статьи и журналы | Тарифы | Оплата | Ваш профиль

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

Опубликовано в журнале "Программные системы и вычислительные методы" в № 1 за 2014 год в рубрике "Математическое и программное обеспечение новых информационных технологий" на страницах 109-124.

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

Ключевые слова: поиск пути, навигационный граф, алгоритм, оптимизация, расширенный метод, алгоритм А*, navigation mesh, препятствия, динамические объекты, трехмерное пространство

DOI: 10.7256/2305-6061.2014.1.11346

Эта статья может быть бесплатно загружена в формате PDF для чтения. Обращаем ваше внимание на необходимость соблюдения авторских прав, указания библиографической ссылки на статью при цитировании.

Скачать статью

Библиография:
А.Ю. Сморкалов. Математическая и программная модели генерации текстур на графических потоковых процессорах // Программные системы и вычислительные методы. – 2013. – № 1. – С. 104-107. DOI: 10.7256/2305-6061.2013.01.10.
Yap, P. Grid-Based Path-Finding / P.Yap // AI '02 Proceedings of the 15th Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence-2002. – 44-55 pp.
Cui, X., Shi, H. A*-based Pathfinding in Modern Computer Games/ X. Cui, H. Shi // IJCSNS International Journal of Computer Science and Network Security-Vol.11 No.1, January 2011.
Tozour, P. Fixing Pathfinding Once and For All [Electronic resource] / Game AI.-Electronic data.-Mode acess: http://www.ai-blog.net/archives/000152.html. free.
Mika, M., Charla, C. Simple,Cheap Pathfinding / M. Mika, C. Charla // AI Game Programming Wisdom-2002.
O'Neill, J. С. Efficient Navigation Mesh Implementation / J. C. O'Neill // Journal of Game Development-Vol. 1 No. 1, 2004.-71-90 pp.
Akbar, A. Raycast Navigation Mesh Generation and Path Finding System [Electronic resource]-Electronic data.-Mode acess: http://syntheticarc.com/?q=node/6, free.
Botea, A., Muller, M., Schaeffer, J. Near Optimal Hierarchical Path-finding / A. Botea, M. Muller, J. Schaeffer // Journal of Game Development-Vol. 1 Issue 1, 2004.
И.А.Садовин, А.Ю. Сморкалов. Система переноса лекций в виртуальный мир vAcademia с использованием возможностей Microsoft Kinect и потоковых процессоров // Программные системы и вычислительные методы. – 2013. – № 4. – С. 90-94. DOI: 10.7256/2305-6061.2013.04.10.

Правильная ссылка на статью:
просто выделите текст ссылки и скопируйте в буфер обмена