Учимся находить кратчайший путь через простой двумерный алгоритм на Python

Как именно мы находим выход из лабиринта? Как быстрее всего проехать из точки А в ближайшую пиццерию? Можем ли мы провести игрового персонажа к выходу так, чтобы он не уперся в стену?

Поиск пути – типичная задача программирования, решаемая в самых разных ситуациях. Она известна в основном из навигационных задач и разработки игр. Но, изучив ключевые алгоритмы поиска пути, вы узнаете, что они применимы к более абстрактным задачам оптимизации и построения последовательностей.

В этом руководстве рассмотрен простейший алгоритм поиска пути, основанный на алгоритме Дейкстры. Этот алгоритм также известен под названием поиск по первому наилучшему совпадению, ключевая логика у него общая со многими другими алгоритмами, например, A*, заливка методом наводнения и диаграммы Вороного.

Здесь мы рассмотрим практическое применение этого алгоритма. Вам понадобятся базовые знания программирования и языка Python.

Настройка Python

Весь код к этому посту находится в репозитории path-finding. Его нужно клонировать и переключиться в ветку tutorial_1. Также установите пакет pygame, он понадобится нам для графики.

python3 -m pip install -U pygame
git clone git@github.com:mortoray/path-finding.git
cd path-finding
git checkout path_finding_1

Теперь проверим, все ли сделали правильно:

python3 find-basic.py

Должно появиться окно с клетками, а в клетках – цифры. Теперь можете закрыть это окно. Мы вернемся к нему позже.

Лабиринт

Поиск пути – это продвижение из точки А в точку B. Алгоритм может описывать прогулку человека по парку, движение автомобиля по городу, либо курс персонажа, который преследует вас в игре. Давайте сведем все эти окружения к абстракции, которую назовем «лабиринт».

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

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

Запускаем код

В коде предоставлена функция, создающая за нас простейший лабиринт. Нужно разобраться, как использовать алгоритм поиска пути для генерации гораздо более интересных лабиринтов, но пока давайте просто вызовем функцию create_wall_maze.

import mortoray_path_finding as mpf

maze = mpf.create_wall_maze( 20, 12 )

Мы создали лабиринт размером 20x12. Поле maze.board – это решетка из объектов Cell. Нам нужен способ отобразить наш лабиринт.

finder = mpf.Finder()
finder.set_board(maze.board)
finder.run()

Исходный файл: tutorial_1_1.py

Finder – это утилита, отображающая за нас лабиринт. Серые клетки свободны, то есть, путь может пройти через них. Коричневые клетки – это стены, через них путь пройти не может. В каждой из клеток также записан ноль, это значение Cell.count для данной позиции. Оно пригодится нам при поиске пути.

Измерение расстояния

Поиск пути во многом основан на исходном алгоритме Дейкстры. Существует множество его вариаций, например, алгоритм Флойда-Уоршелла, он же B*. Они действуют по схожему принципу: в них используются списки узлов и подсчитывается расстояние. Для разных ситуаций можно сочетать различные приемы.

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

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

1. Получаем из списка открытых узлов тот узел, от которого нас отделяет наименьшее расстояние  

2. Вычисляем расстояние до каждого из соседних узлов

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

Термины

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

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

Узлы, которые можно соединить, проложив между ними путь, являются соседними. Путь между узлами-соседями характеризуется расстоянием, для которого есть более общий термин «стоимость». В теории графов путь называют «ребром».

«Список открытых узлов» - это в буквальном смысле список узлов. «Открытые» узлы – это узлы, которые алгоритм все равно должен проверить. Например, если вы ищете елочные игрушки, разложенные в ящиках у вас в подвале, то вы просматриваете каждый из ящиков и отмечаете его в списке. Если внутри большого ящика обнаружатся более мелкие, то их также можно добавить в список.

Алгоритм

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

def fill_shortest_path(board, start, end, max_distance = math.inf):
  nboard = board.clone()
  nboard.clear_count(math.inf)

"Список открытых узлов" – это вектор позиций в решетке. В нем содержатся все местоположения, необходимые нам для поиска пути. Инициализируем список стартовой позицией лабиринта. Также мы должны установить счетчик в 0, поскольку на старте расстояние равно нулю.

nboard.at( start ).count = 0
    
open_list = [ start ]

Этого достаточно, чтобы запустить алгоритм. Перебираем узлы, пока open_list не опустеет.

  while open_list:
    	cur_pos = open_list.pop(0)
    	cur_cell = nboard.at( cur_pos )

Подождите, разве алгоритм не требует перейти к узлу, расстояние до которого является наименьшим? Этот код просто берет следующий узел в списке. Он работает, даже если взять случайный узел, даже если временная сложность в таком случае оказывается гораздо выше. В нашем коде это не важно, так как следующий узел – как раз тот, расстояние до которого является наименьшим. Почему так – будет показано позже.

Для каждого узла рассмотрим всех его соседей.

# (x,y) смещения от текущей клетки
neighbours = [ [-1,0], [1,0], [0,-1], [0,1] ]
for neighbour in neighbours:
  ncell_pos = mpf.add_point(cur_pos, neighbour)
  if not nboard.is_valid_point(ncell_pos):
continue
  
  cell = nboard.at( ncell_pos )

Каждый элемент в neighbors – это Евклидово смещение от текущей клетки до соседней. Например, [-1,0] – это сосед слева. Если cur_pos равно [ 5, 7 ], то сложив его с [-1, 0] получим [4, 7], то есть, ход на клетку влево. Аналогично, [1,0] – это движение в положительном направлении по оси x, то есть, на клетку вправо. [0,-1] влияет только на y и является переходом на одну позицию вверх, тогда как [0,1] – на одну вниз.

Пользуясь численными абстракциями направлений, можно в рамках данного алгоритма точно так же обработать любые другие переходы. Можно учесть и другие направления, например, [1,1], это ход по диагонали вверх и далее вправо. Но при этом мы должны держать в уме и края решетки, за что и отвечает is_valid_point. Например, если мы дойдем до правого края решетки,  то смещение [1,0], соответствующее одному переходу вправо, выведет нас за пределы графа, поэтому мы такой ход пропустим.

Также будем пропускать все непустые клетки, поскольку это стены лабиринта, и пройти через них мы не можем.

if cell.type != mpf.CellType.Empty:
  continue

Переходим к вычислению расстояния.

dist = cur_cell.count + 1

Поскольку мы все время движемся по прямой, клетка за клеткой, здесь можно вспомнить о «Манхэттенском расстоянии», то есть, расстояниями между двумя точками, которое можно покрывать лишь в направлении x или y, причем, ни в один ход нельзя перейти сразу по двум осям. Название обусловлено тем, как пересекаются улицы на Манхэттене, образующие именно такую сетку. Манхэттенское расстояние применимо к Евклидовой геометрии, например, к такой сетке, с которой мы здесь работаем.

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

if cell.count > dist:
  cell.count = dist
  cell.path_from = cur_cell
  open_list.append(ncell_pos)

Используем обобщенное поле cell.count для измерения расстояния, а также обновим поле path_from, указывающее, каким путем мы пришли в данную точку.

Ранее мы говорили, что первым в open_list всегда идет узел с наименьшим значением count. Уже понятно, почему, ведь каждый соседний узел удален от нас ровно на 1. Стартовый узел считается как 0, поэтому добавляем в список открытых несколько узлов, значения которых равны 1. Теперь, поскольку все узлы мы обрабатываем по порядку, добавляем в список несколько двоек, пока не будут охвачены все единицы. В итоге у нас в списке останутся двойки. Продолжим охватывать двойки, также добавляя в список некоторые тройки.

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

Визуализируем

Давайте уделим немного времени визуализации. Вызовем fill_shortest_path из кода, входящего в дистрибутив.

import mortoray_path_finding as mpf
    
maze = mpf.maze.create_wall_maze( 20, 12 )
filled = mpf.tutorial_1.fill_shortest_path(maze.board, maze.start, maze.end)

finder = mpf.draw.Finder()
finder.set_board(filled)
finder.run()

Исходник: tutorial_1_2.py

Откроется такое окно, как показано ниже. Стартовая клетка обозначена желтым, в ней стоит 0. Числа увеличиваются по мере отдаления от этой точки, с инкрементом в единицу. Все клетки в решетке обозначены в соответствии с манхэттенским расстоянием от стартовой точки до них. Находим клетку, обозначенную зеленым, и вычисляем, каково расстояние от стартовой точки до нее.

Получение пути

Кратчайшего пути у нас пока нет, но есть пара способов, которыми его можно получить.

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

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

Альтернативный способ – отслеживать путь, заполняя расстояния. Это именно тот код, который мы пока игнорировали.

if cell.count > dist:
  cell.count = dist
  cell.path_from = cur_cell
  open_list.append(ncell_pos)

Всякий раз, добавляя узел в список открытых узлов, мы также устанавливаем cell.path_from. Здесь хранятся записи о кратчайшем входящем пути, что упрощает отслеживание обратного курса от места назначения.

def backtrack_to_start(board, end):
  """ Возвращает путь до конечной точки, при этом предполагается, что поле заполнялось при помощи алгоритма fill_shortest_path """
  cell = board.at( end )
  path = []
  while cell != None:
    	path.append(cell)
    	cell = cell.path_from
   	 
  return path

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

import mortoray_path_finding as mpf
    
maze = mpf.maze.create_wall_maze( 20, 12 )
filled = mpf.tutorial_1.fill_shortest_path(maze.board, maze.start, maze.end)
path = mpf.tutorial_1.backtrack_to_start(filled, maze.end)

finder = mpf.draw.Finder()
finder.set_board(filled)
finder.set_path(path)
finder.run()

Исходник: tutorial_1_3.py

Здесь есть любопытный момент: функция fill_shortest_path вычисляет расстояние «от старта» для каждой клетки, а не только для конечной. Тот же самый код для отслеживания обратного пути до любого узла. Оказывается, такие исчерпывающие знания могут во многих отношениях пригодиться при поиске пути. Но, если наша приоритетная цель – оптимизация, то мы адаптируем алгоритм так, чтобы он прекращал поиск, как только найдет выход из лабиринта. Также есть алгоритм A*, использующий эвристику, которая позволяет обходиться без сканирования всей карты.

Заключение

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