Итоговый проект. Реализация методов для игры "Герои Меча и Магии 3 против искусственного интеллекта"

Метод generate интерфейса GeneratePreset

Описание:

Метод формирует пресет армии компьютера, т.е. такой набор юнитов разного типа, который был бы максимально эффективен в первую очередь по соотношению атаки к стоимостии соотношению здоровья к стоимости. При этом соблюдается ограничение в 11 юнитов каждого типа.
Цель метода — создать армию компьютера.

Метод имеет следующую сигнатуру:
Army generate(List unitList, int maxPoints), где

• параметр unitList — список юнитов, содержит объект юнита каждого типа. На его основе происходит заполнение армии компьютера. Сейчас существует 4 типа юнитов: лучник, всадник, мечник и копейщик.
• Параметр maxPoints — максимальное число очков в сумме для всех юнитов армии, в этом случае — 1500

Алгоритмическая сложность реализации:

1. Сортировка: O(n⋅logn)
2. Цикл обработки юнитов: O(n) для итерации по списку и O(k) для добавления объектов. Поскольку k≤11⋅n, это упрощается до O(n).

Итоговая сложность метода: O(n⋅logn), где n — количество юнитов в unitList.

Метод simulate интерфейса SimulateBattle

Описание:

Метод осуществляет симуляцию боя между армией игрока и армией компьютера.
Цель метода — провести бой, следуя установленным правилам.

Симуляция происходит так:

1. На каждом раунде юниты сортируются по убыванию значения атаки, чтобы первыми ходили самые сильные.
2. Пока в обеих армиях есть живые юниты, они атакуют друг друга по очереди.
3. Если у одной из армий заканчиваются юниты, она ожидает завершения ходов оставшихся юнитов противника.
4. Когда все юниты походили, раунд завершается, и начинается следующий.

Юниты, которые погибли (значение поля isAlive — false) и еще не походили, исключаются из очередей в момент их смерти, и очереди хода пересчитываются.

Если количество юнитов в армиях становится разным из-за потерь, очередность ходов может измениться.

Юниты атакуют друг друга с помощью метода unit.getProgram().attack(), который возвращает цель атаки (юнит противника), или null, если цель не найдена.

После каждой атаки необходимо вывести лог с помощью метода printBattleLog.printBattleLog(unit, target), где unit — атакующий юнит, а target — цель атаки.

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

Метод имеет следующую сигнатуру:
void simulate(Army playerArmy, Army computerArmy), где:

• параметр playerArmy — объект армии игрока, содержащий список её юнитов.
• параметр computerArmy — объект армии компьютера, содержащий список её юнитов.

Алгоритмическая сложность реализации:

1. Предварительная сортировка:
   Занимает O(n * log(n)), где n и m — количество юнитов в playerUnits и computerUnits.
2. Основной цикл:
   Каждый раунд проходит через всех юнитов в обоих списках: O(n + m), за раунд. Удаление мертвых юнитов: O(n + m).

Итоговая сложность метода: O(nlogn+mlogm+r⋅(n+m)), где r — количество раундов.

В худшем случае r может быть пропорционально количеству юнитов, поэтому сложность можно записать как: O((n+m)⋅(log(n+m)+r))

Метод getSuitableUnits интерфейса SuitableForAttackUnitsFinder

Описание:

Метод определяет список юнитов, подходящих для атаки, для атакующего юнита одной из армий.
Цель метода — исключить ненужные попытки найти кратчайший путь между юнитами, которые не могут атаковать друг друга.

Подходящий юнит для атаки для атакующей армии компьютера — это юнит армии игрока, который не закрыт справа (по координате Y) другим юнитом армии игрока.

Подходящий юнит для атаки для атакующей армии игрока — это юнит армии компьютера, который не закрыт слева (по координате Y) другим юнитом армии компьютера.

Метод имеет следующую сигнатуру:
public List getSuitableUnits(List> unitsByRow, boolean isLeftArmyTarget), где:

• Параметр unitsByRow — трехслойный массив юнитов противника. Для юнита из атакующей армии компьютера эти юниты находятся на координатах 24..26 по оси X. Для армии игрока они располагаются на координатах 0..2 по оси X (фактически, это юниты армии компьютера).
• Параметр isLeftArmyTarget — параметр, указывающий, юниты какой армии подвергаются атаке. Если значение true, то атаке подвергаются юниты армии компьютера (левая армия); если false — юниты армии игрока (правая армия).

Возвращаемое значение — метод возвращает список юнитов, подходящих для атаки, для юнита атакующей армии

Алгоритмическая сложность реализации:

1. Внешний цикл проходит по всем строкам: O(n).
2. Внутренние методы (findRightmostAliveUnit и findLeftmostAliveUnit) проходят строку один раз: O(m) в худшем случае.

Итоговая сложность метода: O(n + m), где n — количество строк, а m — суммарное количество юнитов во всех строках. (Более эффективный вариант по сравнению с O(n * m))

Метод getTargetPath интерфеса UnitTargetPathFinder

Описание:

Метод определяет кратчайший маршрут между атакующим и атакуемым юнитом и возвращает его в виде списка объектов? содержащих координаты каждой точки данного кратчайшего пути.
Цель метода — найти кратчайший путь между атакующим и атакуемым юнитом. Т. е. для атакующего юнита с координатами x = 1 и y = 2 и атакуемого юнита x = 0 y = 0 результатом станет список [Edge(1, 2), Edge (1, 1), Edge (1,0)]

Для определения кратчайшего пути за основу взять алгоритм А-стар из теории графов.

Метод имеет следующую сигнатуру:
List getTargetPath(Unit attackUnit, Unit targetUnit, List existingUnitList), где:

• параметр attackUnit — юнит, который атакует;
• параметр targetUnit — юнит, который подвергается атаке;
• параметр existingUnitList — список всех существующих юнитов.

Возвращаемое значение — список объектов Edge, т.е. координат клеток пути от атакующего юнита до атакуемого юнита включительно. Если маршрут не найден — возвращает пустой список.

Алгоритмическая сложность реализации:

1. Инициализация занятых клеток:
   Занимает O(k), где k — количество юнитов в existingUnitList.
2. Работа алгоритма A*:
   • Обработка каждого узла: В худшем случае алгоритм обрабатывает каждую клетку игрового поля, то есть O(W * H), где W и H — ширина и высота поля.
   • Добавление и извлечение из очереди с приоритетом: Для каждой клетки это занимает O(log(W * H)).

Итоговая сложность метода: O(W * H * log(W * H)), где W и H — размеры игрового поля.