Фон
Есть квадратная карта с некоторыми препятствиями на ней. Препятствия представлены полигонами. Я реализовал следующий алгоритм поиска пути:
1) Выберите точность (обозначим ее k)
2) Разделите карту на квадраты k x k.
3) Составьте график из этих квадратов по следующим правилам:
- Каждый узел представляет один квадрат
- Два узла соединены тогда и только тогда, когда они смежные, и ни один из них не создает препятствий.
4) Найти кратчайший путь с помощью алгоритма A * (или Дейкстры или другого ...)
Этот алгоритм работает достаточно хорошо, если карта не является динамической. Это означает, что препятствия не могут быть перемещены.
Вопросы
1) Это эффективный подход?
2) Что делать, если препятствия можно перемещать?
3) Как лечить другие средства? Рассмотрим ситуацию, когда в комнате 100 агентов. Есть два, существует. Все агенты находятся в одной группе, и эта группа около одного из выходов. Если все агенты уйдут к ближайшему выходу, это вызовет узкое место. Некоторые из них должны перейти к другому выходу, чтобы минимизировать время, необходимое для выхода. Как получить такой результат?