Поиск пути

На гребне волны...

Один из самых простых для понимания алгоритмов поиска путей и вместе с тем довольно эффективный — волновой поиск. Он идеально подходит для небольших карт, которые можно представить в виде двумерного массива ячеек. Для начала вам нужно завести еще один двумерный массив целых чисел такого же размера.

Алгоритм работает следующим образом. Находим точку А, из которой начинается поиск, и в этом месте в вспомогательном массиве ставим 0. Во всех свободных ячейках, которые прилегают к ячейке с нулем, пишем 1. Во всех свободных от цифр и препятствий ячейках, которые прилегают к ячейкам с 1, пишем 2. Повторяем этот процесс для всех остальных ячеек, пока не дойдем до ячейки B, путь до которой нам требовалось найти. Если вы визуализируете этот процесс в динамике, то увидите, что от точки A разбегается волна из цифр. Отсюда и название алгоритма. Как только наша цифровая волна захлестнет точку B, строим от нее путь до точки A по правилу: следующая точка пути должна лежать в ячейке с меньшим, чем в текущей ячейке числом.

Алгоритм неплохо справляется с разного рода тупиками и всегда найдет путь из A в B, если он вообще существует. Другое дело, что этот путь редко будет кратчайшим из возможных. К сожалению, волновой поиск нельзя использовать на больших картах (с десятком тысяч и более клеток), так как он работает очень медленно.

Поиск в глубину

Предыдущий алгоритм иногда называют поиском в ширину, потому что он уровень за уровнем просматривает ближайшие клетки. Поиск в глубину выбирает какое-то одно направление и просматривает его вглубь на заданное число клеток, переходит к следующему направлению и так далее, пока не найдет конечную точку. Представленная ниже рекурсивная функция находит не все возможные пути. Чтобы найти кратчайший путь, надо вызвать эту функцию для каждой из клеток, прилегающих к начальной клетке. Во вспомогательном булевом массиве Mark такого же размера, как и остальная карта, хранится 1, если текущая клетка уже пройдена алгоритмом, и 0 — в противном случае. В переменных Destination_x и Destination_y должны храниться координаты точки, куда в итоге надо попасть. В глобальной перемененной Length будет храниться длина текущего пути, чтобы мы не залетели вглубь матрицы дальше, чем MAX_LENGTH.

Procedure DepthSearch(x,y:integer);

Var

i : integer;

Begin

If Length>MAX_LENGTH then exit;

Mark[x,y] := True;

If (x=Destination_x) and (y=Destination_y) then

Begin

{

Мы нашли эту точку! Искомый путь представлен значениями True в массиве Mark. Здесь вы можете запомнить построенный путь и очистить Mark[x,y], чтобы продолжить поиск, или же остановиться, если задачей было найти хотя бы один путь.

}

End;

Length:=Length+1;

If Mark[x+1,y]=false then DepthSearch(x+1,y);

If Mark[x,y+1]=false then DepthSearch(x,y+1);

If Mark[x+1,y+1]=false then DepthSearch(x+1,y+1);

If Mark[x-1,y-1]=false then DepthSearch(x-1,y-1);

If Mark[x-1,y]=false then DepthSearch(x-1,y);

If Mark[x,y-1]=false then DepthSearch(x,y-1);

Length:=Length-1;

End;

В некоторых случаях этот алгоритм работает быстрее, чем волновой, но у него есть свой недостаток: если точка, путь до которой надо найти, находится дальше, чем MAX_LENGTH, алгоритм ее не найдет. Можно снять это ограничение, но тогда появится опасность зацикливания. Поиск в глубину хорошо работает в случае больших лабиринтов с узкими проходами. На широких открытых пространствах лучше использовать поиск в ширину.