Поиск пути в лабиринте (волновой алгоритм, он же алгоритм Ли)

Поиск пути в лабиринте (волновой алгоритм, он же алгоритм Ли)

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

Как работает волновой алгоритм? Основная идея волнового алгоритма описывается следующими этапами.


1. Из начального положения (элемента) волна распространяется в четырёх направлениях (рис. 1). Элемент, в который пришла волна, создает новый фронт волны. На рисунках цифрами обозначены номера фронтов волны.



Рис. 1 Первый шаг

Каждый из элементов первого фронта волны является источником вторичной волны (рис. 2). Элементы второго фронта волны будут генерировать волну третьего фронта и так далее. Процесс формирования волн продолжается, пока не будет достигнут конечный элемент.



Рис. 2 Последующее распространение волны

2. На втором этапе волнового алгоритма строится сама трасса. Её построение необходимо осуществлять в соответствии со следующими правилами:

a) Движение при построении трассы необходимо осуществлять в соответствии с выбранными приоритетами.

b) При движении от конечного элемента к начальному номер фронта волны (путевые координаты) должны уменьшаться.



Рис. 3 Результат действия

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

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

Код:



REM Файл FindPath.bi

' Тип ячейки в лабиринте
Public Enum SquareLType
   ' Свободная непомеченная ячейка
   Blank = -2
   ' Непроходимая ячейка, стена
   Wall = -1
   ' Стартовая ячейка
   Start = 0
End Enum

Declare Function GetLeePath(ByVal StartX As Integer, _
                     ByVal StartY As Integer, _
                     ByVal EndX As Integer, _
                     ByVal EndY As Integer, _
                     ByVal StageWidth As Integer, _
                     ByVal StageHeight As Integer, _
                     ByVal Grid As Integer Ptr, _
                     ByVal PathX As Integer Ptr, _
                     ByVal PathY As Integer Ptr) As Integer



Здесь:
StartX — координата X точки отправления.
StartY — координата Y точки отправления.
EndX — координата X точки назначения.
EndY — координата Y точки назначения.
StageHeight — высота лабиринта (количество клеток по вертикали).
StageWidth — ширина лабиринта (количество клеток по горизонтали).
Grid — указатель на массив специальным образом сформированного лабиринта.
PathX — указатель на массив (одномерный) координат X пути.
PathY — указатель на массив (одномерный) координат Y пути.
Массивы PathX и PathY должны иметь размерность StageHeight * StageWidth элементов, чтобы вместить весь путь. Сюда функция будет записывать координаты пути, если он существует

Функция возвращает длину пути от стартовой точки до финишной или 0, если пути не существует.

Замечания.
Координаты в лабиринте начинаются с нуля. Ось икс направлена слева направо, ось игрек — сверху вниз.
Координаты в лабиринте указываются «слоями по ширине». То есть сначала идут все иксы принадлежащие игреку с номером ноль, потом все иксы, принадлежащие игреку с номером 1 и так далее. Вот формула вычисления: [y * StageWidth + x]
Лабиринт необходимо соответствующим образом подготовить. Для этого все свободные клетки должны иметь значение SquareLType.Blank, все непроходимые клетки (стены) должны иметь значение SquareLType.Wall, стартовая клетка должна быть помечена SquareLType.Start.
Необходимо помнить, что значения ячеек лабиринта Greed в процессе работы функции будут изменены, поэтому желательно отправлять копию оригинального лабиринта.

Код:



REM Файл FindPath.bas

#include once "FindPath.bi"


Public Function GetLeePath(ByVal StartX As Integer, _
                     ByVal StartY As Integer, _
                     ByVal EndX As Integer, _
                     ByVal EndY As Integer, _
                     ByVal StageWidth As Integer, _
                     ByVal StageHeight As Integer, _
                     ByVal Grid As Integer Ptr, _
                     ByVal PathX As Integer Ptr, _
                     ByVal PathY As Integer Ptr) As Integer
   
   ' смещения, соответствующие соседям ячейки
   Dim dx(3) As Integer = {1, 0, -1, 0}
   ' справа, снизу, слева и сверху
   Dim dy(3) As Integer = {0, 1, 0, -1}
   ' 
   Dim d As Integer, x As Integer, y As Integer, stopp As Integer
   
   ' распространение волны
   
   Do
      ' предполагаем, что все свободные клетки уже помечены
      stopp = 1
      
      For y = 0 To StageHeight - 1
         For x = 0 To StageWidth - 1
            
            ' ячейка (x, y) помечена числом d
            If Grid[y * StageWidth + x] = d Then
               ' проходим по всем непомеченным соседям
               For k As Integer = 0 To 3
                  ' Чтобы не вылезти за границы массива
                  If y + dy(k) >= 0 AndAlso y + dy(k) < StageHeight AndAlso x + dx(k) >= 0 AndAlso x + dx(k) < StageWidth Then
                     'y * StageWidth + x
                     If Grid[(y + dy(k)) * StageWidth + x + dx(k)] = SquareLType.Blank Then
                        ' найдены непомеченные клетки
                        stopp = 0
                        ' распространяем волну
                        Grid[(y + dy(k)) * StageWidth + x + dx(k)] = d + 1
                     End If
                  End If
               Next
            End If
            
         Next
      Next
      d += 1
   Loop While stopp = 0 AndAlso Grid[EndY * StageWidth + EndX] = SquareLType.Blank
   
   If Grid[EndY * StageWidth + EndX] = SquareLType.Blank Then
      ' путь не найден
      Return 0
   End If
   
   ' восстановление пути
   
   ' длина кратчайшего пути из (StartX, StartY) в (EndX, EndY)
   Dim PathLen As Integer = Grid[EndY * StageWidth + EndX]
   x = EndX
   y = EndY
   d = PathLen
   
   Do While d > 0
      ' записываем ячейку (x, y) в путь
      PathX[d] = x
      PathY[d] = y
      d -= 1
      
      For k As Integer = 0 To 3
         If y + dy(k) >= 0 AndAlso y + dy(k) < StageWidth AndAlso x + dx(k) >= 0 AndAlso x + dx(k) < StageWidth Then
            If Grid[(y + dy(k)) * StageWidth + x + dx(k)] = d Then
               x += dx(k)
               ' переходим в ячейку, которая на 1 ближе к старту
               y += dy(k)
               Exit For
            End If
         End If
      
      Next
   Loop
   
   ' Теперь путь будет с начала и до конца
   PathX[d] = StartX
   PathY[d] = StartY
   
   Return PathLen
End Function



Компилировать:

Код:



fbc -lib FindPath.bas



Теперь пора приступить к тестированию функции на лабиринте из рисунка 4.

Код:



REM Файл "test.bi"

#include once "FindPath.bi"

' Ширина и высота поля с лабиринтом
Const StageWidth As Integer = 12
Const StageHeight As Integer = 8

' Массив с лабиринтом
Dim Shared aLab(StageWidth - 1, StageHeight - 1) As Integer
' Копия специально подготовленного лабиринта для работы функции
Dim Shared aGrid((StageWidth - 1) * (StageHeight - 1)) As Integer

' Массив путей
Dim Shared PathX(StageWidth * StageHeight) As Integer
Dim Shared PathY(StageWidth * StageHeight) As Integer


' Стартовая точка
Dim Shared StartX As Integer = 3
Dim Shared StartY As Integer = 6

' Конечная точка
Dim Shared EndX As Integer = 3
Dim Shared EndY As Integer = 0

' Длина пути
Dim Shared PathLen As Integer



А вот и сам тестовый файл

Код:



REM файл "test.bas"

#include once "test.bi"

Color 1 ' цвет символов в консоли, нужен только для красивого вывода результатов

' Нужно создать лабиринт
' Пусть ноль — это пустая ячейка, единица — это стена

aLab(1, 4) = 1
aLab(2, 4) = 1
aLab(3, 4) = 1
aLab(4, 4) = 1
aLab(2, 0) = 1
aLab(2, 1) = 1
aLab(8, 3) = 1
aLab(9, 3) = 1
aLab(9, 5) = 1
aLab(10, 5) = 1
aLab(9, 6) = 1
aLab(10, 6) = 1

' Теперь нужно подготовить копию лабиринта, чтобы не попортить оригинал
Dim p As Integer Ptr = @aGrid(0)
For y As Integer = 0 To StageHeight - 1
   For x As Integer = 0 To StageWidth - 1
      If aLab(x, y) = 1 Then
         p[y * StageWidth + x] = SquareLType.Wall
      Else
         p[y * StageWidth + x] = SquareLType.Blank
      End If
   Next
Next

' Отметим стартовую точку
p[StartY * StageWidth + StartX] = SquareLType.Start

' Распечатать получившуюся копию лабиринта
For y As Integer = 0 To StageHeight - 1
   For x As Integer = 0 To StageWidth - 1
      Select Case p[y * StageWidth + x]
         Case SquareLType.Blank
            Color 6
         Case SquareLType.Wall
            Color 7
         Case SquareLType.Start
            Color 10
         Case Else
            Color 5
      End Select
      Print p[y * StageWidth + x] ; " ";
      Color 1
   Next
   Print
Next


' Запустить функцию
PathLen = GetLeePath(StartX, StartY, EndX, EndY, StageWidth, StageHeight, p, @PathX(0), @PathY(0))

Print
Print "Длина пути лабиринта", PathLen
Print

' Для самопроверки распечатать получившуюся копию лабиринта с готовым путём
For y As Integer = 0 To StageHeight - 1
   For x As Integer = 0 To StageWidth - 1
      Select Case p[y * StageWidth + x]
         Case SquareLType.Blank
            Color 6
         Case SquareLType.Wall
            Color 7
         Case SquareLType.Start
            Color 10
         Case Else
            Color 5
      End Select
      Print p[y * StageWidth + x] ; " ";
      Color 1
   Next
   Print
Next

Print

' Распечатать массив пути

For i As Integer = 0 To PathLen - 1
   Print PathX(i); " "; PathY(i)
Next



Компилировать:

Код:



fbc -l FindPath test.bas



Хорошая статья, спасибо.