С помощью модуля FindPath.pas вы можете найти кратчайший путь между двумя точками на карте. Алгоритм, используемый в данном модуле, предполагает, что на карте (игровой карте) существуют проходимые и непроходимые зоны. Карта - матрица любых размеров. Элементы матрицы - зоны или области (проходимые или непроходимые). Кратчайший путь между заданными точками - сформированный программой список координат проходимых областей.

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

Матрица карты содержит элементы Boolean, хотя она имеет формат массива Matrix (эта возможность появляется благодаря использованию свойств в классе). Проходимые зоны имеют значение False, а непроходимые - True.

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

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

Для использования алгоритма поиска пути вы должны выполнить следующие шаги:

1. Объявить переменную типа TFindPath (var FP: TFindPath);
2. Инициализировать объект FP (FP := TFindPath.Create(100, 50)). При создании объекта автоматически создается матрица карты указанных размеров. Она имеет только нулевые элементы.
3. Скопировать карту в матрицу. В вашей программе карта может храниться в каком угодно формате. Допустим карта храниться в массиве, объявленном следующим образом:

                   var
                     MapArray: array[1..100, 1..50] of Record
                           Color: TColor;  // Цвет области
                           Heigth: Single; // Высота
                           ..............
                           Wall: Boolean;  // Препятствие
                     end;
                   

   В этой записи нас интересует только переменная Wall, указывающая на наличие препятствия. Скопировать карту в матрицу можно следующим образом:

                   for i := 1 to 100 do
                     for j := 1 to 50 do
                           FP.Map[i, j] := MapArray[i, j].Wall;
                   

4. Выполнить поиск пути (if FP.Find(1, 1, 50, 50) then ShowMessage('Путь найден')). Функция Find() является основной в классе TFindPath. В случае, если путь найден, функция вернет True.
5. Считать точки найденного пути из списка PathList. Необходимо учитывать, что в этом списке присутствуют начальная и конечная точки, которые мы передали в функцию Find(). Кроме того, вы можете узнать время поиска. Для этого нужно считать значение переменной SearchTime.

Вы можете хранить карты в файлах, а также загружать их из файлов. Для этого используются соответственно функции SaveMapToFile() и LoadMapFromFile().

Примечание: В алгоритме поиска задействован класс TList для хранения указателей на структуры TPoint. Для оптимизации можете разработать свой собственный список. Для компиляции необходим дополнительный модуль matrix.pas