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

Презентация:



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

Разработка, анализ и программная реализация алгоритмов поиска и оптимизации маршрутов движения в улично-дорожной сети города Научный руководитель: профессор,
Определите координаты отмеченных точек y x а) (–25; –20) А (–15; 15) (–30; 5) (25; 25) (15; 10) (20; –15) C B D E F.
Выпуклая оболочка набора точек Выпуклая оболочка набора точек Определение, применение, свойства, методы построения.
Лучшие работы. Количество студентов в СНК Количество докладов, представленных студентами.
Научно- исследовательская деятельность студентов Где господствует дух науки, там творится великое… Н.Пирогов Федеральное государственное бюджетное образовательное.
Контрольная работа 2 Что такое графика? Как узнать, какой инструмент выбран? Как выбрать основной цвет в графическом редакторе? Как запустить графический.
Дипломная работа Разработка веб-системы для учета и контроля исполнения заданий водителями транспортных средств Исполнители: Ким Кирилл Игоревич Синтяпов.
Муравьиный алгоритм определения критических связей в СБИС Зав. каф. САПР ИКТиИБ ЮФУ, д.т.н., проф. В.В. Курейчик, аспирант каф САПР ИКТиИБ ЮФУ, Д. Ю. Запорожец,
Графические информационные модели Графические(или геометрические) информационные модели являются простейшим видом моделей, которые передают.
Автоматизация службысервисаMicrosoft CRM. Обработка клиентских запросов используя Обращения. Возможность маршрутизации и назначения (сотрудникам или очереди).
«Лингвистический модуль электронного учебника болгарского языка» Диссертация на соискание степени магистра филологических наук Соискатель Соискатель –
Школьная научно – исследовательская конференция «Шаг в будущее» 9 апреля 2012года.
О научном студенческом обществе Архангельского индустриально- педагогического колледжа Актуальная информация о работе творческого объединения студентов.
Портал Университета ШОС Аспекты технической реализации ИКП: разработка и внедрение портала Университета ШОС 26 октября 2009 г. г. Москва Ведущий программист.
Использование КОМПАС-3D на уроках информатики. Задачи курса «Информатика» в школе. 1.Подготовка учащихся к решению различных практических задач с использованием.
Поиск путей в сложных полигонах для динамических систем реального времени. Работа Порошина И.А., 544 гр. Научный руководитель Уфнаровский В.В. Рецензент,
Диофантовы модели сети MPLS для восстановления соединений Кулаков Кирилл Александрович Петрозаводский государственный университет Москва
Результаты реализации программы инновационного развития МБОУ «Гимназия 1»ЕМР
Методическое объединение математики и информатики.
Транксрипт:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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