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


Алгоритм поиска пути на карте
http://www.delphikingdom.com/asp/viewitem.asp?catalogID=1127

George Judkin
дата публикации 28-03-2005 08:59

Алгоритм поиска пути на карте

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

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

А для поиска пути на квадратной сетке наиболее эффективным является так называемый “волновой алгоритм”. Кто его первым придумал, сказать сейчас, наверное, уже невозможно. Но точно можно сказать, что различные варианты волнового алгоритма придумывал каждый нормальный программист, перед которым вставала задача поиска пути на карте из квадратиков (я его первый раз придумал в 1986 году для поиска пути в лабиринте). И название у всех возникает примерно одно и то же: уж больно его работа похожа на бегущую круговую волну.

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

Сразу маленькое замечание к профессионалам: программу я не оптимизировал. Это сделано не потому, что я не умею. Просто пишется это для начинающих. А разобраться в оптимизированной программе порой затруднительно даже профессионалу. Еще хочу добавить, что я -- далеко не господь бог: так как спешил написать за выходные, то вполне мог что-то накосячить.

Постановка задачи

Итак, у нас есть в общем случае прямоугольная карта с квадратной сеткой. Каждая клетка имеет тип территории. Стоимость въезда на клетку представляется целым числом и зависит от типа территории и направления, по которому въехали (я использую слово “въехать”, а не, допустим, “войти” или “продвинуться”, потому что последний писал этот алгоритм для игры, в которой двигалась боевая техника; мне так удобнее). Некоторые клетки имеют тип “препятствие”. Движение по этим клеткам невозможно. Имеется восемь допустимых направлений движения, которые обозначаются целыми числами от 0 до 7 (0 – вертикально вверх, дальнейшее приращение на единицу означает поворот направления движения на 45 градусов по часовой стрелке). На карте заданы начальная и конечная точки. Нужно найти минимальный путь из начальной точки в конечную (точнее один из минимальных путей, так как может быть много различных путей с одинаковыми затратами единиц движения).

Описание

Для передачи принципа работы алгоритма буду рассматривать задачу как поиск оптимального движения автомобиля из начальной точки в конечную.

Из начальной точки выезжают автомобили по всем возможным направлениям (не все из восьми направлений могут быть возможны, так как могут встретиться препятствия и край карты). Чтобы доехать до соседней клетки требуется время, определяемое (как уже говорилось) типом клетки и направлением движения. Соответственно, не все автомобили, выехавшие из начальной точки в один и тот же момент времени достигнут соседних клеток одновременно. После того, как автомобиль до клетки все же доехал, то производится проверка: первым ли он доехал до этой клетки. Если здесь уже проезжали, то автомобиль снимается и в дальнейшем движении не участвует. Если он приехал в эту клетку первым, то в ней фиксируется порядковый номер этой клетки в маршруте движения автомобиля и направление, с которого он приехал. Номер клетки в маршруте движения также является признаком того, что по клетке проехали. Изначально номера всех клеток равны –1. Затем производится проверка: является ли данная точка конечной. Если точка конечная, то алгоритм работу заканчивает. В противном случае из этой клетки отправляются автомобили по всем возможным направлениям. Из возможных направлений кроме препятствий и края карты исключаются клетки, по которым уже проехали. Все.

Реализация

Все необходимое для работы алгоритма вынесено в отдельный модуль (PathFind.pas). Этот модуль является отчуждаемым и может быть использован в других проектах (если кому-то лень писать самостоятельно, могут взять готовое решение и использовать у себя без переработки). Модуль обладает некоторой гибкостью и может быть использован для решения достаточно широкого круга задач аналогичного класса.

unit PathFind;

interface

uses
  Windows, Classes;

type
  TPath = array of TPoint;  // Тип для хранения и передачи найденного пути.

  TPathMapCell = record     // Клетка карты пути в которой мы отмечаем:
    Distance : Integer;     // - порядковый номер клетки в маршруте и
    Direction : Integer;    // - направление, с которого приехали на эту клетку.
  end;

  TPathMap = array of array of TPathMapCell;  // Карта пути.

  {Процедурный тип для передачи в модуль адреса функции, которая возвращает
   стоимость движения на клетку (X,Y) с направления Direction.
   Если (X,Y) -- препятствие, то функция должна вернуть -1.
   Сама функция определяется в основной программе. Для работы алгоритма
   знание реализации функции не обязательно.}
  TGetCostFunc = Function(X,Y,Direction : Integer) : Integer;

{Функция возвращает карту путей для всех клеток основной карты.
 Удобна, если мы рассматриваем различные пути из одной и той же
 начальной точки в различные конечные точки.}
function MakePathMap(
  MapWidth,MapHeight : Integer;
  StartX,StartY : Integer;
  GetCostFunc : TGetCostFunc) : TPathMap;

{Функция возвращает путь в конечную точку, заданную координатами (X,Y)
 по полученной от предыдущей функции карте пути.}
function FindPathOnMap(PathMap : TPathMap; X,Y : Integer) : TPath;

{Функция ищет путь из точки (StartX,StartY) в точку (StopX,StopY).}
function FindPath(
  MapWidth,MapHeight : Integer;
  StartX,StartY,StopX,StopY : Integer;
  GetCostFunc : TGetCostFunc) : TPath;

Если путь не существует, то функции FindPath и FindPathOnMap возвращают NIL. MapWidth и MapHeight -- ширина и высота основной карты. Могут быть различными.

Существуют два возможных варианта поиска путей. Либо с помощью функции FindPath находим сразу путь из одной точки в другую. Либо строим карту всех путей из заданной точки (MakePathMap) и получаем путь в любую конечную точку из заданной начальной (FindPathOnMap). В демонстрационном примере используется именно второй вариант.

Переходим к реализации. Сразу скажу, что мне очень не понравился подход Вадима Кеглеса, описанный в его статье Определение кратчайшего пути между двумя точками: такое количество циклов – это жуткая трата ресурсов. У себя я решил хранить фронт волны. Для этого был специально создан класс TWave.

type
  TWaveCell = record      // Одна ячейка фронта волны. Содержит:
    X,Y : Integer;        // - координаты точки, в которую мы движемся;
    Cost : Integer;       // - оставток времени на движение до точки;
    Direction : Integer;  // - напрвление, по которому мы движемся.
  end;

  TWave = class
  private
    FData : array of TWaveCell;
    FPos : Integer;                // Текущая позиция в массиве.
    FCount : Integer;              // Количество реальных элементов в массиве.
                                   // Размеры динамического массива при изменении
                                   // количества элементов не меняются. Массив
                                   // только растет.
    FMinCost : Integer;
    function GetItem : TWaveCell;
  public
    property Item : TWaveCell read GetItem;    // Текущий элемент массива.
    property MinCost : Integer read FMinCost;  // Минимальное значения Cost
                                               // среди всех элементов массива.
    constructor Create;
    destructor Destroy; override;
    procedure Add(NewX,NewY,NewCost,NewDirection : Integer); // Добавляет новый
                                                             // элемент в массив.
    procedure Clear;  // Очищает массив. На самом деле всего лишь меняет
                      // значение поля FCount. Динамический массив не
                      // освобождается и его значения не изменяются.
    function Start : Boolean;  // Начало сканирования массива. Делает текущим
                               // первый элемент массива. Возвращает false,
                               // если массив пуст.
    function Next : Boolean;   // Делает текущим следующий элемент массива.
                               // Возвращает false, если следующего элемента нет.
  end;

Реализацию методов данного класса описывать не буду. Там все достаточно просто и понятно. Единственное, на что надо обратить внимание, это на увеличение размера динамического массива: я его увеличиваю кусками по 30 элементов (число взято от фонаря). Если кому не нравится, то перепишите (метод TWave.Add).

Несколько слов о дополнительных функциях. Имеется пара вспомогательных функций, для перевода направления в приращения координат. Так же к дополнительным относится функция получения стоимости движения GetCost.

var
  GetCostFunc : TGetCostFunc;  // Переменная для хранения функции определения
                               // стоимости движения, переданной из основной
                               // программы.

{Локальная функция определения стоимости передвижения. В алгоритме первой
 вызывается именно она. Сначала приводим значение Direction к диапазону 0..7,
 а потом проверяем выход за пределы карты. Если выходит, то сами возвращаем
 -1 (код препятствия), а не передаем во внешнюю функцию.
 Типичный FoolProof: вдруг разработчик основоного модуля не предусмотрел
 проверку на выход за пределы карты.
 Заведомо корректное значение параметров передаем во внешнюю функцию и
 возвращаем результат ее работы.}
function GetCost(X,Y,Direction : Integer) : Integer;
begin
  Direction:=(Direction AND 7);
  if (X < 0) OR (X >= MapWidth) OR (Y < 0) OR (Y >= MapHeight)
  then
    Result:=-1
  else
    Result:=GetCostFunc(X,Y,Direction);
end;

{Функция пепеходник: переводит направление в приращение координаты X.}
function DirToDX(Direction : Integer) : Integer;
begin
  case Direction of
    0,4  : Result:=0;
    1..3 : Result:=1;
  else
    Result:=-1;
  end;
end;

{Функция пепеходник: переводит направление в приращение координаты Y.}
function DirToDY(Direction : Integer) : Integer;
begin
  case Direction of
    2,6  : Result:=0;
    3..5 : Result:=1;
  else
    Result:=-1;
  end;
end;

Функция GetCost является предобработчиком запроса на стоимость движения. Она вносит корректировки в значение Direction, если оно выходит за пределы заданного диапазона 0..7 (остаток от предыдущей версии, когда операции с направлением могли привести к выходу за границы диапазона). Она также проверяет запрошенные координаты на предмет невыхода за границы карты. В случае выхода возвращает код препятствия, дабы избежать продолжения движения в том направлении.

Основная функция модуля – FillPathMap – строит карту пути от начальной до конечной точки.

{Основная рабочая лошадка -- ялро алгоритма. Возвращает карту пути,
 рассчитанную от начальной до конечной точки.
 Для упрощения понимания часть кода организовна во внутренние процедуры.}
function FillPathMap(X1,Y1,X2,Y2 : Integer) : TPathMap;
var
  OldWave, NewWave : TWave;
  Finished : Boolean;
  I : TWaveCell;

  procedure PreparePathMap;  // Создает динамический массив под результат и
  var                        // запоняет для каждой клатки поле Distance
    X,Y : Integer;           // (номер клетки в маршруте) значениями -1,
  begin                      // означающими, что поэтой клетке еще не проезжали.
    SetLength(Result,MapHeight,MapWidth);
    for Y:=0 to (MapHeight-1) do
      for X:=0 to (MapWidth-1) do
        Result[Y,X].Distance:=-1;
  end;

  procedure TestNeighbours;  //проверяем восемь клеток, соседних с клеткой,
  var                        // на которую указывает текущий элемент волны.
    X,Y,C,D : Integer;
  begin
    for D:=0 to 7 do
      begin
      X:=OldWave.Item.X+DirToDX(D);
      Y:=OldWave.Item.Y+DirToDY(D);
      C:=GetCost(X,Y,D);
      if (C >= 0) AND (Result[Y,X].Distance < 0) // Если не препятствие и там не
      then                                       // проезжали, то
        NewWave.Add(X,Y,C,D);                    // начинаем движение туда.
      end;
  end;

  procedure ExchangeWaves; // Меняем значения старой и нновой волны.
  var
    W : TWave;
  begin
    W:=OldWave;
    OldWave:=NewWave;
    NewWave:=W;
    NewWave.Clear;
  end;

begin
  PreparePathMap;             // Создаем массив результатов и заполняем его
                              // начальными значениями.
  OldWave:=TWave.Create;
  NewWave:=TWave.Create;
  Result[Y1,X1].Distance:=0;  // Отмечаем, что прошли начальную точку.
  OldWave.Add(X1,Y1,0,0);     // Создаем волну из одной начальной точки
  TestNeighbours;             // Так как единственный элемент в OldWave имеет
                              // значение Cost = 0, то TestNeighbours создаст в
                              // NewWave следующую фазу волны по всем возможным
                              // направлениям от начальной точки.
  Finished:=((X1 = X2) AND (Y1 = Y2));  // Проверка на совпадение начальной и
                                        // конечной точек.
  while NOT Finished do        // Цикл, пока не найдена конечная точка.
    begin
    ExchangeWaves;             // Загоняем новую фазу волны в OldWave и
                               // освобождаем NewWave для загрузки следующей
                               // фазы.
    if NOT OldWave.Start then Break;  // Позиционируем OldWave еа еачало. Если
                                      // значений нет, то волна умерла. Выход.
      repeat                          // Путь не найден.
        I:=OldWave.Item;                 // Берем текущий элемент волны.
        I.Cost:=I.Cost-OldWave.MinCost;  // Вычитая из Cost минимальное значение
                                         // для всей OldWave получаем элементы,
                                         // которые добрались до цели (Cost=0).
        if I.Cost > 0                             // Тех, кто не добрался,
        then                                      // записываем в NewWave с
          NewWave.Add(I.X,I.Y,I.Cost,I.Direction) // остатком Cost.
        else
          begin
          // Если по клетке уже проехали, то выбрасываем.
          if Result[I.Y,I.X].Distance >= 0 then Continue;
         // Если по клетке не проехали, то записываем в Distance номер клетки
          // на маршруте. Номер вычисляется как номер предыдущей клетки
          // маршрута +1.
          Result[I.Y,I.X].Distance:=Result[I.Y-DirToDY(I.Direction),
                 I.X-DirToDX(I.Direction)].Distance+1;
          // Сохраняем направление, по которому мы сюда приехали.
          Result[I.Y,I.X].Direction:=I.Direction;
          // Проверка на достижение конечной точки.
          Finished:=((I.X = X2) AND (I.Y = Y2));
          if Finished then Break;
          // Из достигнутой клетки пускаем новую волну во всех возможных
          // направлениях. Сохраняем в NewWave.
          TestNeighbours;
          end;
      until NOT OldWave.Next;  // Продолжаем цикл, пока не переберем
    end;                       // все элементы из OldWave;
  NewWave.Free;
  OldWave.Free;
end;

Работает эта функция следующим образом. В OldWave хранится текущая фаза волны, то есть элементы, движущиеся к своим клеткам. Момент достижения первыми элементы волны клеток назначения наступит через OldWave.MinCost. Соответственно мы пробегаем по всем элементам OldWave и вычитаем из их поля Cost значение OldWave.MinCost. Элементы, для которых Cost остался больше нуля, еще не добрались до цели. Они переносятся в NewWave, формируя следующую фазу волны. Элементы, достигшие цели, помечают свою клетку как пройденную и начинают движение из этой клетки во всех возможных еще не пройденных направлениях, записывая новые элементы также в NewWave. По завершении цикла OldWave и NewWave меняются содержимым, и все повторяется сначала. Если в начале цикла OldWave пуст, то значит, искомый путь не существует. Если была достигнута клетка, путь к которой мы искали, то выходим из функции. Путь найден.

Ну, и наконец, три последние функции:

function MakePathMap(
  MapWidth,MapHeight : Integer;
  StartX,StartY : Integer;
  GetCostFunc : TGetCostFunc) : TPathMap;
begin
  PathFind.MapWidth:=MapWidth;       // Сохраняем необхдимые значения параметров
  PathFind.MapHeight:=MapHeight;     // в локальных переменных, для использования
  PathFind.GetCostFunc:=GetCostFunc; // другими процедурами модуля.
  // Заполняем крату пути, Так как конечная точка недостижима, то выход
  // произойдет только после того, как мы пройдем все возможные клетки.
  // Соответственно, на выходе мы получим полную карту пути.
  Result:=FillPathMap(StartX,StartY,-1,-1);
end;

function FindPathOnMap(PathMap : TPathMap; X,Y : Integer) : TPath;
var
  Direction : Integer;
begin
  Result:=NIL;
  if PathMap[Y,X].Distance < 0 then Exit;
  SetLength(Result,PathMap[Y,X].Distance+1); // Создали массив для результата.
  // Пробегаем по карте пути в обратную сторону из заданной точки и
  // сохраняем координаты клеток в результрующем массиве.
  while PathMap[Y,X].Distance > 0 do
    begin
    Result[PathMap[Y,X].Distance]:=Point(X,Y);
    Direction:=PathMap[Y,X].Direction;
    X:=X-DirToDX(Direction);
    Y:=Y-DirToDY(Direction);
    end;
  Result[0]:=Point(X,Y);  //Дополняем результат кначальной точкой маршрута.
end;

function FindPath(
  MapWidth,MapHeight : Integer;
  StartX,StartY,StopX,StopY : Integer;
  GetCostFunc : TGetCostFunc) : TPath;
begin
  PathFind.MapWidth:=MapWidth;       // Сохраняем необхдимые значения параметров
  PathFind.MapHeight:=MapHeight;     // в локальных переменных, для использования
  PathFind.GetCostFunc:=GetCostFunc; // другими процедурами модуля.
  // Создаем карту пути до конечной точки и тут же ищем по ней путь.
  // Комбинация двух предыдущих функций.
  Result:=FindPathOnMap(FillPathMap(StartX,StartY,StopX,StopY),StopX,StopY);
end;

Тут все понятно. Дополнительных пояснений не требуется.

Пример использования

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

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

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

О возможностях использования модуля

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

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

Например, задав стоимость движения по диагонали в –1 (препятствие), а стоимость движения по горизонтали и вертикали в 1 (вне зависимости от типа клетки) мы получим модель, реализованную в программе Вадима Кеглеса, которая упоминалась выше.

Используя возможность изменять стоимость движения в зависимости от направления движения, можно, допустим, реализовать поиск пути на карте с рельефом (типа, Старкрафт), когда две соседние клетки не являются препятствиями, однако находятся на разных уровнях, и попасть с одной на другую можно только через пологий подъем, который расположен в стороне. Можно сделать односторонне проходимые клетки для какой-нибудь очень уж экзотической фантастической модели.

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

Это то, что я смог придумать сходу. Желающие могут продолжить сей список. Дерзайте.



Специально для Королевства Delphi


К материалу прилагаются файлы: