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

[андрей чикатила]

Таким образом можно делать ботов которые сами будут искать путь без надобности делать маршруты самому?

 

[Musaigen]

Релиз v3.0.1​

Основные изменения​

1. Изменена логика метода конфигурации collision
   Ранее метод возвращал значение "нет препятствий" между двумя точками, теперь он возвращает "есть препятствия". Это изменение нарушает обратную совместимость. Если вы модифицировали конфигурацию (что рекомендуется делать почти всегда), то потребуется обновить соответствующие части.
2. Оптимизация BinaryHeap
   Теперь бинарная куча кэширует свой размер и хранит хэш-карту своих узлов, что позволяет получать доступ к элементам по хэшу за O(1).
3. Улучшение алгоритмов поиска пути
   Алгоритмы теперь используют хэш-карту для отслеживания посещённых точек, что обеспечивает O(1) проверку на посещённость узла и определение его индекса в бинарной куче.
4. Исправлено поведение DynamicPathBuilder
   Исправлена ошибка, при которой планировщик неправильно добавлял точки из прекешированного пути.
5. Добавление новых классов в INTERFACE
   В таблицу INTERFACE библиотеки добавлены следующие классы: Node, BinaryHeap, Hash, Utility.
6. Изменён потолок оси Z в функции validate
   По умолчанию максимальное значение оси Z уменьшено с 5 до 2.
7. Минорная оптимизация в DynamicPathBuilder
   Ускорен внутренний метод, связанный с нахождением свободной точки в пространстве.
8. Исправлено падение демо-приложения
   Исправлена ошибка, вызывавшая крах в демонстрационной версии.
9. Демо: добавлен вывод времени выполнения
   В раздел "Static Pathing" демо-приложения добавлено отображение времени, затраченного на построение пути.

---

Общая эффективность​

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

---

Перспективы​

Если позволит время, демо-приложение будет расширено и превращено в полноценный тулкит для:

• создания,
• тестирования,
• экспорта конфигураций алгоритмов,
• генерации навигационных сеток.

Таким образом можно делать ботов которые сами будут искать путь без надобности делать маршруты самому?

Нет, если бот для местности, где большая территория (шахты, ферма), лучше создать навигационную сетку (раньше это было бы маршрутом) на всю территорию для определения конечной точки, потом через pathfinding можно будет проложить путь от позиции игрока до этой точки. Для ботов в каких нибудь интерьерах 2х2 метра размером без препятствий и перепад высот будет меньше заморочек конечно.