Соревнования летающих тарелок

Правила игры

Проводится соревнование беспилотных летательных аппаратов на дальность полета. Соревнования проводятся на трассе, представляющей собой бесконечную полосу шириной 60 метров. Маневры по высоте не допускаются правилами соревнований. Каждая команда имеет 10 БПЛА. Цель соревнований -- пролететь как можно дальше одним из БПЛА. На старте каждый БПЛА имеет фиксированный запас горючего, расходуемого в процессе соревнований. Расход горючего на единицу пройденного расстояния различен на разных скоростях. Кроме того, из-за аэродинамического взаимодействия при определенном взаимном расположении БПЛА получают возможность значительно экономить топливо. Поддержание оптимального взаимного расположения усложняется тем фактом, что при столкновениях БПЛА могут выйти из строя и прекратить участие в гонке.

Правила гонки

В соревнованиях участвует две команды, каждая из которых на старте имеет 10 БПЛА с полным запасом топлива (400 см$^3$). БПЛА обоих команд одновременно проходят стартовую линию с хода, на заданной скорости. Размещение аппаратов поперек трассы также задается. Оно симметрично относительно центральной линии трассы (то есть при отражении от этой линии аппараты одной команды наложатся на аппараты другой команды).

Трасса гонки представляет собой горизонтальный коридор шириной 60 метров и неограниченной длины. Летательные аппараты, покинувшие этот коридор, считаются прекратившими гонку. Покиданием коридора считается пересечение центром БПЛА границы трассы.

Если скорость БПЛА оказывается менее 1 м/с, он также выбывает из гонки. Если топливный бак БПЛА при этом пуст, это считается нормальным завершением гонки. Все остальные способы, которыми аппарат может выбыть из гонки (столкновения, выход за границы трассы, скорость ниже 1 м/с при непустом баке), считаются аварийными.

Результатом команды считается наибольшее из расстояний, на которое удалились от линии старта ее БПЛА, нормально завершившие гонку. Если все аппараты команды вышли из гонки аварийно, результат команды считается равным 0.

Динамика одиночного БПЛА

БПЛА представляет собой дискообразное "летающее крыло", т.е. в плане он представляет собой круг радиусом 1 метр. БПЛА может передвигаться со скоростями в диапазоне от 1 м/с до 10 м/с. При этом ограничение в 1 м/с абсолютное: БПЛА, скорость которого упала ниже этого предела, не может держаться в воздухе. Ограничение 10 м/с относится к стационарной скорости аппарата, которую он может развить самостоятельно при помощи собственного двигателя; используя низкоскоростные столкновения и/или аэродинамическое взаимодействие с другими БПЛА, он может развивать и несколько большие скорости.

Движение БПЛА определяется двумя основными силами: сопротивлением воздуха $F$ и тягой двигателя $T$. Если тяга двигателя не равна сопротивлению воздуха, аппарат движется с ускорением, положительным (если тяга двигателя больше сопротивления) или отрицательным (если сопротивление больше тяги). Ускорение определяется по формуле $a=(T-F)/m$, где $m$ равно 1 (изменение массы аппарата за счет выгорания горючего пренебрежимо мало).

Сопротивление воздуха определяется по формуле $F = c_1+c_3 v^2$, где $v$ -- скорость БПЛА, а коэффициенты $c_1$ и $c_3$ определяются аэродинамическими характеристиками планера БПЛА и равны $c_1 = 0.0625$, $c_3=0.0025$.

Тяга двигателя определяется по формуле $T=c_4 q$, где $q$ - расход топлива в см$^3$ в секунду. Здесь $c_4 = 0.3125$, а параметр $q$ находится под контролем бортового компьютера БПЛА и может изменяться в пределах от 0 до 1.

При повороте БПЛА с помощью аэродинамических рулей может придать себе поперечное ускорение в диапазоне от $-0.15$ м/с$\mathstrut ^2$ до $\mathstrut 0.15$ м/с$^2$. (отрицательное поперечное ускорение соответствует повороту налево, положительное -- направо).

Аэродинамическое взаимодействие между БПЛА

При полете за концами крыла БПЛА образуются так назваемые "спутные вихри" -- конические вихревые потоки воздуха, распространяющиеся назад и в стороны от траектории полета под углом около 30 градусов. Если другой БПЛА попадает в этот вихрь, сопротивление его полету резко снижается (см. рис. 1). Напротив, БПЛА, находящиеся за хвостом другого БПЛА, испытывают дополнительное сопротивление движению, обусловленное реактивной струей (см. рис. 1).

Рис. 1: Области, в которых происходит аэродинамическое взаимодействие между БПЛА.
\includegraphics[width=0.5\textwidth]{saucer1.eps}

Если центр второго аппарата находится в областях, отмеченных на рис. 1 знаком "$+$", то сопротивление воздуха падает на 50%. Напротив, если центр второго аппарата находится в области, помеченной знаком "$-$", то сопротивление воздуха возрастает на 50%.

Аэродинамические воздействия от нескольких БПЛА складываются, так что в зоне, отмеченной на рис. 2 знаками "$++$", сопротивление воздуха вообще отсутствует, а в зонах, помеченных знаком "$0$", воздействия компенсируют друг друга. При этом при наложении зон воздействия от трех и более БПЛА сопротивление воздуха не может стать отрицательным.

Рис. 2: Наложение областей аэродинамического взаимодействия от двух БПЛА.
\includegraphics[width=0.75\textwidth]{saucer2.eps}

Столкновения

При столкновении двух БПЛА происходит их абсолютно упругое соударение (без передачи вращательного момента). При этом, если относительная скорость столкновения была более 1 м/с, то оба участвовавших в столкновении аппарата повреждаются и теряют управление.

Под относительной скоростью столкновения понимается проекция векторной разности скоростей летательных аппаратов на прямую, проходящую через центры БПЛА в момент столкновения (см. рис. 3; вектор Vrel соответствует относительной скорости).

Рис. 3: Относительная скорость столкновения.
\includegraphics[width=0.5\textwidth]{saucer3.eps}

После столкновения с относительной скоростью более 1 м/с оба поврежденных аппарата продолжают неуправляемо двигаться с той скоростью, которую они приобрели в результате столкновения, и с ускорением, обусловленным одним только сопротивлением воздуха, пока абсолютная величина их скорости не станет ниже 1 м/с. До этого момента они могут участвовать в последующих столкновениях. После того, как их скорость становится ниже 1 м/c, поврежденные аппараты покидают гонку, выходя за пределы трассы по высоте, и не представляют угрозы для других участников гонки.

Моделирование

Моделирование гонки происходит по ходам, каждый из которых занимает одну секунду. В начале каждого хода программа игрока знает координаты и скорости всех БПЛА, и может задать расход топлива и поперечное ускорение для всех своих БПЛА. Расходы топлива и поперечные ускорения БПЛА другой команды при этом не известны.

Затем программа жюри моделирует движение БПЛА за один ход. Для этого:

  1. Происходит снятие БПЛА, движущихся медленее 1 м/с. При этом, при выбывании кораблей с пустым баком, их пройденные расстояния засчитываются в результат команды.

  2. Рассчитываются ускорения кораблей в соответствии с установленными расходами топлива и поперечными ускорениями, а также аэродинамическим сопротивлением. Ускорения кораблей прибавляются к скоростям кораблей. При этом получившиеся скорости нормируются таким образом, чтобы поперечное ускорение не влияло на величину скорости, а влияло лишь на ее направление.

  3. Происходит повторное снятие БПЛА, движущихся медленее 1 м/с. Как и ранее, при выбывании кораблей с пустым баком, их пройденные расстояния зачитываются в результат команды.

  4. К координатам прибавляются скорости (происходит равномерное прямолинейное движение БПЛА "по инерции"). Если при этом происходит соприкосновение кораблей, то есть расстояние между какими-то кораблями становится меньше 2 м, то координаты изменяются в соответствии с законами упругого соударения шаров одинаковой массы. При этом БПЛА, относительная скорость столкновения которых превосходила 1 м/с, помечаются как потерявшие управление.

  5. Происходит проверка того, что все корабли находятся в пределах трассы. При пересечении одним или несколькими кораблями пределов трассы, они снимаются с гонки.

Гонка заканчивается, когда не остается ни одного управляемого БПЛА. При этом побеждает игрок с максимальным результатом (максимальным расстоянием от старта БПЛА, нормально завершившим гонку). Если результаты игроков равны, то гонка заканчивается вничью.

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

Жюри принимает решения на одном из трех языков: C++, Java, Pascal и Modula 2.

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

C++

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

PLAYER(int owner[MAX_SHIPS],
       double x[MAX_SHIPS], double y[MAX_SHIPS],
       double u[MAX_SHIPS], double v[MAX_SHIPS],
       double fuel[MAX_SHIPS]);
void move(int owner[MAX_SHIPS],
          double x[MAX_SHIPS], double y[MAX_SHIPS],
          double u[MAX_SHIPS], double v[MAX_SHIPS],
          double fuel[MAX_SHIPS],
          double fuel_consumption[MAX_SHIPS],
          double norm_accel[MAX_SHIPS]);

Конструктору PLAYER передаются следующие параметры:

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

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

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

Java

Участники должны предоставить жюри исходные тексты с классом – имплементацией интерфейса Player. Файл должен называться Player1.java Класс Player1 будет содержать следующие методы, унаследованные от интерфейса Player (параметр MAX_SHIPS обозначает общее количество БПЛА): 

void init(
 	/* in  */ int owner[],
	/* in  */ double x[], 
	/* in  */ double y[],
	/* in  */ double u[], 
	/* in  */ double v[],
	/* in  */ double fuel[] 
);

void move(
	/* in  */ int owner[],
	/* in  */ double x[], 
	/* in  */ double y[],
	/* in  */ double u[], 
	/* in  */ double v[],
	/* in  */ double fuel[],
	/* out */ double fuel_consumption[],
	/* out */ double norm_accel[]
);

Методу инициализации init передаются следующие параметры:

Методу move передаются те же параметры, что и методу init, а также следующие дополнительные параметры:

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

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

Pascal

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

{$IFDEF PLAYER1}
Cplayer1
{$ELSE}
Cplayer2
{$ENDIF}

Таким образом, в случае, если при компиляции был определен символ PLAYER1 с помощью директивы компилятора {$DEFINE PLAYER1}, класс автоматически получит имя Cplayer1, в противном случае класс будет автоматически назван Cplayer2.

В описании класса должны быть определены следующие методы: 

constructor Create(
        var owner: TIntArr;
        var x: TDoubleArr;
        var y: TDoubleArr;
        var u: TDoubleArr;
        var v: TDoubeArr;
        var fuel: TDoubleArr;
);

procedure move(
        var owner: TIntArr;
        var x: TDoubleArr;
        var y: TDoubleArr;
        var u: TDoubleArr;
        var v: TDoubeArr;
        var fuel: TDoubleArr;
        var fuel_consumption: TDoubleArr;
        var norm_accel: TDoubleArr;
);

Конструктору Create передаются следующие параметры:

Процедуре move передаются те же параметры, что и конструктору, а также следующие дополнительные параметры:

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

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

Modula-2

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

PROCEDURE Create (VAR owner: TIntArr;
                  VAR x, y, u, v, fuel: TDoubleArr);

PROCEDURE Move   (VAR owner: TIntArr;
                  VAR x, y, u, v, fuel, fuel_consumption,
		  	norm_accel: TDoubleArr);

Процедуре Create передаются следующие параметры:

Процедуре move передаются те же параметры, что и конструктору, а также следующие дополнительные параметры:

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

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

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

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

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

При проверке решений жюри будет использовать компиляторы gcc Version 3.3.5 (C++), Free Pascal Compiler Version 2.0 (Pascal) и XDS Modula-2/Oberon-2 2.51 (Modula-2). Компиляция решений будет производиться в операционной системе Linux. Ядро проверяющей программы будет написано на языке C++ и будет использовать те же алгоритмы расчета игровой ситуации, что и в примере проверяющей программы на языке C++.

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

Для отладки решений жюри предоставляет участникам набор исходных текстов программ и исполняемых файлов. Исходные тексты представлены на трех языках: C++, Pascal и Modula-2.

Описание вышеуказанных средств находится в общем пакете release.zip в файлах koi8-r/readme.txt и windows/readme.txt.

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