Задача заочного тура

1. Правила игры

Играют два игрока. Каждый из них имеет в своем распоряжении одинаковое количество (от 1 до 10) космических кораблей, передвигающихся в двумерном пространстве в гравитационном поле звезды, представляющей собой окружность с центром в точке (0,0) и радиусом R. Каждый корабль также представляет собой окружность и имеет свой уникальный номер (от 0 до 19). Корабль с номером i имеет фиксированный радиус r (не зависящий от номера корабля) и зависящие от времени

• координаты центра (x_i,y_i),
• скорость (u_i,v_i),
• угол атаки α_i (в радианах), (0≤α_i<2π),
• величину энергии E_i (0≤E_i≤1),
• величину здоровья H_i (0≤H_i≤1).

Звезда и корабли не могут «накладываться» друг на друга, то есть два корабля должны отстоять друг от друга на расстояние, не меньше чем 2r, а корабль от звезды — не меньше чем r+R. Под расстоянием между кораблями (или кораблем и звездой) понимается расстояние между их центрами. Координаты кораблей и звезды определяются как координаты их центров.

Игроки совершают ходы одновременно. Перед очередным ходом игроки для каждого своего корабля указывают

• изменение угла атаки change_angle[i],
• ускорение двигателей кораблей acceleration[i],
• мощность выстрела shoot_energy[i],
• величину энергии, передаваемой другим кораблям give_energy.

1. Изменяются углы атаки кораблей α_i. При этом величина изменения угла атаки change_angle[i] каждого из кораблей по модулю не может превышать константы MAX_CHANGE_ANGLE.
2. К скоростям кораблей прибавляется ускорение их двигателей acceleration[i] в пределах от 0 до MAX_ACCELERATION (в направлении угла атаки) плюс ускорение силы тяжести G/(x_i²+y_i²) (в направлении звезды). При этом теряется энергия, равная ENERGY_FOR_ACCELERATION×acceleration[i]. Если кораблю не хватает энергии, то acceleration[i] уменьшается так, чтобы энергии хватило на ускорение.
3. К координатам прибавляются скорости (происходит равномерное прямолинейное движение кораблей «по инерции»). Если при этом происходит соприкосновение кораблей, то есть расстояние между какими-то кораблями становится меньше 2r, то координаты изменяются в соответствии с законами упругого соударения шаров радиуса r одинаковой массы.
4. Проверяется, находятся ли какие-нибудь корабли от звезды на расстоянии, меньшем чем R+r. Корабли, находящиеся ближе, исчезают.
5. Осуществляется стрельба. Для каждого стреляющего корабля определяется, попал ли выстрел в другой корабль, в звезду, или никуда не попал. Выстрел попал в другой корабль, если луч выстрела, идущий от центра стреляющего корабля в направлении угла атаки, пересекает этот корабль, причем последний — ближайший среди тех, которые пересекают луч выстрела. При этом, если луч выстрела пересекается со звездой и отрезок между центром стреляющего корабля и точкой пересечения луча со звездой не пересекается ни с одним кораблем, то в этом случае считается, что выстрел попал в звезду. Если луч выстрела i-го корабля попал в j-й корабль, то от здоровья j-го корабля H_j отнимается величина DAMAGE_FROM_SHOOT×shoot_energy[i]/((x_i-x_j)²+(y_i-y_j)²)). Вне зависимости от того, куда попал выстрел и попал ли он куда-нибудь вообще, от энергии i-го корабля отнимается величина shoot_energy[i]. При этом shoot_energy[i] должно находиться в пределах от 0 до MAX_SHOOT_ENERGY. Если кораблю не хватает его собственной энергии, то shoot_energy[i] уменьшается так, чтобы энергии хватило на стрельбу. После стрельбы всех кораблей потерявшие все здоровье корабли исчезают.
6. Осуществляется перераспределение энергии. Перераспределять энергию могут корабли, находящиеся на расстоянии, не большем DISTANCE_GIVE_ENERGY. Если энергия подается своему кораблю, то к.п.д. передачи равно 1/ENERGY_TO_OWN, то есть получающий корабль получает энегрию в ENERGY_TO_OWN раз меньше, чем теряет передающий. Если энергия подается чужому кораблю, то у противника энергия уменьшается и к.п.д. передачи равно 1/ENERGY_TO_OPPONENT. Если у корабля не хватает энергии, то передача энергии этим кораблем ни к какому другому кораблю не осуществляется. Если после передачи энергия противника стала отрицательной, то осуществляется захват корабля: энергия корабля меняет знак, и корабль теперь принадлежит другому игроку.
7. Осуществляется прирост энергии E_i на величину, равную ENERGY_FROM_STAR/(x_i²+y_i²) -ENERGY_PER_TURN. Корабли, у которых после этого шага энергия становится отрицательной, исчезают.

Значения констант таковы:

• r = 1 — радиус корабля,
• R = 3 — радиус звезды,
• G = 2 — гравитационная постоянная звезды,
• MAX_ACCELERATION = 0.03 — максимальное ускорение,
• ENERGY_FOR_ACCELERATION = 0.3 — энергия, затрачиваемая на ускорение,
• ENERGY_FROM_STAR = ENERGY_FOR_ACCELERATION×G,
• ENERGY_PER_TURN = ENERGY_FROM_STAR/900,
• ENERGY_TO_OWN = 2,
• ENERGY_TO_OPPONENT = 3,
• DISTANCE_GIVE_ENERGY = 4,
• MAX_CHANGE_ANGLE = 0.1 — изменение угла атаки,
• MAX_SHOOT_ENERGY = 0.025 — максимальная мощность стрельбы,
• DAMAGE_FROM_SHOOT = 3,
• MAX_SHIPS = 20 — максимальное количество кораблей,
• MAX_MOVES = 20 000 — максимальное количество ходов.

Игра заканчивается, если у кого-то из игроков не остается кораблей или совершено MAX_MOVES ходов. Побеждает тот, у кого в конце игры остается большее число кораблей. Если у обоих игроков остается равное число кораблей, то игра оканчивается вничью.

В начальной ситуации все корабли имеют равные единице энергию и здоровье, находятся на одинаковом расстоянии d от звезды, направлены на звезду, имеют скорость, перпендикулярную звезде и равную квадратному корню из G/d.

2. Требования к решению

Жюри принимает решения на одном из двух языков: C++ и Pascal, написанные для компиляторов GNU C++ или Free Pascal по выбору участника. Тестирование проходит в операционной системе UNIX.

Участники должны реализовать процедуру расчета хода игрока move.

2.1 C++

Участники должны предоставить жюри исходные тексты с описанием класса PLAYER, реализовывающего функцию (т.е. метод) расчета хода move игровой стратегии:

void move(int owner[MAX_SHIPS], double x[MAX_SHIPS], double y[MAX_SHIPS],
               double u[MAX_SHIPS], double v[MAX_SHIPS], double angle[MAX_SHIPS],
               double E[MAX_SHIPS], double H[MAX_SHIPS],
               double change_angle[MAX_SHIPS], double acceleration[MAX_SHIPS],
               double shoot_sector[MAX_SHIPS], double give_energy[MAX_SHIPS][MAX_SHIPS]);

Функции move передаются восемь массивов с информацией о текущей ситуации игры и четыре массива, в которые она должна записать информацию о своем текущем ходе, а именно:

owner	—	массив, в котором на i-м месте записано число 0 (если i-й корабль не участвует в игре), 1 (если i-й корабль принадлежит текущему игроку), 2 (если i-й корабль принадлежит противнику);
x	—	массив с x-координатами кораблей;
y	—	массив с y-координатами кораблей;
u	—	массив с x-компонентами скоростей кораблей;
v	—	массив с y-компонентами скоростей кораблей;
angle	—	массив с углами атаки кораблей;
E	—	массив с величинами энергии кораблей;
H	—	массив с величинами здоровья кораблей;
change_angle	—	массив, в который должны быть записаны величины изменения углов атаки кораблей;
acceleration	—	массив, в который должны быть записаны величины ускорения кораблей;
shoot_energy	—	массив, в который должны быть записаны мощности выстрелов;
give_energy	—	двумерный массив, на i,j-м месте которого должно быть записано число, равное количеству передаваемой энергии i-м кораблем j-му.

Величины, записанные в места массива, соответствующие чужим или не участвующим в игре кораблям, будут игнорироваться. Если какой-либо элемент массивов change_angle, acceleration, shoot_sector, give_energy не будет удовлетворять указанным выше ограничением, то этот элемент будет изменен таким образом, чтобы он находился внутри допустимого интервала.

Участники могут хранить свои данные в переменных (т.е. членах) класса.

2.2 Pascal

Участники должны предоставить жюри исходные тексты с описанием модуля PLAYER, реализовывающего функцию (т.е. метод) расчета хода move игровой стратегии:

procedure move(owner: tIntArr; 
           x, y, u, v, angle, E, H: tDoubleArr;
           var change_angle, acceleration, shoot_energy: tDoubleArr;
           var give_energy: tDoubleDoubleArr);

type tIntArr = array[0..MAX_SHIPS-1] of integer;
     tDoubleArr = array[0..MAX_SHIPS-1] of double;
     tDoubleDoubleArr = array[0..MAX_SHIPS-1,0..MAX_SHIPS-1] of double;

Следует иметь ввиду, что в предоставляемых участникам средствах для отладки решений, реализованы два модуля: PLAYER и PLAYER2. Второй модуль отличается от первого лишь объявлением unit PLAYER2. Оформлять решения следует по примеру молуля PLAYER.

Функции move передаются восемь массивов с информацией о текущей ситуации игры и четыре массива, в которые она должна записать информацию о своем текущем ходе, а именно:

owner	—	массив, в котором на i-м (0≤i<MAX_SHIPS) месте записано число 0 (если i-й корабль не участвует в игре), 1 (если i-й корабль принадлежит текущему игроку), 2 (если i-й корабль принадлежит противнику);
x	—	массив с x-координатами кораблей;
y	—	массив с y-координатами кораблей;
u	—	массив с x-компонентами скоростей кораблей;
v	—	массив с y-компонентами скоростей кораблей;
angle	—	массив с углами атаки кораблей;
E	—	массив с величинами энергии кораблей;
H	—	массив с величинами здоровья кораблей;
change_angle	—	массив, в который должны быть записаны величины изменения углов атаки кораблей;
acceleration	—	массив, в который должны быть записаны величины ускорения кораблей;
shoot_energy	—	массив, в который должны быть записаны мощности выстрелов;
give_energy	—	двумерный массив, на i,j-м месте которого должно быть записано число, равное количеству передаваемой энергии i-м кораблем j-му.

Величины, записанные в места массива, соответствующие чужим или не участвующим в игре кораблям, будут игнорироваться. Если какой-либо элемент массивов change_angle, acceleration, shoot_sector, give_energy не будет удовлетворять указанным выше ограничением, то этот элемент будет изменен таким образом, чтобы он находился внутри допустимого интервала.

Участники могут хранить свои данные в переменных модуля.

3. Судейство и ограничения, налагаемые на стратегию

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

На стратегию налагаются следующие ограничения:

• максимальное время работы процедуры move — 0.1 с;
• максимальный размер используемой оперативной памяти — 32Мбайт, не допускается хранить информацию на жестком диске.

Тестирование проходит на машинах не медленнее Pentium-III 650.

4. Средства, предоставляемые жюри

Для отладки решений жюри предоставляет участникам набор исходных текстов программ и исполняемых файлов. Исходные тексты представлены на двух языках: Pascal и C++. Код на языке Pascal написан для компиляторов Free Pascal 1.0.10 (OS Linux) и Free Pascal 1.0.10 (OS Windows), код на C++ компилируется GNU C++ compiler (g++) 3.3.3 (OS Linux) и DJGPP 3.3.3 (OS Windows).

Участникам предоставляются следующие файлы:

• исходные тексты программы для проверки стратегий на языках Pascal и C++;
• два примера простых стратегий;
• программа для визуализации протоколов игр в виде исполняемых файлов (графическое приложение для OS Windows и программа для X Window System).

Описание вышеуказанных средств находится в общем пакете release.zip.

Обо всех найденных неточностях и ошибках в условии задачи, а также в исходных текстах просьба сообщать жюри по адресу olymp@ccphys.nsu.ru.

DJGPP можно скачать отсюда: http://www.delorie.com/djgpp/zip-picker.html.