Перемещение нескольких единиц по сетке через ограниченное пространство с разными направлениями

Я только начал изучать алгоритмы поиска пути.
Предположим, что у нас есть этот сценарий:
 Сценарий
Синий и зеленый могут перемещаться только по тем плиткам. Они также могут разговаривать друг с другом.
Синий хочет пройти через туннель, а зеленый тоже хочет пойти, однако оба должны каким-то образом пройти друг к другу. В случае «базового» алгоритма поиска A * они будут застревать в туннеле.

Чтобы предотвратить эту проблему, у меня были некоторые идеи:
- Синий может сказать зеленый, что он должен сначала вернуться назад (дать синий приоритет), когда они оба ступают рядом друг с другом (проблемы возникают, когда их больше 2)
- Лучший алгоритм, который вычисляет это как автоматический регулятор трафика (один будет ждать, пока другой освободит путь) -> кажется сложным

Теперь мне интересно, есть ли более эффективные методы, как это делается в целом, если у вас есть лучшие идеи, если вы можете указать мне на некоторые алгоритмы или на некоторые документы, которые указывают на эту проблему.

4 голоса | спросил RIJIK 10 PMpTue, 10 Apr 2018 23:55:23 +030055Tuesday 2018, 23:55:23

1 ответ


1

Это определенно классическая проблема, которую можно увидеть, если вы играете Red Alert или что-то в этом роде.

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

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

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

ПРИМЕЧАНИЕ. Я бы только блокировал квадраты «впереди» блока, движущегося по «мосту», что позволяет следующему звену за ним пересекать мост. Это означает, что вы «разблокируете» квадраты мостов, когда они пересекают их, а следующий блок просто ставит очередь на новый «блок» на нем.

Это решение O (n) (может считаться O (1)), потому что каждая единица использует столько же вычислений, сколько собиралась определить, что мост «заблокирован», где в качестве единиц, говорящих друг с другом, будет O (n ^ 2) или хуже. Это означает, что он очень эффективен среди различных решений, которые могут получить.

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

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


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

ответил blurry 11 AMpWed, 11 Apr 2018 02:39:18 +030039Wednesday 2018, 02:39:18

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132