Источник: http://www.gamedev.ru/pages/zhekas/articles/Poisk_kratchayshego_puti
В данной статье рассматривается алгоритм поиска кратчайшего пути между двумя элементами в пространстве.
Актуальность. Задача поиска кратчайшего пути появилась довольно давно и включает довольно много алгоритмов (вариантов) их решения. Такие алгоритмы предполагают полный перебор всех возможных вариантов передвижения. Как правило, данные алгоритмы имеют широкое применение в игровых программах, когда необходимо найти и проложить кратчайший маршрут по игровому полю с учетом всех возможных препятствий. Актуальность данного алгоритма заключается в том, что мы заведомо узнаем кратчайший путь еще до начала маршрута. Это один из так называемых алгоритмов планирования. В достоинства данного алгоритма также входит то, что решение благодаря описываемому методу не всегда может быть единственным, но всегда будет однозначным.
Постановка задач исследования. Пространство или то по чему мы будем совершать передвижение может быть представлено в виде четырех-, шести-, восьми- или восемнадцати- связного графа. Связи есть возможные варианты передвижения. Для четырехсвязного графа предполагается передвижение по четырем направлениям, в данном случае это может быть передвижение вверх, вниз, влево и вправо, такой граф будет подобен виду (см. Рис. 1), в случае восьмисвязного графа получаем еще возможность передвижения и по диагоналям (см. Рис. 2). Граничащие вершины имеют меньшее число связей.
Постановка задач исследования. Пространство или то по чему мы будем совершать передвижение может быть представлено в виде четырех-, шести-, восьми- или восемнадцати- связного графа. Связи есть возможные варианты передвижения. Для четырехсвязного графа предполагается передвижение по четырем направлениям, в данном случае это может быть передвижение вверх, вниз, влево и вправо, такой граф будет подобен виду (см. Рис. 1), в случае восьмисвязного графа получаем еще возможность передвижения и по диагоналям (см. Рис. 2). Граничащие вершины имеют меньшее число связей.
Если же мы говорим о шестисвязном графе, то мы имеем в виду «трехмерный» граф в котором помимо передвижений по сторонам возможно передвижение и по высоте. Такое пространство представляет собою двумерный (как в случае с четырех-, или восьми- связном графе) или трехмерный массив, каждая вершина которого имеет итого шесть или восемнадцать связей. В данной статье будут рассмотрены общие правила, по которым этот алгоритм можно применять и модифицировать под любые последующие законы передвижения. Когда мы говорим о поиске кратчайшего пути мы говорим прежде всего об условиях передвижения или точках в которые мы можем передвигаться. Условием передвижения или преграды может быть ячейка двумерного (трехмерного) массива с особым значением. Точки начала и пункта назначения пути должны выделяться и быть заданы априори. В итоге мы имеем матрицу с возможными и невозможными вариантами пути, а также точками начала пути и пункта назначения.
Решение задачи и результаты исследований. Рассмотрим применение данного алгоритма для двумерной карты (двумерного массива), в которой для перехода от клетки к клетке существует четыре возможные варианта передвижения (вверх, вниз, влево и вправо). Пусть условно элемент массива «-1» будет преграда, через которую пройти нельзя, «1» – точка начала пути, «0» клетка через которую возможно передвижение, а «-2» будет пункт назначения. Понятно, что элементы «1» и «-2» должны встречаться единожды, иначе может произойти сбой алгоритма. Допустим, что для поиска кратчайшего пути нам была дана такая исходная карта:
-1 -1 -1 -1 -1 -1
-1 1 0 0 -2 -1
-1 0 0 -1 0 -1
-1 0 0 0 0 -1
-1 -1 -1 -1 -1 -1
Решением будет направление в какую из четырех сторон нужно предпринять движение (влево, вниз, вверх или вправо) из пункта «1» чтобы добраться пункта «-2», либо наглядно проложенный маршрут кратчайшего пути.
Визуально мы без труда его можем проложить:
Итого потратив на передвижение 2 клетки.
А теперь приступим к программированию самого алгоритма, который условно можно поделить на два основных этапа. Первый этап – этап подготовки матрицы так называемое планирование, когда оценивается количество ходов или тяжесть достижения каждой клетки от дальности первоначальной. Начинать возможный маршрут будем с координаты начала пути или значения «1». Когда мы передвинулись в соседнюю клетку с пометкой «0» (возможно перемещение в элементы только с этой пометкой), мы суммируем количество ходов, потраченное на перемещение к предыдущей клетке на единицу, а результат суммирования записываем в ту ячейку, в которую было совершено передвижение, т. е. с пометкой «0». За первый проход этапа планирования мы рассматриваем все возможные ситуации передвижения дальностью в 1 клетку от значения с координатами «1» первоначальной. То есть, таким образом, мы передвигаемся в соседние клетки, замеряя при этом «потраченные силы», записывая количество потраченных на них ходов. Итого после первого прохода мы получим следующий массив:
-1 -1 -1 -1 -1 -1
-1 1 2 0 -2 -1
-1 2 0 -1 0 -1
-1 0 0 0 0 -1
-1 -1 -1 -1 -1 -1
Если бы было возможно передвижение и по диагоналям мы получили бы такой массив:
-1 -1 -1 -1 -1 -1
-1 1 2 0 -2 -1
-1 2 2 -1 0 -1
-1 0 0 0 0 -1
-1 -1 -1 -1 -1 -1
Появилась третья «двойка» в которую мы никак не смогли бы попасть за один ход, передвигаясь в одно из четырех направлений.
Второй проход мы совершаем уже из клеток со значениями «2» в клетки значениями «0», которые иначе можно назвать «не пройденными». Словом так мы будем повторять до тех пор, пока ни останется, ни одной «не пройденной» клетки. Результат второго прохода:
-1 -1 -1 -1 -1 -1
-1 1 2 3 -2 -1
-1 2 3 -1 0 -1
-1 3 0 0 0 -1
-1 -1 -1 -1 -1 -1
После того как последняя «не пройденная» клетка будет заполнена количеством потраченных до нее ходов, получим такую матрицу:
-1 -1 -1 -1 -1 -1
-1 1 2 3 -2 -1
-1 2 3 -1 7 -1
-1 3 4 5 6 -1
-1 -1 -1 -1 -1 -1
На этом этап планирования заканчивается. Второй этап – прокладывание кратчайшего пути. Теперь мы будем двигаться от точки «-2» к точке «1» по наименьшему маршруту. Выбираем наименьший ближайший элемент больший нуля пункта назначения или «-2». Это будет элемент «3». То есть, чтобы добраться от пункта «1» к пункту «-2» понадобится ровно 3 хода. Далее рекурсивно двигаемся от «тройки» по наименьшим элементам к «1», предпоследнее направление передвижения даст сторону, в которую нужно двигаться, чтобы достичь цели (или пункта «-2»). Если после этапа подготовки матрицы соседние элементы пункта «-2» равны «0», то условия такой матрицы фиктивны, или попросту маршрут от начальной точки к пункту назначения невозможен. Пример такой матрицы:
-1 -1 -1 -1 -1 -1
-1 1 -1 0 -2 -1
-1 0 -1 -1 0 -1
-1 0 0 -1 0 -1
-1 -1 -1 -1 -1 -1
А так будет выглядеть эта матрица после этапа планирования:
-1 -1 -1 -1 -1 -1
-1 1 -1 0 -2 -1
-1 2 -1 -1 0 -1
-1 3 4 -1 0 -1
-1 -1 -1 -1 -1 -1
Понятно, что из-за препятствий достижение пункта «-2» не является возможным и точки «0» за «стенкой» остаются недостигнутыми. В таком случае работу алгоритма следует немедленно прекратить и проинформировать пользователя, что маршрут невозможен.
Совершенно необязательно использовать данный алгоритм именно под прямоугольную карту, иными словами границы которой очерчивают прямоугольник.
Края исходной карты под любую другую задачу могут выглядеть примерно вот так:
-1 -1 -1 -1 -1 -1
-1 -1
-1 -1
-1 -1 -1
-1 -1 -1 -1
-1 -1
-1 -1 -1 -1 -1
В этом случае следует модифицировать исходные данные (в нашем примере это двумерный массив). Тем зонам, которые находятся за границами и не входят в очерченные участки, нужно придать значение преграды, т. е. записать туда «-1». Тогда модифицированные исходные данные будут иметь такой прикладной вид:
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
Основные преимущества данного алгоритма в точности, скорости и однозначности решения. Тестирование работы алгоритма показало, что любой результат его работы успешно достигнут (фиктивность исходных данных также учитывается, алгоритм в этом случае выдаст ошибку) и соответствует действительности. Единственное неудобство алгоритма в том, что к каждой клетке элемента массива невозможно применять веса. На практике существует много примеров использования данного алгоритма: это может быть лабиринт, игровая программа, использующая тайлы, однако и тут действует ограничение: только четырех-, шести-, восьми- и восемнадцати- направленное передвижение (в двумерном или трехмерном массиве) от элемента к элементу, хотя правила передвижения мы можем регулировать и задавать их сами. Однако данный алгоритм является самым эффективным алгоритмом поиска кратчайшего маршрута не использующий весовые параметры.