Исходник Софт [2.1.0] pathfinding / Библиотека для реализации алгоритмов поиска пути

[Musaigen]

Pathfinding - библиотека для реализации алгоритмов поиска пути в GTA:SA. Это означает, что данная библиотека стремится реализовать не только один алгоритм поиска пути, а несколько, пытаясь привести их в пригодное для использования состояние. На данный момент ведется работа над наиболее известным и простым в реализации алгоритмом А*.

Использование: Библиотека экспортирует всего одну основную функцию:

local pathfinding = require("pathfinding")
local path = pathfinding:process([algorithm-name: string], [start: Vector], [goal: Vector], (configuration: Configuration|nil))

Демо:
В архиве с библиотекой есть папка demo. Там хранится демонстрация библиотеки и её возможностей. Имеет одну команду pf.demo, которая скрывает/показывает меню.
Предостережение: Подобные алгоритмы, как ни крути, очень затратны по ОЗУ, если не адаптировать их под конкретную ситуацию. Например: вряд ли вам требуется 20+ точек, если вы пишите бота для работы в буквально узком коридорном помещении и так далее. В общем, скорость зависит от вашего процессора и количества + качества ОЗУ.
Также не стоит пытаться построить путь с точками, у которых огромное расстояние между собой. Лучше разделить их на кучу других точек, но ближе друг к другу.
Установка: Скачать библиотеку можно с GitHub. С архива нужно переместить содержимое папки src в вашу папку moonloader/lib.
Также: библиотека написана при помощи moonly
Референсы: Википедия, Википедия (Theta*), FiveTuning, тема c Blast.hk (a.k.a Терминатор от @Rei)

 

[UBP]

Обход краша при слишком большом расстоянии. Ты забыл вырезать у меня из кода step, тоесть разрезание пути на сегменты, а затем прохождение итерации между этими сегментами🧐

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

 

[Musaigen]

V1.0.1-alpha:
Исправлено поведение, когда путь любой сложности был недостижимым из-за функции Neighbors, которая возвращала маленькое количество точек (4-6 штук)

Ты забыл вырезать у меня из кода step, тоесть разрезание пути на сегменты, а затем прохождение итерации между этими сегментами

Окей, посмотрю

а так же применять сглаживание чтобы не было зиг загов.

Сглаживание присутствует, зигзаги из-за алгоритма. Есть другие алгоритмы, вроде theta*, которые такой проблемы не имеют, насколько я знаю. (Хоть это и не проблема, т. к алгоритм отрабатавывает по самым дешевым и эффективным путям как раз таки).

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

Здесь не понял. При создании узла соседа, на его точку сразу же применяется Validate и Collision.

 

[UBP]

V1.0.1-alpha:
Исправлено поведение, когда путь любой сложности был недостижимым из-за функции Neighbors, которая возвращала маленькое количество точек (4-6 штук)


Окей, посмотрю

Сглаживание присутствует, зигзаги из-за алгоритма. Есть другие алгоритмы, вроде theta*, которые такой проблемы не имеют, насколько я знаю. (Хоть это и не проблема, т. к алгоритм отрабатавывает по самым дешевым и эффективным путям как раз таки).

Здесь не понял. При создании узла соседа, на его точку сразу же применяется Validate и Collision.

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

Ррт такую проблему не имеет.

Вообще есть hierarchical path find, и можно комбинировать. Сначала его, потом ррт и астар

 

[Musaigen]

rrt

Я уже переписывал его для теста, взяв за основу FiveTuning, однако он не работал, как бы я не старался. Ну и ещё в FiveTuning в принципе команда /autopilot не работает. Выплюну сюда файл.

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

По такой логике они и будут видны, так что постобработка ничего особо не даст.

Я понял про что ты, подобное есть в theta*, чуть позже его реализую наверное

V1.1.1-alpha:
1. Добавлена функция "ReachedEnd" в класс конфигурации, которая позволяет определить, достигла ли точка конца пути. Первый аргумент это всегда конечная точка пути, второй аргумент это новая точка, взятая из дерева. По умолчанию, её реализация это config:Heuristics(end_point, point) <= config.Step
2. Функция `Heuristics` теперь принимает векторы, а не ноды, как это было раньше.
3. Убрана неиспользуемая функция `clamp` из утилит, также оттуда убрана функция `smooth_path`, так как любила отгрызать пути, количество точек в котором не кратно 4, также это требуется для совместимости с кастомными функциями `ReachedEnd`.

Небольшой пример, для чего может использоваться новая функция:

local path = pathfinding:process("a*", point_a, point_b, {
    ReachedEnd = function(self, end_point, point)
        -- Теперь если end_point находится в прямой видимости point, поиск пути сразу же завершится.
        return isLineOfSightClear(end_point, point, ...)
    end
})

 

[UBP]

Я уже переписывал его для теста, взяв за основу FiveTuning, однако он не работал, как бы я не старался. Ну и ещё в FiveTuning в принципе команда /autopilot не работает. Выплюну сюда файл.


По такой логике они и будут видны, так что постобработка ничего особо не даст.

Я понял про что ты, подобное есть в theta*, чуть позже его реализую наверное

V1.1.1-alpha:
1. Добавлена функция "ReachedEnd" в класс конфигурации, которая позволяет определить, достигла ли точка конца пути. Первый аргумент это всегда конечная точка пути, второй аргумент это новая точка, взятая из дерева. По умолчанию, её реализация это config:Heuristics(end_point, point) <= config.Step
2. Функция `Heuristics` теперь принимает векторы, а не ноды, как это было раньше.
3. Убрана неиспользуемая функция `clamp` из утилит, также оттуда убрана функция `smooth_path`, так как любила отгрызать пути, количество точек в котором не кратно 4, также это требуется для совместимости с кастомными функциями `ReachedEnd`.

Небольшой пример, для чего может использоваться новая функция:

local path = pathfinding:process("a*", point_a, point_b, {
    ReachedEnd = function(self, end_point, point)
        -- Теперь если end_point находится в прямой видимости point, поиск пути сразу же завершится.
        return isLineOfSightClear(end_point, point, ...)
    end
})

Потому что в библиотеке fivetuning нужно правильно все склеить в одну функцию buildpath. Включая некоторые улучшения и несколько методов

Я уже переписывал его для теста, взяв за основу FiveTuning, однако он не работал, как бы я не старался. Ну и ещё в FiveTuning в принципе команда /autopilot не работает. Выплюну сюда файл.


По такой логике они и будут видны, так что постобработка ничего особо не даст.

Я понял про что ты, подобное есть в theta*, чуть позже его реализую наверное

V1.1.1-alpha:
1. Добавлена функция "ReachedEnd" в класс конфигурации, которая позволяет определить, достигла ли точка конца пути. Первый аргумент это всегда конечная точка пути, второй аргумент это новая точка, взятая из дерева. По умолчанию, её реализация это config:Heuristics(end_point, point) <= config.Step
2. Функция `Heuristics` теперь принимает векторы, а не ноды, как это было раньше.
3. Убрана неиспользуемая функция `clamp` из утилит, также оттуда убрана функция `smooth_path`, так как любила отгрызать пути, количество точек в котором не кратно 4, также это требуется для совместимости с кастомными функциями `ReachedEnd`.

Небольшой пример, для чего может использоваться новая функция:

local path = pathfinding:process("a*", point_a, point_b, {
    ReachedEnd = function(self, end_point, point)
        -- Теперь если end_point находится в прямой видимости point, поиск пути сразу же завершится.
        return isLineOfSightClear(end_point, point, ...)
    end
})

Ты не понял. Сверять точки в сегментах пути на предмет прямой видимости иначе перестраивать путь.

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

 

[Musaigen]

Потому что в библиотеке fivetuning нужно правильно все склеить в одну функцию buildpath. Включая некоторые улучшения и несколько методов


Ты не понял. Сверять точки в сегментах пути на предмет прямой видимости иначе перестраивать путь.

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

Это реализовано уже в другом алгоритме theta*, а* не предполагает таких выкрутасов, потому все останется как есть.

Как только допилю основные моменты в а* реализуем и theta*, зигзаги на прямой дороге пофикшены и остались только на поворотах, как и имеет место быть.

 

[UBP]

Это реализовано уже в другом алгоритме theta*, а* не предполагает таких выкрутасов, потому все останется как есть.

Как только допилю основные моменты в а* реализуем и theta*, зигзаги на прямой дороге пофикшены и остались только на поворотах, как и имеет место быть.

Я уверен, ты найдёшь откуда взять рабочий код

 

[Musaigen]

Я уверен, ты найдёшь откуда взять рабочий код

В википедии давно лежит псевдокод, да и такое чувство, будто ты сам своими нейронными связями придумывал тот же А*, который был написан в прошлом веке; или же читал научную статью, где и кода почти нет.

 

[chromiusj]

 

[Musaigen]

V1.2.0-alpha:
1. Добавлен алгоритм Theta*.
2. В команду path из демо теперь можно вводить название алгоритма, по стандарту это А*.
3. Мелкие изменения в коде.

Спойлер: Небольшое сравнение А* и Theta* (где путь с кучей зигзагов там А*)

Сразу же V1.2.1-alpha:
1. Улучшена оптимизация. Теперь, если алгоритм редактирует уже существующий узел, он не будет полностью переконструировать кучу (как это по убогому было раньше).
И небольшая заметка, Theta* намного быстрее чем A*. (Особенно если вы редактировали конфигурацию под свою ситуацию, при 4-6 точках в функции Neighbors, даже А* может генерировать путь почти моментально за 2-3 стенки)

 

[Musaigen]

V2.0.0:
1. Конфигурации перенесены в отдельный класс. Без обратной совместимости.
2. Класс "Point" перенесен в таблицу INTERFACE (т.е pathfinding.INTERFACE.Point, там же можно найти класс конфигурации).
3. Полностью переписано демо.
4. Библиотека больше не в Alpha стадии.

Спойлер: Скриншот нового демо

Примеры можно найти в документации на GitHub, а также в демке библиотеки..

 

[fokichevskiy]

не знаю почему, но алгоритм Theta* всегда создает 2 точки в конце пути

 

[Musaigen]

Посмотреть вложение 262318Посмотреть вложение 262319
не знаю почему, но алгоритм Theta* всегда создает 2 точки в конце пути

Больше похоже на то, что одна точка - конечная, вторая - ближайшая к ней.

Можешь через конфигурацию поменять это, юзай set_end_reached, как вариант можно использовать isLineOfSightClear

 

[Musaigen]

V2.1.0:
1. Добавлен динамический поиск пути. Он должен был быть другим по коду, но в итоге выбрал простейший вариант реализации. Проходится по каждой точке в уже созданном пути, если есть препятствие - ищет точку, где этого препятствия нет и строит до него путь, после чего добавляет новые точки, и так до конца, начальная и конечная точка могут смещаться, если на них находится препятствие. (Если что, при динамическом построении А* лучше чем Theta*).
2. Добавлена новая вкладка "Dynamic pathing" в демо, для тестирования динамических путей.
3. Все LLS классы занесены в отдельный "неймспейс" pathfinding.
4. Ещё что-то по мелочи.