Наверное, некоторые из вас смотрели фильм «Бегущий в лабиринте», где группа подростков живет в ущелье в центре лабиринта, населенного чудовищами? Они находят выход, умело используя подсказки. Но существуют алгоритмы и даже программы, способные на поиск выхода из лабиринта. О них мы и поговорим.

Как пройти лабиринт?

Зачем нам какой-то лабиринт лабиринт, спросит читатель? И как мы можем его найти с помощью программы? Ведь она ходов-выходов не видит? И, потом, есть ведь правило «левой» и «правой» руки, которое, наверное, дает возможность отыскать выход в любом лабиринте.

Действительно, программа выхода не видит. А вот правило «левой или правой» руки запросто может не сработать, если лабиринт имеет независимые элементы, несвязанные непрерывными стенами с остальной частью системы ходов. Тогда остается лишь… общий для всего лабиринта пол, который никак не поможет нам определить верное направление.

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

Лабиринт может быть и не лабиринтом, а картой метро или схемой дорог, которую нужно проскочить с наименьшими затратами либо серпантином горных ущелий, среди крутых склонов которых надо выбрать наиболее доступные. Словом, вариантов много. Так как же нам поступить?

Вездесущая матрица

Мы, конечно, люди современные и понимаем, что для составления маршрута нам необходима карта местности, хотя бы приблизительная. А если её нет — придется её составить. Включим воображение и представим, что мы у порога лабиринта, а в руке у нас пульт от квадрокоптера с видеокамерой. Раз, два, три — дрон уже в воздухе и снимает наш лабиринт сверху. Возможны варианты. Если это пещера — мы отправляем туда самодвижущийся механизм на гусеницах, если подводный «Аравийский тоннель», как в книге про капитана Немо (там предполагалось, что на месте нынешнего Суэцкого канала существует сквозная пещера, соединяющая Средиземное и Красное моря) — то подлодку-дрон. Их нестрашно потерять и карту своего пути они передадут нам с помощью современных технических средств.

Но путь — это только полдела. В современной реальности важнее всего иметь под рукой самый короткий, удобный и дешевый путь, чтобы ускорить перевозку и обойти конкурентов. А составление кратчайшего пути — это уже задача, вполне решаемая для компьютера.

Весь пройденный одной или другой (в зависимости от условий задания) машиной маршрут представляем себе в виде двумерной (в некоторых, особо сложных случаях — трехмерной матрицы. Помните фантастический фильм «Матрица»? Там фигурировала плоская конструкция из множества сот, заполненных человеческими телами. Наша матрица будет содержать ячейки с данными, расположенные на одинаковом удалении друг от друга — по примеру обычной географической карты в Google или Yandex.

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

Конечно, если наш лабиринт имеет несколько уровней, да ещё и с пересечением высот, потребуется трехмерная матрица, но её мы рассматривать не будем. Если вы заметили, даже в современных играх уровни выполнены независимыми, то есть, их тоже можно представить как двумерные матрицы с дополнительными параметрами.

Проходим лабиринт «волной»

К сожалению, компьютер сам по себе путей не увидит, даже если у него будет под рукой цифровая карта. Ему нужно предложить алгоритм, который обеспечит эффективный поиск пути в матрице, заполненной условными цифровыми обозначениями.  Итак, используем для прохождения лабиринта самый простой алгоритм — волновой. И двигаться будем только вправо, влево, вверх и вниз (можно ходить ещё и по диагонали но мы пока этот рассматривать не будем).

Движение «волны» напоминает расходящиеся круги на воде или обвал, когда вниз с горы падает множество камешков. Вокруг стартовой точки, если она расположена не на краю матрицы-карты, всегда находятся ещё четыре точки. Нам необходимо проверить, свободны ли они для прохождения? Инструкция компьютеру будет звучать так: «пройди прямо и проверь, свободна ли клетка впереди? Если да, то перейди туда и измени её единичкой. Если нет, то пройди назад и проверь, свободна ли клетка позади? Если да — перейди туда и пометь её единичкой. Если нет, проверь, свободна ли клетка справа? Если да, то перейди туда и пометь её единичкой. Если нет, проверь клетку слева.

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

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

«Реализация волны»

На программном уровне волновой алгоритм строится достаточно просто. Лабиринт мы, или сканируем или, соответствующим образом обрабатываем, получая матрицу, значения ячеек которой отражают проходимость или непроходимость её узлов. Затем эту матрицу мы вносим в программу или подаем на вход в виде файла.

Далее мы создаем три цикла (обязательно три), которые обходят всю матрицу, генерируя волну. Внешний цикл должен иметь границу, не меньшую чем размер длинной стороны матрицы. Внутренние циклы строятся как обычно: один — по количеству строк, а второй — по числу столбцов. В принципе, можно и наоборот.

Затем нам понадобится несколько условий. Точнее, много условий, каждое из которых программа должна проверить. Необходимо уточнить, что представляет из себя каждая из клеток, расположенных вокруг точки старта — это тупик или это свободная клетка? А может быть это клетка — финишная. А может быть стартовая? Для простоты «волной» мы будем помечать только свободные клетки. Конечно, необходимо проверять, не является ли клетка финишной. Ну и, конечно, стоит завершить работу всех трех циклов при прохождении финиша.

Есть ещё один немаловажный момент — для того, чтобы каждая волна была помечена числами по возрастанию, нам потребуется коэффициент, который надо увеличивать перед завершением внешнего цикла, который и является «генератором» волны.  Этот коэффициент мы назовем Ni. Определителем максимального количества итераций будет коэфициент Nk. Матрицу мы смделали квадратной и количество ячеек в ней обозначим переменной n. Массив наш назовем lab — от слова «лабиринт». Переменными, работающими во внутренних циклах будут обычные i, j, во внешнем — l. Переменные z и k получат значения точки выхода из лабиринта, когда цикл закончится.

Завершим работу циклов с помощью оператора break и метки label. Как мы знаем, break останавливает только свой цикл. Поэтому метку вынесем за внешний.

Для прокладки пути у нас есть массив, аналогичный первому. Для удобства он заполнен однородными цифрами. Соответственно, после окончания той части программы, которая прокладывает волну, сработает вторая — помечающая кратчайший маршрут.  Циклов нам здесь понадобится всего два, так как вокруг любой точки, в нашем случае, будет только одна точка, ближайшая ко входу и все проверять уже не потребуется. Как только мы найдем эту точку, мы присвоим её координаты нашим переменным z и k, тем самым, продвинувшись к выходу на один шаг. Саму клетку мы будем обозначать коэффициентом Ni,  снижая его на одну единицу за каждую итерацию внешнего цикла.

Очень важное добавление: нам потребуется начинать просмотр матрицы не с первого элемента, а со второго. И заканчивать мы будем предпоследним элементом последней строки. Иначе первые числа первой строки и столбца и последняя цифра массива обязательно сделают запрос к несуществующим точкам по адресам 0, 0-1 и 0-1, 0. Так мы выйдем за границы цикла и будет ошибка.

Вот как выглядит эта программка на языке Java в максимально упрощенном для восприятия виде, без функций и методов. Добавлю, что для удобства и понимания я свел её в один листинг, а вывод маршрута сделал в отдельном массиве, заполненном однородными числами.

Код работает на любом компиляторе Java. Его можно скопировать  и запустить. Можно исследовать волновой алгоритм на предмет прохождения различных препятствий сложной формы. При необходимости его можно переписать на языке C, использовать в лабораторной работе, создать соответствующий метод или функцию или даже написать небольшую игру. Код снабжен краткими пояснениями на английском языке.

public class VolNa2 {

      public static void main(String[] args) {

 //Initialization of variables

      int x = 0;

      int y = 0;

      int i = 0;

      int z = 0;

      int k = 0;

      int j = 0;

      int Ni = 0;

      int Nk = 256;

      int n = 10;

      //Labyrinth matrix

      int lab[][] = { 

      {254, 254, 254, 254, 254, 254, 254, 254, 254, 254},

      {253, 254, 254, 254, 254, 254, 254, 254, 254, 254},

      {254, 254, 254, 254, 254, 254, 254, 254, 254, 254},

      {254, 254, 254, 254, 255, 254, 254, 254, 254, 254},

      {254, 254, 254, 254, 254, 254, 254, 254, 254, 254},

      {254, 254, 254, 254, 254,  0,  254, 254, 254, 254},

      {254, 254, 254, 255, 254, 254, 254, 254, 254, 254},

      {254, 254, 254, 255, 255, 254, 254, 254, 254, 254},

      {254, 254, 254, 254, 254, 254, 254, 254, 254, 254},

      {254, 254, 254, 254, 254, 254, 254, 254, 254, 254},

      {254, 254, 254, 254, 254, 254, 254, 254, 254, 254}};

      //initialization of a matrix of a way

      int kurs[][] = new int [n][n];

      for(i = 0; i < n; i++){

      for(j = 0; j < n; j++){

      kurs[i][j] = 122;

      }

      }

      //Three cycles for passing of a matrix of a maze

      label : for (int l = 0; l < 256; l++){

      for (i = 0; i < n; i++){ 

      for (j = 0; j < n; j++){

      //Wave propagation conditions

      if (lab[i][j] == Ni && i > 0 && i < n && j > 0 && j < n-1){

      if(lab[i][j+1] == 254){

      lab[i][j+1] = Ni+1;

      }

      if(lab[i][j+1]== 253){

      z = i;

      k = j+1;

      break label;

      }

      if(lab[i+1][j] == 254){

      lab[i+1][j] = Ni+1;

      }

      if(lab[i+1][j]== 253){

      z = i+1;

      k = j;

      break label;

      }

      if(lab[i][j-1] == 254){

      lab[i][j-1] = Ni+1;

      }

      if(lab[i][j-1] == 253){

      z = i;

      k = j-1;

      break label;

      }

      if(lab[i-1][j] == 254){

      lab[i-1][j] = Ni+1;

      }

      if(lab[i-1][j] == 253){

      z = i-1;

      k = j;

      break label;

      }

      }

      }

      }

      //Wave propagation coefficient

      Ni++;

      }

      //Wave output

      for (i = 0; i < n; i++){

      for (j = 0; j < n; j++){

      System.out.printf("%4d", lab[i][j]);

      }

      System.out.println();

      }

      lab[z][k] = Ni+1;

      Ni++;

      //Plotting

      for (i = 0; i < n; i++){

      for (j = 0; j < n; j++){

      if (lab[z][k]>=lab[z+1][k]){

      kurs[z][k] = Ni;

      z = z+1; 

      Ni--; 

      }

      if (lab[z][k]>=lab[z-1][k]){

      kurs[z][k] = Ni;

      z = z-1;

      Ni--; 

      }

      if (lab[z][k]>=lab[z][k+1]){

      kurs[z][k] = Ni;

      k = k+1;

      Ni--; 

      }

      if (lab[z][k]>=lab[z][k-1]){

      kurs[z][k] = Ni;

      k = k - 1;

      Ni--; 

      }

      kurs[z][k] = Ni;

      }

      }

      //Conclusion of the shortest way

      for (i = 0; i < n; i++){

      for (j = 0; j < n; j++){

      System.out.printf("%4d", kurs[i][j]);

      }

      System.out.println();

      }

      }

      }

Результат работы программы:

Волна:

254  254   8     7    6   5   6   7   8  254

253     8    7     6    5   4   5    6  7    8

  8       7    6     5    4   3   4    5  6    7

  7       6   5   4   255  2   3   4    5    6

  6       5   4   3     2    1   2   3    4    5

  5       4   3   2     1    0   1   2   3     4

  6       5   4 255   2    1   2   3   4     5

  7       6   5 255 255  2   3   4   5     6

  8       7   6   5     4    3   4   5   6     7

254     8   7   6     5    4   5   6   7     8

Маршрут:

 122 122 122 122 122 122 122 122 122 122

   9   122 122 122 122 122 122 122 122 122

   8   7     122 122 122 122 122 122 122 122

 122   6     5   122 122 122 122 122 122 122

 122 122   4     3   122 122 122 122 122 122

 122 122 122     2   1      0  122 122  122122

 122 122 122 122 122 122 122 122 122 122

 122 122 122 122 122 122 122 122 122 122

 122 122 122 122 122 122 122 122 122 122

 122 122 122 122 122 122 122 122 122 122

Эдуард Трошин