Pathfinding System for 3d Space

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

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

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

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

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

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

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

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

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

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

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

Рис.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(M² + N) или O(N²), т.к. N сравнимо с M в нашем случае.

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

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