Программируем… выход из лабиринта

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

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

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

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

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

 

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

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

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

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

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

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

Версия для печатиВерсия для печати

Рубрики: 

  • 1
  • 2
  • 3
  • 4
  • 5
Всего голосов: 0
Заметили ошибку? Выделите ее мышкой и нажмите Ctrl+Enter!

Читайте также

 

Комментарии

Страницы

Аватар пользователя mike

Английский ИМХО кривоват.

В коде не разбирался -- не увидел интереса. Тем более, что в Интернете выложены десятки, если не сотни аналогичных примеров с кодами, переписать которые на джаву -- дело техники. Впрочем, это тоже надо уметь. Автор, кажется, сумел.

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

Супер! - вот для таких программ Javаscript идеально подходит. Имхо.

Хотя там можно и функции и методы. Smile

Аватар пользователя Petro45

...Английский ИМХО кривоват. 

...Тем более, что в Интернете выложены десятки, если не сотни аналогичных примеров с кодами... 

Скопировал не разбираясь и перевёл через Гугл?:-) Такова была идея коммента? И вы, действительно, так думаете?

Хотя там можно и функции и методы.

Можно. Только смысл две строчки гнать через ООП? Чтобы новичков запутать?:-)

petro45 > Можно. Только смысл две строчки гнать через ООП? Чтобы новичков запутать?:-)

Вначале вот такой "плоский" код. "Плоский" - это жаргон - то есть без ООП.

Потом показать как это с объектами.

Потом показать чисто функциональный подход.

Ну и в конце - дойти до монад. Smile

Javаscript идеально подходит. Имхо. - И никакого отдельного компилятора - броузера будет достаточно для запуска кода.

Аватар пользователя Petro45

Вначале вот такой "плоский" код. "Плоский" - это жаргон - то есть без ООП.

Потом показать как это с объектами.

Потом показать чисто функциональный подход.

Так не вместить в одну статью. 

Ну и в конце - дойти до монад. 

Что есть "монады"?

Javаscript идеально подходит. Имхо. - И никакого отдельного компилятора - броузера будет достаточно для запуска кода.

"ЖабаСкрипт" - сложный язык и очень мало общего имеет с Java. Я просто его не знаю. Вы напишите:-).

А реально было бы интересно сделать библиотеку, которая эффективно комбинировала бы алгоритмы поиска в зависимости от того, что на вход поступает. 


Аватар пользователя mike

Скопировал не разбираясь и перевёл через Гугл?:-) Такова была идея коммента? И вы, действительно, так думаете?

Думаю, что разобрались.

Идейка для Гугла: копируем код, пастим в Гугл, а он переводит на др. язык  программирования. Или опездал с идейкой? :)

Аватар пользователя Petro45

Думаю, что разобрались.

Я их все разобрал. В интернете ничего не понять. Воспроизвел, как умел, где-то с псевдокодом догадался, что-то на форумах подсказывали. Может поставят когда.

Идейка для Гугла: копируем код, пастим в Гугл, а он переводит на др. язык  программирования. Или опездал с идейкой? :)

Нет такого

petro45 > Что есть "монады"?

Мона́да в функциональном программировании — это абстракция линейной цепочки связанных вычислений. Её основное назначение — инкапсуляция функций с побочным эффектом от чистых функций, а точнее их выполнений от вычислений.

Аватар пользователя Petro45

А проще можно?

Аватар пользователя mike

А проще он не нашёл где скопипастить.

Страницы