Основные понятия:
Библиотека содержит функции по работе с двумя типами объектов - "путем" и "искателем путей".
Путь - уже найденный маршрут, список точек от начальной до конечной. У него можно получить длину в клетках, дистанцию (с учетом весов клеток), можно получить отдельные элементы, а также "шагать по нему" т.е. получать очередной элемент укорачивая маршрут на одну позицию.
Искатель пути - объект который ищет оптимальный маршрут на заданной карте.
Если в игре много агентов ищущих пути, то они для экономии памяти могут использовать общий искатель, а у себя хранить только объекты пути. Однако если эти объекты используют принципиально разные веса поиска, например одни могут ходить по диагонали, а другие - нет, то придется все-таки создать два разных искателя.
Искатель пути имеет следующие свойства:
1. карта. Есть два варианта задания карты - либо интеграция с BearlibMap и пользовательская функция.
В первом случае искателю надо передать ид карты и номер слоя. Из-за технических проблем в данный момент поддерживаются только слои типа integer (не float).
Во втором случае передается искателю передается указатель на функцию которая принимает координаты исходной и целевой ячейки и возвращает вес перехода в целевую ячейку (умножать на диагональную стоимость не требуется, библиотека сделает это автоматически).
В обоих случаях значение (полученное от функции или считанное из слоя карты) интерпретируется следующим образом:
0 или отрицательное значение - проход невозможен. 1 и более - стоимость перехода. Важно: алгоритм А* некорректно работает с весами от 0 до 1, не используйте их.
2. стоимость диагональных переходов. Алгоритм умножает на это число полученную в прошлом пункте стоимость перехода. Значение 1 означает что диагональные переходы имеют такую же стоимость как и вертикальные (что приведет к обилию диагональных "блужданий" в полученном пути). Значение 0, а также 2 и более означает что переходы по диагонали невозможны. Рекомендуемое значение в обычных условиях - sqrt(2) или 1.4, тогда алгоритм будет предпочитать горизонтальные\вертикльные переходы и использовать диагональные когда они дают более короткий маршрут. Используйте значение 1 если стоимость диагональных переходов уже учитывается в пользовтельской функции.
3. Алгоритм. Поддерживаются два варианта - Дийкстра и A*. A* просто ищет оптимальный путь между заданными точками, не кеширует никакой информации и подходит в большинстве случаев. Дийкстра (также называемый "волна") определяет оптимальный путь из любой точки карты к заданной конечной и потому подходит для случаев когда нужно искать много путей ведущих в одну и ту же точку.
Функции библиотеки:
1. Работа с искателем пути
type
TPathfinderHandle = Pointer;
TPFAlgorithm = (Dijkstra = 0, AStar = 1);
function pf_create(map_id, layer: Integer; algorithm: TPFAlgorithm; diagonal_cost: Single): TPathfinderHandle;cdecl;
Создает объект поиска пути использующий карту BearlibMap, с ид карты map_id, слоем layer, алгоритмом algorithm и стоимостью диагональных переходов diagonal_cost. В текущей версии поддерживаются только слои типа integer.
type
TPFCallback = function(fromx, fromy, tox, toy: integer; opaque: pointer): Single;cdecl;
function pf_create_cb(SizeX, SizeY: Integer; algorithm: TPFAlgorithm; diagonal_cost: Single; opaque: pointer; callback: TPFCallback): TPathfinderHandle;cdecl;
Создает объект поиска пути использующий пользовательскую функцию callback, передающий ей дополнительные данные opaque, c алгоритмом algorithm и стоимостью диагональных переходов diagonal_cost.
procedure pf_set_opaque(Pathfinder: TPathfinderHandle; opaque: pointer);cdecl;
Меняет указатель пользовательских данных opaque у существующего искателя пути Pathfinder.
procedure pf_delete(Pathfinder: TPathfinderHandle);cdecl;
Удаляет искатель пути Pathfinder и освобождает занятую им память.
type
TPathHandle = Pointer;
const
PATH_NOT_FOUND = TPathHandle(0);
function pf_calculate_path(Pathfinder: TPathfinderHandle; fromx, fromy, tox, toy: Integer): TPathHandle;cdecl;
Рассчитывает искателем Pathfinder путь от (fromx, fromy) до (tox, toy) и возвращает указатель на путь либо PATH_NOT_FOUND.
В случае алгоритма Дийкстры если конечная точка совпадает со старой, то будет использована старая рассчитанная карта переходов. Для принудительного пересчета карты используйте pf_dijkstra_calculate.
function pf_calculate_path_gc(Pathfinder: TPathfinderHandle; key: pointer; fromx, fromy, tox, toy: Integer): TPathHandle;cdecl;
Аналогична предыдущей функции, но избавляет пользователя от необходимости следить за освобождением памяти от объектов Path. Функция принимает дополнительный параметр key, и если она ранее уже была вызвана с таким же key, то использует объект созданный в тот раз, иначе создает новый. Все объекты созданные этой функцией будут удалены при удалении искателя пути. Таким образом если требуется много агентов ищущих путь, каждый может передавать себя в качестве параметра key и не удалять пути функцией pf_delete каждый раз когда требуется поиск нового пути.
1. Работа с объектом пути
procedure pf_path_origin(Path: TPathHandle; out fromx: Integer; out fromy: Integer);cdecl;
Записывет начальную точку пути в fromx, fromy
procedure pf_path_destination(Path: TPathHandle; out tox: Integer; out toy: Integer);cdecl;
Записывет конечную точку пути в tox, toy
function pf_path_empty(Path: TPathHandle): Boolean;cdecl;
Возвращает true если путь пуст (конечная точка совпадает с начальной)
function pf_path_length(Path: TPathHandle): Integer;cdecl;
Возвращает число элементов в пути.
procedure pf_path_revert(Path: TPathHandle);cdecl;
Переворачивает путь меняя местами начальную и конечную точку.
function pf_path_distance(Path: TPathHandle): Single;cdecl;
Возвращает суммарную стоимость переходов по пути.
procedure pf_path_get(Path: TPathHandle; index: integer; out x: integer; out y: integer);cdecl;
Записывает элемент номер index пути в x, y. 0 соответствует первому шагу из начальной точки, (pf_path_length(path)-1) - конечной точке.
type
TRecalcMode = (
DontCheck = 0,
CheckOnly = 1,
CheckAndRecalculate = 2
);
function pf_path_walk(Path: TPathHandle; out x: integer; out y: integer; RecalcMode: TRecalcMode): Boolean;cdecl;
Делает один "шаг" по пути, сдвигая начальную точку на одну позицию вперед, соответственно изменяя длину и суммарную стоимость пути. Записывает новую стартовую точку в x, y. Всегда возвращает false для пустого пути, в остальных случаях возвращаемое значение определяется параметром RecalcMode.
Параметр RecalcMode определяет поведение в том случае, если шаг не соответствует текущему состоянию карты.
DontCheck - не анализировать карту. Рекомендуется если карта гарантированно не изменялась с момента нахождения пути или ее изменение не следует принимать во внимание.
CheckOnly - проверяет карту на возможность перехода и возвращает false если данный переход невозможен и true если возможен.
CheckAndRecalculate - проверяет карту, и в случае если переход невозможен заново вызывает pf_calculate_path, формируя новый маршрут. Возвращает false если новый маршрут не найден и true в остальных случаях (т.е. когда пересчета маршрута не потребовалось и когда он был проведен успешно).
procedure pf_path_delete(Path: TPathHandle);cdecl;
Удаляет путь Path.
3. Специальные функции для искателя пути с алгоритмом Dijkstra.
function pf_dijkstra_distance(Pathfinder: TPathfinderHandle; x: integer; y: integer): Single;cdecl;
Возвращает дистанцию (суммарную стоимость переходов) от точки x,y до точки цели.
function pf_dijkstra_length(Pathfinder: TPathfinderHandle; x: integer; y: integer): Integer;cdecl;
Возвращает длину пути (число шагов в маршруте) от точки x,y до точки цели.
procedure pf_dijkstra_calculate(Pathfinder: TPathfinderHandle; tox, toy: Integer);cdecl;
Пересчитывает карту для новой точки цели - tox, toy.
function pf_dijkstra_find_unreachable(Pathfinder: TPathfinderHandle; out x: integer; out y: integer): Boolean;cdecl;
Возвращает True если есть проходимые точки, не имеющие пути к целевой точке, т.е. карта не является связной.
Возвращает False если карта связная и все проходимые точки имеют путь к целевой точке.
Замечание: если карта задана с помощью пользовательской функции, то для проверки проходимости точки (x,y) функция будет вызвана с аргументами fromx=tox=x, fromy=toy=y, поэтому должна корректно обрабатывать такой вызов.