— Да эти подростковые фильмы таки бесят. Дивергент, Инсургент, бегущий в лабиринте, голодные игры, сумерки, гостья и т. д.
— Вот, кстати, да, расплодилось их
— Выпустили бы уже один идеальный подростковый фильм и успокоились “Бегущий в сумеречном лабиринте голодный дивергент”
— На это я б сходил.
Теория
Поиск выхода из лабиринта — простой алгоритм. Основным принципом данного алгоритма является проход по структуре в форме матрицы или графа, который точно определяет связи одной точки в пространстве с другой.
Представим алгоритм в виде анализатора матрицы, тогда будет очевидно что стенкой и пустой клеткой будут определенные значения, по которым алгоритм понимает куда ему можно перейти, а куда нельзя. Однако его достаточно сложно применить, так как далеко не всегда даются готовые наборы данных, как например, матрицы со стенками и проходами. Что делать в случае, если лабиринт не представим в виде матрицы? Например, круглый или вообще пещероподобный лабиринт таким способом обрабатываться не будет.
Для этого есть другие способы, например, анализатор графа. Данный алгоритм представляет лабиринт в виде множества точек и связей между ними, каждая связь сообщает о возможности переместится из точки в другую, и они не завязаны на клетках как матрице. Однако и это не является идеальным вариантом, так как составлять граф руками для каждого лабиринта сложно и очень не удобно.
Задача
В данной лабораторной работе потребуется создать программу, которая по картинке определяет путь к выходу из лабиринта. На картинке белым и близкими цветами обозначается место, по которому можно пройти, черным или оттенками серого - стены и двумя цветами (красным и зеленым) - вход и выход. Остается лишь создать алгоритм, который подготовит структуру. А также алгоритм, который на данной структуре определит выход.
1 часть
Можно рассматривать изображение как лабиринт заданный матрицей, где каждый отдельный пиксель - клетка такого лабиринта.
2 часть
Для более высокой оценки использовать предыдущий подход к анализу лабиринта нельзя. Представьте изображение больше как реальный объект, а не совокупность пикселей.
Примеры
Скачать пример
Скачать пример
Скачать пример
Скачать пример
Скачать пример
Скачать пример
Скачать пример
Дополнительно
От вас требуется сделать программу, которая получает на вход путь к файлу (лабиринту), а на выходе путь в виде списка координат (пиксельных или субпиксельных).
Подсказка 1
По идее любой лабиринт можно представить в виде матрицы с клетками, например, как это делают игроки в Dungeons&Dragons, разделяя поле на клетки. При это разделение происходит не строго по пикселям.
Подсказка 2
Даже если лабиринт представим в виде матрицы не всегда нужно использовать алгоритм связанный с двумерными массивами. Пример брутфорса лабиринта.
Подсказка 3
Можно создать множество точек и попытаться соединить их в граф, а после найти в нем минимальный путь (ну или хотя бы какой-то путь).