BeaRLibPF - поиск пути

Форум библиотеки BeaRLib

Модератор: Apromix

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

Re: BeaRLibPF - поиск пути

Сообщение kipar » 21 сен 2016, 15:19

Хм, да, есть такое.
То что ты привел из кода демки а не самой библиотеки, но в библиотеке оказывается тоже предполагается что X идет от 1, а надо бы сделать от Xmin до Xmax.

Аватара пользователя
Apromix
Мастер
Сообщения: 1236
Зарегистрирован: 04 июл 2011, 10:44
Откуда: Украина, Черновцы
Контактная информация:

Re: BeaRLibPF - поиск пути

Сообщение Apromix » 22 сен 2016, 16:45

Будет исправленная версия?

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

Re: BeaRLibPF - поиск пути

Сообщение kipar » 23 сен 2016, 07:15

BearLibPF.zip
(126.1 КБ) 190 скачиваний
А так конечно надо весь интерфейс переделывать, по образцу libtcod, как минимум чтобы была возможность получать весь путь а не пересчитывать каждый раз, ну и веса задавать а не просто проходимость.

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

Re: BeaRLibPF - поиск пути

Сообщение kipar » 09 фев 2017, 12:11

Эх, сделал дийкстру и интерфейс похожий на libtcod, но понял что в libtcod не зря начали разделять A* и дийкстру по названиям функций, и вообще интерфейс не годится. С ними все равно нужно по-разному работать, заменой одной строки алгоритм не поменять.

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

Теперь пусть мы используем A*. Тогда нам нужен для каждого монстра свой объект хранящий путь. Но на расчет пути потребуется памяти Xmax*Ymax*4, и если каждый из таких объектов будет выделять столько памяти то никакой памяти не напасешься.
Поэтому нужен один общий объект который будет хранить эту память и он же видимо будет рассчитывать путь, а объекты у монстров умеют только хранить путь и следовать по нему.

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

Короче новой версии пока нет. Но к 7drl (который в марте) надеюсь будет, ахаха.

Аватара пользователя
Apromix
Мастер
Сообщения: 1236
Зарегистрирован: 04 июл 2011, 10:44
Откуда: Украина, Черновцы
Контактная информация:

Re: BeaRLibPF - поиск пути

Сообщение Apromix » 09 фев 2017, 13:12

Мне вобщем алгоритм A* как он есть понравился. Не замечал за ним особых тормозов.

Если по другому алгоритму требуется другой интерфейс - не вижу проблем.

Ждем новую версию :D

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

Re: BeaRLibPF - поиск пути

Сообщение kipar » 12 фев 2017, 13:17

Итак, новая версия.
BearlibPF2.zip
(1.08 МБ) 171 скачивание
В архиве демка с исходниками и библиотека. И текстовый файл описания. хидеры пока только на паскале.
Копия описания под спойлером (у меня видимо нет аккаунта на вики и непонятно как его создать)
Скрытый текст: ПОКАЗАТЬ
Основные понятия:
Библиотека содержит функции по работе с двумя типами объектов - "путем" и "искателем путей".

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

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

Искатель пути имеет следующие свойства:
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, поэтому должна корректно обрабатывать такой вызов.

Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 28 гостей