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

2
3
Аннотация
Магистерская диссертация на тему «Разработка программного обеспечения
для реализации алгоритмов проблемы распознавания поверхностей и
препятствий» содержит 57 страницы текста и рисунков, использованных
источников - 19.
В данный момент подобные задачи востребованы в связи с нарастающей
потребностью оценки наикратчайшего пути обходя разного типа препятствий,
данный вид задачи найдет применение как теоретическое, так и практическое
в разработке игр, программ, а также все более популярных в данное время
алгоритмах планирования для механизмов под управлением искусственного
интеллекта(ИИ).
Ключевые слова: поиск пути А*, поиск в ширину, алгоритм поиска путей на
графе, динамическая генерация графа.
Предмет
исследования.
Содержание
программного
обеспечения
для
математического моделирования процесса динамической генерации графа в 3х мерном пространстве на основе которого заданный алгоритм поиска
кратчайшего пути, отображает путь с наименьшей стоимостью от начальной
до конечной вершины учитывая проходимые и полу проходимые препятствия.
Объект
исследования.
Математическое
моделирование
процесса
динамической генерации 3-х мерного графа в пространстве с определением
типов поверхностей и препятствий на его пути.
Цель работы. На основе программы Unreal Engine 4 реализовать программное
обеспечения для поиска пути алгоритмом A* в 3-х мерном пространстве на
динамически заданном графе, содержащем информацию о типах поверхностей
и препятствий.
Метод исследования. Для исследования применяется метод генерации
сетчатого графа алгоритмом поиск в ширину, а для поиска пути на заданном
графе применяется алгоритм A*.
Результаты работы. В магистерской диссертации разработана программа на
языке Blueprint, позволяющая решить задачу о динамической генерации графа
4
в 3-х мерном пространстве и поиска пути на нем с наименьшей стоимостью от
начальной до конечной вершины, выполнена апробация комплекса на
тестовых и произвольных задачах.
Работа имеет теоретическое и практическое значение, т.к. разработанная
программа и ее исходный код может применяться для дальнейших
исследований, связанных с алгоритмами; поиска, генерации, планирования.
5
Abstract
Master's thesis on "Mathematical simulation of subsidence of the hill
groundwater in homogeneous layers under the action of gravity and the drainage
device in the presence of one inclusion" contains 57 pages of text and figures, of
sources used - 19.
At the moment, these tasks are popular due to the shortest way around various types
of obstacles, this kind of tasks, and just as in a practical way in the development of
games, programs, as well as more and more popular algorithms for managing under
the control of artificial intelligence (AI).
Keywords: search for the path A *, search in width, algorithm for finding paths on a
graph, dynamical generation of a graph.
The subject of the study. The content of the software for mathematical modeling of
the process of dynamic graph generation in 3-dimensional space on the basis of
which a given algorithm of searching the shortest path displays the path with the
least cost from the initial to the final vertex, taking into account passable and semipassable obstacles.
The object of study. Mathematical modeling of the process of dynamic generation of
a 3-dimensional graph in a space with the definition of types of surfaces and
obstacles in its path.
The purpose of the work. Based on the Unreal Engine 4 program, software is
implemented to find the path by the algorithm A* in 3-dimensional space on a
dynamically defined graph containing information about the types of surfaces and
obstacles.
Method of the study. For the study, the method of generating a grid graph is used for
algorithm-wide width search, and algorithm A * is used to find the path on a given
graph.
The results of the work. In master's thesis developed a program in Blueprint, which
allows to solve the problem of dynamically generating a graph in 3-dimensional
space and searching for a path on it with the least cost from the initial to the final
vertex. The complex was tested on test and arbitrary problems.
6
The work has theoretical and practical importance, because the developed program
and its source code can be used for further studies related to algorithms; search,
generation, and planning.
7
СОДЕРЖАНИЕ
ВВЕДЕНИЕ .............................................................................................................. 9
ГЛАВА I ОСОБЕННОСТИ ПОСТАВЛЕННОЙ ЗАДАЧИ И АНАЛИЗ
СРЕДСТВ ЕЕ РЕАЛИЗАЦИИ ............................................................................. 13
§1.1 Формулировка задачи ................................................................................... 13
§1.2 Анализ ПО для решения поставленной задачи .......................................... 14
ГЛАВА II ОПИСАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ
РЕАЛИЗАЦИИ ПОИСКА ПУТИ НА ГРАФЕ В 3-Х МЕРНОМ
ПРОСТРАНСТВЕ АЛГОРИТМОМ A* .............................................................. 16
§2.1 Подготовка проекта и начало работы в Unreal Engine 4.......................... 16
§2.2 Динамическая реализация графа в среде Unreal Engine 4 ....................... 21
§2.3 Визуализация ячеек графа в пространстве ................................................ 27
§2.4 Реализация алгоритма A* на заданном графе........................................... 38
ГЛАВА III ИССЛЕДОВАНИЯ, ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ.................... 49
§3.1 Нагруженный граф и поиск пути на нем ................................................... 49
§3.2 Реализация 3-х мерности графа. Перемещение ячеек по z ..................... 50
§3.3 Оптимизация программы ............................................................................ 52
ЗАКЛЮЧЕНИЕ ..................................................................................................... 54
СПИСОК ЛИТЕРАТУРЫ..................................................................................... 56
8
ВВЕДЕНИЕ
Обоснование выбора темы и ее актуальность
В современном мире особой востребованностью пользуются задачи о
поиске пути, которые позволяют построить математические модели для
описания движения искусственного интеллекта по заданному пути. Одними из
наиболее востребованных являются задачи, описывающие движение объекта
в 3-х мерном пространстве с наличием факторов влияющих на перемещение
от начальной до конечной точки.
При учете объектов стоящих на пути движения искусственного
интеллекта вычисляется наименьшая стоимость из всех возможных путей и
выбирается оптимальный путь. Сложность задачи обуславливается анализом
типов встречающихся препятствий на пути алгоритма их преодолением.
Одним
из
способов
анализа
препятствий
является
создание
динамического графа, содержащего информацию о их местоположении. Граф,
как и путь на нем, генерируется автоматически в области движения
искусственного интеллекта.
Актуальность работы подкреплена востребованностью задачи в связи с
нарастающей потребностью оценки наикратчайшего пути учитывая факторы,
влияющие на движение. Данный вид задачи найдет применение как
теоретическое, так и практическое в разработке игр, программ, а также все
более популярных в данное время алгоритмах планирования для механизмов
под управлением искусственного интеллекта(ИИ).
Степень разработанности проблемы
Ключевая идея всех алгоритмов заключается в том, что мы отслеживаем
состояние расширяющегося кольца, которое называется границей. В сетке
этот процесс иногда называется заливкой, но та же техника применима для
поиска препятствий. Принцип реализации заключается в повторении шагов,
пока
граница
не
окажется
пустой.
Необходимо
выбирать
и
удалить точку из границы. Отметить ее как посещённую, чтобы знать, что не
9
нужно обрабатывать её повторно. Расширяем границу, глядя на её соседей.
Всех соседей, которых мы ещё не видели, добавляем к границе.
Данный способ подходит для поиска пути на статически заданной
поверхности. Поэтому кроме стандартного метода необходимо разработать
способ поиска пути на графе с динамически изменяемой информацией.
Решение кроется в методе совмещение двух алгоритмов поиска для решения
задачи о поиске пути на графе в 3-х мерном пространстве с учетом
поверхностей и препятствий.
Помимо выбора метода решения данной проблемы, необходимо уделить
внимание выбору популярного и современного средства, способного в
процессе счета обеспечить высокую скорость и точность решения при работе
с большим объемом динамической информации. Исходя из рассуждений, был
выбран визуальный язык программирования – Blueprint [1] и среда разработки
Unreal Engine 4.
Предмет исследования
Разработка программного обеспечения для реализации алгоритмов
проблемы распознавания поверхностей и препятствий возможности его
применения для исследования задачи.
Объект исследования
Программное обеспечение для реализации алгоритмов проблемы
распознавания поверхностей и препятствий.
Цель работы
Разработать программное обеспечение для реализации алгоритмов
проблемы распознавания поверхностей и препятствий.
Основные задачи исследования
1.
Изучить основные печатные и электронные источники, касающиеся
темы работы;
2.
Провести анализ программного обеспечения и выбрать наиболее
подходящие средство для реализации алгоритма;
3.
Средствами Unreal Engine 4 создать динамически граф в трехмерном
10
пространстве;
4.
Реализовать с помощью Unreal Engine 4 по ранее созданному графу
поиск пути алгоритмом A*;
5.
Провести анализ программы на наличие ошибок и нагрузок на ЦП.
6.
Осуществить экспорт программы на доступные платформы.
Метод исследования
Для исследования применяется алгоритм поиска в ширину(алгоритм
поиска в глубину по графу) и алгоритм A*.
Теоретическое и практическое значение работы
Работа имеет теоретическое и практическое значение, т.к. полученные
теоретические результаты могут быть использованы для корректировки
модели и построения более сложных, а разработанная программа может
применяться для дальнейших исследований.
Структура работы
Во
введении
обосновывается
актуальность
решаемой
задачи,
анализируются труды по данной тематике, ставится цель и задачи
исследования, а также основные направления исследования.
В первой главе кратко формулируется поставленной задача и
характеризуются ее специфические особенности.
Во второй главе подробно рассмотрено программное обеспечение,
реализующее работу с динамическим графом в 3-х мерном пространстве, а
также описывается подробное применение алгоритма А* на нем.
В третьей главе проводится апробация разработанного программного
обеспечения.
В заключении делается вывод о полученных в ходе исследования
результатах работ и дальнейших перспективах исследования.
Приводится список использованных источников.
Апробация работы
Промежуточные результаты исследования были опубликованы в
следующих научных работах:
11
1. Визуализация модели архитектуры. Создание интерактивной карты
проблемы создания интерактивных карт помещений // II Международная
научно-практическая
конференция
«Современные
проблемы
физико-
математических наук», г. Орел, Орловский государственный университет им.
И. С. Тургенева, 24-27 ноября 2016 г. С. 173-175.
2. Реализация поиска путей проблемы распознавания алгоритмом
поверхностей и препятствий // семинар «Вычислительные технологии и их
приложения» г. Орел, ОГУ им. И. С. Тургенева, на основании Распоряжения
ректора ОГУ от 15.11.2017 № 577р, 1 февраля 2018 г.
12
ГЛАВА I ОСОБЕННОСТИ ПОСТАВЛЕННОЙ ЗАДАЧИ И АНАЛИЗ
СРЕДСТВ ЕЕ РЕАЛИЗАЦИИ
§1.1 Формулировка задачи
На трехмерном графе, заданном динамически с помощью алгоритма
поиска в ширину, необходимо найти маршрут с наименьшей стоимостью от
одной вершины до другой используя алгоритм A*.
Требуется разработать в программе Unreal Engine 4 скрипт для
демонстрации(симуляции) работы алгоритма A* в трехмерном пространстве
используя возможности визуального скриптового языка Blueprint.
Для реализации данной программы, можно использовать множество
различных программ, языков программирования, но так как данная задача
популярно в среде игровой индустрии, а также в алгоритмах поиска и
планирования пути для задач групповой робототехники, предпочтительной
средой разработки был выбран на данный момент популярный игровой
движок Unreal Engine 4. Полученный опыт работы в нем с визуальным языком
программирования Blueprint и C++ пригодится как в игровой индустрии так и
в стремительно развивающейся робототехнике. Unreal Engine 4 прост и
удобен, открыт и полностью бесплатен, однако стоит отметить, что любые
коммерческие проекты должны отдавать 5% от прибыли если ежемесячный
доход компании или частного лица от продукции реализованной в Unreal
Engine 4 составляет 3000 долларов. В остальном движок не имеет изъянов, а
разработки довольно часто выпускаю обновления
с
исправленными
ошибками и нововведениями. Unreal Engine 4 обладает встроенными
инструментами для визуализации трехмерного пространства а именно таких
как Terrain и Immediate Geometry, с их помощью отпадает необходимость
использовать сторонние программы для 3-х мерного моделирования, что
значительно упрощает процесс визуализации.
13
§1.2 Анализ ПО для решения поставленной задачи
Существует достаточно большое количество средств и способов
создания 3-х мерного представления здания. Для данной работы потребуется
данной программы, можно использовать множество различных программ,
языков программирования, но так как данная задача популярно в среде
игровой индустрии, а также в алгоритмах поиска и планирования пути для
задач групповой робототехники, предпочтительной средой разработки был
выбран на данный момент популярный игровой движок Unreal Engine 4.
Полученный опыт работы в нем с визуальным языком программирования
Blueprint и C++ пригодится как в игровой индустрии так и в стремительно
развивающейся робототехнике. Unreal Engine 4 прост и удобен, открыт и
полностью бесплатен, однако стоит отметить, что любые коммерческие
проекты должны отдавать 5% от прибыли если ежемесячный доход компании
или частного лица от продукции реализованной в Unreal Engine 4 составляет
3000 долларов. В остальном движок не имеет изъянов, а разработки довольно
часто выпускаю обновления с исправленными ошибками и нововведениями.
Unreal Engine 4 обладает встроенными инструментами для визуализации
трехмерного пространства а именно таких как Terrain и Immediate Geometry, с
их помощью отпадает необходимость использовать сторонние программы для
3-х мерного моделирования, что значительно упрощает процесс визуализации.
Blueprint – это визуальный скриптовый язык, который позволяет
написать логику игры без применения языков программирования. Каким бы
сложными или простым он не казался, он остается довольно таки мощным
инструментом, на котором можно создать почти что угодно, от простенького
персонажа или открытия дверцы до процедурной генерации уровня.
Любой может изучить Blueprint за пару дней и через неделю не испытывать
проблем в составлении логики.
Как и большинство визуальных языков, от Blueprint ожидаема высокая
продуктивность, зависящая от правильно составленной логике, чем проще и
логичнее скрипт, тем меньше мы нагружаем систему нашей программой.
14
Неправильное составление логики — это снижение быстродействия, но так
как Unreal Engine 4 написаны на C++ и множество критичных методов
размещены внутри ядра программы, то конечного быстродействия более чем
достаточно [4].
Найденные в работе с программой критические места, которые
нагружают систему можно реализовать на C++ и транслировать в скрипт
Blueprint. API фреймворк классов полностью доступны из обоих систем. Обе
системы можно использовать по отдельности, но используя их вместе можно
получить более мощную и гибкую систему. Созданные классы на C++, в
дальнейшем можно будет расширен с помощью Blueprint. Созданные в классе
различные свойства (переменные), возможно задать в Blueprint. На их основе
извлекаются новые значения созданных свойств. Данный процесс очень прост
благодаря инструментам и макросам, которые предоставляет Unreal Engine 4.
15
ГЛАВА II ОПИСАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ
РЕАЛИЗАЦИИ ПОИСКА ПУТИ НА ГРАФЕ В 3-Х МЕРНОМ
ПРОСТРАНСТВЕ АЛГОРИТМОМ A*
§2.1 Подготовка проекта и начало работы в Unreal Engine 4
Unreal Engine — игровой движок, разрабатываемый и поддерживаемый
компанией Epic Games.
Все элементы данной программы представлены в виде объектов,
имеющих набор характеристик, и класса, который определяет доступные
характеристики. В свою очередь, каждый класс является «дочерним»
классом object. Среди основных классов и объектов можно выделить
следующие:
Актёр (actor) — родительский класс, содержащий все объекты, которые
имеют отношение к игровому процессу и имеют пространственные
координаты.
Пешка (pawn) — физическая модель игрока или объекта, управляемого
искусственным интеллектом. Название происходит от англ. pawn — тот,
кем манипулируют (или пешка, поэтому такой объект без какой-либо модели
выглядит как пешка). Метод управления описан специальным объектом, такой
объект называется контроллером. Контроллер искусственного интеллекта
описывает лишь общее поведение пешки во время игрового процесса, а такие
параметры как «здоровье» (количество повреждений, после которых пешка
перестаёт функционировать) или, например, расстояние, на котором пешка
обращает внимание на звуки. задаются для каждого объекта отдельно.
Мир, уровень (world, game level) — объект, характеризующий общие
свойства «пространства», например, силу тяжести и туман, в котором
располагаются все актёры. Также может содержать в себе параметры игрового
процесса, как, например, игровой режим, для которого предназначен уровень.
Для работы с простыми и, как правило, неподвижными элементами игрового
пространства
(например,
стены)
используется двоичное
разбиение
пространства — всё пространство делится на «заполненное» и «пустое». В
«пустой» части пространства располагаются все объекты, а также только в ней
16
может находиться «точка наблюдения» при отрисовке сцены. Возможность
полного или частичного помещения объектов в «заполненную» часть
пространства не исключается, однако может привести к неправильной
обработке таких объектов (например, расчёт физического взаимодействия)
или неправильной отрисовки в случае помещения туда «точки наблюдения»
(например, эффект «зала зеркал»). Все пешки, попадающие в «заполненную»
часть пространства, сразу «погибают». В камеру не попадает ни один портал
(пунктирная линия) красной зоны, поэтому объекты в ней не обрабатываются
вовсе.
Поверхность (surface) является основным элементом двоичного дерева
пространства. Эти элементы создаются на грани пересечения между
«заполненной» и «пустой» частями пространства. Группа элементов
двоичного дерева пространства называется нодом (node, рус. узел). Этот
термин, как правило, употребляется в контексте node count — количество
нодов на экране или в игровом пространстве вообще. Количество нодов,
одновременно видимых на экране влияет на производительность при
прорисовке сцены. Если какой-то нод не попадает на экран или перекрывается
целиком другими нодами, он не обсчитывается — это служит для повышения
производительности, особенно в закрытых пространствах. Разбиение всего
пространства на группы нодов называется зонированием.
Для этого иногда используются порталы — невидимые поверхности, которые
служат для того чтобы вручную разделить крупный нод на два меньших (в
версии движка Unreal Engine 3 ввели поддержку аддитивной геометрии, что
позволило
отказаться
от
зонирования).
Кроме
порталов
используются антипорталы.
Описание «заполненных» и «пустых» частей пространства выполняется
с помощью набора замкнутых трёхмерных объектов, составленных из
непересекающихся поверхностей — брашей (brush, рус. кисть). Этот принцип
построения пространства называется конструктивной сплошной геометрией.
Геометрия может быть «аддитивной» (всё пространство изначально «пустое»)
17
и «вычитательной» (изначально заполненное материей пространство).
Кисти делятся на три типа:
Сплошные (solid) — полноценно участвуют в двоичном разбиении
пространства.
Аддитивные (additive) — «заполняют» двоичное пространство.
Вычитательные (substractive) — «вырезают» объёмы в пространстве.
Полу-сплошные (semi-solid) — не влияют напрямую на двоичное дерево
пространства, однако влияют на её физическую модель. Могут только
«заполнять» пространство. Служат для создания «невидимых» препятствий, а
также снижения числа полигонов и нодов.
Пустые (non-solid) — только создают поверхности, не влияют на
двоичное
дерево
пространства.
создания объёмов(volume) —
Используются
часть
преимущественно
пространства,
которая
для
обладает
свойствами, отличными от свойств игрового мира. Объёмы имеют приоритет,
свойства объёма с большим приоритетом применяются к находящимся в нём
актёрам. Игровой мир всегда имеет минимальный приоритет. При помощи
объёмов можно изменить гравитацию, вязкость, туман и тому подобное.
Объёмы, начиная с версии движка Unreal Engine 2, используются для создания
воды.
На первом этапе работы необходимо создать Blueprint Class. Каждый
новый класс содержит в себе Viewport – в котором можно просмотреть
результат работы скрипта, Construction Script – основная функция,
создающаяся внутри каждого нового класса Blueprint, Graphs – в нем
создаются обработчики событий, Functions – список в котором можно
создавать свои функции и использовать их вместе с событиями и Construction
Script, Macros – список макросов, Variables – вкладка с переменными
локального и глобального типов, Event Dispatchers – диспетчер событий (Рис.
1).
18
Рис. 1. Новый класс Blueprint
При создании графа в 3-х мерном пространстве, следует задать
несколько начальных переменных. GridLocation – приватная переменная типа
Vector, которая будет содержат расположение графа в пространстве,
GridSizeWorld – публичная переменная типа Vector2D с заданными
размерами сетки, CellSize – публичная переменная типа Float содержащая
визуальный размер ячейки или узла графа, CellPosition – приватная
переменная типа Vector, содержащая заданные алгоритмом координаты
каждой ячейки в пространстве, CellSizeMinus – приватная переменная типа
Float с статическим значением 5.0, которая задает минимальный размер ячейки
графа. Для визуального отображения сетки в редакторе занесем три приватные
переменные типа LinearColor. GridBoxColor – содержит цвет компонента
Blueprint Class, BottomLeftCollor – переменная с цветом границ графа,
CellColor – цвет ячеек графа. Для удобства переменным назначены категории
Debug и Grid (Рис. 2).
19
Рис. 2. Объявление глобальных переменных для генерации графа
Перед работай со скриптом класса необходимо обратить внимание на
вкладку Components – содержащей компоненты класса. По стандарту каждый
класс Blueprint содержит defaultScene компонент, который отлично подходит
для создания любых процедурно генерируемых проектов, но он статичен и не
может быть переименован, чтобы не испытывать в дальнейшем дискомфорт в
работе с данным компонентом, его советуют заменять на вручную
добавленный компонент Scene. Во вкладке Components необходимо нажать на
вкладку Add Component и выбрать из списка Scene, перетащив на компонент
defaultScene. Компонент Scene можно дополнить Bilboard, который
отобразится только в редакторе в виде иконки класса, что очень удобно при
перемещении сетки графа с помощью мышки (Рис. 3).
Рис. 3. Работа с компонентами
Для наглядности работы алгоритма A* граф необходимо нагрузить
20
информацией о типах поверхностей. И по заданным типам присвоить каждой
ячейке начальную стоимость пути. Стоит объявить изначально пять типов
поверхностей, а поможет в этом Enumerator. Enumerator как и тип enum в C++
хранит значения указанные программистом. Первое значение Normal – легко
проходимый тип поверхности, Defficult и ReallyDifficult – значения с
усложненным прохождением, Impossible – непроходимое препятствие и None
– значение где поверхность отсутствует (Рис. 4).
Рис. 4. Объявление значений в Enumerators
§2.2 Динамическая реализация графа в среде Unreal Engine 4
В динамическом создании графа следует отсечь любое ручное
заполнение огромных массивов, списков, структур и т.п. Поэтому следует
воспользоваться достаточно распространенным алгоритмом поиск в ширину
или поиском в глубину на графе. Данный алгоритм хорошо показывает себя
как в генерации сложных 2-х мерных, так и сложных 3-х мерных фигур,
структур, ландшафтов и т.п. Среди трех популярных алгоритмов, а именно
Дейкстры и A*, поиск в ширину показывает себе намного производительнее
так как выполняет исследование равномерно во всех направлениях.
За основу динамического создания графа был использован поиск в ширину для
генерации лабиринтов и в конечном итоге полностью измененный под задачи
данной работы. Целью данного алгоритма является прохождение по пустым
клеткам графа с начальной ячейки и до конечной, отмечая все ячейки, которые
соприкасаются с объектами, принадлежащими типам поверхностей (Рис. 9).
21
Рис. 9. Принцип работы алгоритма
Переходя к созданию графа следует начать с объявления основных
функций, которые положат основу и в дальнейшем будут дополнятся и
использоваться алгоритмом A* для вычислений наипростейшего пути. Чтобы
добавить новые функции необходимо открыть созданный ране класс Blueprint
и во вкладке Functions добавить GridCellNumber, GridBottomLeft,
SphereTrace, GenerateCellData (Рис. 10).
Рис. 10. Объявление основных функций для генерации графа
Важно отметить, что в каждой новой функции создаются два связанных
между собой узла Inputs и Outputs. На узле Inputs можно объявить входные
переменные, а на узле Outputs выходные (Рис. 11).
22
Рис. 11. Новая функция
Функция GridCellNumber достаточно проста в написании, ее главной
задачей является возвращением положения ячейки на сетке графа. Данная
функция может использоваться при необходимости узнать позицию по оси x
и y, а также по z, непосредственно внутри границ графа. Входные переменные
функция заданные ранее GridSizeWorld и CellSize. Выходные переменные
функции заданы на узле ReturnNode, они представляют собой координаты
ячейки по x и y внутри сетки. Координата z не берется внутри функции так как
перед данной работай не стоит задача генерировать произвольный граф по
ширине и высоте. Поэтому в дальнейшем функция будет дополняться
условиями перемещения отдельных ячеек выше по уровню чем все остальные,
при условии, что данный тип поверхности позволяет это сделать (Рис. 12).
Рис. 12. Функция GridCellNumber
23
Узел Round(округление) не работает на прямую с вектором, поэтому в
Blueprint скриптах, сперва следует разобрать вектор на два или более
значений.
Графу следует задать ограниченное пространство, чтобы поиск в
ширину не ушел в бесконечность. С данной задачей нам поможет функция
GridBottomLeft. Входными параметрами которой являются; компонент Scene
и его метод RightVector, публичная переменная типа Vector2d GridSizeWorld
и приватная переменная GridLocation типа Vector хранящая в себе
расположение графа в пространстве на основной сетке. Функция реализует
изначально невидимую границы графа (Рис. 13).
Рис. 13. Реализация границ графа в пространстве сцены
Для упрощения поиска поверхностей и препятствий поможет функция
SphereTrace. При генерации ячеек графа поиск в ширину используя данную
функцию будет проверять у каждой ячейки соприкосновение с объектами, у
которых есть указанный тип. На основе среднего значения CellSizeMinus и
CellSize вычисляется радиус трассирующей сферы для каждой ячейки графа
(Рис.14).
24
Рис. 14. Функция проверки соприкосновений
Подходя к последней функции следует предварительно в ContentBrowser
создать компонент Structure. В Structure вносятся глобальные переменные и
любые другие компоненты, созданные пользователем. В Structure добавляем
все что связанно с графом и с его ячейками, а именно groundType,
worldLocation, gridIndex. В первом случае будем обращаться к типам
соприкосновений, в следующем к координатам графа в пространстве и в
последнем к индексу ячейки графа. Данная структура значительно упростит
обмен информацией между функциями (Рис. 15).
Рис. 15. Структура с компонентами и переменными для графа
Создав структуру можно переходить к самой основной и завершающей
части генерации графа. Разделим функцию GenerateCellData на три этапа и
рассмотрим каждый отдельно. На первом этапе формируются x и y с помощью
Loop(циклов) берущих за основу данные полученные из раннее описанной
функции GridCellNumber (Рис. 16).
25
Рис. 16. Тело цикла
Необходимо учесть, что все функции, которые используются внутри
GenerateCellNumber имеют включенный параметр Pure, из-за этого являются
чистыми функциями, возвращающими при одинаковых аргументах одни и те
же значения.
Во втором этапе происходит формирования ячеек внутри заданного
пространства используя GridBottomLeft. Данный этап генерирует ячейки
внутри границ графа, проверяя соприкасается ли ячейка с чем-либо. Движение
алгоритма начинается с низу вверх и слева на право, что значительно ускоряет
работу программы и не нагружает процессор (Рис. 17).
Рис. 17. Формирования ячеек графа
Стоит отметить что участок функции отвечающий за формирование
ячеек работает строго от ячейки с индексом 0 и до последней с индексом n, для
каждого графа, если на сцене их более одного. Во многих примерах генерации
каких-либо структур с помощью поиска в ширину широко используется
26
рандомизация движения алгоритма по ячейкам графа. Данный способ
помогает работать с сложными запутанными структурами в виде лабиринтов.
На последнем завершающем этапе, проверяем соприкосновение ячейки
с типом поверхности. Отдельно указывается тип None и Normal, а все
остальные типы извлекаются с помощью узла Cast To(компонент содержащий
визуальные модели объектов соприкосновений с указанием типов) и Target с
указанием на Object Type(тип объекта) (Рис. 18).
Рис. 18. Определение столкновений
На данном этапе работы, граф можно проверить только на наличие
вычислительных ошибок. Поэтому встает необходимость визуализировать
граф в окне редактора и в окне программы.
§2.3 Визуализация ячеек графа в пространстве
Unreal Engine 4 предлагает два способа решения данной проблемы.
Первый использовать DebugPlane – позволяет создавать плоскости, видимые
только в окне Viewport редактора. Второй способ вынуждает создать 3-х
мерную модель ячейки, либо любым редактором 3-х мерной графики или
воспользоваться стандартным набором объектов в Unreal Engine 4.
27
Реализуем два способа, не используя сторонних программ для
моделирования. Отобразить ячейки в редакторе, можно всего на всего двумя
функциями, чтобы увидеть результат работы в окне собранной программы,
необходимость создать новый Blueprint класс с названием Cell для упрощения
обращения внутри скриптов других классов.
Иерархия компонента Cell схожа с компонентом, содержащим граф, но
дополнена StaticBody. В StaticBody можно добавить любую модель, из
стандартных имеющихся в Unreal Engine 4. В данном случае выбрана модель
Cube (Рис. 19).
Рис. 19. Содержимое компонента Cell
Стоит обратить внимание на вкладку Material. Оперировать с цветом 3х мерных объектов можно лишь через материалы. Создание материала для
ячейки облегчит работу с цветом в дальнейшем.
Добавив
новый
материал,
перед
пользователем
открывается
MaterialEditor. Работа в нем также проста, как и работа со скриптами. На
начальном этапе имеется только один узел Result Node, задачей пользователя
является размещением узлов с текстурой или цветом комбинируя их между
собой и отправляя на выход узла Result Node. Получившийся результат
отображается в левом верхнем углу в окне препросмотра. В данной работе
лучше всего подходит белая текстура с черными краями. Белый цвет легко
заменяется на любой другой, а черные края можно инвертировать, чтобы
28
создать эффект выделения ячейки при наведении курсора. Сперва формируем
текстуру ячейки, связываем ее операцией сложение с ConstantColor
переименованной в CellColor. К CellColor будем обращаться через скрипт и
менять ее цвет в зависимости от ситуации. Learp(Linear Interpolate) – поможет
совместить два состояния для материала, обычный цвет заданный при
генерации и цвет выделения при событии наведения курсора на ячейку графа.
В Result Node на параметре Shading Model следует включить Unlit, для
игнорирования освещения сцены (Рис. 20).
Рис. 20. Текстура и смена цвета для ячеек
Дополняем материал выделением ячейки по заданному событию. Из
начальной текстуры берем зеленый канал и с помощью не сложного условия
инвертируем цвет, чтобы определить границу. Предаем ей любой цвет и
подключаем к Lerp параметр bIsSelected. Данный параметр будет менять
состояние ячейки графа при наведении на него курсора (Рис. 21).
29
Рис. 21. Реализация обводки ячейки
Перейдем к программной части, визуализации ячеек графа. Сперва в
компоненте с графом объявим две функции DrawDebugPlane и DrawCell.
Первая функция реализует отображение ячейки в виде плоскости по заданным
размер в границах графа, а вторая функции будет передавать сгенерированный
поиском в ширину граф.
DrawDebugPlane – получая данные из Struct отправляет их в узел Switch,
где распределяет по типу и присваивает цвет. На выходе функции узел
DrawDebugPlane берет на себя отображение ячейки в области графа (Рис. 22).
Рис. 22. Функция DrawDebugPlane
Функция DrawCell принимает полученные раннее координаты и
размеры ячеек в пространстве, а также их тип соприкосновения и передает их
30
в DrawDebugPlane (Рис. 23).
Рис. 23. Функция DrawCell
Граф корректно отображается в редакторе и распределяет каждой ячейке
необходимый цвет при соприкосновении с заданными объектами (Рис. 24).
Рис. 24. Установка шаблонов экспорта
Остается также корректно отобразить 3-х мерные ячейки в окне
программы. Перейдя в компонент Cell следует объявить на этот раз три
функции SetCellColor, GetCellData, SetCellSize и четыре глобальных
переменных gridId, bp_Grid, bIs_overed, bIs_Selected.
31
Рассмотрим сперва переменные. Первая gridId – тип Vector2D,
предназначена для обращения к ячейкам графа, bp_Grid – ссылается на
компонент с графом, чтобы иметь доступ к его функциям. Остаются последние
две переменные типа Boolean bIs_overed и bIs_selected. Данные переменные
будут в роле флага, если на ячейку наведена мышь, то bIs_overed равна истине
программа отображает выделение, для bIs_selected ожидаем нажатия на
ячейку и отображения ее как выделенной на графе.
Перейдем к рассмотрению функций. GetCellData позволяет получить
всю необходимую информацию о ячейках графа из Struct Cells и в дальнейшем
передать ее в SetCellColor (Рис. 25).
Рис. 25. Функция GetCellData
Функция SetCellSize задаст размер ячеек графа, на основе изначально
заданных параметрах в сетке (Рис. 26).
Рис. 26. Функция SetCellSize
В разработке функции SetCellColor следует заранее продумать все
32
возможные случаи, в которых к ячейкам применяется тот или иной цвет.
Чтобы поделить функцию на разные случаи, нужно воспользоваться узлом
Sequence. Изначально добавим пять случаем. Важно не забывать, что отчет
идет от нуля и первый случай будет с индексом ноль.
Переходя к описанию случаев рассмотрим первый. В нем проводится
проверка на тип поверхности и как в DrawDebugPlane распределяется каждому
типу соответствующий цвет (Рис. 27).
Рис. 27. Определение цветов по типам для компонента Cell
В следующих двух случаях реализуется действие при событии
наведения мышки на ячейку и нажатия на нее. Наведя мышку на ячейку графа,
функция передает параметру bIs_selected единицу при которой края ячейки
выделяются, а при нажатии подсвечиваются (Рис. 28).
33
Рис. 28. Действия выбора и нажатия ячейки графа
Предпоследний случай достаточно прост в реализации. Ему потребуется
глобальная переменна типа Boolean isInPatch. Если эта переменная получает
истину, то путь от начала до конца окрасится в заданный цвет. Он будет
использоваться в работе алгоритма A* (Рис. 29).
Рис. 29. Отрисовка пути, найденного алгоритмом A*
Последний случай всегда должен выполняться в конце, он обновляет
материал при любых малейших изменениях цвета, как на одной, так и на всех
ячейках графа (Рис. 30).
34
Рис. 30. Применение изменения материалов ячеек
Перейдем в редактор событий для Cell и добавим все новые функции, на
событие Event BeginPlay. Данное событие запускает работу связанных между
собой функций на старте программы. При этом нужно учесть задержку в 0.2
секунды, для того чтобы поиск пути успел передать данные работы функциям
компонента Cell (Рис. 31).
Рис. 31. Событие при старте программы для Cell
Добавим пять Custom Event и разберем их подробно. Начнем с события
On Begin Cursor Over - данное событие определяет ячейку, на которую
наведен курсор мыши, а также оно предусматривает смену наведения курсора
мыши с одной ячейки на другую. Последующие два Custom Event, а именно
Event_StartOveredCell и Event_EndOveredCell отвечают за отображение при
наведении курсора мыши и отведении курсора. Событие On Clicked уже
находится в компоненте Cell, поэтому не стоит создавать Custom Event.
35
Данное событие позволит выделять ячейки с помощью следующих событий
Event_Select_Cell
и
Event_Deselect_Cell.
Последние
событие
Event_IsInPatch определяет есть ли путь на графе, если есть, то окрашивает
его от начальной до конечной ячейки, найденной алгоритмом A* (Рис. 27, Рис.
29, Рис. 30, Рис. 31, Рис. 32).
Рис. 27. Событие On Begin Cursor Over
Рис. 29. События Event_StartOveredCell и Event_EndOveredCell
36
Рис. 30. Событие On Clicked
Рис. 31. События Event_Select_Cell и Event_Deselect_Cell
Рис.32. Событие Event_IsInPatch
В
заключении
нагруженный
предпросмотра так и в окне редактора.
37
граф
отобразится
как
в
окне
§2.4 Реализация алгоритма A* на заданном графе
A* пошагово просматривает все пути, ведущие от начальной вершины в
конечную, пока не найдёт минимальный. Как и все информированные
алгоритмы поиска, он просматривает сначала те маршруты, которые
«кажутся» ведущими к цели. От жадного алгоритма, который тоже является
алгоритмом поиска по первому лучшему совпадению, его отличает то, что при
выборе вершины он учитывает, помимо прочего, весь пройденный до неё
путь. Составляющая g(x) — это стоимость пути от начальной вершины, а не
от предыдущей, как в жадном алгоритме.
В начале работы просматриваются узлы, смежные с начальным;
выбирается тот из них, который имеет минимальное значение f(x), после чего
этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством
путей из начальной точки до всех ещё не раскрытых (листовых) вершин
графа — множеством частных решений, — которое размещается в очереди с
приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x)[56]. Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой
вершины не окажется меньшим, чем любое значение в очереди, либо пока всё
дерево не будет просмотрено. Из множества решений выбирается решение с
наименьшей стоимостью.
Чем меньше эвристика h(x), тем больше приоритет, поэтому для реализации
очереди можно использовать сортирующие деревья.
Множество просмотренных вершин хранится в closed, а требующие
рассмотрения пути — в очереди с приоритетом open. Приоритет пути
вычисляется с помощью функции f(x) внутри реализации очереди с
приоритетом[6].
Отображать стоимость пути непосредственно на ячейках графа,
поможет виджет содержащий текст, данная возможность есть в классе Widget
Blueprint. Создав класс, во внутрь основного компонента стоит поместить
Canvas Panel и два Text как показано на (Рис. 33).
38
Рис. 33. Создание компонента Widget Blueprint
С помощью Canvas Panel можно позиционировать текст и любые другие
компоненты внутри него.
Создадим для Widget Blueprint две функции и две глобальные переменные
Get_FinalCostText, Get_CellCost, gridIndex и grid. Переменная gridIndex
хранит информацию о каждой ячейки графа, а с помощью grid мы сможем
получить компонент содержащий граф.
Функция Grid_FinalCostText передаст на Widget минимальную стоимость
достижения цели для A* (Рис. 34).
Рис. 34. Функция Grid_FinalCostText
Следующая функция Get_CellCost отображает стоимость прохождения
через ячейку (Рис. 35).
39
Рис. 35. Функция Get_CellCost
При отображении текста на ячейках, стоит добавить компонент Widget
внутри Cell и выбрать в нем раннее созданный Widget.
В скрипте компонента Cell создадим передачу числовой информации о
ячейках для компонента Widget (Рис. 36).
Рис. 36. Функция SetWidgetVar
Перейдем к реализации алгоритма поиска наикратчайшего пути на
заданном графе. Из всех известных алгоритмов A* является более точным чем
поиск в ширину и Дейкстра, так как находит путь к одной точке. Он отдаёт
приоритет путям, которые ведут ближе к цели.
40
В начале работы алгоритма просматриваются узлы, смежные с
начальным; выбирается тот из них, который имеет минимальное значение
стоимости, после чего этот узел раскрывается. На каждом этапе алгоритм
оперирует с множеством путей из начальной точки до всех ещё не раскрытых
(листовых) вершин графа — множеством частных решений, — которое
размещается в очереди с приоритетом. Алгоритм продолжает свою работу до
тех пор, пока значение стоимости целевой вершины не окажется меньшим,
чем любое значение в очереди, либо пока всё дерево не будет просмотрено. Из
множества решений выбирается решение с наименьшей стоимостью.
Объявим десять глобальных переменных с подробным описанием каждой.
Первая переменная список StructCells типа Vector2D хранит в себе все ячейки
графа и упрощает к ним обращение. Массив patch типа Vector2D хранит все
возможные пути до цели включая оптимально минимальный путь.
Переменные типа Vector2D DebugStartCell_L, DebugTargetCell_L и
DebugCurrentCell хранят информацию о начальной ячейки, промежуточной
и конечной, на пути A*. Переменные типа Vector2D DebugOpenSet и
DebugClosetCell также получают информацию о ячейках, но только о тех,
которые принадлежат к открытому и закрытому типу, упрощая их
отображение на Widjet и при старте программы. DebugOpenSetCheapest и
DebugCurrentNeighbours типа Vector2D хранят открытые ячейки с
наименьшей стоимостью, и ячейки соседи каждой конкретно выбранной
ячейки
графа.
DebugCurrentNeighboursCostFromStart
также
как
и
предыдущие переменные типа Vector2D хранит стоимость соседних ячеек
графа конкретно изначально выбранной ячейки как пользователем так и
алгоритмом. Завершает список переменная DebugJobComplited типа Boolean,
необходимая для выхода из работы алгоритма по его завершению (Рис. 37).
41
Рис. 37. Переменные для A*
Реализуем основную функцию алгоритма. Для полноценной работы A*
объявим четыре функции GetCellNeighbours, GetEstimatedCostToTarget,
FindPatchToTarget, RetracePatch (Рис. 38).
Рис. 38. Функции алгоритма A*
GetCellNeighbours – функция формирующая информацию о соседях
выбранной ячейки. На первом этапе задается матрица возможных соседей,
если соседей нет, то функция заканчивает работу, если сосед найден, тогда
переходим к определению типа и взятию стоимости прохождения пути через
данного соседа (Рис. 39).
42
Рис. 39. Первый этап функции GetCellNeighbours
Следующим этапом функции GetCellNeighbours как было сказано
раннее является определением принадлежности соседа к заданному в
Enumerator типу поверхности. Если сосед ячейки None или Impossible, то
отображение пути через них отменяется, а функция завершается на последнем
пройдённом этапе (Рис. 40).
Рис. 40. Завершающий этап функции GetCellNeighbours
Чтобы упростить взятие оценки стоимости пройденного пути,
воспользуемся
функцией
GetEstimateCost.
Функция
требует
начальной и конечной ячейки, для проведения вычислений (Рис. 41).
43
наличие
Рис. 41. Функция GetEstimateCost
Описывая функцию FindPatchToTarget стоит разделить ее на несколько
этапов. В начале функция формирует информацию о начальной и конечной
точки и проверяет ее, чтобы условие не попадало в типы None и Impossible
(Рис. 42).
Рис. 42. Начальный этап FinPatchToTarget
Default Value в следующей части функции формирует стартовые
значения на начальной и конечной ячейки графа основываясь на раннее
заданной информации Structure. GetEstimateCost здесь формирует начальную
оценку стоимости пути до конечной точки (Рис. 43).
44
Рис. 43. Начальные значения FinPatchToTarget
Взяв информацию о начальной и конечной ячейках далее следует цикл
определяющий расстояние, если оно меньше чем две ячейки, то алгоритм
завершает работу, иначе входим в следующий цикл (Рис. 44).
Рис. 44. Цикл, проверяющий длину пути
Войдя в следующий цикл, сперва проверяем пути с наименьшей
стоимостью. Берем каждый и заносим в переменную openSetCheapest (Рис. 45).
45
Рис. 45. Проверка путей с наименьшей стоимостью
Следующий далее цикл определяет множество уже пройденных вершин
которое можно опустить (при этом алгоритм превратится в поиск по дереву
решений), если известно, что решение существует (Рис. 46).
Рис. 46. Отсеивание наименьшей стоимости
Оставшиеся условия проводят оценку стоимости каждого соседа ячейки
с начала пут и завершают работу алгоритма если минимальное значение
целевой вершины оказывается самым меньшим, чем любое значение в
очереди, либо пока всё дерево не будет просмотрено (Рис. 47, Рис. 48).
46
Рис. 47. Оценка стоимости каждого соседа ячейки
Рис. 48. Завершающий этап функции FinPatchToTarget
В
заключении
следует
сказать,
что
существует
несколько
особенностей реализации и приёмов, которые могут значительно повлиять на
эффективность алгоритма. Первое, на что не мешает обратить внимание — это
то, как очередь с приоритетом обрабатывает связи между вершинами. Если
вершины добавляются в неё так, что очередь работает по принципу LIFO, то
в случае вершин с одинаковой оценкой A* «пойдёт» в глубину. Если же при
добавлении вершин реализуется принцип FIFO[7-8], то для вершин с
одинаковой оценкой алгоритм, напротив, будет реализовывать поиск в
47
ширину. В некоторых случаях это обстоятельство может оказывать
существенное значение на производительность. В данной работе алгоритм
построен по принципу FIFO, и работает не с стеком как в LIFO, а с
сортирующим деревом.
В случае данной работы, по окончании работы от алгоритма требуется
маршрут, вместе с каждой вершиной хранится ссылка на родительский узел.
Эта ссылки позволяют реконструировать оптимальный маршрут. Поэтому
важно, чтобы одна и та же вершина не встречалась в очереди дважды (имея
при этом свой маршрут и свою оценку стоимости). Для решения этой
проблемы при добавлении вершины алгоритм проверяет, нет ли записи о ней
в очереди. Если она есть, то запись обновляют так, чтобы она соответствовала
минимальной стоимости из двух. Для поиска вершины в сортирующем дереве
многие стандартные алгоритмы требуют времени O(n)[8]. Поэтому данное
дерево усовершенствовано с помощью хеш-таблицы, что значительно
ускоряет время работы алгоритма.
48
ГЛАВА III ИССЛЕДОВАНИЯ, ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
§3.1 Нагруженный граф и поиск пути на нем
В результате проделанной работы в окне редактора Unreal Engine 4,
отображается нагруженный динамически генерируемый граф (Рис. 49).
Рис. 49. Граф в окне редактора
На [Рис. 49] граф нагружен стоимостью прохождения каждой ячейки на
основе информации о типах соприкосновений. Каждый статический объект на
сцене хранит определенный тип соприкосновения. Граф можно двигать и
вращать относительно объектов сцены, чтобы изменять значение ячеек. В
местах соприкосновения на сгенерированном графе при изменении или
удалении статического объекта пересчет стоимости прохождения ячейки
ведется в конкретном месте, где соприкосновение изменилось, придвижении
графа пересчет идет по всему графу.
49
В окне программы отчетливо демонстрируется работа алгоритма A*.
Синие ячейки отображают оптимально минимальный путь, найденный
алгоритмом, желтые и зеленые ячейки относятся к закрытому и открытому
спискам (Рис. 49).
Рис. 49. Граф в окне программы
Стоит отметить, что любые изменения местоположения объектов на
графе не приводят к перерасчету всего графа, а только в начальной и конечной
точках перемещенного объекта, что значительно снижает на грузку на ЦП.
Данная
особенность
подробно
описана
при
записи
информации
о
встречающихся препятствиях.
§3.2 Реализация 3-х мерности графа. Перемещение ячеек по z
Случай, когда необходимо отобразить ячейки графа над непроходимым
50
объектом, конкретно на его поверхности. Ячейки с типом Impossible
дублируются и приподнимаются по z с учетом высоты статического объекта.
Следует отметить, при дублировании связи ячеек сохраняются, изменяется
лишь тип соприкосновения с Impossible на Normal. Важно добавить, что
алгоритму, реализующему генерацию сетки следует добавить функцию для
определения вхождения поиска пути на данную поверхность, либо через
другой объект соприкосновения или при соприкосновении с Impossible. Для
определения уровней или этажей сетки по z можно использовать встроенный
узел Layer (Рис. 50).
Рис. 50. Отображение ячеек графа над непроходимым объектом Impossible
Описанный способ хорошо показывает себя при создании графа на 3-х
мерном ландшафте на котором можно задать не типы препятствий, а типы
проходимых поверхностей на участках ландшафта. Данную особенность
51
можно использовать при расчетах времени на прохождение того или иного
участка ландшафта, каждый участок можно нагружать такими параметрами
как трение вязкость и т.п. (Рис. 51).
Рис. 51. Визуализация графа на 3-х мерном ландшафте
Проводя тестирование алгоритма на разных типах поверхностей от
плоскостей до ландшафтов инструмента Terrain, граф и поиск пути на нем
показывали наилучшие результаты по работе алгоритма в целом.
§3.3 Оптимизация программы
Подводя итог следует сказать об оптимизации проекта. Чтобы выявить
нагрузку на процессор, ошибки в написании скриптов и в конечном итоге
ускорить работу программы Unreal Engine 4 большой набор инструментов для
52
отладки программы. В результате работы с ними, были внесены изменения в
ряд работы некоторых функций, что ускорило скорость генерации одного
заданного графа с 0.206 до 0.07 секунд. Сгенерированный граф в работающей
программе при его повторной генерации требует 0.001 секунду или 1
миллисекунду. Работа алгоритма поиска на графе также не загружает ЦП и на
просчет пути требует всего 1 миллисекунду с незначительной погрешностью
в плюс равной 0.00192138 секунд. При работе двух алгоритмов сразу, а именно
при просчете графа и отображении пути на нем задержка проходит в 2
миллисекунды или 0.00292165 секунды. Данные значения могут разниться на
разных комплектациях ПК. Разработка и тест программы на момент написания
диссертации проводился на ПК с процессором Intel Core i5-2500k CPU
3.30GHz 3.60 GHz и установленной памятью 8,00 ГБ. Следует сделать вывод,
что на современных ПК скорость работы программы будет расти, так как
прогресс не стоит на месте.
53
ЗАКЛЮЧЕНИЕ
В данной работе рассматривается задача о разработке программного
обеспечение для реализации алгоритмов проблемы распознавания
поверхностей. Подобные задачи являются востребованными, так как имеют
теоретическое и практическое применение.
Очевидно, что для решения подобных задач должны применять
алгоритмы, обеспечивающие высокую степень точности результата. Так как
одним алгоритма поиска пути не решить данную задачу, то в данной работе
применяется метод совмещения двух алгоритмов для решения поставленной
цели.
В процессе работы были наглядно продемонстрированы все этапы
создания программы, от реализации алгоритма генерации сетки графа, до
алгоритма А* и экспорта в конечный вариант для запуска на ОС.
Достигнута следующая цель: разработать программное обеспечение для
реализации
алгоритмов
проблемы
распознавания
поверхностей
и
препятствий.
В процессе работы были решены следующие задачи:
1.
Исследованы разные типы графов и алгоритмы поиска на них, в
результате выбраны оптимальные;
2.
Обоснованно найдено наиболее подходящее средство для реализации
программы;
3.
Найдено оптимальное решение нескольких алгоритмов в среде Unreal
Engine 4.
4.
Проведены работы по оптимизации программы;
5.
Осуществлен экспорт приложения в конечный исполнимый файл.
Работа выполнена с помощью визуального языка программирования
Blueprint программы Unreal Engine 4. Приложение и его исходный код,
созданные с помощью данного инструмента, подготовлены для дальнейшего
широкого применения.
Работа имеет теоретическое и практическое значение, так как
54
полученный результат может быть использованы для корректировки модели и
построения более сложных алгоритмов, а разработанная программа может
применяться для дальнейших исследований при различных входных
параметрах и решении задач прикладного характера, связанных с процедурной
генерации структур, а также поиском пути на 3-х мерных поверхностях.
Промежуточные результаты исследования были опубликованы в
следующих научных работах:
1. Визуализация модели архитектуры. Создание интерактивной карты
проблемы создания интерактивных карт помещений // II Международная
научно-практическая
конференция
«Современные
проблемы
физико-
математических наук», г. Орел, Орловский государственный университет им.
И. С. Тургенева, 24-27 ноября 2016 г. С. 173-175.
2. Реализация поиска путей проблемы распознавания алгоритмом
поверхностей и препятствий // семинар «Вычислительные технологии и их
приложения» г. Орел, ОГУ им. И. С. Тургенева, на основании Распоряжения
ректора ОГУ от 15.11.2017 № 577р, 1 февраля 2018 г.
55
СПИСОК ЛИТЕРАТУРЫ
1.
Unreal
Engine
[Электронный
ресурс].
–
Режим
доступа:
https://www.unrealengine.com/ – Дата доступа: 21.02.2018.
2.
Русскоязычное сообщество Unreal Engine 4 [Электронный ресурс]. –
Режим доступа: https://uengine.ru – Дата доступа: 21.02.2018.
3.
Поиск В Ширину. URL: https://ru.wikipedia.org/wiki/Поиск_в_ширину
4.
Генерация и решение лабиринта с помощью метода поиска в глубину по
графу
[Электронный
ресурс].
–
Режим
доступа:
https://habrahabr.ru/post/262345/ – Дата доступа: 21.02.2018.
5.
Поиск
A*
[Электронный
ресурс].
–
Режим
доступа:
https://ru.wikipedia.org/wiki/A* – Дата доступа: 21.02.2018.
6.
Основные понятия теории графов [Электронный ресурс]. – Режим
доступа: http://lib.vvsu.ru/books/Bakalavr01/page0221.asp – Дата доступа:
21.02.2018.
7.
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и
анализ. 2-е издание. – М.: Вильямс, 2010. – 1296с.
8.
Sedgewick R. Algorithms in C++ Part 5: Graph Algorithms, 3rd Edition. –
Addison-Wesley Professional, 2001. – 528 с.
9.
Barnes E. R. An algorithm for partitioning the nodes of a graph // SIAM J.
Algebraic Discrete Methods. — 1982. — Vol. 4, no. 3. — P. 541—550.
10.
Dijkstra E. W. A note on two problems in connexion with graphs // Numer.
Math. — 1959. — Vol. 1. — P. 269—271.
11.
Fakcharoenphol J., Rao S. Planar graphs, negative weight edges, shortest
paths, and near linear time // Proc. 42nd IEEE Symp. Foundations of Computer
Science. — 2001. — P. 232—241.
12.
Fredman M. L., Tarjan R. E. Fibonacci heaps and their uses in improved
network optimization algorithms // J. ACM. — 1987. — Vol. 34, no. 3. — P. 596—
615.
13.
Goldberg A. V., Harrelson C. Computing the shortest path: A∗-search meets
graph theory // Proc. Sixteenth Annual ACM—SIAM Symp. on Discrete
56
Algorithms, January 23—25, Vancouver, BC (2005). — P. 156—165.
14.
Hilger M., Kohler E., M ¨ ohring R. H., Schilling H. Fast point-to-point
shortest path ¨ computations with arc-flags // The Shortest Path Problem: Ninth
DIMACS Implementation Challenge C. Demetrescu, A. V. Goldberg, D. S. Johnson,
eds. — Amer. Math. Soc., 2009. — (DIMACS Book; Vol. 74). — P. 41—72.
15.
Steinhaus H. Sur la division des corps materiels en parties // Bull. Acad.
Polon. Sci. ´ Cl. III. — 1956. — No. 4. — P. 801—804.
16.
Nash A. Any-Angle Path Planning. Dis. … Doctor of Philosophy (Computer
Science). University of South California. August 2012.
17.
Botea A., Muller M., Schaeffer J. Near Optimal Hierarchical Path-Finding.
Journal of Game Development, 2004, vol. 1, issue 1, pp. 7–28.
18.
Daniel K., Nash A., Koenig S., Felner A. Theta*: Any-Angle Path Planning
on Grids. Journal of Artificial Intelligence Research, 2010, vol. 39, pp. 533–579.
19.
Variants of A*, Amit Patel’s Home Page [Электронный ресурс]. – Режим
доступа: http://theory.stanford.edu/~amitp/ GameProgramming/Variations.html –
Дата доступа: 12.04.2018.
57
58