Существуют ли алгоритмы для поиска пути в графе для нескольких объектов одновременно?

Здравствуйте.
Буду очень признателен, если кто-нибудь сможет подсказать мне какие алгоритмы можно применить к такой задаче:

Есть комната с N фигурами, которые могут ходить по горизонтали и вертикали. У каждой фигуры есть пункт назначения. Нужно найти оптимальные пути для всех фигур одновременно, чтобы время этого перемещения было минимальным.

Основная проблема, что фигуры должны синхронизировать свои движения друг с другом. Для примера в данной простой ситуации вторая фигура должна зайти в тоннель и подождать там, пока первая фигура пройдет мимо.
5a5dd4dde56d8784061433.png

Задача судя по всему NP полная и тут можно делать полный перебор путей на графе с отсечением, но наверняка уже есть наработки на эту тему.
  • Вопрос задан
  • 534 просмотра
Пригласить эксперта
Ответы на вопрос 1
Taraflex
@Taraflex
Ищу работу. Контакты в профиле.
Двигайте юнитов с учетом физики по пути расчитанному при помощи какого-нибудь A* (в стиле шарика на резинке или собаки на поводке), при столкновении уменьшайте импульс юнитам у которых больше свободных соседей (чтобы не возникло заторов).
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы