Светлана Винокурова МарГУ ФМФ 5 курс СИСТЕМА ПОИСКА ПУТИ В ТРЕХМЕРНОМ ПРОСТРАНСТВЕ

Поиск пути задача нахождения наилучшего, оптимального маршрута между двумя точками пространства.

Область применения Виртуальные миры Компьютерные игры Тренажеры и симуляторы

Обзор существующих методов Алгоритм А* Навигационный граф Метод сочетания эвристик в трехмерном пространстве

Алгоритм А* 3D-мир состоит из объектов произвольной формы Трудно учитывать перемещающиеся препятствия Неестественная траектория Большое время ПП при большом количестве клеток

Навигационный граф Сложность задания. Значительное время поиска пути в графе с большим числом ребер.

Метод сочетания эвристик Путь ищется локально. Сложность разрешения коллизии может быть очень высокой.

Усовершенствованный метод НГ Базовый метод Усовершенствованный метод

Алгоритм 1. Удлинение отрезка 2. Поиск точек пересечения 3. Поиск ближних сегментов 4. Сортировка точек пересечения 5. Разделение списка точек пересечения на части 6. Поиск оптимального пути 7. Компоновка в единый путей

Алгоритм 2. Поиск точек пересечения 3. Поиск ближних сегментов 4. Сортировка точек пересечения 5. Разделение списка точек пересечения на части 6. Поиск оптимального пути 7. Компоновка в единый путей 1.Удлинение отрезка на некоторый ε с обеих сторон 1.Удлинение отрезка на некоторый ε с обеих сторон

Алгоритм 3. Поиск ближних сегментов 4. Сортировка точек пересечения 5. Разделение списка точек пересечения на части 6. Поиск оптимального пути 7. Компановка в единый путей 1. Удлинение отрезка 2. Поиск точек пересечения удлиненного отрезка с навигационными графами

Алгоритм 4. Сортировка точек пересечения 5. Разделение списка точек пересечения на части 6. Поиск оптимального пути 7. Компоновка в единый путей 1. Удлинение отрезка 2. Поиск точек пересечения 3. Поиск ближних сегментов, если не хватает точек пересечения

Алгоритм 5. Разделение списка точек пересечения на части 6. Поиск оптимального пути 7. Компоновка в единый путей 1. Удлинение отрезка 2. Поиск точек пересечения 3. Поиск ближних сегментов 4. Сортировка ТП по удаленности от начала пути

Алгоритм 6. Поиск оптимального пути 7. Компоновка в единый путей 1. Удлинение отрезка 2. Поиск точек пересечения 3. Поиск ближних сегментов 4. Сортировка точек пересечения 5. Разделение списка ТП на части. Каждая часть – 1 граф

Алгоритм 7. Компоновка в единый путей 1. Удлинение отрезка 2. Поиск точек пересечения 3. Поиск ближних сегментов 4. Сортировка точек пересечения 5. Разделение списка точек пересечения на части 6. ПП по критерию min (длины сегментов) 6. ПП по критерию min (длины сегментов)

Алгоритм 1. Удлинение отрезка 2. Поиск точек пересечения 3. Поиск ближних сегментов 4. Сортировка точек пересечения 5. Разделение списка точек пересечения на части 6. Поиск оптимального пути 7. Компоновка полученных отрезков путей в единый путь

Учет динамических объектов Динамический объект - объект, который может изменить позицию и поворот, появится или исчезнуть в любой момент времени.

Учет динамических объектов Сохранение в отдельный список. Обновление в момент начала поиска пути: пересчет абсолютных координат сегментов объединение графов динамических объектов Несколько попыток обхода динамического объекта в случаи его попадания на путь в момент следования по найденному маршруту.

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

Преимущества Сокращение объема ручной работы: свой навигационный граф для каждого объекта; автоматическое копирование навигационных графов для повторяющихся объектов; автогенерация обходных путей для путей простой геометрической формы. Более высокая скорость по сравнению с базовым алгоритмом.

Заключение Система была успешно апробирована в образовательной 3D-среде «Виртуальная академия».

Спасибо за внимание!