Статья 'Система поиска пути в трехмерном пространстве' - журнал 'Кибернетика и программирование' - NotaBene.ru
по
Меню журнала
> Архив номеров > Рубрики > О журнале > Авторы > О журнале > Требования к статьям > Редакция и редакционный совет > Порядок рецензирования статей > Политика издания > Ретракция статей > Этические принципы > Политика открытого доступа > Оплата за публикации в открытом доступе > Online First Pre-Publication > Политика авторских прав и лицензий > Политика цифрового хранения публикации > Политика идентификации статей > Политика проверки на плагиат
Журналы индексируются
Реквизиты журнала

ГЛАВНАЯ > Вернуться к содержанию
Кибернетика и программирование
Правильная ссылка на статью:

Система поиска пути в трехмерном пространстве

Иванов Андрей Юрьевич

кандидат технических наук

доцент, кафедра системного программирования, Нижегородский технологический университет им. Горького

Ivanov Andrei Yur'evich

PhD in Technical Science

ivanov@mail.ru
Синицын Александр Петрвоич

кандидат биологических наук

профессор, кафедра международного права, МГТУ им. Баумана

Sinitsyn Aleksandr Petrvoich

PhD in Biology

oldbird@mail.ru
Несвязин Игорь Антонович

кандидат медицинских наук

профессор, кафедра математики, Марийский Государственный Университет

Nesvyazin Igor' Antonovich

PhD in Medicine

antoha@mail.ru

Дата направления статьи в редакцию:

20-11-2014


Дата публикации:

04-12-2014


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


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

поиск пути, граф, навигация, 3D-пространство

Abstract: The article is devoted to the extension of the navigation graph (NG) method for 3D space pathfinding systems using numerous NGs relevant to each object instead of a single graph. This method significantly reduces the volume of manual work for setting NGs as well as the general time of algorythm without distoring the adequacy of the path being found. 


Keywords:

3D space, navigation, graph, pathfinding

Введение

Поиск пути (ПП) – задача нахождения наилучшего, оптимального маршрута между двумя точками пространства. В зависимости от контекста критерии оптимальности могут быть различные, но во всех случаях на найденном пути не должно встречаться препятствий.

ПП - важная часть виртуальной 3D среды. Пользователь не должен отвлекаться от основной цели (например, обучения) на решение проблем перемещения в пространстве, и если он хочет переместиться из одной точки в другую, то путь разумной длины должен быть обязательно найден. При появлении на выбранном пути какого-либо препятствия система должна автоматически скорректировать найденный путь.

Также ПП используется в компьютерных играх, различных симуляторах и тренажерах, чтобы обеспечивать корректное перемещение персонажей, управляемых компьютером.

Обзор существующих методов ПП

Для ПП получили распространение 3 основных метода: алгоритм А*, НГ, метод сочетания эвристик в трехмерном пространстве.

Алгоритм А*[1] подразумевает разбиение пространства на одинаковые клетки, для каждой из которых задано, проходима клетка или нет. Персонаж занимает одну клетку. По полученной матрице проходимости волновым алгоритмом или одной из его модификаций находится путь из одной клетки в другую (рис.1). Метод получил большое распространение в 2D-пространстве (в играх-стратегиях и т.д.), однако при применении в 3D-пространстве имеет серьезные недостатки:

· 3D-мир состоит из объектов произвольной формы, которые плохо ложатся на клеточную структуру поиска.

· Трудно учитывать перемещающиеся препятствия, так как они могут занимать до 4 клеток сразу (если размер препятствия 1 клетка).

· Перемещение по клеткам выглядит очень неестественно в трехмерном пространстве. Методы сглаживания пути сплайнами могут привести к проблемам с непроходимостью отдельных участков пути.

· Большое время ПП при большом количестве клеток.

pf1

Рис. 1. Алгоритм А* (Серые круги – точки начала и конца пути, черные клетки – препятствия, окружности – найденный путь.)

pf2

Рис.2. НГ (Серые прямоугольники – препятствия, черные линии – ребра графа, черные точки – вершины графа, пунктирная линия – найденный путь).

НГ [2]это граф, вершины которого - трехмерные точки, ребра графа - отрезки, соединяющие эти точки, с ценой равной длине отрезка. Все ребра графа являются проходимыми (персонаж может пройти по ним, не наткнувшись на препятствие). Задача ПП сводится к нахождению ближайших вершин к начальной и конечной точке, а затем к ПП на графе между этими вершинами с использованием критерия минимального веса общего пути (рис 2). Главные недостатки метода:

· Сложность задания НГ (большой объем ручной работы).

· Значительное время ПП в графе с большим числом ребер.

Метод сочетания эвристик [3] в трехмерном пространстве предполагает применение специального алгоритма разрешения проблемной ситуации для небольшого числа распространенных случаев необходимости обхода препятствия.

Возможным примером можно назвать попытку при столкновении с препятствием найти луч с минимальным отклонением от вектора взгляда персонажа, который бы не пересекался с полигонами 3D-мира. В случае нахождения такого луча, персонаж перемещается по нему, а затем пытается следовать к конечной точке по прямому пути.

Основные недостатки:

· В большом числе ситуаций не может найти правильный путь, так как при разрешении коллизии путь ищется локально.

· В случае столкновения с препятствием сложность разрешения коллизии может быть очень высокой и напрямую зависеть от детальности трехмерного мира. В приведенном примере сложность расчетов напрямую зависит от числа полигонов 3D-мира.

Поиск путей на основе усовершенствованного метода НГ.

На основе собственного расширения метода НГ была разработана система ПП для 3D мира. Вместо одного НГ в системе используется множество НГ, по одному для каждого объекта (рис. 3).

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

ПП выполняется по известной начальной и конечной точке. При поиске выполняются следующие шаги:

1. Удлинение отрезка, соединяющего начальную и конечную точку, на некоторый ε с обеих сторон. Это требуется для корректного ПП в случае, если НГ расположен вблизи отрезка, соединяющего начальную и конечную точку.

2. Поиск НГ, которые пересекаются удлиненным отрезком. Все точки пересечения (ТП) сохраняются в общий список.

3. Если найдена всего 1 ТП, то идет поиск сегментов НГ, перпендикуляр к которым из начальной или конечной точки имеет длину < ε. Из числа найденных сегментов выбирается тот, длина перпендикуляра к которому меньше других, и добавляется ТП с перпендикуляром в общий список ТП.

4. ТП сортируются по удаленности от начальной точки пути.

5. Список ТП разбивается на несколько частей, в каждой из которых идут подряд точки одного и того же графа.

6. Внутри получившихся частей списка ПП ведется отдельно, а крайние точки соседних частей соединяются прямым отрезком. При ПП внутри одного НГ рассматриваются варианты:

· 1 ТП — путь касается НГ, и поиск оптимального пути не требуется.

· 2 и более ТП — выполняем ПП по крайним ТП по критерию минимальной суммарной длины сегментов.

7. Полученные отрезки путей компонуются в единый путь.

Результаты

Оценим сложность алгоритма (табл. 1), п. 1, 5, 6 можно опустить за незначительностью объема расчетов.

В п. 7. сложность зависит от метода поиска на графе. Если М –кол-во вершин, а N – ребер, то для алгоритма Дейкстры сложность составит O(M2 + N) или O(N2), т.к. N сравнимо с M в нашем случае.

Также можно оценить среднее время ПП. Была взята выборка из 10000 реальных случаев ПП. Замеры производились на компьютере с ЦП Intel Core 2 Duo 2.7 ГГц (использовалось 1 ядро).

Среднее время поиска – 24 мкс, минимальное время поиска – 1 мкс, максимальное время поиска - 110 мкс. Полученные результаты говорят о возможности применения алгоритма в реальном времени.

Библиография
1.
2.
3.
4.
5.
References
1.
2.
3.
4.
5.
Ссылка на эту статью

Просто выделите и скопируйте ссылку на эту статью в буфер обмена. Вы можете также попробовать найти похожие статьи


Другие сайты издательства:
Официальный сайт издательства NotaBene / Aurora Group s.r.o.