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

1 Винокурова Светлана

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

3 «Виртуальная академия»

4 До внедрения поиска пути в «Виртуальную академию»

5 Поиск пути в «Виртуальной академии»

6 Обзор алгоритмов Клеточное представление с поиском по алгоритму А* Navigation mesh

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

8 Методы задания данных для поиска путей Автоматическая генерация путей Ручное задание через визуальный редактор

9 Выбор базовых методов Метод поиска пути – навигационный граф Метод задания данных – визуальное редактирование через редактор мира

10 Архитектура «Виртуальной Академии»

11 Поиск пути, шаг 1 Расчет координат сегментов для динамических объектов

12 Поиск пути, шаг 2 Объединение и разъединение графов

13 Поиск пути, шаг 3 Поиск точек пересечения

14 Поиск пути, шаг 4 Сортировка точек пересечения

15 Поиск пути, шаг 5 Разбиение точек пересечения на группы

16 Поиск пути, шаг 6 Поиск пути внутри отдельных графов

17 Поиск пути, шаг 7 Объединение в единый путь

18 Учет динамических объектов Изменение состояния проходимости ребра Найденный путь обхода динамического объекта при первой попытке поиска пути (слева) и второй попытке (справа). Черным цветом выделено ребро, отмеченное как непроходимое после первой попытки.

19 Учет динамических объектов Учет динамических объектов, расположенных на ребре навигационного графа статического объекта Поиск пути с динамическим объектом на ребре без заданного признака проходимости статического навигационного графа (справа) и без него (слева).

20 Учет динамических объектов Учет динамических объектов, расположенных на ребре навигационного графа статического объекта Поиск пути с динамическим объектом на ребре с заданным признаком проходимости статического навигационного графа (справа) и без него (слева).

21 Преимущества алгоритма Базовый метод Усовершенствованный метод Преимущества: 1. Сложность задания меньше. 2. Траектория пути более естественная. 3. Поиск пути быстрее.

22 Система поиска пути в клиенте Схема взаимодействия

23 Модуль поиска пути в редакторе мира Добавление сегмента пути Перемещение вершин графа Удаление всего пути Поверка проходимости пути Автогенерация пути Удаление сегмента пути

24 Редактор мира

25 Автогенерация путей в редакторе мира Автоклонирование Автогенерация

26 Результаты работы: внедрение Система поиска пути внедрена в «Виртуальную Академию» начиная с версии Beta 1.

27 Апробация работы Студенческая конференция МарГУ по итогам научно- исследовательской работы за 2010 год (Йошкар-Ола, МарГУ) Всероссийская научно- практическая конференция «Информационные технологии в профессиональной деятельности и научной работе- 2011» (Йошкар-Ола, МарГТУ)

28 Апробация работы ГрафиКон' я Международная Конференция по Компьютерной Графике и Зрению сентября 2011, Москва Публикация в сборнике статей Школы Молодых Учёных.

29