Размещение защитных структур в игре
Я работаю над ботом AI для игровой Обороноспособности. Игра имеет города с переменным населением и защитными структурами с ограниченным диапазоном. Я пытаюсь разработать хороший алгоритм для размещения оборонных башен.
- Города с более высоким населением более важны для защиты
- Потеря оборонной башни является ударом, таким образом, башни должны быть помещены обоснованно близко друг к другу
- Башни и города могут только быть помещены в землю
Так, с этими тремя правилами мы видим, что лучший вид размещения является башнями, помещаемыми в кольцо вокруг самых больших областей населения (хотя я не хочу алгоритм только для слепого размещения кольца вокруг самой высокой области населения, когда-то могло бы быть 2 набора городов далеко друг от друга, в этом случае алгоритм должен сделать 2 круга, каждая половина моих общих башен).
Я задаюсь вопросом, какие алгоритмы могли бы использоваться для определения размещения башен?
4 ответа
Я не знаю игры, но из вашего описания кажется, что вам нужен алгоритм, аналогичный тому, который используется для решения задачи (взвешенных) k-центров. К сожалению, это сложная проблема NP, поэтому в лучшем случае вы получите приближение, ограниченное сверху некоторым фактором.
Взгляните здесь: http://algo2.iti.kit.edu/vanstee/courses/kcenter.pdf
Просто определите функцию утилиты, которая принимает потенциальную позицию построения в качестве входных данных и возвращает «оценку» для этой позиции. Я представляю, что это выглядело бы примерно так:
utility(position p) = k1 * population_of_city_at_p +
k2 * new_area_covered_if_placed_at_p +
k3 * number_of_nearby_defences
( k1 , k2 и k3 - произвольные константы, которые нужно будет настроить)
Тогда просто случайным образом выберем кучу различных точек, p и выберем ту, у которой самая высокая полезность.
Для переключения между режимами поиска, чувствительными к регистру, используйте это сопоставление в приложении .vimrc
nmap < F9 >: set ignorecase! ignorecase?
Я бы определил функцию, определяющую значение башни, размещенной в этой позиции. Затем найдите максимумы в этой функции и поместите там башню.
Эскиз для функции может выглядеть следующим образом:
if water return 0
popsum = sum for all city over (population/distance) // it's better to have towers close by
towersum = - sum for all existing towers (1/distance) // you want you towers spread somewhat evenly
return popsum + towersum*f // f adjusts the relative importance of spreading towers equally and protecting the population centers with many towers
Должен дать разумный алгоритм для начала. Для улучшения вы можете изменить функцию 1/distance на что-то другое, чтобы получить более быстрое или медленное падение.
Я бы начал с реализации функции пригодности, которая вычисляет ожидаемую защиту, обеспечиваемую набором башен на данной карте.
Вы бы посчитали количество населения внутри «защищенной» области, где области, покрытые двумя башнями, оцениваются немного выше, чем область, покрытая только одной башней (точный коэффициент масштабирования во многом зависит от игровой механики, хотя ).
Затем вы можете использовать генетический алгоритм , чтобы поэкспериментировать с различными наборами размещений и позволить этому работать в течение нескольких (сотен?) Итераций.
Если ваша фитнес-функция хорошо соответствует реальному качеству размещения и ваша реализация генетического алгоритма верна, то вы должны получить разумный результат.
И как только вы сделаете все, вы можете приступить к разработке плана атаки, который пытается оптимизировать потери для любого заданного набора защитных башен. Получив это, вы можете настроить две популяции друг против друга и таким образом достичь еще лучших планов защиты (это одна из основных идей искусственной жизни ).
Просто определите полезную функцию, которая принимает на вход потенциальную позицию сборки и возвращает "рейтинг" для этой позиции. Я представляю, что это будет выглядеть примерно так:
utility(position p) = k1 * population_of_city_at_p +
k2 * new_area_covered_if_placed_at_p +
k3 * number_of_nearby_defences
(k1, k2, и k3 - произвольные константы, которые вам нужно будет настроить)
Затем, просто произведите случайную выборку кучи различных точек, p и выберите одну с наибольшей полезностью.