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

Question

[antkatcin]

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

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

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


Задача судя по всему NP полная и тут можно делать полный перебор путей на графе с отсечением, но наверняка уже есть наработки на эту тему.

Comments

[Therapyx]

насчет поиска кратчайших путей, конечно же такие алгоритмы есть и их найти не трудно https://en.wikipedia.org/wiki/Pathfinding
А вот у тебя уже более специфичный вариант, думаю искать придется долго или уж очень хорошо словить удачу)) Скорее всего придется просто доработать какой-нибудь уже из существующих. А так задачка интересная хд

[Андрей]

Как только объекты сделают по 2 шага вперед и окажутся в тоннеле, если они учитываются в алгоритме поиска путей, оба окажутся в тупике и дальнейшее развитие событий уже будет зависеть от алгоритма, что и как там учитывается. Допустим пути можно искать дважды для каждого объекта - с учетом других объектов и без учета. Тогда при наличии разницы будет понятно, что это другой объект преграждает путь и можно пойти альтернативным путем. Однако если будет несколько доступных путей, то все сильно усложняется.

Еще вариант, искать пути без учета других объектов, но при их обнаружении поднимать флаг.

[Максим]

Навскидку для данного примера: можно найти с помощью A* путь для одного и второго юнита, затем найти точку их встречи (где они по идее упрутся друг в друга) и с этой точки в обратном направлении искать ближайшее отклонение от найденных путей. В итоге для одного юнита будет путь с этим отклонением, для другого - обычный путь.

Answer 1

[Александр Таратин]

Двигайте юнитов с учетом физики по пути расчитанному при помощи какого-нибудь A* (в стиле шарика на резинке или собаки на поводке), при столкновении уменьшайте импульс юнитам у которых больше свободных соседей (чтобы не возникло заторов).