Это мой проект для университета, который визуализирует алгоритм оптимизации маршрутов использующий рой «слепых» частиц. Частицы взаимодействуют друг с другом для поиска и проложения оптимальных путей между рядом точек, при этом избегая преграды.

Сайт включает в себя мощный редактор с гибкими настройками, набор карт и графических шаблонов, а также возможность легко и быстро делиться своими работами. Полная функциональность доступна на ПК.
Имеется английская версия.

Все частицы в рое «слепые» и не имеют представления о карте.

Они не знают, где находятся ключевые точки, и могут обнаружить их только вплотную. Однако они способны обмениваться данными в небольшом радиусе, сообщая друг другу, как давно они видели каждую точку, если когда-то их посещали.

Если частица узнаёт от соседей, что до цели можно добраться быстрее, чем она предполагала, она корректирует свой маршрут и движется в сторону источника сигнала (при условии, что ищет именно эту точку).

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

Связанные материалы:
Роевой интеллект — Википедия
Метод роя частиц — Википедия
₍ᐢ‥ᐢ₎

Что интересного в этом подходе?

В отличие от многих других алгоритмов, он не зависит от заранее заданных путей. Рой прокладывает собственный маршрут в пустом пространстве, ориентируясь лишь на редкие препятствия, которые ограничивают его движение. Это позволяет применять алгоритм в нестандартных ситуациях, где невозможно чётко определить границы.

Но есть и недостатки.

На успех работы влияет множество факторов:
— Плотность частиц в начале и их распределение по рабочей области
— Дистанция их взаимодействий относительно плотности
— И, конечно, элемент случайности

В этом примере многое задаётся случайным образом, например:
— Начальные цели частиц (они посещаются по порядку)
— Вектор смещения (который применяется, если частица "теряется")

В итоге алгоритм получается довольно чувствительным и не таким быстрым, как некоторые другие. Но если правильно подобрать параметры и минимизировать случайность (например, за счёт повторных прогонов), он может превзойти классические методы в сложных условиях.