Я разрабатываю игру / симулятор, где агенты сражаются за землю. У меня есть ситуация, показанная на картинке ниже:
Эти существа ходят вокруг и занимают участки земли, на которые они ступают, если они свободны. Чтобы сделать это более интересным, я хочу представить «патрулирующее» поведение, чтобы агенты фактически ходили по своей земле, чтобы патрулировать от любых злоумышленников, которые могут захотеть взять это.
С технической стороны каждый квадрат представлен как x,y
позиция, а также размер, представляющий длину его стороны. Он также содержит информацию о том, кто занимает площадь. Все квадраты хранятся в ArrayList
.
Как я могу представить патрулирование? Я хочу, чтобы каждый агент патрулировал определенную часть области (они делят между собой, какие области они будут патрулировать). Основная проблема, которую я обнаружил, заключается в следующем:
- Площадь земли очень случайная, как видно на картинке. Довольно сложно понять, где находятся границы в каждом направлении.
- Как им агенты должны разделить регионы для патрулирования?
- Участки земли могут быть непересекающимися, так как противоборствующая команда может захватить территорию с середины.
У меня была идея взять самый дальний квадрат в каждом направлении, рассматривая их как границы области, и разделить регионы на основе этих границ, но это может включать в себя множество не относящихся к делу земель.
Как мне подойти к этой проблеме?
Ответы:
Увлекательный вопрос. Я думаю, что одна из первых проблем, которую вы должны решить, - хотите ли вы, чтобы патрульное поведение было «оптимальным» патрулированием или «реалистичным» патрулированием. Я просто сочиняю эти слова, но я имею в виду следующее:
Оптимально : агенты перемещаются таким образом, который идеально распределяет их зону покрытия для системы в целом.
Реалистичная жизнь : агенты перемещаются и пытаются распределить себя настолько равномерно, насколько это возможно, но у каждого есть доступ только к данным, локальным для их перспективы.
Я собираюсь сосредоточиться на втором подходе, который, я думаю, вы можете решить, используя взвешенное смешивание различных шаблонов управления из Крейга Рейнольдса « Поведение управления для автономных персонажей» . Основная идея управления поведением состоит в том, чтобы использовать простые силы, которые объединяются для создания импровизационной навигации по окружающей среде. В вашем случае, я думаю, вы захотите объединить следующие способы управления:
Избежание (за пределами территории) - агенты пытаются оставаться на своей территории и избегать выезда за ее пределы. Для некоторого реализма, однако, влияние "выхода за пределы" территории не должно быть 100% здесь. Немного «острых углов», чтобы выйти за пределы области, вероятно, сделало бы более реалистичное движение.
Блуждающий - агенты пытаются продолжать двигаться и исследовать. Это тот, который вы захотите взвесить, иначе агенты попытаются найти оптимальную точку отрыва друг от друга, а затем «оставаться на месте».
Разделение (другие агенты) - агенты пытаются держаться на расстоянии от других агентов (таким образом, они покрывают максимум земли и не сгущаются).
Seek (invaders) - Агенты пытаются приблизиться к любым обнаруженным захватчикам.
Я думаю, что вы захотите поиграть с относительным весом динамически. Например, если агент обнаруживает захватчика, вес разделения должен уменьшаться. (Другими словами, они должны распространяться, только когда они охотятся, а не когда они находят кого-то.) Я думаю, что если вы поиграете с весами для вышеупомянутых четырех паттернов, у вас будет что-то довольно близкое к тому, что у вас » ищу.
В Интернете довольно много ресурсов о том, как реализовать «boids», которые следуют описанным моделям поведения. Я рекомендую реализацию с открытым исходным кодом .
источник
Один подход состоит в том, чтобы записать для каждой ячейки, когда ее в последний раз посещал «охранник», и чтобы охранники постоянно перемещались в ту соседнюю ячейку, которая не была посещена дольше всего.
Конечно, это предполагает, что территория связана.
Это не идеальное решение, но легко кодируемое, адаптивное к изменяющимся обстоятельствам и эффективное. Я успешно использовал этот алгоритм для разведки и преследования в RTS-а я написал некоторое время назад.
источник