Лабораторная работа №2 Алгоритмы поиска пути

Реализовать приложение, выполняющее следующие функции

1. Загрузка карты уровня в формате bmp (или любом схожем). Белый цвет – проходимая ячейка, черный – непроходимая. Размер карты 32х32 пикселя

2. Точка старта и точка финиша задаются по варианту

3. Отрисовка карты уровня

4. Перемещение фишки (игрока) от точки старта до точки финиша в автоматическом режиме

5. Отрисовка пройдённого маршрута любым удобным способом

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

Сдача лабораторной работы происходит в два этапа:

1. Демонстрация загрузки карты уровня, отрисовка и разбиение ее на блоки, пригодные к обработке

2. Добавление движения фишки и поиска пути от старта к финишу

№	Ключевые точки	Алгоритм	№	Ключевые точки	Алгоритм
1.	Старт – верхний левый угол. Финиш – нижний правый	Алгоритм Дейкстры	2.	Старт – верхний правый Финиш – верхний левый угол.	Алгоритм Дейкстры
3.	Старт – верхний правый Финиш – верхний левый угол.	Волновой алгоритм	4.	Старт – слева по центру. Финиш – верхний правый угол.	Волновой алгоритм
5.	Старт – слева по центру. Финиш – верхний правый угол.	Алгоритм A*	6.	Старт - нижний правый. Финиш – справа по центру.	Алгоритм A*
7.	Старт - нижний правый. Финиш – справа по центру.	Алгоритм Дейкстры	8.	Старт – верхний левый угол. Финиш – нижний правый	Алгоритм Дейкстры
9.	Старт – верхний левый угол. Финиш – нижний правый	Волновой алгоритм	10.	Старт – верхний правый Финиш – верхний левый угол.	Волновой алгоритм
11.	Старт – верхний правый Финиш – верхний левый угол.	Алгоритм A*	12.	Старт – слева по центру. Финиш – верхний правый угол.	Алгоритм A*
13.	Старт – слева по центру. Финиш – верхний правый угол.	Алгоритм Дейкстры	14.	Старт - нижний правый. Финиш – справа по центру.	Алгоритм Дейкстры
15.	Старт - нижний правый. Финиш – справа по центру.	Волновой алгоритм	16.	Старт – верхний левый угол. Финиш – нижний правый	Волновой алгоритм
17.	Старт – верхний левый угол. Финиш – нижний правый	Алгоритм A*	18.	Старт – верхний правый Финиш – верхний левый угол.	Алгоритм A*

Алгоритм поиска A*

A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. От жадного алгоритма (который тоже является алгоритмом поиска по первому лучшему совпадению) его отличает то, что при выборе вершины он учитывает, помимо прочего, весь пройденный до неё путь (составляющая g(x) — это стоимость пути от начальной вершины, а не от предыдущей, как в жадном алгоритме). В начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено).

Из множественных решений выбирается решение с наименьшей стоимостью.

Чем меньше эвристика h(x), тем больше приоритет (поэтому для реализации очереди можно использовать сортирующие деревья).

Волновой алгоритм

На двумерной клетчатой карте (матрице), состоящей из «проходимых» и «непроходимых» клеток, обозначена клетка старта и клетка финиша. Цель алгоритма — проложить кратчайший путь от клетки старта к клетке финиша, если это, конечно, возможно. От старта во все направления распространяется волна, причем каждая пройденная волной клетка помечается как «пройденная». Волна, в свою очередь, не может проходить через клетки, помеченные как «пройденные» или «непроходимые». Волна движется, пока не достигнет точки финиша или пока не останется непройденных клеток. Если волна прошла все доступные клетки, но так и не достигла клетки финиша, значит, путь от старта до финиша проложить невозможно. После достижения волной финиша, от финиша прокладывается путь до старта и сохраняется в массиве.

Алгоритм Дейкстры

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.